En su trabajo de 1936 "An unsolvable problem of elementary number theory" Church formuló por primera vez lo que ahora se conoce como la tesis de Church que es la identificación del concepto vago de calculabilidad efectiva con la noción precisa de función recursiva.