Kapitel 1

Computermodelle

Der Beginn der modernen Informatik in den Jahren unmittelbar nach dem Zweiten Weltkrieg war nicht nur durch praktischen Einfallsreichtum bei der Konstruktion der ersten Rechenmaschinen gekennzeichnet, sondern auch durch die Schaffung solider theoretischer Grundlagen, die die Entwicklung der Disziplin für die kommenden Jahrzehnte leiten sollten. In diesem Kapitel werden wir einige der einflussreichsten Computermodelle untersuchen, die den Grundstein für das Verständnis und den Aufbau von Computersystemen gelegt haben.

1.1 Die Turingmaschine:
Definition der Grenzen der Berechnung

Im Jahr 1936, lange vor der Konstruktion der ersten elektronischen Computer, veröffentlichte der britische Mathematiker Alan Turing einen wegweisenden Artikel mit dem Titel „On Computable Numbers, with an Application to the Entscheidungsproblem“. In dieser Arbeit schlug Turing ein abstraktes Modell eines Computers vor, das heute allgemein als Turing-Maschine bekannt ist. Hierbei handelte es sich nicht um eine physikalische Maschine im herkömmlichen Sinne, sondern vielmehr um ein theoretisches Konstrukt, ein Gedankenexperiment zur Beantwortung einer grundlegenden und zutiefst philosophischen Frage: Welche Probleme können durch einen algorithmischen Prozess, also durch eine endliche Folge eindeutiger Anweisungen, gelöst werden?

Eine Turingmaschine besteht konzeptionell aus:

Ein unendliches Band: Stellen Sie sich ein unbegrenztes Band in beide Richtungen vor, unterteilt in zusammenhängende Zellen.

Jede Zelle kann ein einzelnes Symbol aus einem endlichen Alphabet enthalten, das mindestens ein spezielles Symbol enthält, um eine leere Zelle anzuzeigen (häufig mit „B“ oder „□“ bezeichnet).

Ein Kopf: Ein Mechanismus, der sich auf einer bestimmten Zelle des Bandes positionieren kann. Dieser Kopf hat die Fähigkeit, das in der aktuellen Zelle vorhandene Symbol zu lesen, ein neues Symbol in dieselbe Zelle zu schreiben und eine Position entlang des Bandes nach rechts oder links zu verschieben.
Eine endliche Menge von Zuständen: Die Maschine befindet sich jederzeit in einem bestimmten Zustand. Diese Menge von Zuständen ist endlich und umfasst einen Anfangszustand (von dem aus die Berechnung beginnt) und einen oder mehrere Endzustände (oder Akzeptanzzustände), die das Ende einer erfolgreichen Berechnung anzeigen.
Eine Übergangsfunktion: Das Herzstück der Turingmaschine ist ihre Übergangsfunktion. Diese Funktion, die als Tabelle oder Regelwerk dargestellt werden kann, bestimmt das Verhalten der Maschine in jedem Schritt. Basierend auf dem aktuellen Zustand der Maschine und dem vom Kopf gelesenen Symbol gibt die Übergangsfunktion eindeutig drei Aktionen an: Das Symbol, das in die aktuelle Zelle geschrieben werden soll (bei dem es sich um dasselbe gelesene Symbol handeln kann). Die Richtung, in die sich der Kopf bewegen soll (nach links, rechts oder, in einigen Definitionen, still bleiben). Der neue Zustand, in den die Maschine wechseln muss.
Das Symbol, das in die aktuelle Zelle geschrieben werden soll (das könnte das gleiche gelesene Symbol sein).
Die Richtung, in die sich der Kopf bewegen soll (nach links, rechts oder, in einigen Definitionen, still bleiben).
Der neue Zustand, in den die Maschine gehen muss.

Die konzeptionelle Bedeutung der Turingmaschine ist außergewöhnlich. Es lieferte eine präzise und strenge Formalisierung des intuitiven Konzepts des Algorithmus. Die Grundidee besteht darin, dass jeder Rechenprozess, der durch einen endlichen Satz eindeutiger Regeln beschrieben werden kann, von einer Turingmaschine simuliert werden kann.

Diese Vorstellung wird in der Church-Turing-These formalisiert, einem grundlegenden Prinzip (nicht mathematisch beweisbar, aber weithin akzeptiert), das besagt, dass jede Funktion, die von einem Menschen nach einem Satz mechanischer Regeln berechnet werden kann, von einer Turing-Maschine berechnet werden kann.

Die Turingmaschine lieferte nicht nur eine funktionierende Definition der Berechenbarkeit, sondern ermöglichte auch die Erforschung der intrinsischen Grenzen der Berechnung. Beispielsweise verwendete Turing selbst sein Modell, um die Existenz unentscheidbarer Probleme zu demonstrieren, d. Ein symbolträchtiges Beispiel ist das Halteproblem : Ist es bei einem gegebenen Programm (oder einer Turing-Maschine) und seiner Eingabe möglich, zu bestimmen, ob das Programm seine Ausführung beendet oder unendlich weiterläuft? Turing hat bewiesen, dass es keinen allgemeinen Algorithmus zur Lösung dieses Problems gibt.

1.2 Das Von-Neumann-Modell:
Die Architektur moderner Computer

Während die Turingmaschine ein theoretisches Rechenmodell darstellte, lieferte die von John von Neumann in Zusammenarbeit mit anderen Pionieren wie John Presper Eckert und John William Mauchly vorgeschlagene Architektur den konzeptionellen Entwurf, auf dem die überwiegende Mehrheit der modernen Computer basiert. Diese Architektur, die erstmals 1945 in einem einflussreichen Bericht mit dem Titel „First Draft of a Report on the EDVAC“ beschrieben wurde, führt einige Grundprinzipien ein, die auch heute noch die Struktur unserer Computer bestimmen:

Zentraleinheit (CPU): Das „Gehirn“ des Computers, verantwortlich für die Ausführung von Anweisungen. Die CPU ist weiter unterteilt in: Steuereinheit (CU): Ruft Anweisungen aus dem Speicher ab, dekodiert sie und generiert die Steuersignale, die zur Koordinierung der anderen Komponenten des Systems erforderlich sind. Arithmetisch-logische Einheit (ALU): Führt arithmetische (Addition, Subtraktion, Multiplikation, Division) und logische (AND, OR, NOT) Operationen an Daten durch.
Steuereinheit (CU): Ruft Anweisungen aus dem Speicher ab, dekodiert sie und generiert die Steuersignale, die zur Koordinierung der anderen Komponenten des Systems erforderlich sind.
Arithmetisch-logische Einheit (ALU): Führt arithmetische (Addition, Subtraktion, Multiplikation, Division) und logische (AND, OR, NOT) Operationen an Daten durch.
Speicher: Wird zum Speichern sowohl der zu verarbeitenden Daten als auch der Programmanweisungen verwendet. Dieser Speicher ist konzeptionell als eine Folge von Orten organisiert, die jeweils durch eine eindeutige Adresse identifiziert werden. Der Speicher ermöglicht den direkten Zugriff auf jeden Ort in relativ konstanter Zeit (Random Access Memory oder RAM).
Eingabe-/Ausgabegeräte (E/A): Ermöglichen dem Computer die Interaktion mit der Außenwelt. Eingabegeräte ermöglichen die Eingabe von Daten und Befehlen in den Computer (z. B. Tastatur, Maus), während Ausgabegeräte die Anzeige oder Übertragung der Verarbeitungsergebnisse ermöglichen (z. B. Monitor, Drucker).
Bus: Ein System von Leitern (Drähte oder Leiterbahnen auf einer Leiterplatte), das als Kommunikationsweg zwischen den verschiedenen Komponenten des Systems dient. Normalerweise gibt es drei Haupttypen von Bussen: Datenbus: Transportiert Daten zwischen CPU, Speicher und E/A-Geräten. Adressbus: Gibt die Speicher- oder E/A-Geräteadresse an, auf die zugegriffen wird. Steuerbus: Überträgt Steuersignale, die Vorgänge zwischen verschiedenen Komponenten koordinieren.
Datenbus: Transportiert Daten zwischen CPU, Speicher und E/A-Geräten.
Adressbus: Gibt die Speicher- oder E/A-Geräteadresse an, auf die zugegriffen wird.
Steuerbus: Überträgt Steuersignale, die Vorgänge zwischen den verschiedenen Komponenten koordinieren.

Ein grundlegendes konzeptionelles Element der von Neumann-Architektur ist das Konzept des gespeicherten Programms . Dies bedeutet, dass sowohl die Programmanweisungen als auch die Daten, auf denen sie basieren, im selben Speicher gespeichert sind. Diese scheinbar einfache Idee stellte eine entscheidende Abkehr von frühen Computern dar, bei denen Anweisungen oft direkt in die Hardware integriert oder auf separaten Medien gespeichert waren.

Das gespeicherte Programm bietet enorme Flexibilität, da es Ihnen ermöglicht, das Verhalten des Computers zu ändern, indem Sie einfach ein neues Programm in den Speicher laden. Außerdem können Sie Anweisungen als Daten behandeln und so den Weg für fortgeschrittene Techniken wie das Ändern von Code zur Laufzeit ebnen.

Obwohl von Neumanns Architektur unglaublich einflussreich war und den meisten Computern zugrunde liegt, die wir heute verwenden, weist sie auch einige inhärente Einschränkungen auf. Am bekanntesten ist der von Neumann-Engpass . Da sowohl Daten als auch Anweisungen denselben Speicherbus durchlaufen müssen, kann die Ausführungsgeschwindigkeit des Prozessors dadurch begrenzt werden, wie schnell Daten und Anweisungen aus dem Speicher abgerufen werden können. Um diese Einschränkung zu überwinden, wurden verschiedene Techniken entwickelt, beispielsweise die Verwendung von Cache-Speichern und alternativen Architekturen. Eine bedeutende alternative Architektur ist die Harvard-Architektur , die in einigen spezialisierten Systemen wie digitalen Signalprozessoren (DSPs) verwendet wird und den Befehlsspeicher physisch vom Datenspeicher trennt, sodass auf beide gleichzeitig zugegriffen werden kann.

1.3 Shannons Informationstheorie:
Messung der Unsicherheit

Gleichzeitig mit der Entwicklung der ersten Computer und der Formalisierung von Rechenmodellen lieferte Claude Shannons bahnbrechende Arbeit zur Informationstheorie , die 1948 in seinem wegweisenden Artikel „A Mathematical Theory of Communication“ veröffentlicht wurde, einen strengen theoretischen Rahmen für die Quantifizierung und das Verständnis des Informationskonzepts. Diese Arbeit hatte tiefgreifende Auswirkungen nicht nur auf die Informatik, sondern auch auf die Telekommunikationstechnik und viele andere Bereiche.

Shannon definierte Informationen im Hinblick auf die Reduzierung der Unsicherheit. Mit anderen Worten: Die in einer Nachricht enthaltenen Informationen sind proportional zur Überraschung, die sie hervorruft. Je unerwarteter ein Ereignis oder eine Nachricht ist, desto mehr Informationen vermittelt sie. Um diese Idee zu quantifizieren, führte Shannon die grundlegende Informationseinheit ein: das Bit (Binärziffer). Ein Bit stellt die Informationsmenge dar, die erforderlich ist, um eine Unsicherheit zwischen zwei gleich wahrscheinlichen Alternativen aufzulösen (z. B. das Ergebnis eines Münzwurfs).

Mathematisch ist die Informationsmenge (H) eines Ereignisses mit der Eintrittswahrscheinlichkeit p definiert als:

H = -log₂(p)

Wobei der Logarithmus die Basis 2 ist, was die binäre Natur des Bits widerspiegelt.

Die Shannon-Informationstheorie lieferte die grundlegenden mathematischen Werkzeuge für:

Messung der Informationsmenge , die in einer Datenquelle oder Nachricht enthalten ist. Dadurch konnten wir die maximale Kapazität eines Kommunikationskanals definieren (das sogenannte Shannon-Hartley-Theorem).
Verständnis der theoretischen Grenzen der Datenkomprimierung . Die Shannon-Theorie legt eine Untergrenze für die Größe fest, auf die ein Datensatz ohne Informationsverlust (Entropie) komprimiert werden kann.
Entwerfen Sie zuverlässige Kommunikationssysteme , selbst bei Vorhandensein von Rauschen oder Störungen. Die aus Shannons Arbeit entwickelte Theorie der Fehlerkorrekturcodes ermöglicht das Hinzufügen von Redundanz zu übertragenen Daten, sodass durch den Kommunikationskanal verursachte Fehler erkannt und korrigiert werden können.

Das aus Shannons Theorie abgeleitete Konzept des Bits ist zur grundlegenden Einheit für die Darstellung und Manipulation von Informationen in Computersystemen geworden. Jedes Datenelement, jede Anweisung, jedes Bild oder jeder Ton in einem Computer wird letztendlich als Folge von Bits kodiert.

Die Computermodelle von Turing und von Neumann stellen zusammen mit Shannons Informationstheorie die theoretischen Säulen dar, auf denen das Gebiet der Informatik aufgebaut wurde und sich weiterentwickelt. Die Turingmaschine lieferte eine formale Definition der Berechenbarkeit und ermöglichte es uns, die Grenzen algorithmischer Berechnungen zu erkunden. Die von Neumann-Architektur bot ein praktisches und flexibles Design für die Herstellung elektronischer Computer, die jahrzehntelang die Branche dominierte.

Schließlich lieferte Shannons Informationstheorie einen mathematischen Rahmen für das Verständnis und die Verwaltung von Informationen, einem zentralen Element jedes Computersystems. Das Verständnis dieser grundlegenden Konzepte ist nicht nur für Informatikstudenten von entscheidender Bedeutung, sondern bietet auch einen tiefen Einblick in die intellektuellen Wurzeln dieser Disziplin, die unsere Welt weiterhin verändert.