Turmas - 1º Semestre de 2026(IFFar, 2016) A Máquina de Turing, proposta por Alan Turing em 1936, é um mecanismo simples que formaliza a ideia de uma pessoa que realiza cálculos, usando um instrumento de escrita e um apagador. O modelo formal de uma Máquina de Turing é baseado em três componentes básicos: uma fita (utilizada para entrada, saída e rascunho); uma unidade de controle que possui cabeça de leitura e escrita sobre a fita; e um programa. Considerando as extensões da Máquina de Turing, a extensão que aumenta seu poder computacional é:
A Múltiplas fitas.
B Múltiplas cabeças.
C Não determinismo.
D Fita bidimensional infinita à esquerda e à direita.
E As extensões da Máquina de Turing não aumentam seu poder computacional.
Na Teoria da Computação, poder computacional refere-se ao conjunto de problemas/funções que um modelo é capaz de resolver ou reconhecer. É um resultado clássico e amplamente demonstrado que todas as variantes listadas (múltiplas fitas, múltiplas cabeças, não determinismo, fita bidimensional ou infinita em ambas as direções, etc.) são computacionalmente equivalentes à Máquina de Turing padrão de fita simples e determinística. Todas reconhecem exatamente a classe das linguagens recursivamente enumeráveis e decidem exatamente as linguagens recursivas.
O que essas extensões alteram é a complexidade (tempo e espaço necessário para resolver um problema), e não a computabilidade. Por exemplo:
Portanto, nenhuma dessas modificações amplia o que é computável; apenas impactam a eficiência. A afirmação da alternativa E está alinhada com a Tese de Church-Turing e com os teoremas de equivalência de modelos de computação.
E As extensões da Máquina de Turing não aumentam seu poder computacional.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 