(A ordem não foi a que está aí)

1 - Defina
1) Maquina de Turing
2) M aceita w
3) Linguagem reconhecível
4) Linguagem decidível
5) Mostre que toda linguagem decidivel é reconhecível

2 - Esboço da prova de que Amt é indecidível

3 - Esboço da prova de que PCP é indecidível

4 - Esboço da prova de que toda máquina multifita de tempo t(n)
tem uma MT de uma fita equivalente em tempo O(t²(n))

5 - Esboço da prova de que Vmt é indecidível

6 - Prove que, se A <= B e B é reconhecível, A é reconhecível

7 - Esboço da prova do teorema de Cook-Levin

Questão extra - Prove que toda MT não-determinística tem uma determinística
que lhe é equivalente