O problema de decisão representa qualquer problema com resposta “sim ou não”, além de ser utilizado para decidir se determinado elemento pertence a um conjunto específico. Sobre o problema de decisão, é correto afirmar que:

Alternativa E

Análise da Questão

A questão aborda conceitos fundamentais da Teoria da Computação, especificamente sobre Problemas de Decisão e Decidibilidade.

Conceitos-Chave

1. Problema de Decisão: É um problema cuja resposta é binária: SIM ou NÃO. Na teoria dos conjuntos, isso equivale a verificar se um elemento pertence a um conjunto específico (pertence ou não pertence).
2. Decidibilidade: Um problema é considerado decidível se existir um algoritmo (uma máquina de Turing) que, para qualquer entrada válida, termine após um número finito de passos e retorne a resposta correta.
3. Indecidibilidade: Existem problemas para os quais não existe nenhum algoritmo capaz de resolvê-los para todas as entradas. O exemplo mais famoso é o Problema da Parada (Halting Problem).

Justificativa Detalhada

• Por que a Alternativa E está correta?
• A afirmativa diz que definir a primalidade (se um número é primo) é um exemplo de problema decidível.
• De fato, existem diversos algoritmos eficientes (como o Teste de Primalidade AKS ou testes probabilísticos como Miller-Rabin) que determinam se um número é primo e sempre terminam. Portanto, é um problema perfeitamente decidível.
• Por que as outras estão incorretas?
• Alternativa A: Embora problemas de decisão retornem verdadeiro/falso, a definição de "entrada genérica" é imprecisa. O foco está na existência do algoritmo de parada, não apenas na natureza da entrada.
• Alternativa B: O termo alemão Entscheidungsproblem (Problema da Decisão) refere-se à busca por um método mecânico para determinar a verdade de qualquer proposição matemática. A resposta não é "decimal", mas booleana (verdadeiro/falso), e o problema foi provado indecidível por Church e Turing.
• Alternativa C: O "detector universal de loops" refere-se ao Problema da Parada, que é de fato um problema de decisão não solucionável (indécidível). No entanto, a explicação de que o algoritmo "continua sendo executado" é enganosa; a realidade é que nenhum algoritmo geral consegue decidir para todos os casos sem entrar em erro ou loop infinito indefinidamente.
• Alternativa D: A equivalência de compiladores (ou equivalência de programas) é um problema indécidível (Teorema de Rice). Não é possível criar um algoritmo geral que compare dois compiladores quaisquer e diga se são equivalentes.

Resumo

A teoria da computação distingue claramente entre problemas que podem ser resolvidos automaticamente por um computador (decidíveis) e aqueles que não podem (indecidíveis). A primalidade é um exemplo clássico de classe P (tempo polinomial), logo, é decidível.

Alternativa E.