Máquinas de Turing

10 Novembro 2020, 09:30 • André Souto

Recordar a definição formal de máquina de Turing, de configuração e computação numa máquina de Turing.

Linguagem reconhecível por uma máquina de Turing.
Noção de linguagem Turing-reconhecível.
Máquinas de Turing de decisão.
Noção de linguagem Turing-decidível.
Prova que toda a linguagem Turing-decidível é Turing-reconhecível.

Exemplo de desenho de uma máquina de Turing para uma linguagem regular.

Estudar secção 3.1 do Sipser.
A aula foi dada em regime síncrono não presencial com transmissão via Zoom.