Leia o texto a seguir: TMs são autômatos abstratos criados por Alan Turing em 1936 para investigar os limites da computação. As TMs são capazes de ...

Leia o texto a seguir:

TMs são autômatos abstratos criados por Alan Turing em 1936 para investigar os limites da computação. As TMs são capazes de computar funções seguindo regras simples.

A TM é um modelo computacional primitivo com 3 componentes:

•  Uma memória: uma fita de entrada-saída dividida em células discretas que armazenam símbolos. A fita tem uma célula na extremidade esquerda, mas é ilimitada à direita, de modo que não há limite para o comprimento das strings que ela pode armazenar.

•  Uma unidade de controle com um conjunto finito de estados e uma cabeça de fita que aponta para a célula atual e é capaz de se mover para a esquerda ou para a direita durante o cálculo.

•  Um programa armazenado no controle finito que governa o cálculo da máquina.

Refletindo sobre a máquina de Turing não Determinística, avalie as seguintes asserções e a relação proposta entre elas.

I. As Máquinas de Turing têm muitas aplicações na Ciência da Computação Teórica e estão relacionadas à teoria da linguagem formal. São reconhecedores de linguagem que aceitam a classe superior da hierarquia de Chomsky.

PORQUE

II. No estágio de finalização, a computação é interrompida quando há regra para o estado e símbolo atuais. Se o estado atual for final, a Máquina de Turing rejeita a string de entrada.

A respeito dessas asserções, assinale a opção correta:

Grupo de escolhas da pergunta

As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.

As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

As asserções I e II são proposições falsas.

A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.