Loogika aine ja ajalugu
predikaatarvutuse väite puhul alati õigesti otsustada, et seda väidet tuletada ei saa ja otsingu võib katki jätta.
Tuletatavate väidete puhul aga suudab Turing masin tuletuse teoreetiliselt alati leida. Muidugi võib mittetriviaalsete
väidete tuletuste leidmiseks sageli rohkem aega kuluda kui universumil vanust.
1936. aastal esitas Alonzo Church minimaalsete vahenditega algoritmikirjutamise- ehk progammeerimiskeele, nn.
lambda-arvutuse. Lambda-arvutus erineb kardinaalselt Turingi masinast, kuid teoreetiliselt on neil samasugused
arvutamisvõimed: üks on teises algoritmiliselt simuleeritav. Churchi loodud lambda-arvutus on kaasaegsete
funktsionaalsete programmeerimiskeelte eellane, ning tema teoreetiline tähtsus praegusagses loogikas ja teoreetilises
arvutiteaduses on erinevalt Turingi masinast väga suur. Analoogiliselt Turingile tõestas Church, et lambda-arvutuse
annaabi.ee 
