Aus der Geschichte der Computer
und
Mathematische Logik

Inhalt:

 1.Zahlen-Darstellungen
 2. Analog-Rechner
 3. Leibniz und die erste Rechenmaschine
 4. Ada und Babbage
 5. Zuse
 6. Computer in USA und England
 7. Turing-Maschinen
 8. Mathematische Logik
 9. Gödel und die Unvollständigkeit der Arithmetik
 10. von Neumann Maschinen
 

1. Zahlen-Darstellungen

Die ersten Computer waren die Finger der Hände. Deshalb wundert es nicht, dass schon die alten Ägypter das Zehnersystem benutzten.

Bild 1_1: Ägyptische Hieroglyphen 1800 v. Chr. für die Zahlen, aus Michael R. Williams, A History of Computing Technology, p. 10, signatur: phd 751/t85a

Es eignete sich schon gut zum Addieren und zum Subtrahieren. Keine unterschiedlichen Symbole für die 10 Ziffern, sondern primitives Aufzählen. Kein positional decimal system, d.h. neue Symbole für die Einer-, Zehner-,
Hunderter-Position.

Die Ägypter hatten noch kein Symbol für die null, wodurch ein positionales System verunmöglich wird.

1300 v. Chr. geschichtlich nachgewiesen, die Chinesen benutzen ein positionales Zehnersystem mit individuellen Symbolen für die Ziffern.

Bild 1_2: Die Zahlen von 1 bis 10 in 3 chinesischen Varianten, aus Williams, p. 33

Die linke Variante war im Volksgebrauch, die mittlere Variante war in juistischem Gebrauch, z.B. für Verträge, weil man die Ziffern durch Zusatzstriche nicht so leicht fälschen konnte. Die rechte Variante wurde von Buchhaltern zum Rechnen benutzt wegen der einfacheren Symbole.

Arithemtik blüht in China, auch Lehrbücher der Arithmetik.

213 v. Chr. Kaiser Chi Hwang-ti befielt, alle Bücher zu verbrennen und alle Gelehrten hinzurichten

800 n. Chr. In China wird die 0 verwendet, wahrscheinlich aus Indien übernommen.

Unsere Ziffern nennt man arabische Ziffern. Es gab aber verschiedene Varianten. Besonders verwirrend, dass in einer Variante die 5 wie eine 0 geschrieben wurde.

Bild 1_3: Weit verbreitete Variante der arabischen Ziffern, aus Williams, p. 28

Es muss schon als ein großer Fortschritt betrachtet werden, dass sich eine Variante durchsetzte.

Bild 1_4: Ein Rechenzentrum aus dem Jahre 1430, aus Williams, p. 27

Bild 1_5: Das erste gedruckte Mathematikbuch, das zwischen 1542 bis ca. 1700 ein Standardwerk war, aus Williams, p. 64

Der Zählrahmen (= Abakus) war für viele Jahrhunderte der wichtigste Computer.
 

2. Analog-Rechner


Der Zählrahmen ist ein digitaler Computer. Daneben wurden auch analoge Computer entwickelt. Dabei sind Ein- und Ausgabe (sowie die interne Verarbeitung analog), d.h. die Variablen können kontinuierliche Werte annehmen, wie beim Zeiger eine Uhr.

Bild 1_6: Ein griechischer Analog-Rechner, aus Williams p. 201

Bei obigem Analog-Rechner wird die Multiplikation durch geeignete Übersetzungsverhältnisse der Zahnräder realisiert. Das Stück wurde im Jahre 1900 von Fischern aus dem Ägäischen Meer geborgen.

Bild 1_7: Lord Kelvin's analoger Voraussager für Ebbe und Flut, funktionsfähig ca. 1900, aus Williams, p. 206

Bild 1_8: Als Rolle aufgewickelter Rechenschieber von ca 30m Länge, ca 1900, aus Williams, p. 117

Auch elektronische analoge Rechner (unter Verwendung von Operationsverstärkern = OpAmp's) wurden bis 1980 intensiv weiterentwickelt, mussten aber schließlich das Feld den digitalen Computern räumen.

Zurück zu den digitalen Rechenmaschinen:
 

3. Leibniz und die erste Rechenmaschine


1642 Pascal erfindet eine mechanische Addier-Maschine

Bild 1_9: Gottfried Wilhelm Leibniz (1646-1716), aus Williams, p. 134

Die bedeutendste Leistung von Leibniz war die Erfindung der Differentialrechnung, allerdings parallel zu Newton. Er war ein Universalgenie seiner Zeit.

Bild 1_10: Schema der Leibniz'schen Rechenmaschine, aus Williams, 139

Weniger bekannt ist, dass er auch Erfinder der ersten mechanischen Multipliziermaschine ist. Sein Grundprinzip enthalten auch alle mechanischen und elektrischen Rechenmaschinen, die bis vor kurzem noch in manchem altmodischen Büros standen.

Wie schon für Pascal war das Haupt-Hemmnis von Leibniz die schlechte Ausbildung der Arbeiter (Metall-Facharbeiter gab es nicht) sowie schlechtes Material, so dass manche Modelle aus Holz gefertigt wurden.

Erst 1674 konstruierte ihm der Pariser Uhrmacher Olivier eine funktionierende Multiplizermaschine.

Bild 1_11: Die Leibnizsche Multiplizier-Maschine (1674), aus Williams, p. 140

Vorne oben sieht man ein Register von 8 Dezimalziffern, die in Form von Zeigern das Ergebnis angaben. Nicht zu erkennen sind Schieber, an denen man den Multiplikand eingab. Für jede Stelle des Multiplikators musste der vordere Wagen an die richtige Stelle geschoben werden. Die linke Handkurbel (war man damals mehr Linkshänder?) musste nun so oft gedreht werden, wie diese Ziffer des Multipliktors angab. Zur Fehlervermeidung gab man vielmehr diese Ziffer in dem horizontalen Rad oben rechts ein und konnte nun gedankenlos so lange drehen, bis man anschlug.

Die Leibnizsche Multiplizier-Maschine war 200 Jahre lang verschollen, bis man sie in einem Speicher der Universität Göttingen wieder auffand.

Mit 15 Jahren begann Leibniz das Studium der Rechtswissenschaft in Leipzig, wo er mit 20 Jahren seine Doktor-Arbeit fertigstellte. Man verweigerte ihm aber die Promotion mit dem Argument, dass er zu jung sei. Die Universität Nürnberg lies ihn jedoch sofort durch und bot ihm eine Professur an. Die erschien ihm aber zu langweilig. Vielmehr nahm er die Stelle eines Beraters des Kurfürsten von Mainz an, der damals einer der berühmtesten Staatsmänner war. Seine Aufgabe bestand darin, als Gesandter in Paris die Franzosen davon abzuhalten, Deutschland zu kassieren, was man befürchtete, und sie dazu zu überreden, lieber Ägypten anzugreifen. Argument war, dass Ägypten ja noch christianisiert werden musste.

In seinen letzten Jahren, auch krankheitsbedingt, wurde Leibniz sehr missmutig und geizig und schaffte sich sehr viele Feinde. Er war auch verbittert, weil ihm Newton den alleinigen Ruhm wegen der Erfindung der Differential-Rechnung streitig machte. Seine Beerdigung war wie die eines Verbrechers: Sein Sekretär war als einziger anwesend.
 

4. Ada und Babbage


Bild 1_12: Charles Babbage (1791-1871), Geistiger Großvater des modernen Computers, aus Williams, p. 160

Babbage, der als erster die wesentlichen Ideen konzipierte, die auch beim modernen Computer immer noch realisiert sind, gilt als Großvater des Computers (nicht als Vater, weil seine Maschinen nie funktionierten).

So ab 1780 waren mathematische Zahlentafeln, wie Tabellen für Logarithemen und den trigonometrischen Funktionen (cosinus, sinus, tanges) weit verbreitet. Babbage besaß 140 solcher Bände. Diese Tabellen waren aber voller Fehler, so fanden sich auf einer verbreiteten Multiplikations-Tabelle für alle Produkte x.y  (x <100, y < 1000) schon auf der ersten Seite 40 Fehler.

Nach der französischen Revolution (1789) startete die Regierung ein groß-angelegtes Projekt, bessere Tabellen zu entwickeln.

Bild 1_13: Tabelle von zwei ganzzahligen Polynomen, wie sie später  von einer Weiterentwicklung der Babbage'schen Differenzmaschine erstellt wurden, aus Williams, p. 177

Es ist zu bemerken, dass die meisten wichtigen Funktionen näherungsweise auf solche Polynome (Potenzreihen) zurückführbar sind.

16 der besten Mathematiker leiteten das Projekt und 100 einfache Mitarbeiter führten die tatsächliche Rechenarbeit aus. Dabei stellte man hauptsächlich arbeitslose Friseure ein. Von denen gab es genügend, denn seit der Revolution war das Tragen von gepuderten Perücken, wie wir es noch beim Bild von Leibniz sahen, außer Mode gekommen.

Jeder Zahlenwert wurde in mehreren unabhängigen Städten Frankreichs berechnet (so dass eine Zusammenarbeit unmöglich schien) und verglichen. Dennoch enthielten diese Tabellen viele Fehler.

Wenn man die Werte für das Polynom f(n) = 2n+3, ein Polynom ersten Grades, berechnen wollte, so unterscheiden sich ihre Werte für fortlaufende n jeweils um 2, haben also konstante Differenz. Für Polynome zweiten Grades waren die Differenzen Polynome ersten Grades, d.h. die Differenz der Differenzen waren konstant. Das brachte Babbage  auf die Idee seiner Differenzenmaschine, indem sukkzessive ein konstaner Wert aufaddiert wurde.

Babage war Sohn eines reichen Bankiers und  brauchte sich nicht um einen Lebensunterhalt zu kümmern. Er war in der High Society von London bestens bekannt und hatte Einfluss auf Minister. 1823 bekam er für sein Projekt von der Regierung 1 500 Pfund (= $7 500) und war bereit, selber den doppelten Betrag aus seinem Vermögen beizusteuern. Er glaubte in 3 Jahren fertig zu sein.

Bild 1_14: Holzstich eines Planes eines kleinen Ausschnittes des Babbage'schen Differenzmaschine, aus Williams, p. 170

Oben erkennt man die Angabe "Calculation complete". Man musste solange drehen, bis die erschien.

Die Planung für das oben abgebildete Teil wurde 1823 begonnen, 1833 tatsächlich aufgebaut, und  ganze Projekt 1842 fallengelassen. Insgesamt hatte die britische Regierung umgerechnet $84 000 und Babbage aus seinem Vermögen $ 100 000 investiert.

Erst 1853 gelang es dem Schweden Georg Scheutz eine funktionierende Differenz-Maschine herzustellen, mit der obige Polynome 4. Grades berechnet wurden.

Bild 1_15: Die Scheutz'sche Differenz-Maschine (1853), aus Williams, p. 176

Man konnte die (ganzzahligen) Werte von Polynomen bis zum Grade 4 (mit ganzzahligen Koeffizienten) für ganzzahlige Argumente n berechnen. Man musste von Hand kurbeln, bis das Schild "calculation complete" erschien. Die Fehlerquellen durch Abschreiben des Ergebnisses auf Papier und durch den nachfolgenden Buchdruck, blieben weiterhin bestehen.

Die Scheutz-Maschine war damit die erste mechanische Rechenmaschine, die schon eine gewisse Programmierung erlaubte (= spezieller Computer), indem die Koeffizienten des Polynoms vorher eingestellt (einprogrammiert) werden konnten.

Die Probleme von Babbage waren, wie schon bei Pascal und Leibniz,  immer noch vor allem handwerklicher Natur: Es gab keine Fein-Metall-Facharbeiter. Er musste sie selber anlernen und die notwendigen Maschinen erst entwickeln.  Dadurch entstand in London erst diese Handwerksrichtung, was ein wesentliches Verdienst von Babbage ist.

Es ist eine interessante historische Tatsache, dass somit der Computerbau wesentlich die Entwicklung der Feinmechanik vorantrieb.

Da die Regierung zwischendurch die Förderung mehrmals einstellte, musste er immer wieder neue Leute einarbeiten. Man sagt, dass sich auf diese Weise die o.g. finanzielle Investition auf jeden Fall gelohnt hat.

Babbage war ein außerordentlicher Pedant; sonst hätten ihn ja auch die vielen Fehler in den Tabellen nicht gestört.

Er versuchte sogar, eine Partei zu gründen mit dem Ziel, die vielen Strassen-Musikanten in London zu verbieten, die ihn abends und nachts immer sehr störten. Eines seiner Argumente: Einige Ladies von zweifelhafter Tugend nehmen die Freude  an der Musik zum Vorwand, ihre eigenen Reize an ihrem offen Fenster darzustellen. Er wurde jedoch nicht gewählt.

Obwohl er in seiner Fachwelt eine hohe Reputation genoss, endete er in Verbitterung. Aus Rache spielten die Stadt-Musikanten besonders oft vor seinem Haus, oft bis tief in die Nacht hinein. Ging er auf die Straße, liefen sie ihm nach und verspotteten ihn.

So überwarf er sich wegen einer Kleinigkeit mit seinem Chef-Mechaniker, Mr. Clement,  der jahrelang mit ihm durch dick und dünn ging. Nach damaligen britischen Gesetzen durfte dabei ein Arbeiter alle seine eigenen Werkzeuge mitnehmen, auch wenn er sie auf Kosten seines Arbeitgebers hergestellt hatte. Clement nahm sogar alle Pläne mit, musste sie aber später wieder zurückgeben.

Dieses Gesetz war sinnvoll, denn normalerweise handelte es sich nur z.B. um eine Schaufel. Es erschien sinnvoll, dass ein Arbeiter seiner Schaufel mitnehmen durfte, wenn er gefeuert wurde, auch wenn die Schaufel auf Kosten des Arbeitgebers erstellt wurde. Hier ging es sich jedoch um ein ganzes Arsenal von Mechanik-Maschinen.

Dies war heilsam, denn Babbage musste alles nochmals von vorne überdenken. Dabei kam er 1834 auf die Idee seiner berühmten sog. analytischen Maschine, eine Rechenmaschine, die von einem externen Programm gesteuert wurde, also im wesentlichen ein moderner Computer in rein mechanischer Ausführung. Es ist fraglich, ob seine Pläne wirklich ausgegoren waren und funktioniert hätten. Er verbrachte seine letzten 38 Jahre seines Lebens mit der gedanklichen Ausarbeitung dieser Maschine.

Bild 1_15a: Ein Plan der analytischen Maschine von Babbage, aus Williams, p. 184

Er sah 50 Register-Kolonnen zu je 100 Zahlen mit bis zu 40 Stellen vor. Ihr Inhalt konnte von einem Register ins andere verschoben werden (memory). Einige Register konnten addieren und multiplizieren. Dies wurde von einem Programm gesteuert, das auf Lochkarten (punched cards) abgelegt war.

Diese Lochkarten übernahm er von einem damals neu erfundenen programmierbaren Webstuhl (Jacquard loom), bei dem das zu verwebende Textil-Muster von solchen Lochkarten gesteuert wurden.

Bild 1_16: Babbage'sche Lochkarte mit dem Befehl das Register V6 mit dem Register V2 zu multiplizieren, aus Williams, p. 188
 


 

Bild 1_16a: Jaquard's programmierbarer Webstuhl. Oben das Band mit Lochkarten. Aus Scientific American, Ada and the First Computer, May 1999, p. 71

Auf einem anderen Lochkarten-Leser waren die Daten gespeichert. Seine Programme sahen auch schon (bedingte) Sprünge vor: überspringe N Lochkarten, wenn ein Register-Inhalt kleiner als M ist, oder: beginne mit dem Lochkarten-Stapel von vorne.

Er sah auch schon vor, dass Register-Inhalte automatisch ausgedruckt wurden.

Aus gesundheitlichen Gründen empfahl ihm sein Arzt, zur Kur in ein wärmeres Land zu gehen. In Turin erklärte er seine Pläne einer Gruppe von Militär-Ingenieuren, die seine Ideen auf italienisch ausformulierten.

Bild 1_17: Ada Augusta Byron, Countess of Lovelace, 1815-1852, eine Freundin von Babbage, aus J.G.P. Barness: Programmieren in ADA, Titelblatt, signatur kid 252.60/b17

Ada Byron übersetzte den italienischen Text auf englisch und ergänzte ihn mit vielen Kommentaren und Erläuterungen.

Nach ihr wurde die Computer-Sprache ADA benannt, die vom DoD (= Department of Defence = US-amerikanisches Verteidigungs-Ministerium) entwickelt und verwendet wird. Ada war 17, Babage ein 41 jähriger Witwer der London High Society, als sie sich kennenlernten. Ada studierte Mathematik.  Später heiratete sie den Grafen von Lovelace. Über viele Jahre diskutierte sie mit Babbage theoretisch die Entwicklung der Analytischen Maschine. Sie schrieb ein Programm zur Berechnung der Bernoulli-Zahlen für diesen gedachten Computer. Damit war sie der erste Programmierer der Welt.

5. Zuse

Den ersten funktionierenden Computer baute Konrad Zuse (1910-1995) und er gilt deshalb als der Vater des Computers.

Es scheint, mir dass man die Bedeutung von Babbage überschätzt. Zuse hatte 1941 den ersten funktionierenden Computer der Welt fertiggestellt, ohne von den Ideen Babbage's gewusst zu haben.

Bild 1_18: Die Zuse Z1 mit Konrad Zuse (rechts) im Wohnzimmer seiner Eltern in Berlin, aus Williams, p. 218

Er kam auf die Idee, die Daten binär zu speichern  und baute einen Speicher, bei dem sich ein Stift entweder im linken oder rechten Loch eines kleinen Metall-Plättchens befand (Patent 1936); anstelle der bisherigen Räder mit 10 Stellungen. Er erkannte (1934), dass ein automatischer Rechner nur aus 3 Einheiten bestehen muss: eine arithmetische Einheit, ein Steuerwerk (= control unit, zum Abbarbeiten der Befehle, beides die heutige CPU) und ein memory.

Zuse war bei der Flugzeugfirma Henschel angestellt, aber zum Entsetzen seiner Eltern kündigte er diesen Job und begann, im Wohnzimmer ihrer kleinen Wohnung die Zuse Z1 aufzubauen. In obigem Bild erkennt man eine 35mm-Filmrolle, die anstelle von Papier-Lochstreifen die Programme trugen. Dies beschaffte sein Freund und Mitarbeiter Schreyer (links im Bild), der ein Film-Operateur war.

1939 wurde Zuse zur Wehrmacht eingezogen. Seine Freunde versuchten, die Armee davon zu überzeugen, dass er besser an seinen Maschinen weitertüfteln sollte. Es dauerte ein Jahr, bis sie den Antrag bearbeiteten, und dann entschieden sie, dass er wieder als Ingenieur in seiner ehemaligen Flugzeugfirma zu arbeiten habe.

Bild 1_18a: Die Zuse Z3, der erste funktionierende Computer der Welt (5. Dez. 1941), bestehend aus 2600 Relais, vorne links der Monitor mit einzelnen Lampen und eine Tastatur, ganz vorne links eine gebrauchte 35mm Filmspule als Lochstreifen zur Speicherung des Programmes, aus Williams, p. 220

Am 5. Dez. 1941 war die Zuse Z3 fertig: der erste wirklich funktionierende Computer, aufgebaut aus 2 600 Relais, davon 600 für die CPU mit den ersten drei Grundrechenarten, 600 für die Steuereinheit, 1400 für das memory mit einem Umfang von 64 Worten zu 22 Bits. Die Z3 konnte addieren in 1/4 sec, multiplizieren in 5 sec.

Bedingte Sprünge konnte die Z3 nicht ausführen, aber das dauerte noch Jahre. Warum eigentlich: Man konnte doch einfach dem Filmspulenmotor den Befehl geben, n Schritte nach vor- oder rückwärts zu drehen.

Die Materialkosten  beliefen sich auf $ 6 500. Die Z3 wurde für keine reale Anwendung benutzt, weil ihr memory zu klein war. Sie blieb in Zuses's Wohnung, bis sie bei einem Bombenangriff 1944 zerstört wurde. Zuse hatte keinerlei Kenntnisse von Vorläufern (wie Babbage) oder von parallelen Entwicklungen (Harvard Mark I, fertiggestellt Jan 1943).

Bild 1_19: Die Zuse Z4, aus Williams, p. 223

Die Z4, eine Weiterentwicklung ebenfalls aus Relais aufgebaut, war beinahe fertig, als sie wegen der ununterbrochenen Bombenangriffe von Berlin nach Göttingen, dann in den Keller eines kleinen Hauses in Hinterstein in Bayern transportiert wurde.

1950 wurde die Z4 aus ihrem Versteck geholt und an der ETH Zürich aufgestellt und leicht verbessert. Sie war damals der einzige funktionierende Computer Europas. Sie leistete dort ihren Dienst bis 1955, dann in einem französischen ärodynamischen Institut nahe Basels bis 1960.

Konrad Zuse versuchte nach dem Krieg, eine Firma zu gründen, die aber Pleite ging.
Sein einziger Dank von der Menschheit: er erhielt als erster den nach ihm benannten Konrad-Zuse-Preis.
 

6. Computer in USA und England


Parallel zu Zuse lief die Entwicklung bei den Allierten, wobei vorallem Howard Aiken aus Harvard zu nennen ist.

1943 Fertigstellung der ENIAC, auch mit Relais aufgebaut.
1948 Erfindung des Transistors

Bild 1_20: Ein britischer Computer, 1949, aus Williams, p. 327

Bild 1_21: Lochstreifen (-Leser) zur Speicherung von Daten und Programmen, aus Williams, p. 245

Bild 1_22: Elektronische Rechner füllen ganze Hallen, 1958, aus Williams, p. 253

Bild 1_23: Computer-Operateure mussten die Binärzahlen gut beherrschen, aus Williams, p. 396

Zwischen dem ersten und zweiten Weltkrieg wurde in Deutschland die Enigma entwickelt, eine Maschine zur Verschlüsselung von Daten, die als Morse-Signale per Funk übermittelt wurden. Sie bestand aus 3 Rädern, die je nach Stellung solche Kontakte schalteten, dass eine bestimmte Verschlüsselung des Eingangs-Codes (= gewöhnliches Morse-Zeichen) erzielt wurde. Sender und Empfänger brauchten die 3 Räder nur in derselben Stellung einzustellen, um ver- bzw. entschlüsseln zu können. Diese gleiche Lage der Räder mussten sie auf konventionellem Wege verabreden.

Es gab eine miltärische und eine kommerzielle Version der Maschine. Letztere war für Firmen gedacht, die abhörsichere Information zwischen ihren Filialen austauschen wollten.  Als ab 1928 die Wehrmacht verschlüsselt funkte, alarmierte dies den polnischen Geheimdienst. Sie kauften die kommerzielle Version der Maschine und da sie damit das Prinzip der Maschine verstanden, konnten sie alsbald auch ohne Kennntis der Stellung der Räder 75% der mit der militärischen Maschine verschlüsselten Nachrichten verstehen. Allerdings wurde die Maschine auf Seite der Wehrmacht dauernd verbessert, d.h. verkompliziert.

Am 25 Juli 1939, als es klar war, dass der Krieg bald ausbrechen würde, organisierten die Polen mit dem britischen und dem französischen Geheimdienst ein Meeting. Diese waren erstaunt, dass die Polen den Code entschlüsseln konnten, da sie dies selbst auch lange, aber erfolgloserweise versucht hatten. Die Polen übergaben ihnen einen polnischen Nachbau der Enigma und auch viel statistische Information, wie die Räderstellung von der Wehrmacht gewechselt wurde.

Die britische Code and Cipher School befand sich in Bletchley Park nördlich von London. Die britische Computer-Entwicklung wurde damals massgeblich durch diese Entschlüsselungs-Aufgaben bestimmt.

Bild 1_24: Alan M. Turing, 39 Jahre, aus Williams, p. 291

Einer der durch seine anderweitigen Leistungen am bekanntesten Mitarbeiter war der Mathematiker Alan M. Turing (1912-1954, Suizid).

An seinem Fahrrad hing des öfteren die Kette aus. Anstatt dies einfach reparieren zu lassen, fand er eine Regelmäßigkeit heraus und stieg rechtzeitig ab und ging einige Schritte zu Fuss, um so das nächste Herausfallen der Kette zu umgehen.

Er fürchtete, dass die Deutschen bald England angreifen würden, verwandelte deshalb sein Vermögen in Silber-Barren und vergrub diese an zwei Stellen in einem Wald in der Nähe von Bletchley Park. Nach dem Kriege konnte er sich überhaupt nicht mehr an die Stellen erinnern, wo er sie vergraben hatte.
 

7. Turing-Maschinen

1936 konzipierte er eine abstrakte Maschine, die in der mathematischen Logik eine große Rolle spielt, die sog. Turing-Maschine. Sie ist ein besonders einfach aufgebauter und damit einfach beschreibarer, gedachter Computer. Sie eignet sich deshalb besonders gut, um allgemeine mathematische Sätze über die prinzipiellen Eigenschaften von Computern zu beweisen. Sie hat andererseits keine praktische Bedeutung als Ersatz für reale Computer, da sie wegen ihrer Einfachheit alles beliebig umständlich machen muss.

Wir besprechen die Turing-Maschine hier etwas ausführlicher, weil alle notwendigen Prinzipien der Programmierung schon an ihr besprochen werden können. Außerdem ist es die Gelegenheit zu einem kleinen Ausflug in die mathematische Logik.

Bild 1_24a: Band einer Turing Maschine, welche eine Funktion f(n) berechnet, wobei der Fall f(6) = 360 dargestellt ist, oben: vor Beginn der Rechnung, mitte: nach Ende der Rechnung. Falls das Alphabet der Turing-Maschine nur aus einem Zeichen, sagen wir | besteht, müssen statt 6 in der Anfangskonfiguration 6 Striche auf dem Band stehen (unten).
 

Wir benutzen die Turing-Maschine, um bestimmte Funktionen f(n) zu berechnen, z.B. die Funktion

f(x) = x4 - 6x3 + 11x2 - 6x

wie auch schon in Bild 1_13  von der Scheutz-Maschine geschehen. Argument x und Funktionswert f(x) müssen natürliche Zahlen (0, 1, 2, 3 ...) sein.

Ein Compter tut (im Prinzip) auch nichts anderes, denn wir können den Inhalt seines memory (inkl. aller seiner Festplatten) als eine ganz lange natürliche Zahl (in Binärdarstellung) auffassen. Dies trifft vor, wie auch nach Ausführen eines bestimmten Programmes zu.

Die Turing-Maschine besitzt ein Band, das auf beiden Seiten unendlich lang ist.

Das Band muss nicht aktual-unendlich lang sein, es muss nur hinreichend lang sein, d.h. wenn die Turing-Maschine auf einer Seite ein längeres Band verlangt, kommt eben ein Operateur, der ihr bereitwilligst, das Band verlängert. In jedem Rechenschritt hat das Band stets eine endliche Länge. Ebenso darf die Turing-Maschine so lange rechnen wie sie will. Nach jedem Rechenschritt, hat sie erst endlich lange Zeit gerechnet. Zur Frage, ob sie jemals abbricht, kommen wir später.
 
 

Das Band (tape) besteht aus Feldern (squares), aber die Turing-Maschine schaut sich in jedem Rechenschritt nur ein Feld an (das scanned square) d.h. der nächste Rechenschritt hängt von keinem der anderen Felder ab.

Wenn die Turing-Maschine den Funktionwert f(x) zum Argument x=6 berechnen soll, so wollen wir ihr dieses Argument links vom scanned square anbieten (bzw. wir setzen die Turing-Maschine mit ihrem scanned square unmittelbar rechts vom Argument auf). Im übrigen soll das Band leer sein. Wir verlangen von der Turing-Maschine, dass sie irgend wann mal anhält, und dabei das Ergebnis f(6)=360 links vom scanned square abliefert.

Großzügigerweise erlauben wir ihr, dass sie noch Zwischenergebniss o. dgl. rechts (oder auch links vom Ergebnis mit einem Leerfeld dazwischen) stehen hat. Es ist leicht zu beweisen, dass es immer eine Aufräum-Turing-Maschine gibt, die das anderenfalls vorher noch erledigen würde.

Eine Turing-Maschine besitzt ein (endliches) Alphabet, z.B. aus den Dezimalziffern: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.  Auf endlich vielen Feldern des Bandes steht irgendein "Buchstabe" des Alphabetes; die restlichen Felder sind leer. Auf die Wahl des Alphabetes kommt es nicht an: eine Turing-Maschine mit einem Alphabet aus nur zwei Symbolen (0, 1), ja sogar eine mit nur einem Symbol (stroke, |) kann gleichviel, wie eine mit einem längeren Alphabet. In Bild 1_24a unten ist die Anfangskonfiguration x=6 eben mit 6 markierten (|) Feldern, gefolgt von einem Leerfeld, dargestellt.

Eine Turing-Maschine (mit einbuchstabigem Alphabet) kann nur 5 verschiedene Befehle ausführen:

  lösche das scanned square
|      (allgemein: irgend ein Buchstabe des Alphabetes, überschreibenderweise)
r     move scanned square one field to right
l     move scanned square one field to left
h    halt

Es ist erstaunlich, dass dennoch folgendes gilt:

Alles was ein Computer kann, kann auch eine Turing-Maschine.

Dabei sind nur die rein rechnerisch-logischen Dinge gemeint. Eine Turing-Maschine kann z.B. nicht: Aufs Internet zugreifen, reale Musik spielen, ausdrucken, einen echten physikalischen Zufallsgenerator abfragen, Ergebnisse übersichtlich grafisch auf dem Monitor darstellen, etc.

Andererseits ist auch klar, dass eine Turing-Maschine durch einen Computer ersetzt (von einem Computer simuliert = emuliert) werden kann,
vorausgesetzt, sein memory ist hinreichend groß und man lässt ihn hinreichend lange rechnen.
(emulieren heißt: ein Computer führt den Befehlssatz eines anderen Computers aus.)

Mit den 5 Befehlen haben wir erst sozusagen die CPU einer Turing-Maschine beschrieben, noch nicht ihre Steuer-Einheit (control unit), d.h. wie sie programmiert wird (damit sie z.B. eine bestimmte Funktion f(x) berechnet) und wie sie ihr Programm abarbeitet (executes).

Das Programm hat die Form einer sog. Turing-table. Die Turing-Maschine kann beliebige bedingte Sprünge (conditional jumps) ausführen, wobei die Sprung-Bedingung (jump condition) durch den Inhalt des scanned squares (| oder) gegeben ist.Wir betrachten am besten einfache Beispiele:

Das folgende Turing-Programm berechnet die Funktion f(x) = x+1(f = succesor function, das Programm zu obigem Polynom vierten Grades f(x) wäre schon unglaublich lang):

   |    0
     |    r   1
   h
     |    h

Im Prinzip wäre es also ausreichend nur Turing-Computer zu bauen und nur diese Turing-Programmiersprache zu beherrschen.

Dieses Programm besteht aus zwei Befehls-Zeilen (statements, instructions), wobei wir aus Übersichtlichkeitsgründen jede Befehls-Zeile als zwei typografische Zeilen geschrieben haben, entsprechend den beiden Möglichkeiten ( | oder ), die das scanned square zu der Zeit des Programm-Ablaufs gerade beinhaltet.

Wie in der Mathematik üblich, beginnen wir mit 0 zu zählen. Wir haben also statement 1 und statement 2, und im statement 2 hält die Maschine bereits an (unabhängig von der jump-condition). Die Maschine beginnt mit Statement 0.

Die erste Kolonne eines Turing-Programmes gibt also die (logische) Zeilennummer (logisch im Unterschied zu typografisch).
Die dritte Kolonne sagt, was die Maschine bei Ausführung dieses Befehles tut (einer der ihr möglichen 5 Einzel-Befehle:  | r l h), in Abhängigkeit aktuellen Inhalt des scanned square,  oder |, = 2. Kolonne).
Die 4. Kolonne sagt, wohin (welche statement-number) er nach Ausführen dieses Befehles springen soll (= Sprung-Ziel).

Aus Übersichtlichkeitgründen haben wir in der Turing-Tabelle einige Einträge leer gelassen. Wenn das stört, kann man in der ersten Kolonne die Statement-Nummer auch für die zweite Sprung-Bedingung nochmals wiederholen. Ferner kann man nach h= halt (formal) irgendwohin springen; dieser Sprung wird ja gar nicht mehr ausgeführt.

Wir haben der Turing-Maschine ja auch ein besonders einfaches Problem gegeben, sie muss ja nur die Zahl ihrer Anfangskonfiguration um 1 erhöhen, d.h. der Zahl einfach hinten ein | anfügen, und nach unseren Konventionen bezüglich der Lage des scanned square bei der Anfangs-Konfiguration, bedeutet dies einfach: in ihr scanned square ein | schreiben. Dies leistet die erste typografische Zeile.

Nach unseren Konventionen, wie die Turing-Maschine, ihr Ergebnis abliefern soll, muss sie nun das scanned square (das nun ein |) enthält, noch um 1 Feld nach rechts schieben. (Nach den Anfangskonventionen ist dieses Feld leer; außer dem Argument war das Band ja leer.) Das leistet die zweite typografische Zeile.

Als nächstes wollen wir ein Turing-Programm schreiben, welches die Funktion f = parity = Geradheit  berechnet, d.h. f(x)=0 falls x eine gerade Zahl und f(x)=1 falls x eine ungerade Zahl ist.

Anstatt darauf los zu programmieren (zu kodieren, to encode), ist es sinnvoll sich das Problem zuerst allgemein-sprachlich zu überlegen:

Wir nehmen der Anfangszahl x (= den x Strichen in der Anfangs-Konfiguration) immer ein Paar von zwei Strichen weg, bis entweder nichts mehr übrig bleibt (Ergebnis: f(x)=0) oder nur noch ein Strich (Ergebnis: f(x)=1) übrig bleibt (so dass kein ganzes Paar mehr wegnehmbar ist).

Nun müssen wir konkreter werden,  z.B. die Anfangs-Konvention berücksichtigen, dass wir 1 rechts von allen Strichen sitzen (wir = die Turing-Maschine, als Programmierer steuern wir sie ja, sitzen = Ort des scanned square). Ferner können wir die großzügige Ergebnis-Konvention benutzen, dass wir auf dem Band noch Schrott belassen dürfen im und rechts vom scanned square. Das Ergebnis steht ja links vom scanned square.
Wir müssen also nur paarweise nach links gehen, löschen brauchen wir nicht.

Nun kann man zu einer halb formalen, halb sprachlichen Programmiersprache übergehen. Wenn diese viele grafische Elemente wie Pfeile (statt gehe zu), Kringel (für zusammenghörige Bemerkungen) etc. enthält, so spricht man von einem Fluss-Diagramm (flow-diagram). Es soll auch viele Kommentare (comments) enthalten.

Statt Statement-Nummern verwenden wir Symbole wie anfang, korrektur.
Ein sehr sprachlich orientiertes Fluss-"Diagramm" könnte also etwas so aussehen:

anfang:  Du stehst 1 rechts von der zu untersuchenden Zahl
             Gehe auf jeden Fall 1 nach links
             Jetzt stehst Du am rechten Ende der zu untersuchenden Zahl
             Ist sie null?

ja, Ergebnis=0, h (Band links ist ja leer)
         |   nein, es war ein Strich da, gehe nach links  und
                         schau ob noch ein Partner für ihn da ist.

nein, Ergebnis=1, aber du bist zu weit gegangen, gehe zu  korrektur
            |   ja, wenn Du diesen zweiten Strich auch wegdenkst,
                       hast Du eine neue äquivalente zu untersuchende
                       Zahl. Du stehst 1 rechts von ihr. Gehe zu anfang

korrektur: Das Ergebnis=1 muss richtig hingeschrieben werden,
                 gehe dazu einfach 2 mal nach rechts, so dass Du rechts von genau einem | stehst.
 

Ich bin kein Freund von Fluss-Diagrammen, sondern ziehe es vor, in den Programm-Code hinreichend viele Kommentare einzufügen. Da die Syntax der Turing-Maschinen-Sprache keine Kommentare vorsieht, fügen wir diese  einfach sprachlich dazu.

Das Turing-Programm lautet dann etwa so:

anfang: gehe auf jeden Fall 1 nach links, dann zu statement 1
l 1
0  |  l 1
Du stehst jetzt am rechten Ende der zu untersuchenden Zahl
h    Die zu untersuchende Zahl war 0, Ergebnis=0
1  | l 2  Es war ein Strich da
Ist für den Strich noch ein Partner da?
r 3 nein, Du bist zu weitgegangen: also nach links und Korrektur
2  |  l  1 ja, wenn Du diesen zweiten Strich wegdenkst, hast Du eine neue äquivalente zu untersuchende Zahl, gehe nach links, dann stehst Du an ihrem rechten Ende, gehe also zu statement 1
korrektur: Du stehst auf dem Ergebnis |, aber Du musst rechts davon stehen
3 | r h
 

Eine Turing-Maschine kann nicht nur Funktionen berechnen, sondern irgend ein Muster auf dem Band erzeugen, etwa das unendliche Muster

| ...

auf dem anfänglich leeren Band mit Hilfe des Codes:

   |   0
     |    r   1
   r   0
     |    h   1

Die erste Zeile  erzeugt, den ersten Strich,
die zweite Zeile rückt nach rechts,
die dritte Zeile rückt nochmals nach rechts, da das Band ja leer war, belässt also dieses leere Feld. Sprung zu statement 0 wiederholt alles unendlich oft.
Die vierte Zeile ist eigentlich überflüssig. Sie bewirkt einen Programm-Abbruch, falls auf dem anfänglichen Band schon an einer richtigen Stelle ein Strich vorhanden war. Wir haben sie dazu gefügt, weil die strenge Syntax der Turing-Maschinen-Sprache zu jedem Statement die beiden Zeilen, entsprechend des Inhaltes des scanned square, verlangt. Das Beispiel zeigt auch, dass eine Turing-Maschine nicht abbrechen muss, auch wenn irgendwo der Befehl h vorkommt. Ob sie abbricht oder nicht kann auch vom Input (= Anfangs-Konfiguration des Bandes) abhängen und ist keine triviale Frage.
 

Man kann der Turing-Maschine vorwerfen, sie sei kein Computer sondern nur eine Rechenmaschine, weil sie immer nur eine spezielle Funktion berechnet bzw. ausführt. Aber das ist eine mehr haarspalterische Frage, denn man kann natürlich die Turing-Tabelle (ihr Programm) als Input zu einem anderen Kanal als dem Band auffassen; dann ist sie beliebig programmierbar.

Dazu beweist man die Existenz einer sog. universellen Turing-Maschine. Diese kriegt auf ihrem Anfangs-Band neben dem Argument (oder den Argumenten, jeweils durch ein leeres Feld getrennt) der zu berechnenden Funktion, noch als weiteres Argument die gewünschte Turing-Tabelle. Die universelle Turing-Maschine liest zuerst ihr Programm (Turing-Tabelle) und benimmt sich danach wie eine gewöhnliche Turing-Maschine mit dieser Tabelle.

Eine solches Programm wirklich zu schreiben, dürfte jedoch eine sehr umfangreiche Arbeit sein.
 

8. Mathematische Logik


Dabei hat man jedoch das formale Problem, dass die Turing-Tabelle keine Zahl sondern eben eine Tabelle mit Symbolen ist. Dies löst man durch eine sog. Gödel-Numerierug (= Gödelisierung). Eine einfache Variante davon wird in jedem Computer benutzt durch den sog. ASCII-Code, indem jedes Symbol als eine Zahl codiert wird. Im Falle der Turing-Tabelle können wir etwa die Statement-Numern durch Dualzahlen darstellen, wobei wir die Ziffern 0 und 1 benötigen. Die weiter benötigten Symbole ,  |,  l,  r,  h, sollen dann durch die Ziffern 3, 4, 5, 6, 7 dargestellt werden. Das Zeilen-Ende soll druch die Ziffer 8 codiert werden. Dann wird z.B. die letzte obige Turing-Tabelle durch die Dezimal-Zahl:

03408 04618 13608 14718

dargestellt. Falls die Turing-Maschine nur das einbuchstabige Alphabet { | } besitzt, muss man ihr dieses Programm in Form von so vielen Strichen mitteilen, wie obige lange Zahl angibt. Man erkennt hier nochmals, dass die Turing-Maschinen nicht zur praktischen Anwendung, sondern nur für mathematische Betrachtungen erdacht wurden.

Die Turing-Maschine dient in der mathematischen Logik vor allen als Präzisierung des Begriffes der Berechenbarkeit. Weil wir die entsprechenden Turing-Maschinen konstruiert haben und uns davon überzeugt haben, dass sie für alle x abbrechen, sind z.B. die beiden Funktionen f(x)=x+1 und f=parity berechenbare Funktionen.

Eine  Menge (set) heißt bekanntlich endlich (finite), wenn sie aus endlich vielen, z.B. aus 25  Elementen besteht. Eine unendliche Menge heißt abzählbar unendlich, wenn man sie durch die durch die natürlichen Zahlen abzählen kann. So ist z.B. die Menge aller Turing-Maschinen abzählbar  unendlich, denn wir hatten soeben eine Abzählung durch die natürlichen Zahlen gegeben.

Dabei tritt das Problem auf, dass einige Zahlen nicht einer syntaktisch-korrekten, d.h. gar keiner Turing-Maschine entsprechen. So ist z.B. die Zahl 88  keine Turing-Maschine, denn ihre Tabelle besteht nur aus zwei Leerzeilen. Es gilt aber, dass eine Teilmenge einer abzählbaren Menge abzählbar ist. Dies gilt sogar im konstruktiven Sinne, denn es ist entscheidbar, ob eine Zahl einer Turing-Maschine entspricht oder nicht (z.B. 88).

Der Begriff der Entscheidbarkeit ist identisch mit dem Begriff einer berechenbaren Funktion, welche nur die Werte 0 (falls die Entscheidung nein lautet) und 1 (falls die Entscheidung ja lautet). So hatten wir oben durch Konstruktion der entsprechenden abbrechenden Turing-Maschine bewiesen, dass es entscheidbar ist, ob eine natürliche Zahl gerade oder ungerade ist.

Andere Sprechweise: alle Turing-Maschinen sind aufzählbar (enumerable), weil es entscheidbar ist, ob eine Zahl einer (syntaktisch-korrekten) Turing-Maschine entspricht oder nicht. Nochmals anders ausgedrückt: Es gibt eine Turing-Maschine, welche n auf ihr Anfangs-Band geschrieben, nach endlicher Zeit gerade die n.te Turing Maschine als Ergebnis ausgibt(dabei nie eine syntaktisch inkorrekete ausgibt, andererseits auch keine syntaktisch korrekte vergisst).

Es gilt aber der folgende erstaunliche Satz aus der mathematischen Theorie der Turing-Maschinen (siehe z.B. Hans Hermes: Enumerability, Decidability, Computability, Springer-Verlag, W.J. Paul: Komplexitätstheorie, Teubner, signatur: lbs 830/p19):

Es ist nicht entscheidbar, ob eine Turing-Maschine, welche eine Funktion f(x) berechnet, für alle natürlichen x abbricht oder nicht.

Dies gilt sogar, wenn man sich auf x=0 beschränkt: Es ist nicht entscheidbar, ob eine Turing-Maschine, aufs leere Band angesetzt, abbricht oder nicht (undecidability of the halting problem).

Damit ist der Begriff der Berechenbarkeit selbst ein nicht-entscheidbarer Begriff. Man könnte zunächst vermuten, dass diese Turing-Berechenbarkeit gar kein so sinnvoller Begriff ist, dass wir etwa die Definition der Turing-Maschine zu restriktiv gefasst haben, sie etwa zu wenig Befehle ausführen darf. Man konnte jedoch beweisen, dass so gut wie jede andere vorgeschlagene Definition von Berechenbarkeit, etwa durch kompliziertere Turing-Maschinen oder etwa durch den Begriff der rekursiven Funktionen mit dem Begriff der Turing-Berechenbarkeit übereinstimmt.

Die Funktion n! = 1.2.3...n (z.B. 5!= 1.2.3.4.5= 120) wird meist rekursiv definiert:

0!=1
n!=n.(n-1)!

d.h. die Definition von f(n) wird auf die Definition von f(n-1) zurückgeführt (von lat. recurrere = zurück-rennen).

Dass alle, auch zukünftigen, Vorschläge eines sinnvollen Begriffes der Berechenbarkeit mit der Turing-Berechenbarkeit äquivalent sind, bezeichnet man als die Church'sche Hypothese.

Auch alle rationalen Zahlen (= alle Brüche = alle Zahlen der Form n/m, wobei n und m natürliche Zahlen, m ungleich 0)  sind abzählbar. Aber alle reellen Zahlen (= alle Punkte auf der reellen Zahlengeraden = x-Achse) sind über-abzählbar (= nicht-abzählbar). Umso mehr sind alle Funktionen nicht abzählbar. (Denn sogar alle konstanten, reell-wertigen Funktionen sind über-abzählbar.) Nur die wenigsten Funktionen sind also berechenbar.

Physiker-Witz. Ein Physiker kam bei seinen Berechnungen auf eine Differential-Gleichung. Er fragte einen befreundeten Mathematiker brieflich, ob er ihm diese Differential-Gleichung lösen könne. Nach einem halben Jahr bekam er eine Antwort: Die Lösung existiert.

Analoge Situation: Nachforschungen bei meinen Ahnen hat ergeben, dass ich ein großes Vermögen geerbt habe und dieser Schatz irgendwo vergraben liegt. Leider fehlte aber eine Angabe, wo er vergraben ist.

Der Teil der Mathematik, der sich nur mit den berechenbaren Funktionen beschäftigt, heißt konstruktive Mathematik. Da Computer im Prinzip Turing-Maschinen sind, können Computer sich nur mit den berechenbaren Funktionen beschäftigen. (Manchmal bestimmen sie berechenbare Näherungen zu nicht-berechenbaren Funktionen.) Wenn in der konstruktiven Mathematik eine Existenz von etwas behauptet wird, so heißt dies immer konstruktive Existenz, d.h. wenigstens im Prinzip ist das Ding z.B. die Funktion konstruierbar, indem etwa die entsprechende Turing-Maschine im Prinzip (d.h. vielleicht mit viel Mühe, aber mit hinreichend viel Aufwand) konstruierbar ist.

Falls mein Schatz irgendwo auf der Erde vergraben ist, existiert mein Schatz im konstruktiven Sinne, denn die Erdoberfläche ist ja endlich und ich könnte sie im Prinzip ja überall aufgraben. Heißt aber irgendwo nur irgendwo im Universum und ist das Universum unendlich ausgedehnt, dann existiert mein Schatz nicht im konstruktiven Sinne, oder jedenfalls nicht notwendigerweise. Ich könnte allerdings ja mal wahllos herumgraben, etwa geleitet durch rudimentäre Zeichnungen im genannten Testament. Wenn ich dann den Schatz zufällig finde, ist die Existenz nun doch auch konstruktiv gesichert.

Das bisherige war ein Plädoyer für die konstruktive Mathematik und in der Tat beschäftigen sich die Puristen unter den Mathematikern vorwiegend mit ihr. Die konstruktive Mathematik ist jedoch von vielen hässlichen Ausnahmen geplagt und kommt trotz vieler Mühen nicht sehr weit. Außerdem ist sie auch von sog. Paradoxien (= scheinbaren Widersprüchen) geplagt, wie etwa der obigen, dass der Begriff der Berechenbarkeit selbst gar nicht entscheidbar (= berechenbar) ist. Aus diesem Grunde benutzt das Gros der Mathematiker die sog. naiven Mengenlehre von Georg Cantor.
Die Cantor'sche Mengenlehre postuliert z.B. dass es zu je zwei Mengen die sog. Durchschnitts-Menge gibt (evtl. die leere Menge), d.h. die Teil-Menge, die in beiden Mengen enthalten ist. Dies ist jedoch i.A. keine konstruktive Existenz sondern nur eine axiomatische Existenz. (Auch mein Schatz existiert nur axiomatisch, d.h. aufgrund von verbalen Setzungen meiner Ahnen.)

In der Mathematik ist es erlaubt, beliebige Axiome zu postulieren und die naive Mengenlehre darauf anzuwenden. Dies ist solange ein erlaubter Teil der Mathematik bis jemand einen Widerspruch in diesem Axiomen-System aufgezeigt hat. Gewisse Axiomen-Systeme haben bis jetzt keinen Widerspruch erbracht, so dass man an deren Widerspruchsfreiheit glaubt, zumal wenn diese Systeme wichtige Anwendungen in der Realität haben. Dies gilt z.B. für die Axiome der Arithmetik. Die Arithemtik beschäftigt sich mit den ganzen Zahlen (integers, 0, 1, -1, 2, -2, 3, -3..., wobei wir gerade eine Aufzählung der integers gegeben haben) zusammen mit den Grundrechenarten (+, -, ., /). Dann ist es manchmal möglich, für andere Axiomen-Systeme (und dies gilt für den größten Teil der Mathematik), einen sog. relativen Widerspruchsfreiheitsbeweis zu führen.

Die formale Arithmetik besteht aus einem Alphabet. Je nach konkreter Ausgestaltung dieser formalen Arithmetik könnte das Alphabet etwa u.a. folgende Symbole enthalten:

(Dies ist keine vollständige Liste.)

Dann stehen in Bild 1_24b drei Formeln der formalen Arithmetik. Die erste lautet im Klartext: Für alle ganzen Zahlen n und m gibt es stets eine ganze Zahl p, für die gilt n+p=m.

Diese Zahl nennt man normalerweise p=n-m. Diese erste Aussag ist wahr.

Bild 1_24b: Eine wahre, eine falsche und eine syntaktisch inkorrekte (unsinnige) Aussage der Arithmetik

Die mittlere Aussage besagt, dass es immer die ganze Zahl p=m/n gibt. Diese Aussage ist falsch, z.B. für n=0, aber auch für m=1 und p=2, weil 1/2 keine ganze Zahl ist.

Die dritte Zeile ist syntaktisch-falsch, d.h. gar keine sinnvolle Aussage der Arithmetik oder der Logik.

In der üblichen (=Mengen-theoretischen) Arithmetik beginnt man mit einigen Axiomen, die man etwa in der obigen formalen Sprache formulieren kann und leitet daraus, wie aus der Schul-Mathematik bekannt, Sätze (Theoreme) her, die man wieder in der formalen Sprache schreiben kann.

(Dies ist allerdings nur im Prinzip möglich, denn meist würde es zu kompliziert und damit unverständlich, so dass man die natürliche Sprache bevorzugt.)

In der formalen Arithmetik benützt man nicht die natürliche Logik, sondern eine formale Logik, wobei einige logische Axiome dazukommen, aber vorallem einige Manipulationsregeln (auch Axiome genannt), wie man von wahren Ausssagen zu weiteren wahren Aussagen kommt, was das sonst übliche logische schließen ersetzt. (Damit ist auch sichergestellt, dass nur syntaktisch-korrekte Formeln zustande kommen.) Diese Manipulationen  können auch von einer Turing-Maschine übernommen werden, d.h. es können von ihr der Reihe nach alle herleitbaren und damit syntaktisch-korrekten und wahren arithmetischen Aussagen herauzusgespuckt (aufgezählt) werden.

In der üblichen Mathematik ist jede (syntaktisch-korrekte) Aussage entweder wahr oder falsch (= Satz vom ausgeschlossenen Dritten).
 

9. Gödel und die Unvollständigkeit der Arithmetik


Bild 1_24c: Kurt Goedel (1906-1978) im Alter von 52 Jahren am Institute for Advanced Study in Princeton, aus Scientific American: Gödel and the Limits of Logic, June 1999, p. 69

Gödel (1906-1978) hat 1931 folgenden spektakulären Satz bewiesen (in drei äquivalenten Formulierungen):

Die Arithmetik ist unentscheidbar.
Die Arithmetik ist unvollständig.
Die Arithmetik ist nicht axiomatisierbar.

ferner

Es ist nicht herleitbar, dass die Arithmetik widerspruchsfrei ist.

Die erste Formulierung besagt, dass es keine Turing-Maschine gibt, die von einer vorgelegten formalen arithmetischen Aussage entscheidet, ob sie wahr oder falsch ist.
Es gibt aber Turing-Maschinen, welche die trivialerer Entscheidung fällen können, ob die Formel syntaktisch korrekt ist oder nicht.

Die zweite Formulierung besagt: Jede Turing-Maschine, die nur arithmetisch wahre Aussagen ausspuckt, lässt mit Sicherheit einige arithmetisch wahre Aussagen aus. Insbesondere lässt sie die Aussage aus, dass die Arithmetik widerspruchsfrei ist.

Die Wahl des Alphabetes, der konkreten Axiome und der Manipulationsregeln ist in einem gewissen Grade frei. Wichtig ist nur, dass dies nur endlich viele sind (so dass die Aufzählung aller herleitbaren Formeln von einer Turing-Maschine übernommen werden kann) und ferner dass die uns bekannte Arithmetik herauskommt.

Dies setzt voraus, dass wir einen intuitiven Begriff der Arithmetik, d.h. von arithmetisch wahr und falsch haben, einer Arithmetik, die wir ständig und zwar vor aller Mathematik und aller Axiomen-Systeme überall, auch im täglichen Leben ununterbrochen benutzen.

Die dritte Formulierung sollte genauer heißen: nicht vollständig axiomatisierbar.
Es gibt ja schon Axiomensysteme, aus denen die meisten wichtigen wahren arithmetischen Aussagen herleitbar sind, aber eben nicht alle. Die Begriffe wahr und herleitbar fallen auseinander. Kein Computer kann die ganze Arithmetik ersetzen.

Anstatt Arithmetik, kann man in den obigen meta-mathematischen Sätzen auch Mengenlehre und auch Logik einfügen. Die Aussagen gelten ebenfalls. Auch von diesen Bereichen haben wir ein intuitives Wissen von wahr und falsch, was von keinem Computer vollständig übernommen werden kann. Die meisten mathematischen Theorien, z.B. die übliche Differential- und Integralrechnung, enthalten die Arithmetik als Teilgebiet. Dafür gelten die obigen Aussagen umso mehr.

Wenn eine spezielle mathematische Theorie sich als widersprüchlich erweist, d.h. mit einer einzigen Aussage auch ihr Gegenteil hergeleitet werden kann, so kann sofort jede Aussage (insbesondere auch ihr Gegenteil) in dieser mathematischen Theorie hergeleitet werden. Diese mathematische Theorie wäre zusammengebrochen und nicht mehr Gegenstand der Mathematik (außer der Aussage, dass diese Theorie widersprüchlich war).

Wenn das für die Arithmetik passieren sollte, so würde nicht nur die ganze Mathematik sondern die ganze rationale Wissenschaft zusammenbrechen. Insbesondere wären natürlich mit den obigen meta-mathematischen Aussagen auch ihr Gegenteil richtig.

Es ist nicht zu erwarten, dass dies passieren wird. Wie schnell man aber zu Paradoxien und Antinomien kommen kann, hat Bertrand Russel in der folgenden harmlos erscheinenen Definition demonstriert:

Der Dorfbarbier ist derjenige Mann im Dorf, der alle Männer des Dorfes rasiert, die sich nicht selbst rasieren.

Frage: Rasiert sich der Dorfbarbier selbst?

Falls ja, dann rasiert er sich nicht selbst. Falls nein, muss er sich selbst rasieren. Widerspruch!

Die obigen prägnanten Ergebnisse Gödels lauten etwas ausführlicher formuliert so: Jede Formalisierung (durch endlich viele Axiome und Manipulationsregeln, was dann von einer Turing-Maschine übernommen werden kann) einer mathematischen Theorie, welche die uns intuitiv vertraute Arithmetik enthält,  ist unvollständig d.h. gibt einige von uns intuitiv als richtig anerkannte Wahrheiten nicht wieder, insbesondere nicht die Wahrheit, dass die Arithmetik widerspruchsfrei ist. Ob eine vorgelegte arithmetische Aussage, auch wenn man sich auf solche Aussagen beschränkt, die durch die Syntax des betrachteten Formalismus ausdrückbar sind, läßt sich nicht von einem Computer allein entscheiden.

Bild 1_24d: Gödel (48) und Einstein (75, ein Jahr vor seinem Tode) bei ihren täglichen Spaziergängen in Princeton, aus Scientific American, June 1999, p. 73
Die Unterernährung Gödels ist sichtbar.

Gödel ist ohne Zweifel der größte Mathematiker auf dem Gebiete der mathematischen Logik. Obwohl seine Arbeiten Rationalität in höchster Form entwickelten, war er selbst von irrationalen Ängsten (Angst vergiftet zu werden) geplagt, welche zeitweise die Stärke einer Geisteskrankheit annahmen. Er war extrem schüchtern, liebte aber die Anwesenheit von Frauen und wirkte offensichtlich attraktiv auf sie. Als Student lernte er in einem Wiener Night Club die 6 Jahre ältere Tänzerin Adele kennen, die er später heiratete. Ihr ist es zu verdanken, dass Gödel seine bahnbrechenden Arbeiten überhaupt vollenden konnte, denn  sie konnte ihn immer wieder zum essen überreden. Insbesondere diente sie ihm als seine Vorkosterin.

Adele war als geschiedene Frau sowohl von ihren katholischen Eltern als auch von der damaligen Wiener Snob-Society ausgestossen. Außerdem hatte sie ein entstellendes Muttermal im Gesicht.

Statt zu essen, schluckte Gödel nur Tabletten gegen seine eingebildete Herzkrankheit. Infolge Unterernährung bekam er ein blutendes Magengeschwür, das er lange nicht behandelte, aus Misstrauen vor allen Ärzten.

Auch Einstein kümmerte sich um Gödel, der bei täglichen gemeinsamen Spaziergängen (siehe obiges Bild) beruhigend auf ihn wirkte. Dadurch entstand Gödels bedeutender Beitrag zur Allgemeinen Relativitätstheorie, indem er durch die Entdeckung des Gödel-Universum zeigte, dass Einsteins Gleichungen die Möglichkeit nicht ausschließen, dass Teilchen in ihre eigene Vergangenheit zurücklaufen. Falls ein Mann als Teilchen behandelt werden kann, wäre es somit möglich, dass ein gealteter Mann nochmals im Schoße seiner Mutter geboren wird. Jedenfalls schließen die Einsteinschen Gleichungen, diese Möglichkeit nicht aus.

Nachdem Adele einen Hirnschlag erlitten hatte (Gödel pflegte sie aufopferungsvoll) konnte sie sich nicht mehr um ihn kümmern. Gödel starb ein Jahr später im Alter von 72 Jahren an verhungern.

Unter allen großen Mathematikern war Gödel derjenige (außer Riemann), der am wenigsten publiziert hatte.
 

10. von-Neumann-Maschinen


Nach diesem Ausflug in die Meta-Mathematik und in die mathematische Logik, kehren wir zur Geschichte des Computers zurück. Als nächstes erwähnen wir John von Neumann (1903-1957). Der im Bild gezeigte Computer war ein Meilenstein.

Bild 1_25: John v. Neumann mit einem Radio-Röhren-Rechner, aus Williams, p.358

Er benutzte keine Relais mehr, sondern die viel schnelleren Radio-Röhren (CRT = cathode ray tubes). Röhren werden heute beim Computerbau nur noch für die Bildschirm-Röhre benutzt.

John von Neumann hat auch wichtige Arbeiten zu den mathematischen Grundlagen der Quantenmechanik verfasst.
Er war auch wesentlich am amerikanischen Atombomben-Projekt beteiligt.

Wir erwähnen ihn hier jedoch nur wegen der sog. 5 von Neumannschen Prinzipien des Computer-Baues. Eines besagt, dass jeder Computer ein von Neumann-Rechner sein muss, d.h. aus CPU, Steuerwerk (=Leitwerk), Speicher (= memory), Ein-Ausgabe-Einheit und Bus bestehen muss.

Allerdings hatte dies Zuse schon viel früher erkannt. Da aber Zuse durch den Krieg isoliert war, wird diese Erkenntnis dem John von Neumann zugeschrieben und ist so in den Sprachgebrauch übergegangen.

Nach der Entdeckung des Transistors erfolgte die Computer-Entwicklung rasant, wenn auch ohne viele (bekannte) geschichtlichen Anekdoten.

Wir erwähnen den Begriff eines Computer z.B. der dritten Generation. Er hätte nicht entwickelt werden können, ohne dass Computer der früheren Generation bereits zur Verfügung standen, am Anfang die mechanische Rechenmaschine.

Ein Meilenstein war die IBM360, der jahrzehntelang das Zugpferd für den Erfolg von IBM und auch für die meisten Computer-Anwendungen war. IBM hat aber den Sprung auf den Zug der Personal Computer zwar versucht, aber im wesentlichen verfehlt.

Bild 1_26: Rechts das Zugpferd von IBM ab 1964, die IBM360, links eine Hollerith-Maschine aus dem Jahre 1900, aus Williams, p. 405

Hermann Hollerith hat aus Anlass der amerikanischen Volkszählung vom Jahre 1890 die Lochkarte und die entsprechenden Lese-Maschinen neu erfunden.
Obiges Bild zeigt nicht nur die Entwicklung der Computer in dieser Zeitspanne, sondern auch die Entwicklung der Mode.
1896 gründete er die Firma Tabulating Machine, die später in IBM (= International Business Machines) umbenannt wurde.

In älterem Sprachgebrauch ist Hollerith synomym mit (z.B. binär) codierter Information und Hollerith-Maschine synomym mit EDV-Maschine (EDV = elektronische Datenverarbeitung).

Damit soll die geschichtliche Entwicklung des Computers, die hier allerdings nicht vollständig, sondern eher pointenhaft dargestellt wurde, beendet werden.