Sumários

3 Dezembro 2019, 09:30 • André Souto

Consequências da indecidibilidade de A_TM.

O problema da terminação e a sua indecidibilidade.

Noção de função computável.

Exemplos.

Noção de redução por mapeamento entre linguagens.

Resultados sobre linguagens redutíveis por mapeamento.

Exemplos.

Prova que o complementar de A_TM não é Turing reconhecível.

Prova que EQ_TM e o seu complementar não são Turing reconhecíveis.

Estudar a secção 4.2 e o capítulo 5 do Sipser.

2 Dezembro 2019, 08:00 • André Souto

Resolução de exercícios da folha 8 sobre decidibilidade de turing-reconhecimento.

29 Novembro 2019, 11:30 • 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.

29 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.

29 Novembro 2019, 08: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.