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 afi...
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:
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.
💡 2 Respostas
Ed 
A resposta correta é a alternativa E: V - V - F - F. Explicação: - A primeira afirmação é falsa, pois existem problemas que não podem ser resolvidos nem por máquinas de Turing nem por cálculo lambda. - A segunda afirmação é verdadeira, pois se dois programas produzem o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem. - A terceira afirmação é falsa, pois existem problemas que não podem ser resolvidos por algoritmos computacionais, mas que podem ser resolvidos por máquinas de Turing. - A quarta afirmação é falsa, pois uma máquina de Turing com fita de tamanho infinito não é mais eficiente do que uma máquina de Turing com fita de tamanho finito.
DS Laxus
Resposta correta: C. F - V - F - F.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Compartilhar