Berechenbarkeit: Post, Gödel, Church, Turing (und viele andere)

Kurt Gödels Arbeit hatte weitreichende Auswirkungen, über die eher spezialisierten Bereiche der mathematischen Logik und Grundlagen der Mathematik hinaus. Es war schon lange ein Traum von Wissenschaftlern, Mathematikern und Philosophen, ‚Rechenmaschinen‘ zu bauen, die im einfachsten Fall mathematische Berechnungen automatisieren würden: zunächst die einfachen Operationen von Addition und Multiplikation. Nach der Entwicklung von Präzisionsuhrwerken im späten 17. Jahrhundert schien dieser Traum in greifbarer Nähe zu sein. Gödels zeitweiliger Held Gottfried Wilhelm Leibniz baute tatsächlich eine solche Rechenmaschine (um 1670–1700) mit Zahnrädern und Sperrklinken, sowie eine Verschlüsselungsmaschine. Seine Rechenmaschine (Multiplikationsmaschine) erweiterte Ideen, die von Blaise Pascal vorgeschlagen wurden, und wurde als ‚Stepped Reckoner‘ bezeichnet (siehe Abb. 12.1). Leibniz selbst wird mit der eher elitären Aussage zitiert: „... es ist unter der Würde ausgezeichneter Männer, ihre Zeit mit Berechnungen zu verschwenden, wenn jeder Bauer die Arbeit mit Hilfe einer Maschine genauso präzise erledigen könnte“.