ASPEC TEOR DA COMP módulo 2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

ASPECT TEOR DA COMP
1) Uma Linguagem aceita por uma Máquina de Turing é dita:
R: A, Recursivamente enumerável;
2) Para a classe das Linguagens Recursivas:
 
R: B, existe pelo menos uma Máquina de Turing reconhecedora que sempre para qualquer que seja a entrada;
3) A Classe das Linguagens Recursivas:
 
R: A, está contida propriamente na Classe das Linguagens Enumeráveis Recursivamente;
4) Quando uma máquina de Turing M, processa uma palavra w que não pertencente à Linguagem L:
R: C, A máquina de Turing M pode parar ou permanecer infinitamente em processamento;
5)Quando uma máquina de Turing M, que reconhece as palavras de uma determinada linguagem L recursiva rejeita uma palavra w não pertencente a L:
R: B, a máquina de Turing M para necessariamente em um estado que não seja de aceitação;
6) Considere as seguintes afirmativas:
I - Dada uma máquina de Turing M com alfabeto de entrada S e uma string w não se sabe se a computação de M com entrada w vai não parar.
II -Máquinas de Turing aceitam quaisquer linguagens do Universo de todas as Linguagens;
III – Existe pelo menos uma Linguagem L que não é Recursivamente Enumerável. 
São corretas as afirmações:
R: C, apenas 1 e 3
7)A configuração de uma Máquina de Turing é indicada por um tripla, cujos elementos são:
R: C, O estado corrente, porção do conteúdo da fita de trabalho que se encontra à esquerda do cursor de acesso, porção do conteúdo da fita de trabalho que se encontra à direita do cursor de acesso, incluindo a posição correntemente apontada por ele ( o cursor).