Sobre o conjunto de problemas que podem ser computados por ...

Com base no mesmo assunto

Q958899

Ano: 2018 Banca: FCM Órgão: IFN-MG Prova: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação |

Q958899 Sistemas de Informação

Sobre o conjunto de problemas que podem ser computados por Máquinas de Turing, é correto afirmar que

a demonstração da tese de Church-Turing permitiu compreender o que pode ser computado com diversos modelos de computação, como a máquina de Turing.

uma Máquina de Turing Universal não determinística pode resolver o Problema da Parada.

uma Máquina de Turing com duas fitas pode resolver o Problema da Parada em tempo polinomial.

o Teorema do Bombeamento pode ser utilizado para mostrar que uma Máquina de Turing não pode reconhecer uma determinada linguagem.

o Teorema de Rice mostra que toda propriedade não trivial é indecidível.

Incorreta. Gabarito oficial da banca:

Errou um tema comum da banca? Veja o que mais costuma cair no Raio-X. Ver raio-X

teste

Parabéns! Você acertou!

Essa questão segue o padrão da banca! Veja o que mais costuma cair. Ver raio-X

teste

Questões de assuntos semelhantes