Turmas - 1º Semestre de 2026(IFNMG, 2018) Na década de 1930, motivados pelos desafios de David Hilbert sobre decidibilidade matemática, Alonzo Church e Alan Turing lançaram as bases da teoria da computação. A Tese de Church-Turing formalizou a noção intuitiva de "cálculo efetivo", estabelecendo um consenso sobre o que é computável. No mesmo contexto, Turing propôs as máquinas universais, dispositivos teóricos capazes de emular qualquer outro processo computacional, antecipando a concepção dos computadores de propósito geral. Juntas, essas contribuições redefiniram a lógica matemática e delimitaram o alcance teórico da computação moderna. 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 Uma Máquina com mais que duas Pilhas pode resolver o Problema da Parada em tempo polinomial.
E O Problema da Parada é um problema indecidível, cuja demonstração de impossibilidade algorítmica foi provada por Alan Turing em 1936.
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.
A Tese de Church-Turing é uma conjectura (ou hipótese), não um teorema. Ela postula que qualquer função computável por um algoritmo intuitivo pode ser computada por uma Máquina de Turing (ou pelo cálculo lambda, funções recursivas, etc.). Por relacionar um conceito informal ("algoritmo/efetivamente computável") com modelos formais, ela não pode ser demonstrada matematicamente.
B Uma Máquina de Turing Universal não determinística pode resolver o Problema da Parada.
O Problema da Parada é indecidível para qualquer modelo equivalente à Máquina de Turing, seja ela determinística, não determinística ou universal. O não determinismo não altera a classe de problemas decidíveis, apenas pode impactar a complexidade de tempo (no caso de problemas decidíveis).
C Uma Máquina de Turing com duas fitas pode resolver o Problema da Parada em tempo polinomial.
Novamente, o Problema da Parada é indecidível. Adicionar fitas a uma Máquina de Turing apenas melhora a eficiência (fator constante ou polinomial) para problemas já decidíveis, mas não torna decidível um problema indecidível. Portanto, nenhuma variante de TM consegue resolvê-lo, muito menos em tempo polinomial.
D Uma Máquina com mais que duas Pilhas pode resolver o Problema da Parada em tempo polinomial.
Uma máquina com duas ou mais pilhas é computacionalmente equivalente a uma Máquina de Turing (duas pilhas podem simular perfeitamente uma fita infinita). Logo, herda todas as limitações de computabilidade, incluindo a indecidibilidade do Problema da Parada.
E O Problema da Parada é um problema indecidível, cuja demonstração de impossibilidade algorítmica foi provada por Alan Turing em 1936.
O Problema da Parada foi provado indecidível por Alan Turing em 1936 utilizando um argumento de diagonalização (inspirado na diagonalização de Cantor e no paradoxo do mentiroso). A prova assume a existência de uma máquina que decide a parada e, por diagonalização, constrói uma máquina que se comporta de forma oposta, levando a uma contradição lógica. Isso estabelece formalmente a impossibilidade algorítmica de resolvê-lo.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 