Sumários

Exercícios sobre máquinas de Turing

27 Novembro 2020, 11:30 • André Souto

Resolução de exercícios sobre máquinas de Turing.
Resolução do 3º exercício prático sobre máquinas de Turing de computação.
Aula em regime alternado misto com transmissão via zoom.

Exercícios sobre máquinas de Turing

27 Novembro 2020, 08:00 • André Souto

Resolução de exercícios sobre máquinas de Turing.
Resolução do 3º exercício prático sobre máquinas de Turing de computação.
Aula em regime alternado misto com transmissão via zoom.

Exercícios sobre máquinas de Turing

27 Novembro 2020, 08:00 • Andreia Mordido

Resolução de exercícios sobre máquinas de Turing. 
Resolução do 3º exercício prático.
Aula em regime misto alternado.

Problema da terminação e redutibilidade

25 Novembro 2020, 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 5.3 do livro do Sipser.

A aula foi dada em regime síncrono não presencial com transmissão via Zoom. 

Exercícios sobre máquinas de Turing

25 Novembro 2020, 08:00 • Andreia Mordido

Resolução de exercícios sobre máquinas de Turing. 
Resolução do 3º exercício prático.
Aula em regime misto alternado.