Embora uma máquina de Turing seja uma estrutura muito simples, ela é extremamente poderosa. Acerca de suas características, uma linguagem L é chamada aceitável, se existe uma máquina de Turing M que:
I) Entra em loop infinito para cadeias em L.
II) Aceita L.
III) Rejeita L.
IV) Resolve o problema em um tempo de execução polinomial.
V) Resolve o problema da Parada.
a) III, IV e V.
b) IV e V.
c) I, II e III.
d) I, III e V.
e) II e III.
I) Entra em loop infinito para cadeias em L.
II) Aceita L.
III) Rejeita L.
IV) Resolve o problema em um tempo de execução polinomial.
V) Resolve o problema da Parada.
a) III, IV e V.
b) IV e V.
c) I, II e III.
d) I, III e V.
e) II e III.
More Questions From This User See All
Lista de comentários
Resposta: I, II, e III.
Explicação:
Após revisarmos sobre os critérios de aceitação e rejeição de uma Linguagem pela máquina de Turing, definimos que a alternativa C está correta.
Entendendo sobre a Máquina de Turing
Uma máquina de Turing é uma estrutura matemática que foi proposta por Alan Turing em 1936 como uma forma de formalizar o conceito de computação.
Além disso, é possível que a máquina de Turing rejeite uma cadeia pertencente à linguagem L. Isso pode ocorrer se a máquina chegar a um estado de rejeição ou se ela não conseguir chegar a um estado de aceitação ou rejeição após um número finito de passos.
Deste modo, as afirmações I, II e III são verdadeiras. A afirmação IV é falsa, pois uma máquina de Turing pode não ser capaz de resolver o problema em um tempo de execução polinomial. A afirmação V é falsa, pois a máquina de Turing não é necessariamente capaz de resolver o problema da Parada.
Deste modo a alternativa C está correta.
Saiba mais sobre máquina de Turing em: https://brainly.com.br/tarefa/53712556
#SPJ1