Máquinas de Turing

9 Novembro 2021, 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.