Sumários
Aula Teórica 15
16 novembro 2010, 10:00 • 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.
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.
Aula Prática 9
16 novembro 2010, 08:30 • Manuel Biscaia Martins
Exercícios 1.1a) b), 1.4 a) b), 2.3 e) e 2.4 b) da lista de exercícios para a aula prática 9 .
Aula Prática 8
12 novembro 2010, 12:00 • Manuel Biscaia Martins
Exercicios 2.5 a) c) e 2.6 da lista de exercícios para a aula prática 7. Exercícios 1.1 a) c) e 1.2 e 2.4 a) da lista de exercícios para a aula prática 8.
Aula Teórica 14
11 novembro 2010, 12:00 • Maria Paula Antunes Abrantes Gouveia
Realização do teste 2.