Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-SC 2014

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq081847
Banca
IF-SC
Órgão
IF-SC
Ano
2014
Nível
Superior
Cargo
Professor - Informática
A máquina de Turing pode ser usada como ferramenta para estudar o processo algorítmico. Assinale a alternativa CORRETA.
  1. AA máquina de Turing consiste de uma fita finita; um cabeçote que lê, escreve e move para direita ou esquerda; um registrador de estados e uma tabela de ações.
  2. BO problema da parada da máquina de Turing deve-se ao limite finito de sua fita e as poucas operações que um cabeçote pode executar (avançar ou retroceder).
  3. CA máquina de Turing pode ser considerada um autômato infinito de grau dois.
  4. DSe um problema não puder ser resolvido por uma máquina de Turing, então esse problema não poderá ser resolvido por qualquer outro sistema algorítmico.
  5. ECriar uma máquina de Turing com fita infinita ainda não é possível devido às restrições tecnológicas atuais.
Revelar gabarito e comentário

GabaritoD — Se um problema não puder ser resolvido por uma máquina de Turing, então esse problema não poderá ser resolvido por qualquer outro sistema algorítmico.

Link permanente: /questoes/qq081847