De acuerdo a la tesis de Church-Turing, los problemas solucionables por una máquina universal de Turing son exactamente esos problemas solucionables por un algoritmo o un método efectivo de computación, para cualquier definición razonable de esos términos.