Máquinas de Turing
12 Novembro 2019, 09:30 • André Souto
Motivação para o estudo das máquinas de Turing.
A tese de Church-Turing como ponto central da Teoria da computação.
Noção intuitiva de máquina de Turing.
Diferença para os FA e PDA.
Périplo para a definição formal de máquina de Turing.
Exemplos.
Definição formal de máquina de Turing.
Noção 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.
Estudar secção 3.1 do sipser.