Alternativa A - I, II e IV
Análise Detalhada
A questão aborda conceitos fundamentais da Teoria da Computação, especificamente sobre Máquina de Turing, Computabilidade e Decidibilidade. Vamos analisar cada afirmação para encontrar a combinação correta:
Avaliação dos Itens
- I. Existência de problemas insolúveis (CORRETA)
- É um teorema fundamental que existem problemas que nenhuma máquina de Turing pode resolver. O exemplo clássico é o Problema da Parada (Halting Problem), provado por Alan Turing em 1936. Isso confirma que computadores têm limites intrínsecos.
- II. Definição de Decidibilidade (CORRETA)
- A decidibilidade trata especificamente de problemas de decisão. Para um problema ser considerado decidível, deve existir uma Máquina de Turing que, para qualquer entrada, pare em um número finito de passos e retorne uma resposta binária: Sim ou Não (ou 1 e 0). Isso corresponde aos "dois valores possíveis" mencionados.
- III. Problema da parada da palavra vazia (INCORRETA)
- Embora existam variações do problema da parada (como determinar se a linguagem aceita por uma máquina é vazia, denotado por E_{TM}), a descrição fornecida ("nem sempre se tem como resultado uma saída válida") é imprecisa e confusa no contexto de decidibilidade formal. Além disso, ao comparar com as outras opções, esta afirmação é menos precisa que a I, II e IV.
- IV. Linguagens e Algoritmos (CORRETA)
- Na teoria da computação, decidir uma linguagem significa possuir um algoritmo (Máquina de Turing) que determina se uma string pertence a essa linguagem ou não. As linguagens formais são o objeto central de estudo da decidibilidade.
- V. Problema de Totalidade (INCORRETA)
- O Problema da Totalidade (TOTAL) pergunta se uma Máquina de Turing aceita todas as strings possíveis (\Sigma^*).
- A afirmação diz que ele verifica a equivalência entre duas máquinas universais. Isso está errado; a equivalência entre duas máquinas é um problema diferente (EQ_{TM}). Ambos são indecidíveis, mas definem questões distintas.
Conclusão
As afirmações corretas são I, II e IV.
| Item | Status | Motivo |
|---|
| I | ✅ Correto | Prova da existência de indecidibilidade. |
| II | ✅ Correto | Definição correta de problema de decisão (Sim/Não). |
| III | ❌ Incorreto | Descrição confusa/imprecisa. |
| IV | ✅ Correto | Relação correta entre linguagens e algoritmos. |
| V | ❌ Incorreto | Confunde Totalidade com Equivalência. |
Portanto, a alternativa que apresenta somente as afirmações corretas é a A.