Função -> Tabela

[Cath]

Estou a tentar fazer a tarefa 4 do seguinte projecto:

http://wiki.di.uminho.pt/twiki/bin/view/Education/LI1/Projecto

e sinceramente não sei por onde lhe pegar. Se fosse de um número unário dado no início seria mais simples mas tenho quase a certeza que é para tornar a função numa tabela qualquer que seja o número.

O exemplo  na página é fácil de entender:

Por exemplo, dada a função f(x)=(x+2)+x e a fita 111, a tabela de acção deverá calcular o valor 11111111

Não faço a mínima como começar, alguma sugestão seria óptima.

[Baderous]

Aceitam-se ajudas para resolver este problema. De notar que apenas se tem acesso à expressão matemática indicada, a qual será traduzida internamente no tipo Exp, isto é, não se tem acesso à fita (seria bastante mais fácil se se tivesse).

[nunolevsky]

ja agora tambem estou a fazer o mesmo projecto que a cath mas inda tou na tarefa3 e n faço ideia de como fazer para simplificar as tabelas do tipo:

1,1->2, ,D

2,1->2,1,D

2, ->3, ,D

3, ->4,1,E

3,1->3,1,D

4,1->4,1,E

4, ->5, ,E

5,1->5,1,E

5, ->8,1,D

6,1->7,1,D

7,1->6, ,E

8,1->9, ,D

9,1->9,1,D

9, ->3, ,D

sei k provavelmente tenho k dividir a tabela em cada linha e dps comparalas mas nao faço ideia k tipo de comparaçoes tenho que fazer para a tabela ser simplificada

se alguem poder ajudar era fixe

akela tabela simplificada poderia ficar assim

1,1->2, ,D

2,1->2,1,D

2, ->3, ,D

3, ->4,1,E

3,1->3,1,D

4,1->4,1,E

4, ->5, ,E

5,1->5,1,E

5, ->1,1,D

[Rui Carlos]

Tendo em conta que só há somas, podias fazer uma simplificação da expressão em algo do tipo n1+n2*x. Mas se calhar os profs não iam achar muita piada a isto  😛

Vou tentar explicar a minha ideia para fazer uma coisa um pouco melhor.

Partindo mais uma vez do pressuposto de que só há somas (e assim os parêntesis são irrelevantes), a minha estratégia seria criar uma máquina de Turing que começasse preencher a fita com os operandos. Por exemplo, para a função f(x)=x+(2+x)+3, a primeira parte da máquina de Turing seria preencher a fita com os valores x, 2 e x. Há muitas formas diferentes de criar uma máquina de Turing que faz isto, mas a minha estratégia seria uma máquina de Turing que preenche a fita da seguinte forma, tendo no início o valor x:

x -> x x -> x 2 x -> x 2 x x -> x 2 x 3 x -> x 2 x 3 x

Ou seja, manténs sempre o x no fim da fita, que por vezes terás de replicar, e depois de já teres colocado todos os valores na fita, apagas-lo. Precisarias de duas máquinas de Turing, uma que acrescenta uma série de uns no meio da fita, e uma que duplica o último valor da fita. Depois é só colocá-las em sequência.

Depois de terem esta tarefa feita, só precisam de gerar uma máquina de Turing que soma os dois últimos valores da fita, enquanto houver mais do que um valor na fita. Esta parte deve ser simples, visto que é sempre igual.

Penso que isto deve ser suficiente para resolver o problema.

Para coisas mais complexas, em que tens operações como a multiplicação, por exemplo, em que tens que te preocupar com as precedências, eu iria para uma stack.

Aqui o primeiro passo da máquina de Turing gerada seria converter a expressão dada para notação infixa.

Exemplo, 4*x+2 corresponderia a + * 4 x 2. Com uma travessia preorder da árvore da expressão obtens isto facilmente.

Terias que adicionar símbolos para as operações, mas a estratégia para transformar um fita com só com x nesta poderia ser semelhante à anterior.

Depois disto tinhas uma máquina de Turing que calculava a expressão. Mais uma vez esta máquina de Turing seria sempre a mesma para qualquer expressão. Basicamente esta última componente da máquina apenas teria que procurar os o último operador, e aplicá-lo aos dois valores que estavam imediatamente antes.

Esta última estratégia tem a vantagem de ser extensível a muitas outras funcionalidades.

A ideia por de trás de ambas as estratégias é gerares uma máquina de Turing que começa por gerar uma compilação do código, e depois aplicar um interpretador ao código gerado.