Variantes das máquinas de Turing.
11 Novembro 2020, 09:30 • André Souto
Recordar a definição e diferençe entre linguagens Turing-reconhecíveis e Turing-decidíveis.
Exemplo de máquina de Turing.
Variantes das máquinas de Turing: versão Stay, multifita, fita infinta para ambos os lados e não determinista.
Equivalência entre todas as variantes por equivalência à máquina de Turing standard.
Estudar secção 3.1 e 3.2 do Sipser.
A aula foi dada em regime síncrono não presencial com transmissão via Zoom.