Aspectos Teoricos I E II

Pergunta 1
0,5 em 0,5 pontos

A máquina de Turing permite a computação de números naturais. Seja I um símbolo fixo não branco. Um número natural n pode ser representado em notação unária, pela cadeia de símbolos I, de comprimento n+1.
Considerando essa definição, selecione a representação unária para os números 0, 1 e 2, respectivamente, com I =1|.

Resposta Selecionada:
c.
1, 11, 111
d)
Respostas:
a.
a) 1 - 1, 1, 1+1
b)

b. i, ii, iii
c)

c.
1, 11, 111
d)

d.
0, 1, 2
e)

e.
00, 01, 10

Pergunta 2
0 em 0,5 pontos

Para a classe das linguagens recursivas:

Resposta Selecionada:
d.
Existe, pelo menos, uma máquina de estados finitos que sempre para qualquer que seja a entrada.
Respostas:
a.
Não existe uma máquina de Turing que a reconheça.

b.
Existe, pelo menos, uma máquina de Turing reconhecedora que sempre para qualquer que seja a entrada.

c.
Existe uma classe equivalente de linguagens dinâmicas.

d.
Existe, pelo menos, uma máquina de estados finitos que sempre para qualquer que seja a entrada.

e. Existe uma classe equivalente de linguagens irregulares.

Pergunta 3
0,5 em 0,5 pontos

“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, uma a uma, todas as células da memória localizadas entre a célula atual e aquela que se deseja acessar. Em contraste, os computadores reais apresentam uma memória de acesso aleatório, onde cada célula da memória pode ser acessada em uma única etapa, se for adequadamente endereçada.” (LEWIS, Papadimitrious). Considere as afirmações I e II:
I - As máquinas de Turing de acesso aleatório são mais poderosas que as máquinas de Turing padrão.
PORQUE
II - Prova-se que a hipótese de Turing Church é verdadeira.
Assinale a alternativa correta: