Church, Alonzo

(1903—–1995) –– amerikansk matematiker. Han bevisade 1936 i artikeln ””A note on the Ent­scheidungs­pro­blem”” (se avgörbarhetsproblemet) att det finns mate­matiska frågor som det inte går att besvara med mekaniska metoder. Det var samma sak som Churchs studie­­kamrat Alan Turing bevisade senare samma år i sin upp­sats om stopproblemet. Turing visade senare att de två bevisen var lik­värdiga. Båda byggde på Kurt Gödels ofull­ständig­hets­sats. –– Church-Turings hypotes säger att alla mate­matiska beräkningar som kan beskrivas i ett ändligt antal steg (med en algoritm) kan lösas av en maskin. Om en nog­­grann men fantasi­lös människa med papper och penna kan räkna ut lösningen (lösa problemet mekaniskt) kan en maskin också göra det. Men: beräkningen kan pågå i all evighet. Till exempel är det lätt att beskriva divisionen 2 delat med 3, men det tar en evig­het att räkna ut svaret (0,6666666……) om man inte sätter stopp. För att inte tala om sådant som att räkna ut värdet på pi. – Det som både Church och Turing bevisade var att även om en maskin kan utföra alla beräkningar som kan uttryckas som algoritmer, så kan maskinen inte avgöra ifall be­räk­ningen tar slut någon gång, eller om den fort­sätter i all evighet. – En artikel på engelska om vanliga miss­­upp­­fatt­ningar av Church-Turings hypotes finns här.