Continuação das Máquinas de Turing
14 Novembro 2018, 09:30 • André Souto
Revisão da definição formal de Máquina de Turing e de computação.
Máquinas de Turing que terminam para qualquer input (máquinas de decisão).
Definição de linguagem Turing-reconhecível e Turing-decidível.
Exemplos de Máquinas de Turing para algumas linguagens e de configurações em máquinas de Turing.
Menção às variantes das máquinas de Turing:
Variante Stay
Variante Multi-fita
Variante de fita infinita para ambos os lados
Variante não determinista.
Estudar secções 3.1 e 3.2 do Sipser.