Indecidibilidade e diagonalização

4 Dezembro 2018, 09:30 • André Souto

Continuação da aula anterior sobre indecidibilidade de linguagens.

Indecidibilidade de linguagens sobre máquinas de Turing:

-- Aceitação de uma string por uma máquina de Turing;

-- Linguagem aceite por uma máquina de Turing ser vazia;

-- Igualdade de linguagens de máquinas de Turing.

O problema da terminação, HALTING.

Estudar as secções 4.1 e 4.2 do Sipser.