En la década de 1930, uno de los problemas más estudiados por los matemáticos era el Entscheidungsproblem propuesto por David Hilbert: dada una proposición en un sistema formal, ¿existe un algoritmo tal que pueda decidir si la proposición es cierta (y por tanto es un teorema del sistema) o por el contrario es falsa?
Se ha acordado que un procedimiento efectivo o algoritmo consiste en un número finito y preciso de pasos descrito en un número finito de símbolos que podría ser también ejecutado por un ser humano.
Sin embargo, nada de esto ha sido una definición formal pues no es claro qué significa “instrucción precisa” o cuál es el tipo de inteligencia necesaria para seguir las instrucciones.
La tesis de Church-Turing ha sido tan exitosa que la mayoría la supone verdadera.
Basta con exponer un método efectivo o algoritmo que no sea computable en el sentido de Turing (i.e.
A esto se le ha llamado tesis de Church-Turing fuerte.