Sumários

Indecidibilidade de A_TM

27 Novembro 2019, 09:30 André Souto

Prova que N, Z e Q, conjunto das máquinas de Turing e de todas as strings são enumeráveis.

Prova que R e que o conjunto das sequências infinitas não é enumerável.
Prova que A_TM é indecidível.
Consequências da indecidibilidade de A_TM.

Estudar a secção 4.2 do Sipser. 


Resolução de exercícios sobre máquinas de Turing

27 Novembro 2019, 08:00 André Souto

Continuação da resolução de exercícios sobre máquinas de Turing.

Resolução de um exercício prático para a avaliação contínua.


Resolução de exercícios sobre máquinas de Turing

26 Novembro 2019, 11:00 Andreia Mordido

Continuação da resolução de exercícios sobre máquinas de Turing. 

Resolução de um exercício prático para a avaliação contínua. 


Resolução de exercícios sobre máquinas de Turing

26 Novembro 2019, 10:30 André Souto

Continuação da resolução de exercícios sobre máquinas de Turing.

Resolução de um exercício prático para a avaliação contínua.


Decidibilidade de linguagens

26 Novembro 2019, 09:30 André Souto

Continuação da aula anterior: Decidibiliade da linguagem vazia em DFA e da igualdade entre linguagens de DFA.

Decidibilidade de linguagens baseadas em linguagens livres de contexto.
Introdução aos problemas indecidíveis.
O problema de aceitação em máquinas de Turing. Prova que é Turing-reconhecível.
Periplo para a demonstração que é indecidível.
Argumentos de diagonalização.
Noção de conjunto enumerável.