• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Cath

Direita/Esquerda

22 mensagens neste tópico

Mais uma pessoa que está a fazer a máquina de turing xD

Estou a converter a fita inicial para uma lista e após verificar que existe alguma instrução para o estado e cabeçote actual mudo o caracter e movo para a esquerda ou para a direita. Não tenho nenhuma ideia de como irei mover para a direita e para a esquerda, alguma ideia?

basicamente aquilo que tive a explicar de uma forma mais clara:

[1,1,0,1]

começa na posição 1, também no estado 1 e na tabela de acção indica que no estado 1 o 1 muda para para 0 e move para a direita ou seja:

[0,1,0,1]. O "cursor" muda para o 1. Só que o "cursor" pode mudar também para a esquerda e assim sucessivamente. Não tenho ideia de como o fazer. Obrigada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens de armazenar a posição actual do cabeçote (o índice da lista).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes usar um inteiro para indicar a posição em que estás num determinado momento.

Outra hipótese é teres um triplo ([int],Int,[int]) para representar a fita. Assim, dado o triplo (l1,e,l2), andar para a direita resulta em (l1++[e],head l2,tail l2) e andar para a esquerda (init l1,last l1,e:l2). Com um par de listas também podes obter algo parecido.

EDIT: A primeira alternativa é basicamente o que o Baderous disse.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes usar um inteiro para indicar a posição em que estás num determinado momento.

Outra hipótese é teres um triplo ([int],Int,[int]) para representar a fita. Assim, dado o triplo (l1,e,l2), andar para a direita resulta em (l1++[e],head l2,tail l2) e andar para a esquerda (init l1,last l1,e:l2). Com um par de listas também podes obter algo parecido.

EDIT: A primeira alternativa é basicamente o que o Baderous disse.

Estou a ver, neste caso como se a lista se separasse em três, antes do caracter onde estamos, o caracter actual e depois do caracter, certo?

Obrigada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto agora já não tem tanto a ver com direita/esquerda mas como não quis abrir outro tópico.

Tenho isto:

jogar [] ([],0,[]) x = []

jogar tabeladeaccao (antes,actual,depois) estado =

  if veestado tabeladeaccao estado actual == False then

      antes ++ [actual] ++depois

  else

      jogar tabeladeaccao (mudacurrent(antes,actual,depois) (checklist tabeladeaccao estado actual ) ) (mudaestado (checklist tabeladeaccao estado actual))

basicamente o jogar começa a simular a maquina de turing. o veestado ve se existe algo na tabela para aquele estado e para aquele valor. o mudacurrent muda o valor actual, o muda estado muda o estado actual, o checklist tem a instrucao da tabela de acção para aquele estado e valor. As funções auxiliares estão todas a funcionar.

tenho o seguinte erro e não sei porque está a acontecer, já procurei no google mas nada parece dar-me a solução :/

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No "else" não faltam vírgulas?

Btw, mete o código entre [ code=haskell ] [ /code ] (sem os espaços).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

vírgulas?

jogar [] ([],0,[]) x = []
jogar tabeladeaccao (antes,actual,depois) estado = 
  if veestado tabeladeaccao estado actual == False then
      antes ++ [actual] ++depois
  else 
      jogar tabeladeaccao (mudacurrent(antes,actual,depois) (checklist tabeladeaccao estado actual ) ) (mudaestado (checklist tabeladeaccao estado actual))

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O 2º argumento da função jogar é um tuplo e quando a invocas no "else" não me parece que estejas a passar um tuplo. A menos que a combinação das função mudacurrent e checklist dê como resultado um tuplo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A combinação deles dá um tuplo. Eu consigo que ele funcione em certas situações.

Exemplo:

*Turing> jogar [(1,1,2,0,2),(2,1,2,1,1)] ([1,1],1,[1,0]) 1
[1,1,0,1,0]
*Turing> jogar [(1,1,2,0,2),(2,1,2,1,1)] ([1,1],1,[1,0]) 2
*** Exception: Prelude.last: empty list

(mover para a direita é 2, outro número é esquerda, na lista de tuplos:  [(1,1,2,0,2),(2,1,2,1,1)]  o último é a direcção.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não analisei o problema com muita atenção (até porque é um bocado complicado saber qual a máquina de turing que aquilo representa), mas tendo em conta o erro, diria que estás  a tentar andar para a esquerda quando já estás na primeira posição.

Só mais um pormenor, por definição, as máquinas de turing têm uma fita infinita, por isso talvez fosse vou ideia ter sempre no 3º elemento do tuplo uma lista infinita (tendo em conta que estamos em Haskell, isto não deve ser problemático), caso contrário arriscas-te a ter um erro parecido quando chegares ao fim da fita. E se no primeiro caso o erro é aceitável, pois atingiste um estado de erro (mesmo do ponto de vista matemático), no segundo a aplicação é suposto continuar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Okay, vou ter de pesquisar um pouco sobre listas infinitas em haskell algo do tipo [0..] é relativamente fácil mas não sei como usar para este tipo de problema (nada como uma pesquisa no google), obrigada pela dica.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A máquinas de Turing têm sempre o símbolo branco, que preenche as posições vazias das lista.

Por exemplo, se convencionares que o -1 representa o símbolo branco (talvez o ideal fosse usar o construtor Maybe), só precisas de adicionar uma lista infinita de -1 à 3ª componente do tuplo que representa a lista. É relativamente simples criares uma função que faz isto.

Já agora, não sei o quão genérico o teu trabalho pretende ser, ou quão próximo do conceito teórico ele é suposto estar. Se o objectivo é apenas implementar uma função que lide com certas máquinas de Turing, onde estas nunca têm transições associadas ao símbolo branco, por exemplo, talvez não seja necessário ter este aspecto em conta. Já se pretendes criar algo que seja capaz de lidar com qualquer máquina de Turing, este aspecto parece-me relevante. Talvez devas esclarecer este aspecto primeiro, pois apesar de não ser muito complicado lidar com listas infinitas, tal implica compreender a forma de funcionar do Haskell e alguma experiência na linguagem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Enunciado do problema para quem quiser saber mais http://wiki.di.uminho.pt/twiki/bin/view/Education/LI1/Projecto

Bem o que eu acho, é que deves fazer isto

 
type Fita = ([int],[int])

A primeira lista vai ser com as posições [-3,-2,-1,0] e a segunda [1,2,3,4]

E para utilizar a primeira lista fazer um reverse dessa mesma fita, penso que sja mais fácil de trabalhar.

A primeira com as posições negativas e a segunda com as positivas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tendo em conta o enunciado é mesmo necessário ter em conta que a fita tem tamanho ilimitado. Mesmo que não se use uma lista infinita, convém pelo menos prever nas funções o caso em que chegaram ao fim da fita, de modo a que possam continuar a execução.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tive a tentar saber mais sobre listas infinitas mas não encontrei nada que se aplicasse ao meu caso. Ainda não entendi muito bem como sei se estou no inicio ou no fim da lista. O -1 que falavas é definido onde?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Imagina a seguinte constante:

inf=(-1):inf

Esta constante vai conter uma lista infinita de -1. Se dada uma fita inicial l definires o tuplo ([],head l,(tail l)++inf) vais obter uma fita de comprimento infinito, que te garante que nunca chegas ao fim da fita.

Por exemplo, se tiveres uma máquina de Turing que a única coisa que faz é deslocar-se para a direita, a máquina nunca irá parar, o que corresponde ao seu comportamento teórico.

Como já referi, se na função testares antecipadamente o caso em que já não tens mais elementos à direito, e adicionares nesse momento um elemento, também funciona, e é capaz de ficar mais simples.

O -1 é um exemplo de um valor que podias usar para representar o símbolo branco. Tens que escolher, um valor qualquer que não apareça no input da fita. Se assumires que o números da fita são sempre não negativos, podes usar um número negativo para esse efeito.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tive a considerar o assunto e acho que vou guardar uma variavel com a posicao. começa com 0 e se vai para a esquerda -1 ou se vai para a direita +1, e faço uma condição de acordo com esse número (que adiciona ou não elementos à lista).

Outra questão (que pode parecer um bocado estranha) mas em haskell nunca fiz. Por exemplo não posso fazer o if then [duas instrucoes] else [cinco instrucoes] pois não? (só um exemplo). Confesso que às vezes é um bocado complicado desligar das outras linguagens.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes fazer "if ... then composição de n funções else composição de m funções".

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Outra questão (nunca mais acabam ^^v) isto:

length( antes ++ [actual] ++depois )

devia funcionar certo? pelo menos dar o comprimento dessa lista (visto que antes é uma lista, actual é um int e depois é uma lista.

edit: não sei porquê de ontem para hoje começou a funcionar e a máquina funciona, agora basta por uma condicao para nao colocar nada à esquerda e à direita caso vá acabar na próxima "jogada", nada que seja muito complicado de fazer. Obrigada pela ajuda.

A minha questão era mesmo por exemplo sempre que ele começava a "jogar", ele mostrava o valor actual da lista, nunca posso por duas instruções no if :/ pelo menos sem estar dentro de outra função

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sabendo que é necessário mostrar os estados intermédios da fita, qual será a melhor maneira de o fazer:

1) Ir concatenando as strings que representam os estados intermédios (obtidas com o show do tipo) e na função main, fazer apenas o putStrLn da string resultante da concatenação;

2) Tirar partido do Monad IO e, após "calcular" cada estado, mostra-se com o putStrLn $ show.

A minha dúvida é que a segunda opção obriga-me a usar funções de IO numa função que deve apenas realizar cálculos, enquanto que se usasse a 1ª opção, bastava alterar a função que faz os cálculos para me retornar uma String e depois então na main fazia o putStrLn dessa String. Ou será que devo considerar a função que faz os cálculos como uma função da camada de IO?

(Quando falo em estado, não é para usar o Monad State, é o estado das listas que representam a fita.)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boa noite,

Andei a ler este tópico mas ainda não consegui achar uma solução a este problema..

É o seguinte: eu tenho uma lista Char, e quero criar uma especie de Index, de maneira a poder adicionar elementos que ou são maiores que o length dessa lista, ou a posição desse elemento seja negativo (considerando que o index começa no 0). Por exemplo tenho uma funcao que recebe uma lista Char, e um par com o novo elemento a ser adicionado à lista e um Int que marca a posicao:

funcao :: [Char] -> (Char,Int) -> [Char]
funcao l (c,i)
| (length l) <  i = f ++ [c]
        | (length l) >= i = (take (i-1) f) ++[c]++ (drop i l)
        | (length l >= i) && (i < 0) = [c] ++ l

> funcao (funcao ['1','1','1'] ('k',-1)) ('k',-2)

"kk111"

> funcao (funcao (funcao ['1','1','1'] ('k',-1)) ('k',-2)) ('x',-1)

"xkk111"

O problema é que o caracter 'x' deveria ter substituido o segundo 'k', e não fez isso pois não tem noção das posições da lista, por falta de um Index.

Como altero esta funcao de maneira a que o output seja por exemplo:

> funcao (funcao (funcao ['1','1','1'] ('k',-1)) ('k',-2)) ('x',-1)

"xk111"

?

Não estou mesmo a conseguir alterar isto.

Agradecia uma explicação. Obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora