UNIVERSIDADE FEDERAL DE UBERLÂNDIA
Faculdade de Computação
Disciplina : Teoria da Computação 1 - 10 Semestre 2008
Professora : Sandra Aparecida de Amo
3a Aula de Exercicios - Problemas Indecidı́veis - Turing Reconhecı́veis
Exercicio 1: Seja P1 o problema {< M > | < M > é código de Máquina de Turing que aceita
algum input }. Pergunta-se: P1 é indecidı́vel ? Justifique sua resposta. P1 é Turing-reconhecı́vel
? Justifique sua resposta.
Exercicio 2: Seja P2 o problema {< M > | < M > é código de Máquina de Turing que
aceita todos os inputs }. Pergunta-se: P2 é indecidı́vel ? Justifique sua resposta. P2 é Turingreconhecı́vel ? Justifique sua resposta.
Exercicio 3: Seja P3 o problema {< M > | < M > é código de Máquina de Turing que não
aceita nenhum input}. Pergunta-se: P3 é indecidı́vel ? Justifique sua resposta. P3 é Turingreconhecı́vel ? Justifique sua resposta.
Exercicio 4 : Seja P4 o problema {< M > | < M > é código de Máquina de Turing que não
aceita algum input}. Pergunta-se: P4 é indecidı́vel ? Justifique sua resposta. P4 é Turingreconhecı́vel ? Justifique sua resposta.
Exercicio 5 : Seja A uma linguagem (ou problema) Turing-reconhecı́vel e suponha que A ≤ A.
Mostre que A é decidı́vel. (A denota o complementar de A, isto é, o problema cuja resposta é
sim quando A responde não e vice-versa.
Exercicio 6:Seja J = {w | w = 0x para algum x ∈ AT M ou w = 1y para algum y ∈ AT M .
Mostre que nem J nem J são Turing-reconhecı́veis.
Exercicio 7: Dê um exemplo de uma linguagem indecidı́vel B tal que B ≤ B.
1