Questão 2876704

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Sistemas de Informação
• Assuntos: Conceito de TI e SI

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

• A. 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.
• B. uma Máquina de Turing Universal não determinística pode resolver o Problema da Parada.
• C. uma Máquina de Turing com duas fitas pode resolver o Problema da Parada em tempo polinomial.
• D. o Teorema do Bombeamento pode ser utilizado para mostrar que uma Máquina de Turing não pode reconhecer uma determinada linguagem.
• E. o Teorema de Rice mostra que toda propriedade não trivial é indecidível.

Gabarito: E

Comentários

• A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico  (-), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em ). Num sentido preciso, é um modelo abstrato de um , que restringe-se apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições), e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.

• GABARITO. E.