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.