Sumários
Aula Prática 6
27 outubro 2009, 12:00 • Maria Paula Antunes Abrantes Gouveia
Exercício 6 da lista de exercícios para a aula prática 5 . Exercícios 1.3a)b), 1.4a)b), 2.10a) e 2.3f) da lista de exercícios para as aulas 6 e 7 .
Aula Teórica 11
27 outubro 2009, 10:00 • Maria Paula Antunes Abrantes Gouveia
Máquina de Turing como calculadora de funções ( transparente). Representação unária dos números naturais (n--> 1^n). Máquina de Turing que calcula a função sucessor. Máquina de Turing que calcula a função soma. Definições alternativas da máquina de Turing: máquinas com transições-S.
Aula Teórica 11
27 outubro 2009, 08:30 • Maria Paula Antunes Abrantes Gouveia
Noção intuitiva de algoritmo e de função computável. Breve referência a diversos modelos de computação usuais na literatura (máquina de Turing, cálculo lambda, máquina URM). Postulado de Church-Turing. Máquinas de Turing com transições-S. Teorema: Para cada máquina de Turing com transições- S existe uma máquina de Turing equivalente. Prova deste teorema. Máquinas de Turing multifita. Teorema: Para cada máquina de Turing multifita existe uma máquina de Turing equivalente. Esboço da prova deste teorema.
Aula Prática 6
27 outubro 2009, 08:30 • Paulo Manuel Fontaínha Gomes
Exercícios 1.3a)b), 1.4a)b), 2.1, 2.10a) e 2.3f) da lista de exercícios para as aulas 6 e 7.
Aula Prática 5
23 outubro 2009, 12:00 • Paulo Manuel Fontaínha Gomes
Exercícios 2a), 2b), 2c), 3, 5 e 6 da lista de exercícios para a aula prática 5.