Praktische Informatik 1

Kapitel 3: Rechenanlagen

Anmerkung: Dieses Kapitel wird zum Selbststudium und der Vollständigkeit halber zur Verfügung gestellt. Inhaltlich ist es durch die beiden Exkursionen, zum Deutschen Technikmuseum und zum Potsdamer Platz, abgedeckt.
Um Programme auszuführen, ist ein Prozessor erforderlich, der die einzelnen Schritte tätigt. Das kann ein Mensch oder eine Maschine (auf mechanischer, elektronischer oder biochemischer Basis) sein, oder sogar ein anderes Programm, welches eine Ausführungsmaschine nur simuliert.

3.1 Historische Entwicklung

Die Entwicklung und den Aufbau moderner Rechner begreift man besser, wenn man sich ihre historischen Wurzeln betrachtet.

• 
  1842 Charles Babbage / Ada Lovelace: „Die analytische Maschine“; Konzept einer programmierbaren mechanischen Rechenanlage zur Lösung von Differentialgleichungen. Dieser „erste Computer der Weltgeschichte“ wurde jedoch nie realisiert, da Kosten, Machbarkeit und Haltbarkeit nicht einschätzbar waren
  
• 
  1936: Alonzo Church (1903-1995): „lambda-Kalkül“, Begriff der berechenbaren Funktion
  
• 
  1936: Alan Turing: Computer als universelle Maschine; Äquivalenz von Programm und Daten („Turing-Maschine“)
  
• 
  1941 Konrad Zuse: Z3: vollautomatischer, programmierbarer, in binärer Gleitkommarechnung arbeitender Rechner mit Speicher und einer Zentralrecheneinheit aus Telefonrelais
  
• 
  1946 Johan von Neumann (EDVAC-Report): konkrete Vorschläge für Aufbau („von-Neumann-Computer“)
  

Programmierparadigmen:

• 
  Analytische Maschine: Rechnen als Durchführung arithmetischer Operationen
  
• 
  lambda-Kalkül, Lisp-Maschine: Rechnen als Termersetzung
  
• 
  Turing-Maschine (vgl. ThI): Rechnen als Schreiben von Zeichen auf ein Band
  
• 
  von Neumann: Rechnen als Modifikation von Wörtern im Speicher.
  

Die analytische Maschine

Babbage’s „analytische Maschine“ (http://www.henrykautz.org/Computers/index.htm) war das „Nachfolgemodell“ der „Differenzmaschine“ (1821-1833), die arithmetische Berechnungen durchführen können sollte, aber nie funktionierte. Zitat eines Zeitgenossen (L. F. Menabrea, *): “Mr. Babbage has devoted some years to the realization of a gigantic idea. He proposed to himself nothing less than the construction of a machine capable of executing not merely arithmetical calculations, but even all those of analysis, if their laws are known.” Historisches Vorbild waren mit so genannten Jaquard-Lochkarten „programmierbare“ Webstühle (mit bis zu 24000 Karten). Die Rechenmaschine sollte ein „Mill“ genanntes Rechenwerk, ein „Store“ genanntes Speicherwerk (1000 fünfzigstellige Zahlen), Lochkartenleser und -stanzer als Ein- und Ausgabe und einen Drucker als Ausgabe enthalten. Die Maschine sollte mit Dampf angetrieben und frei programmierbar sein. Ein Programm sollte drei Kartentypen enthalten:

• 
  Operationskarten
  enthalten mögliche Operationen: Addition, Subtraktion, Multiplikation und Division. Die Maschine hat einen Schalter für den auszuführenden Operationstyp, der in seiner Stellung bleibt bis er durch eine Operationskarte umgestellt wird.
  
• 
  Zahlenkarten
  enthalten numerische Konstanten und dienen als externer Speicher, damit nicht alle benötigten Zahlen im (teuren) Speicherwerk bereit gehalten werden müssen. Auf einer Zahlenkarte steht jeweils neben dem Wert auch die Nummer des Speichers, in welchen dieser Wert geschrieben werden soll. Zwischenergebnisse können von der Maschine auf Karten gestanzt und später wieder eingelesen werden.
  
• 
  Variablenkarten
  steuern den Transfer von Werten aus dem Store zur Mill und zurück („Adressierung“). Die Maschine besitzt zwei Operandenregister („Ingress-Achsen“, je zweimal 50 Stellen: I₁ und I₁´, I₂ und I₂´) und ein Resultatregister („Egress-Achse“, zweimal 50 Stellen: E und E´); es gibt Karten zum Transport einer Variable (eines Speicherwerts) in die Ingress-Achsen und zum Transport der Egress-Achse in den Speicher.
  

Spezielle Karten sind kombinatorische und Indexkarten, die im Kartenstapel vor- und zurückblättern können und somit Sprünge realisieren. Für Verzweigungen gibt es einen „Alarmhebel“, der hochgesetzt wird, falls

• 
  bei einer arithmetischen Operation ein Überlauf oder eine Division durch Null auftritt
  
• 
  das Ergebnis einer arithmetischen Operation ein anderes Vorzeichen hat als das erste Argument (d.h. Egress-Achse E hat ein anderes Vorzeichen als die Ingress-Achse I₁ )
  

Ferner gibt es Kontrollkarten wie „Stopp“ und „Pause“.

Aus den vorhandenen Dokumenten lässt sich rekonstruieren, dass für die analytischen Maschine folgende Befehle vorgesehen waren (Ausschnitt):

::= {Karte}

::= | |

::= “N”[z _ [“+|“-][z

Die Zahl wird an der bezeichneten Stelle in den Speicher eingetragen

::= “+” | “-” | “*” | “/”

Die Operation wird für nachfolgende Befehle eingestellt

::= | |

::= (“L”|“Z”|“S”)[z[“´”]

Lzzz: Transfer des Inhalts der Variable zzz in die Mill Ingress Achse

Zzzz: Wie Lzzz, wobei Variable zzz gleichzeitig auf Null gesetzt wird

Szzz: Transfer der Egress-Achse in Variable zzz

Falls ein ´ nach der Adresse steht, sind die zweiten 50 Stellen betroffen

Transfer in I₂ löst die Ausführung der eingestellten Operation aus

::= “C”(“F”|“B”)(“+”|“?”)[z

blättert die angegebene Zahl von Karten vor (F) oder zurück (B)

+ bedeutes unbedingtes, ? bedingtes Blättern (falls Alarmhebel hochgesetzt)

::= “B” | “H” | “P”

B läutet eine Glocke um den Operateur zu verständigen

H hält die Maschine an (keine weiteren Karten werden gelesen)

P druckt den Wert der Egress-Achse auf dem Druckapparat
Beispiel: drucke 17 + 4

N001 +00000000000000000000000000000000000000000000000017

N002 +00000000000000000000000000000000000000000000000004

+

L001

L002

P

Beispiel: Variable in Speicher 003 := 10000 div 28, Variable 004 := 10000 mod 28,

N1 10000

N2 28

/

L1

L2

S3'

S4
Beispiel: Fakultätsfunktion S2 := S1!

N1 6

N2 1

N3 1

*

L2

L1

S2

-

L1

L3

S1

L3

L1

CB?11

Beispiel: drucke Tabelle für f(x) = x² + 6x + 6, x=1..10

V1 = x

V2 = x²

V3 = 6

V4 = x², x²+6x, x²+6x+6

V5 = 6x
N1 10

N3 6

*

L1

L1

S4

L1

L3

S5

+

L4

L5

S4

L4

L3

S4

…

Umformung als f(x) = (x+3)² – 3 bringt eine Verbesserung:

V1 = x

V2 = 3

V3 = x+3, (x+3)², (x+3)² – 3
N1 10

N2 3

+

L1

L2

S3

*

L3

L3

S3

-

L3

L2

S3

Ada Lovelace schlägt etliche solcher Verbesserungs-Transformationen vor.

Ähnliche (einfachere) Optimierungen heute im Code-Generator guter Compiler enthalten.

Ada Lovelace schreibt: “the Analytical Engine does not occupy common ground with mere `calculating machines´”… “on the contrary, (it) is not merely adapted for tabulating the results of one particular function and of no other, but for developing and tabulating any function whatever. In fact the engine may be described as being the material expression of any indefinite function of any degree of generality and complexity.“ …

“It may be desirable to explain, that by the word operation, we mean any process which alters the mutual relation of two or more things, be this relation of what kind it may. This is the most general definition, and would include all subjects in the universe.” …

“Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.“ …

Gedanken zur Universalität mathematischer Funktionen

Die Turingmaschine

Nahezu 100 Jahre später (1936) untersuchte Alan Turing die Grenzen des Berechenbaren. Die Arbeit „On Computable Numbers, with an Application to the Entscheidungsproblem“ kann als der Beginn der modernen Informatik betrachtet werden. Turing definierte darin eine hypothetische Maschine, die die „Essenz des Rechnens“ durchführen können soll. Eine „berechenbare“ reelle Zahl ist eine, deren (unendliche Folge von) Nachkommastellen endliche Mittel (d.h. durch einen Algorithmus) berechnet werden kann. Turing schreibt:

„Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent. …

The behaviour of the computer at any moment is determined by the symbols which he is observing, and his "state of mind" at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be "arbitrarily close" and will be confused.“

Eine Turingmaschine ist also gegeben durch

• 
  einen endlichen Automaten zur Programmkontrolle, und
  
• 
  ein (potentiell unbegrenztes) Band auf dem die Maschine Zeichen über einem gegebenen Alphabet notieren kann.
  

Zu jedem Zeitpunkt kann die Maschine genau eines der Felder des Bandes lesen (abtasten, „scannen“), und, ggf.. abhängig von der Inschrift dieses Feldes, das Feld neu beschreiben, zum linken oder rechten Nachbarfeld übergehen, und einen neuen Zustand einstellen.

Hier ist eine Syntax, die Turings Originalschreibweise nahe kommt.

::= {}

::=

::=

::=

::= {R | L | P}
Dabei wird angenommen, dass für jeden Zustand und jedes Abtastzeichen des Alphabets genau eine Zeile der Tabelle existiert, welche Operation und Nachfolgezustand festlegt. (Turing nennt solche Maschinen “automatisch”, wir nennen sie heute “deterministisch”. In Turings Worten: „If at any stage the motion of a machine is completely determined by the configuration, we shall call the machine an ‚automatic machine’ ... For some purposes we might use machines (choice machines or c-machimes) whose motion is only partially determined by the configuration… When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator… In this paper I deal only with automatic machines.’’)

Da die Tabellen für deterministische Turingmaschinen oft sehr groß werden, darf man Zeilen, die nicht benötigte werden, weglassen, und Zeilen, die sich nur durch das Abtastzeichen unterscheiden, zusammenfassen. In der entsprechenden Zeile sind beliebige Mengen von Abtastzeichen zugelassen. „any“ steht dann für ein beliebiges Abtastzeichen, d.h. für das gesamte Alphabet. Ferner fordert Turing, dass das Alphabet immer ein spezielles Leerzeichen „none“ enthält, und „E“ eine Abkürzung für „P none“ ist..

Beispiel für eine Maschine, die das Muster „0 11 0 11 0 11…“ auf ein leeres Band schreibt:
s0 any P0,R,R s1

s1 any P1,R,P1,R,R s0

Ein äquivalentes Programm mit nur einem Zustand s0 ist
s0 none P0 s0

s0 0 R,R,P1,R,P1 s0

s0 1 R,R,P0 s0
Beispiel für eine Maschine, die die Sequenz 0 01 011 0111 01111 … erzeugt:

Arbeitsweise dieser Maschine:

Die von Turing verwendete Tabellenschreibweise für Programme betrachten wir heute als unleserlich. Eine moderne Variante („Turing-Assembler“) wäre etwa:

::= {}

::= “:” | “print” “;” |
“left;” | “right;” | “goto” “;”

::=

In dieser Notation sähe unser Beispielprogramm etwa so aus:

label0:

print 0;

right;

right;

print 1;

right;

print 1;

right;

right;

goto s0;

Im Internet sind viele Turingmaschinen-Simulatoren verfügbar, versuchen Sie z.B. http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html

Andere empfohlene Beispiele:

http://www.matheprisma.uni-wuppertal.de/Module/Turing/

http://ais.informatik.uni-freiburg.de/turing-applet/turing/TuringMachineHtml.html

Zuse Z3

erster voll funktionsfähiger programmierbarer Digitalrechner

viele Merkmale moderner Rechner:

• 
  Relais-Gleitkommaarithmetikeinheit für Arithmetik
  
• 
  einem Relais-Speicher aus 64 Wörtern, je 22 bit
  
• 
  einem Lochstreifenleser für Programme auf Filmstreifen
  
• 
  eine Tastatur mit Lampenfeld für Ein- und Ausgabe von Zahlen und der manuellen Steuerung von Berechnungen.
  
• 
  Taktung durch Elektromotor, der Taktwalze antreibt (5rps)
  

Programmiersprache: Plankalkül

http://www.zib.de/zuse/Inhalt/Programme/Plankalkuel/Compiler/plankalk.html

Von-Neumann-Rechner, EDVAC & ENIAC

John von Neumann wurde vor hundert Jahren (im Dezember 1903) in Budapest geboren. 1929 wurde er als jüngster Privatdozent in der Geschichte der Berliner Universität habilitiert. Von Neumann wurde binnen kurzer Zeit weltberühmt durch seine vielfältigen Interessen auf dem Gebieten Mathematik, Physik und Ökonomie. 1930 emigrierte er wegen der Nazis nach USA. In Princeton schuf von Neumann dann mit dem von ihm erdachten Rechnerkonzept die Grundlagen für den Aufbau elektronischer Rechenanlagen, die noch bis heute gültig sind. Er gilt daher als einer der Begründer der Informatik

EDVAC, ENIAC (Electronic Numerical Integrator and Computer)

• 
  Elektronenröhren zur Repräsentation von Zahlen
  
• 
  elektrische Pulse für deren Übertragung
  
• 
  Dezimalsystem
  
• 
  Anwendung: H-Bomben-Entwicklung
  
• 
  Programmierung durch Kabel und Drehschalter