Sumários

Máquinas de Turing.

16 Novembro 2016, 09:30 • Ana Respicio

Teorema: Uma linguagem é Turing-reconhecível se e só se algum enumerador a enumera. Prova. 

O 10º problema de Hilbert e a sua influência na Teoria da Computação.
O postulado de Church-Turing.
O resultado fundamental da Teoria da Computação.
A linguagem dos polinómios só com uma variável e que têm raiz inteira é decidível.

Autómatos de Pilha. Máquinas de Turing.

16 Novembro 2016, 08:00 • Ana Respicio

Folha 6 exercícios 1f) g) h) i) discussão j, k, l. 4. Uma computação no autómato de pilha do exercício 4.

Folha 7 exercício 2.

Autómatos de Pilha - Folha 6, e Máquinas de Turing - Folha 7

15 Novembro 2016, 11:00 • Alexandre Miguel dos Santos Martins Pinto

Folha 6: Exercícios 1a, b, c, d, e, f, g, 4

Folha 7: Exercício 1

Autómatos de Pilha. Máquinas de Turing

15 Novembro 2016, 10:30 • Ana Respicio

Folha 6 exercícios 1e) f) g) h) i) discussão j, k, l. 4. Uma computação no autómato de pilha do exercício 4.

Folha 7 exercícios 2, 3.

Máquinas de Turing

15 Novembro 2016, 09:30 • Ana Respicio

Máquinas de Turing: variantes ao modelo padrão, equivalência do poder computacional entre as variantes ao modelo padrão.

Linguagem Turing-reconhecível.
Linguagem decidível.