1.1Vorbemerkungen
In den 1930er Jahren beginnen Konrad Zuse (Deutschland) sowie Howard Aiken, George Stibitz und John Atanasoff (USA) mit dem Bau digitaler Relais- und Röhrenrechner. Alan Turing (England) macht sich Gedanken zu einer universellen Turingmaschine. Brauchbare Geräte erscheinen ab den 1940er Jahren. Der Ausdruck „Computer“ im heutigen Sinn war noch nicht geläufig, Computer waren damals rechnende Menschen.
Wer hat nun was wann erfunden? Für die Nachwelt, besonders die Nutzerinnen und Nutzer, ist im Grunde entscheidend, dass eine wegweisende Erfindung gemacht wurde. Urheber und Zeitpunkt sind für sie weniger wichtig. Darüber gehen die Auffassungen ohnehin häufig auseinander. Für die Beteiligten sieht die Sache natürlich anders aus (Patentrecht). Noch heute werden die Begriffe „Computer“, „Turingmaschine“ und „Von-Neumann-Rechner“ unterschiedlich ausgelegt.
Es war ein langer Weg von den mechanischen zu den elektronischen Rechnern (vgl. Tab. 1.1).
Tab. 1.1: Vorläufer der Relais- und Röhrenrechner (Auswahl)
Anmerkungen
Der Rechenrahmen gilt nicht als Rechenmaschine. Die schickardsche Rechenuhr hatte getrennte Rechenwerke für die Addition und die Subtraktion bzw. die Multiplikation und die Division (nepersche Einmaleinswalzen). Du Bois Parmelee (USA) erhielt 1850 ein Patent für seine Tastenrechenmaschine. Victor Schilt (Schweiz) fertigte 1850 einen (erhaltenen) Nachbau des schwilguéschen Geräts an. Von Schwilgués Maschine sind neben Vorläufern zwei Exemplare (1844 und 1851) bekannt. Vor der Einführung der Maschinen mit Tastenantrieb hatten die Einstellwerke Schieber, Drehscheiben u. dgl.
Die beiden Maschinen von Schickard gingen verloren, von Leibniz ist nur ein (einziges) späteres Gerät bewahrt. Torchis Tastenmaschine ist nicht überliefert. Von der Pascaline sind noch mehrere Ausführungen vorhanden. Charles Babbage (England) hat weder seine Differenzen- noch seine analytische Maschine vollendet.
1.2Was ist ein Computer?
Die Ansichten der Fachleute über das Wesen des Computers gehen weit auseinander. Erwartungsgemäß gibt es viele unterschiedliche Umschreibungen. Hinzu kommt, dass sich der Inhalt des Begriffs „Computer“ im englischsprachigen Raum je nach dem Stand der technischen Entwicklung mehrfach verändert hat. Der Bedeutungswandel erstreckt sich vom rechnenden Menschen über analoge und digitale, mechanische und elektronische Rechenmaschinen zu programmgesteuerten und speicherprogrammierten Rechenautomaten. Von wenigen raumfüllenden Riesenrechnern (meist Einzelanfertigungen) ging es zu einer unübersehbaren Masse von leichten, tragbaren, allgegenwärtigen Vielzweckgeräten und zu einer unüberschaubaren Menge von verborgenen winzigen Spezialeinrichtungen, die in Dinge aller Art eingebaut sind.
Im deutschen, französischen, italienischen und spanischen Sprachraum waren Rechnerinnen und Rechner ursprünglich ebenfalls Menschen. Heute werden unter „Rechnern“ üblicherweise Maschinen verstanden. Die Wende setzte erst in der zweiten Hälfte des 20. Jahrhunderts ein. Lange Zeit unterschied man auch zwischen datenverarbeitenden und technisch-wissenschaftlichen Rechenanlagen. Die Datenverarbeitung spielte beispielsweise in der Statistik und der Buchhaltung eine erhebliche Rolle. In den frühen angelsächsischen Schriften finden sich neben „computer“ auch Ausdrücke wie „computing machine“, „calculator“ und „calculating machine“. Der Gebrauch ist jedoch uneinheitlich.
Die Bezeichnung „Computer“ wird in dieser Arbeit in einem weiten Sinn verwendet. Darunter fallen bestimmte analoge sowie digitale, mechanische, elektromechanische und elektronische Rechner, Relais-, Röhren- wie auch Transistormaschinen, festprogrammierte, stecktafelgesteuerte, programmgesteuerte und speicherprogrammierte Geräte. Weil die Vielfalt dieser Rechenhilfsmittel groß ist, gibt es nicht nur einen einzigen, sondern mehrere Erfinder des Computers.
1.3Was ist eine Turingmaschine?
Im Folgenden finden Sie einige Gedanken zu der für Laien ziemlich schwer verständlichen Turingmaschine
1.3.1Aufbau der Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell einer (idealisierten, universellen) Rechenmaschine. Die Turingmaschine ist ein Gedankenmodell, keine echte Maschine. Alan Turing hat sie in seiner 1936 eingereichten wegweisenden Abhandlung „On computable numbers, with an application to the Entscheidungsproblem“ vorgestellt. Sie gleicht einem Tonbandgerät. Das Grundmodell besteht aus folgenden Bestandteilen:
–Steuerwerk (Steuereinheit, Schaltwerk),
–Lese-Schreib-Kopf,
–beidseitig unendliches Speicherband.
Das unendlich lange Band ist in Felder (Zellen) eingeteilt. Jede Speicherzelle kann ein (einziges) Zeichen (aus einem Alfabet mit endlich vielen Zeichen) aufnehmen oder leer sein. In einem Feld kann z.B die Zahl 0 oder 1 stehen. Das „Alfabet“ (Zeichenvorrat) umfasst nicht nur Buchstaben, sondern auch Ziffern.
Ist die Turingmaschine ein Automat? Darüber gehen die Ansichten auseinander. Die Antwort hängt wie stets von der zugrunde liegenden Begriffsbestimmung ab.
1936 waren Rechner Menschen
„Turing’s achievement was to determine not what machines could compute, but what human beings could compute with enough resources of time and space for the computation.“ (siehe Robert Irving Soare: Turing computability, Springer-Verlag, Berlin, Heidelberg 2016, Seite 238).
Auf Deutsch: Turings Meisterleistung bestand darin zu bestimmen, was Menschen mit ausreichend Zeit und Platz berechnen konnten und nicht, was Maschinen zu berechnen imstande waren.
1.3.2Programmablauf
Das Steuerprogramm (Zustandsänderungstabelle) bestimmt die Handlungen (Lesen, Schreiben, Bewegen, Zustandsänderung) der Turingmaschine. Sie hängen vom jeweiligen Zustand der Maschine und vom Inhalt der Zelle ab. Das Programm legt dabei für jeden Zustand fest, welcher Buchstabe welchen Vorgang auslöst. Nach jeder Handlung kann sich der Zustand der Maschine ändern. Der Lese-Schreib-Kopf liest oder beschreibt jeweils das Feld (Arbeitsfeld, Arbeitszelle), das sich zu diesem Zeitpunkt unter ihm befindet. Er kann den Zellinhalt überschreiben oder unverändert lassen. Das Speicherband (Arbeitsband) lässt sich um ein Feld nach rechts oder links verschieben. Die Steuereinheit kann eine endliche Zahl von Zuständen einnehmen.
Jede Turingmaschine entspricht einer bestimmten Rechenvorschrift (Algorithmus). Diese ist dann berechenbar, wenn die zugehörige Turingmaschine nach endlich vielen Schritten anhält.
Dank der Turingmaschine lassen sich grundlegende Erkenntnisse über die Fähigkeiten von Rechenmaschinen (Berechenbarkeit, Entscheidbarkeit) gewinnen. Der Amerikaner Emil Leon Post hat 1936 ein gleichwertiges mathematisches Modell erarbeitet, auch Alonzo Church (USA) hat eine vergleichbare Untersuchung durchgeführt. Posts (gedankliche) universelle Maschine hat sich aber nicht durchgesetzt.
1.3.3Bedeutung für die theoretische Informatik
Der Turingmaschine kommt in der theoretischen Informatik eine grundlegende Bedeutung zu. Ihr Schöpfer hat gezeigt, dass es Aufgabenstellungen gibt, die mit Rechenverfahren (Algorithmen) nicht lösbar, d.h. nicht entscheidbar sind. Als Beispiele werden das hilbertsche Entscheidungsproblem (Untersuchung, ob eine Formel der Prädikatenlogik allgemein gültig ist) und das Halteproblem (Frage, ob die Ausführung eines Algorithmus endlos lange verläuft, ob die Turingmaschine jemals zum Stillstand kommt) angeführt.
Alle Berechnungen, die auf einem derzeitigen Computer, z.B einem Von-Neumann-Rechner, durchführbar sind, können nach der Church-Turing-These auch auf der Turingmaschine ausgeführt werden. Es handelt sich hier um eine durch die Erfahrung bestätigte Annahme. Sämtliche bisher bekannten sinnvollen Berechnungsmodelle und Rechner sind gleich mächtig wie die Turingmaschine. Diese kann einen Von-Neumann-Rechner nachahmen (simulieren). Eine Aufgabe lässt sich genau dann berechnen, wenn sie sich durch eine Turingmaschine bewältigen lässt. Eine Datenverarbeitungsanlage gilt als turingmächtig (turingvollständig), wenn sie universell (d.h. frei) programmierbar ist.
Die Turingmaschine ist Gegenstand der Berechenbarkeitstheorie (Welche Probleme lassen sich grundsätzlich algorithmisch lösen? Welche Funktionen lassen sich automatisch berechnen?) und der Komplexitätstheorie (Wie hoch sind der Aufwand an Rechenzeit und der Speicherbedarf, um eine Fragestellung zu lösen? Ist die Aufgabe mit vertretbarem Aufwand praktisch lösbar?).
Die Turingmaschine ist überdies bedeutsam für die Automatentheorie (Wie verhält sich die abstrakte Maschine, wie ist das mathematische Modell aufgebaut?) und die Theorie der formalen Sprachen (z.B Programmiersprachen). Sie eignet sich für das Beweisen von Behauptungen algorithmischer Art.
1.3.4Algorithmus
Ein Grundbegriff der Informatik ist der Algorithmus. Ein Algorithmus lässt sich etwa so umschreiben:
–Anleitung zur Lösung einer Aufgabe; Verfahren zur Lösung eines Problems; Lösungsverfahren; Verarbeitungsvorschrift; Verfahrensregel; Rechenvorschrift; Rechenverfahren;
–endliche Folge von allgemein(gültig)en, eindeutigen, ausführbaren Anweisungen (Arbeitsschritten).
Der Fachbegriff ist nach dem persischen Mathematiker Muhammad Ibn Musa Al Chwarismi, Verfasser eines Werks über Rechenregeln (etwa 780 bis 850 n.Chr.) benannt.
Beispiele aus dem Alltag sind Kochrezept, Bastelanleitung, Spielregeln, Gebrauchsanweisung, Partitur, Schnittmuster.
Babylonische und griechische Algorithmen
Die ersten bekannten schriftlichen Algorithmen wurden um 2000 v. Chr. im Zweistromland (Mesopotamien) geschaffen (siehe Donald E. Knuth; Luis Trabb Pardo: The early development of programming languages, in: Donald E. Knuth (Hg.): Selected papers on computer languages, Center for the study of language and information, Stanford 2003, Seite 4, sowie Donald E. Knuth: Ancient Babylonian algorithms, in: Communications of the ACM, Band 15, 1972, Heft 7, Seiten 671–677, und Band 19, 1976, Heft 2, Seite 108).
Zu den klassischen Algorithmen gehören
–das sumerisch-babylonische Wurzelziehen (Verfahren zur Lösung quadratischer Gleichungen, Kodex Hammurapi (Rechtssammlung), um 1700 v. Chr.),
–der euklidische Algorithmus (Verfahren zur Ermittlung des größten gemeinsamen Teilers, Euklid von ...