Question

1-Uma Máquina de Turing ____________ possui um único "caminho de computação" a ser seguido. Já uma Máquina de Turing ____________ possui uma "árvore de computação", onde, qualquer ramo da árvore para em uma condição de aceitação, dizemos que a Máquina aceita a entrada.

Assinale a alternativa que preenche corretamente as lacunas.

Escolha uma:
a.
com Oráculos / Não-Determinística

b.
Não-Determinística / Determinística

c.
Determinística / com Oráculos

d.
de Redução / Determinística

e.
Determinística / Não-Determinística

2-A principal característica de uma máquina de Turing ____________ é que para o mesmo estado corrente e símbolo lido, diversas alternativas são possíveis.

Assinale a alternativa que preenche corretamente a lacuna.

Escolha uma:
a.
De fina infinita

b.
De múltiplas cabeças de fita

c.
Não-determinística

d.
De múltiplas fitas

e.
De fina finita

3-Qual a classe de problemas denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística?

Assinale a alternativa correta.

Escolha uma:
a.
Classe NPSPACE

b.
Classe PSPACE

c.
Classe NP-completo

d.
Classe NP

e.
Classe P

Answer 1

Resposta:

1 - Determinística / Não-Determinística

2 - Não-determinística

3 - Classe P

Explicação:

CORRIGIDO PELO AVA.