Sumários

5 Dezembro 2018, 09:30 • André Souto

Noção de redução por mapeamento entre problemas.

Noção de função computável.

Prova que se A se reduz a B e B é Turing-reconhecível (resp. decidível) então A também é Turing-reconhecível (resp. decidível).

Prova que se A se reduz a B e A é indecidível então A é indecidível.

Exemplos de uso.

Teorema de Rice.

Noção de complexidade temporal numa máquina de Turing.

Notação O-grande.

Exemplos de análise de complexidade.

Tempo de simulação de máquinas de Turing multi-fita e não deterministas em máquinas de fita simples.

5 Dezembro 2018, 08:00 • André Souto

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.

4 Dezembro 2018, 11:00 • Andreia Mordido

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.

4 Dezembro 2018, 10:30 • André Souto

Resolução de exercícios da folha 8 e 9 sobre decidibilidade.

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.