Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

Einblicke in das Wesen maschineller Rechenvorgänge


09.03.1990 - 

Buchhaltungsprogramm spielt auch das "Spiel des Lebens"

Kommerzielle Computerspiele gibt es heute wie Sand am Meer. Daß man auch mit Programmen, die für "seriöse" Business-Anwendungen geschaffen wurden, durchaus sein Spielvergnügen haben und nebenbei einiges über das maschinelle Rechnen schlechthin lernen kann, ist wohl weniger bekannt. Der Wissenschaftsjournalist Brian Hayes hat sich in der Zeitschrift "Scientific American" mehrfach mit diesem Thema beschäftigt.

Praxisferne darf man den Erfindern moderner Computerspiele wirklich nicht vorwerfen: Sie bringen zwar den Anwender liebend gerne in Gott weiß welche unangenehmen Situationen - aber nur im Spiel. Taucht in der realen Bürowelt plötzlich der Chef auf, offerieren sie ihm großzügig Hilfe: Ein Druck auf die "Paniktaste" (Control P) genügt, und die Raumschiffe, Schachfiguren oder was auch immer verschwinden vom Bildschirm. Anstelle des Schlachtfelds präsentiert der PC jetzt eine weit weniger verdächtige Business-Grafik.

Überall werden Vorgänge simuliert

Reines Spielvergnügen oder seriöse Geschäftstätigkeit - damit sind die beiden Pole der Computeranwendung wohl ausgelotet. Natürlich ist der Raum dazwischen nicht leer. Er umfaßt den Einsatz von Computern in allen Bereichen von Wissenschaft und Kunst. Ein sehr wichtiges Gebiet ist die Simulation von Vorgängen in Natur und Gesellschaft. Sie kommt heute praktisch überall zum Einsatz: in der Grundlagenforschung, bei der Konstruktion technischer Geräte, in der Meteorologie etc.

Neben all den praxisbezogenen Anwendungen kann man den Computer aber auch dazu verwenden, das Wesen mechanischer Rechenvorgänge, also sozusagen sich selbst, zu untersuchen. Dazu sind nicht unbedingt spezielle Hilfsmittel nötig. Ganz alltägliches Handwerkszeug - zum Beispiel ein Tabellenkalkulations-Programm - kann zu sehr interessanten Erkenntnissen führen.

Normalerweise brauchen Buchhalter oder Betriebswirte solche Programme, um Zahlenlisten zu verrechnen. Im Prinzip ist das nichts anderes als eine elektronische Form des herkömmlichen Kalkulationsblattes, bei dem man jeder Firmenabteilung eine Spalte der Tabelle und jeder Art von Einnahme oder Ausgabe eine Zeile zuteilt. Werden die Zahlen in die entsprechenden Kästchen eingetragen und die nötigen Summen und Prozentwerte berechnet, erhält man - zum Beispiel - eine Bilanz des Betriebsergebnisses.

Das elektronische Kalkulationsblatt liefert die gleiche Art von Aufstellung auf dem Bildschirm - allerdings mit ein paar bemerkenswerten Unterschieden. Während ein Kästchen auf dem Papier eine bestimmte Zahl enthält, zum Beispiel den Jahresumsatz der Abteilung X, kann dem entsprechenden Kästchen in der Computertabelle auch eine Rechenvorschrift zugeordnet werden - summiere die Zahlen der Kästchen, welche die Monatsumsätze der Abteilung X enthalten. Auf dem Bildschirm erscheint dann an dieser Stelle stets das aktuelle Ergebnis. Der Vorteil liegt auf der Hand: Die Änderung irgendeines Eintrags in der elektronischen Tabelle bewirkt die Korrektur aller anderen damit zusammenhängenden Einträge. Bei der Papier- und-Bleistift-Methode kann die gleiche Änderung möglicherweise stundenlange Neukalkulationen nach sich ziehen.

Kein Wunder also, daß entsprechende Computerprogramme auf Anhieb sehr gefragt waren. Das erste kommerzielle Tabellenkalkulations-Programm, Visicalc, stammt vom Amerikaner Daniel Bricklin, der es 1978 während seines Studiums an der Harvard University School of Business entwarf. Visicalc war nach Ansicht von Fachleuten das Programm, das dem lange als "Spielzeug" apostrophierten Personal Computer endlich zum Durchbruch verhalf. Inzwischen gibt es Dutzende von ähnlichen Programmen - die bekanntesten heißen Multiplan und Lotus 1-2 3.

Das Interessante daran ist, daß sie zwar alle für das Rechnungswesen in kommerziellen Betrieben entwickelt wurden, aber, wie wir gleich sehen werden, auch noch ganz andere Aufgaben lösen können.

Rechnen ohne Algorithmus

Das elektronische Kalkulationsblatt besteht aus lauter Zellen, deren Werte einzeln oder gruppenweise miteinander verknüpft werden können. Die Zellen sind durch ihre Koordinaten (A, B, C . . . für die Spalten 1, 2, 3 . . . für die Zeilen) gekennzeichnet. Weist man beispielsweise den Zellen A1 und A2, also den beiden obersten Zeilen der ersten Spalte, je den Wert 1 zu und trägt in die Zelle A3 die Formel A1+A2 ein, so addiert das Programm die Inhalte von A1 und A2 und liefert für A3 die Zahl 2. Übernimmt man die gleiche Rechenvorschrift (addiere den Inhalt der beiden nächstoberen Zellen) für sämtliche Zellen der ersten Spalte, so erhält man die Zahlenfolge 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. . .

Es gibt auch bequemere Wege

Natürlich gibt es bequemere und auch viel effizientere Wege, um diese nach dem italienischen Mathematiker Fibonacci benannten Zahlen auf dem Computer zu berechnen. Trotzdem lohnt sich die Betrachtung dieser Methode, denn sie offenbart einen interessanten Vergleich der unterschiedlichen Rechenmethoden.

Die meisten Computerprogramme beruhen auf sogenannten Algorithmen. Ein Algorithmus ist eine Folge von Anweisungen, die der Rechner eine nach der andern ausführen muß - ähnlich wie ein Kochrezept: "Man nehme x und y, vermische es und füge nach zehn Minuten Garzeit z hinzu." Jede andere Reihenfolge ergäbe ein unterschiedliches Resultat. Die Tabellenkalkulation hingegen ist nicht algorithmisch - hier spielt der zeitliche Ablauf für den Anwender *) keine Rolle. In den einzelnen Zellen steht nicht eine Folge von Schritten, die vom Problem zur Lösung führt, sondern nur eine Zahl oder Formel. Die Rechenvorgänge in allen Zellen werden in einem Schritt ausgeführt, und das Ergebnis erscheint als Ganzes auf dem Bildschirm.

Damit soll keineswegs der Eindruck erweckt werden, die eine Methode sei besser als die andere. Jede hat ihre Vor- und Nachteile. Wenn eine Aufgabe sehr komplex wird, löst man sie vielleicht besser mit einem Algorithmus, da sich dieser leichter in übersichtliche Teile zerlegen läßt.

Die nicht-algorithmische Methode wiederum kann ihre Stärken nicht nur in der Buchhaltung ausspielen, sondern auch auf dem Gebiet der zellulären Automaten. Der etwas seltsame Begriff wurde in den frühen fünfziger Jahren von den beiden Computerpionieren John von Neumann und Stanislaw Ulam eingeführt. Sie beschäftigten sich damals mit künstlichen Welten, die aus einer Vielzahl von Zellen bestehen. Jede Zelle verkörpert einen Automaten, der eine bestimmte Anzahl von Zuständen annehmen kann. Der Zustand einer Zelle hängt von ihrer eigenen Vorgeschichte und von den Zuständen der direkten Nachbarzellen ab.

Interessant sind zum Beispiel gleichförmige Räume, wo alle Automaten den gleichen Gesetzen unterliegen und sich im Laufe der Zeit stets von neuem reproduzieren. Ein Tabellenkalkulations-Programm erlaubt die einfache Darstellung, indem beispielsweise nur die Zustände 0 und 1 zugelassen sind. Die Forderung nach gleichen Gesetzen für alle bedeutet nichts anderes, als daß jeder Zelle die gleiche Formel zugewiesen wird.

Muster, die sich selbst vermehren

Edward Fredkin vom Massachussetts Institute of Technology hat 1960 ein solches System entworfen. Der Raum ist eine Ebene aus lauter Zellen, welche die Zustände 0 und 1 annehmen können. Dies läßt sich so interpretieren, daß die entsprechende Zelle entweder tot oder lebendig ist. Der Zustand einer Zelle in der nächsten Generation hängt ab vom Zustand der Nachbarzellen der jetzigen Generation. Entscheidend sind dabei die vier Nachbarn, die sich unmittelbar oben, unten, links und rechts von einer Zelle befinden. Ist die Zahl lebender Nachbarn gerade (0, 2 oder 4), so stirbt die Zelle oder bleibt tot. Zellen mit einer ungeraden Zahl lebender Nachbarn ( 1 oder 3) bleiben oder werden lebendig.

Fredkins System läßt sich mit einem Tabellenkalkulations-Programm problemlos computerisieren. Toten Zellen wird der Wert 0 zugewiesen, lebenden der Wert 1. Die Formel für die Berechnung des Zustandes der nächsten Zellgeneration ist einfach: Sie addiert für jede Zelle die Werte der vier Nachbarzellen, teilt die Summe durch 2 und behält den Rest, der nur 0 oder 1 betragen kann.

Wer Fredkins System auf seinem PC aufbauen will, muß auf ein wichtiges Detail achten: Weil der Zustand jeder Zelle vom Zustand der Nachbarzellen der vorherigen Generation abhängt, müssen stets zwei Generationen des zellulären Geschehens im Speicher vorhanden sein.

Nachdem das Startmuster eingegeben ist, liefert jeder Rechenzyklus eine neue Struktur. Nach einigen Zyklen erscheinen dann vier Kopien des Ausgangsmusters (siehe Bild). Natürlich werden auch sie vervierfacht, so daß dann das Ausgangsmuster 16fach vorliegt. Wie viele Zyklen es für eine vollständige Reproduktion braucht, hängt von der Komplexität des Startmusters ab. Im einfachsten Fall einer einzigen lebenden Zelle erscheinen die vier Abkömmlinge bereits in der folgenden Generation.

Je nach Ausgangslage ist das Geschehen auf dem Bildschirm langweilig oder spannend. Manchmal entstehen sehr schöne sternförmige Gebilde. Jedenfalls bleibt die Vierer-Symmetrie stets erhalten, und das Wachstum findet in einem bestimmten Rhythmus statt: Die von lebenden Zellen bevölkerte Fläche dehnt sich stetig aus, während in ihrem Innern Zellen periodisch aufleben und wieder sterben.

Das bekannteste System zellulärer Automaten heißt "Spiel des Lebens". Es wurde von einem Mathematiker namens John Horton Conway erfunden. In diesem Spiel geht es nicht mehr um die sture Reproduktion eines Musters. Die Regeln sind im Gegenteil so angelegt, daß das Geschehen sehr abwechslungsreich ist und stets neue Überraschungen mit sich bringt .

Jede Zelle kann wieder zwei Zustände annehmen. Welcher jeweils zum Tragen kommt, hängt ab von ihrer eigenen Vergangenheit und von den Zuständen sämtlicher acht Nachbarzellen. Eine lebende Zelle überlebt in der nächsten Generation nur dann, wenn sie zwei oder drei lebende Nachbarn hat. Sind es weniger, stirbt sie an Vereinsamung, sind es mehr, stirbt sie an Übervölkerung. Tote Zellen können auferstehen, und zwar dann, wenn sie genau drei lebende Nachbarn haben.

Wollte man das Spiel des Lebens mit einem Algorithmus durchrechnen, wäre dieser voller Wiederholungen. Zelle für Zelle würde nacheinander herausgegriffen, die Zahl ihrer Nachbarn bestimmt und ihr Schicksal entschieden. Auch mit einem Tabellenkalkulations-Programm läßt sich das Spiel nicht ohne Wiederholungen programmieren - aber diese sind nicht zeitlich, sondern räumlich gestaffelt: In jeder Zelle des Kalkulationsblattes steht die gleiche Formel. Das Spiel zeigt eine verblüffende Vielfalt von Variationen.

* Die Bearbeitung des Textes erfolgte durch Felix Weber. Nachdruck der Grafik aus "Spektrum der Wissenschaft, Computer Kurzweil" II, 1988 mit freundlicher Genehmigung des Verlags.

Die Grenzen der künstlichen Welt auf dem Computer hängen ab von der Größe des Kalkulationsblattes, der Leistungsfähigkeit des Programms und der Geduld des Spielers. Die Zeit, die der Rechner zum Schaffen einer neuen Generation braucht, wächst ungefähr proportional zur Zahl der beteiligten Zellen.

Der ersten dieser Beschränkungen kann man allerdings ein Schnippchen schlagen, indem man die Zellen an gegenüberliegenden Rändern für benachbart erklärt. Werden die zwei Enden so verbunden, entsteht aus der endlichen Fläche ein Zylinder. Das Feld ist dann zwar immer noch endlich, aber wenigstens in einer Richtung unbegrenzt. Bringt man alle vier Kanten zusammen, erhält man eine Art Rettungsring. Mathematiker nennen diese in allen Richtungen unbegrenzte Fläche Torus.

Die meisten Tabellenkalkulations-Programme sind, verglichen mit anderer Software, relativ langsam. Dafür sind sie aber wie wir gesehen haben, sehr vielseitig. Man kann nicht nur Bilanzen erstellen und künstliche Welten kreieren, sondern jede Zahlenfolge erzeugen, deren Glieder sich durch Formeln beschreiben lassen. Eine einfache Formel, ein paar hundertmal wiederholt, taugt beispielsweise als Primzahlen-Sieb.

Interessant ist die Frage, wo denn die Grenzen des Verfahrens liegen. Läßt sich mit einer simplen Tabelle von Formeln alles berechnen, was überhaupt berechenbar ist? Das würde bedeuten, daß Tabellenkalkulations-Programme nicht nur vielseitig sind, sondern sogar universell anwendbar wären.

Zumindest für eine unendlich große Tabelle steht die Antwort fest: Sie lautet "Ja". John Horton Conway hat bewiesen, daß man mit seinem Spiel des Lebens und seiner zellulären Welt im Prinzip eine Turing-Maschine bauen könnte - einen universellen Computer, wie ihn der britische Mathematiker Alan Mathison Turing 1937 als Gedankenmodell entworfen hatte.

Leider hat die Sache einen entscheidenden Haken: Selbst wenn eine endliche Tabelle genügen würde, was bisher weder bewiesen noch widerlegt ist, wäre die schöne Theorie ohne jeden praktischen Wert, denn unser Leben ist viel zu kurz, als daß wir das Spiel des Lebens je zu Ende führen konnten. +