Aula Teórica 15
16 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia
Exercício: Máquina de Turing que calcula a soma de naturais em notação unária (exercício 2.7 da lista de exercícios para a aula prática 9 ). Máquinas de Turing com transições S. Proposição: para cada máquina de Turing com transições S existe uma máquina de Turing equivalente. Máquinas de Turing multifita. Exemplo: Máquina de Turing com 3 fitas que decide a linguagem das palavras binárias nas quais o número de 0's é igual ao número de 1's (exercício 2.2 b) da lista de exercícios para a aula prática 10. ). Proposição: para cada máquina de Turing multifita existe uma máquina de Turing equivalente. Esboço da prova para o caso de máquinas com 2 fitas. Enumerador. Exemplo: enumerador que enumera a linguagem sobre {1} constituída pelas palavras de comprimento ímpar.