Problemas incomputáveis não podem ser resolvidos por algoritmos com um número finito de passos. Marque V para verdadeiro e F para falso para as afirmações a respeito dessa categoria de problemas: ( ) Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda. ( ) Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem. ( ) Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing. ( ) A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito. Assinale a alternativa que apresenta a sequência correta:
Questão
Problemas incomputáveis não podem ser resolvidos por algoritmos com um número finito de passos. Marque V para verdadeiro e F para falso para as afirmações a respeito dessa categoria de problemas:
( ) Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda.
( ) Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem.
( ) Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing.
( ) A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito.
Assinale a alternativa que apresenta a sequência correta:
Alternativas
a) V - V - V - F.
b) F - F - F - V.
c) F - V - F - F.
d) V - F - F - V.
e) V - V - F - F.
Explicação
Vamos avaliar cada afirmação.
1) “Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda.” Falso. Máquina de Turing e cálculo lambda são modelos equivalentes em poder computacional (Tese de Church‑Turing). Logo, se algo é incomputável em um, também é incomputável no outro.
2) “Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem.” Verdadeiro. Se, para toda entrada , ambos devolvem o mesmo resultado (por exemplo, aceitam/rejeitam do mesmo jeito, ou retornam a mesma saída que determina aceitação), então o conjunto de entradas aceitas por cada um é o mesmo; portanto, reconhecem/decidem a mesma linguagem.
3) “Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing.” Falso (na forma como está escrita). “Algoritmo computacional” é um termo ambíguo: pode incluir procedimentos de “computação” fora do modelo efetivo clássico (ex.: oráculos/hipercomputação). Só é verdade se o enunciado assumisse explicitamente algoritmo efetivo no sentido da Tese de Church‑Turing. Como isso não foi afirmado, a proposição não é necessariamente verdadeira.
4) “A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito.” Falso. Ter fita infinita é uma suposição padrão do modelo de Turing e não garante “a versão mais eficiente” de um algoritmo. Eficiência depende de tempo/espaço e de escolha de estratégia; além disso, fita infinita não é um “método” de otimização.
Sequência: F – V – F – F.
Alternativa correta: (c).