Alternativa A - I, II e IV
Esta questão aborda conceitos fundamentais da Teoria da Computação, especificamente focados em Computabilidade e Decidibilidade. Para encontrar a resposta correta, analisamos cada afirmação com base nas definições clássicas das Máquinas de Turing.
Análise das Afirmações
✅ Afirmação I: Correta
"Existem problemas que são insolúveis na visão computacional, já que os computadores são limitados..."
Esta afirmação resume o conceito central da teoria da computabilidade. Alan Turing demonstrou que existem problemas matemáticos que nenhuma máquina de Turing (e, portanto, nenhum algoritmo geral) consegue resolver. O exemplo mais famoso é o Problema da Parada (Halting Problem). A afirmação valida a ideia de que há limites teóricos para o que pode ser calculado.
✅ Afirmação II: Correta
"Decidibilidade é uma definição para um caso particular de computabilidade, quando a função somente pode atribuir dois valores possíveis à saída..."
Em teoria dos autômatos, um problema de decisão (que é o foco da decidibilidade) exige uma resposta binária: Sim/Não ou Aceita/Rejeita. Uma linguagem é considerada decidível se existe uma Máquina de Turing que para em todas as entradas e decide corretamente se a string pertence à linguagem. Isso corresponde exatamente à descrição de "dois valores possíveis".
❌ Afirmação III: Incorreta (ou menos adequada)
Embora existam variações do Problema da Parada (como a parada na entrada vazia), a descrição fornecida confunde a terminologia técnica padrão ("saída válida" é vago; o correto seria "parar" ou "não parar"). Além disso, em questões desse tipo, a afirmação genérica e verdadeira (Item I) costuma ser preferida sobre detalhes específicos mal formulados.
✅ Afirmação IV: Correta
"Linguagens são utilizadas na decidibilidade e definem como as máquinas expressam e resolvem problemas..."
As Linguagens Formais são o objeto de estudo da decidibilidade. Elas definem conjuntos de strings que podem ser reconhecidos ou decididos por máquinas. O processo descrito (etapas para determinar ações) refere-se ao funcionamento do algoritmo implementado pela máquina. Esta é a base da relação entre linguagens e autômatos.
❌ Afirmação V: Incorreta
"O problema de totalidade é um problema de decisão... verificando a equivalência entre duas máquinas universais."
O Problema da Totalidade pergunta se uma máquina para em todas as entradas (domínio infinito). Já o Problema da Equivalência pergunta se duas máquinas aceitam a mesma linguagem. São dois problemas distintos e ambos são indecidíveis, mas um não verifica o outro. A definição dada na afirmação mistura conceitos diferentes.
Conclusão
Com base na análise:
- I é verdadeira (limites da computação).
- II é verdadeira (natureza binária da decisão).
- IV é verdadeira (papel das linguagens formais).
Portanto, a combinação correta é I, II e IV, correspondente à alternativa A.