trabalho computaçao

1- Uma Linguagem aceita por uma Máquina de Turing é dita:
A Recursivamente enumerável;
B Dinâmica;
C Regularmente Recursiva;
D Regularmente Adaptável;
E Adaptável;

2- A Classe das Linguagens Recursivas:
A está contida propriamente na Classe das Linguagens Enumeráveis Recursivamente;
B não pode ser reconhecida por uma máquina de Turing;
C não pode ser reconhecida por uma máquina de Turing que sempre para qualquer que seja a entrada;
D é sempre reconhecida por um autômato finito;
E é sempre reconhecida por um autômato de pilha;

3- Quando uma máquina de Turing M, processa uma palavra w que não pertencente à Linguagem L:
A a máquina de Turing M para necessariamente em um estado final;
B a máquina de Turing M para necessariamente em um estado não final.
C A máquina de Turing M pode parar ou permanecer infinitamente em processamento;
D Máquinas de Turing não reconhecem linguagens;
E A máquina de Turing M não para;

4- 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 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;

5- 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;
.

6- “Apesar do aparente poder e versatilidade das variantes da Máquina de Turing,..., todas apresentam uma característica importante. O modelo de memória é sequencial, isto é, a fim de acessar uma informação armazenada em alguma localização, a máquina necessita primeiramente acessar, um a um, todas as