Apesar do aparente poder e versatilidade das variantes da M quina de Turing

1. “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:

a.
Ambas afirmações, I e II, são verdadeiras e a afirmação I é justificada pela afirmação II.

b.
Ambas afirmações são falsas.

c.
Ambas afirmações são verdadeiras, mas a afirmação I não pode ser justificada pela afirmação II.

d.
Apenas a afirmação I é verdadeira.

e.
Ambas afirmações são verdadeiras, mas a afirmação II é justificada pela afirmação
0,5 pontos
Pergunta 2
1. - Sabe-se que a máquina de Turing é definida formalmente como uma quíntupla MT = (Q, A, Γ, g, q0, >, b, F), em que:
Q é o conjunto finito não vazio de estados.
A é o alfabeto de entrada, formado por um conjunto não vazio de símbolos.
Γé o conjunto finito e não vazio de símbolos que podem ser lidos e/ou escritos na fita de trabalho Γ⊇ A. q0∈Q é o estado inicial.
F ⊆ Q é o conjunto de estados finais. Assinale a alternativa correta sobre a Máquina de Turing MT:

a.
O cursor de acesso à fita de trabalho de uma máquina de Turing pode se deslocar apenas à direita.

b.
Apresenta a fita de trabalho limitada à direita.

c.
Sempre, para qualquer que seja o conteúdo da fita de entrada e qualquer que seja a função de transição.

d.
Apresenta um conjunto ilimitado de