Jump to content

Máquina de Turing: Direita/Esquerda


Cath

Recommended Posts

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.

Link to comment
Share on other 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.

Link to comment
Share on other 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.

Link to comment
Share on other 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 :/

Link to comment
Share on other 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))
Link to comment
Share on other 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.

Link to comment
Share on other 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 boa 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.

Link to comment
Share on other 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.

Link to comment
Share on other 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.

Link to comment
Share on other 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.

Link to comment
Share on other 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.

Link to comment
Share on other 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

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.