Direita/Esquerda

[Cath]

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.

[Baderous]

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

[Rui Carlos]

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.

[Cath]

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.

[Rui Carlos]

Sim, é isso mesmo.

[Cath]

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 :/

[Baderous]

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

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

[Cath]

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))

[Baderous]

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.

[Cath]

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.

[Rui Carlos]

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.

[Cath]

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.

[Rui Carlos]

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.

[marco_iku]

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.

[Rui Carlos]

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.

[Cath]

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?

[Rui Carlos]

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.

[Cath]

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.

[Rui Carlos]

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

[Cath]

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