Máquina de Turing e sua capacidade computacional

Prévia do material em texto

01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/4
 Módulo 3 - Tese de Turing Church
Exercício 1:
Não se trata de uma Máquina equivalente à Máquina de Turing:
A)
Autômato com uma pilha;
B)
Autômato com uma pilha;
C)
Autômato com Múltiplas Fitas;
D)
Máquina de Turing Multidimensional;
E)
Máquina de Turing com múltiplos cabeçotes; 
O aluno respondeu e acertou. Alternativa(B)
Comentários:
D) A máquina de touring não é multidimensional
C) A máquina de touring não possui multiplas fitas
B) A máquina de touring não uma pilha
Exercício 2:
 Para se aumentar o poder computacional de uma máquina de
Turing:
 
A)
 deve-se adicionar ao seu modelo inicial duas ou mais pilhas;
B)
https://online.unip.br/Arquivo?id=63519.pdf
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/4
deve-se adicionar ao seu modelo inicial múltiplos cabeçotes de
leitura e gravação sobre a mesma fita;
C)
deve-se adicionar ao seu modelo inicial duas ou mais fitas de
entrada;
D)
 torná-la multidimensional;
E)
As modificações dos itens anteriores não alteram o poder
computacional da máquina de Turing;
O aluno respondeu e acertou. Alternativa(E)
Comentários:
E) A máquina de touring já é o maximo da capacidade computacional.
Exercício 4:
A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode
ser atingido por qualquer dispositivo de computação". Este enunciado é conhecido como:
A)
 Teorema de Post;
 
 
B)
 Lema adaptativo de Kleene;
C)
 Hipótese das Funções Recursivas;
D)
 Hipótese de Turing-Church;
E)
 Primeiro Lema da Computação;
O aluno respondeu e acertou. Alternativa(D)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/4
Comentários:
D) é uma hipótese sobre a natureza de artefatos mecânicos de cálculo
Exercício 5:
A Hipótese de Turing-Church:
 
A)
afirma que qualquer forma de expressar algoritmos terá no máximo a mesma capacidade
computacional de um Autômato de Pilha;
 
B)
 prova que qualquer forma de expressar algoritmos terá no máximo a mesma capacidade
computacional da Máquina de Turing;
 
C)
 prova que qualquer forma de expressar algoritmos terá no máximo a mesma capacidade
computacional de um Autômato de Pilha;
 
D)
Torna os formalismos Autômatos de uma pilha e máquina de turing equivalentes
 
E)
afirma que qualquer forma de expressar algoritmos terá no máximo a mesma capacidade
computacional da Máquina de Turing;
O aluno respondeu e acertou. Alternativa(E)
Comentários:
E) Uma vez que o conceito é o mesmo
Exercício 6:
A Hipótese de Turing-Church sugere:
A)
Que à Máquina de Turing devem ser adicionadas duas ou mais pilhas de
forma que o seu poder computacional de expressar algoritmos seja
menos restritivo;
B)
 Que se a máquina de Turing fosse multidimensional seu poder
computacional de expressar algoritmos seria menos restritivo;
C)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/4
Que à Máquina de Turing devem ser adicionados múltiplos cabeçotes de leitura e gravação sobre a mesma fita, de forma que
o seu poder computacional de expressar algoritmos seja menos restritivo;
D)
Que se a máquina de Turing fosse multidimensional seu poder computacional de expressar algoritmos seria muito restritivo;
E)
Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade
computacional da Máquina de Turing;
O aluno respondeu e acertou. Alternativa(E)
Comentários:
E) Uma vez que a máquina de touring é a áxima capacidade computacional.