Sa mahusay na papel na isinulat ni Turing na " On Computable Numbers ( mga bilang na matutukoy ng isang nagwawakas na algoritmo ) , with an Application to the Entscheidungsproblem " ( na kanyang isinumite noong 28 Mayo 1936 at itinanghal noong 12 Nobyembre ) , kanyang binago ang mga resulta na isinulat ng matematikong si Kurt Godel noong 1931 tungkol sa limitasyon ng pagpapatunay ( proof ) at komputasyon , kung saan pinalitan ni Turing ang pangkalahatang nakabatay @-@ sa @-@ aritmetikang pormal na lenggwahe ng isang makinang Turing , na mga makinang pormal at simple.
