Dans un article datant de 1937 et concernant les nombres calculables, Alan Mathison Turing démontra qu'une machine numérique pouvait calculer toute fonction récursivement calculable en un temps fini. Ces travaux se fondaient sur ceux du mathématicien Alonzo Church : ce dernier avait quant à lui démontré que toute fonction calculable est récursivement calculable.