Jurgen Kraus
Universität Dortmund
Februar 1980
Download PDF (37.66Mb) (Du musst im Forum registriert sein)
Jürgen Kraus
Diplomarbeit
Abteilung Informatik
Universität Dortmund
Februar 1980
Hiermit, erkläre ich, daß ich diese Arbeit selbständig und ohne fremde Hilfe verfaßt und keine anderen als die angegeben Quellen und Hilfsmittel benutzt habe.


Alle in der vorliegenden Diplomarbeit vorkommenden Beispielprogramme wurden auf dem SIEMENS-Rechner, Typ 7738, der Abteilung Informatik an der Universität Dortmund gerechnet.
Die Erde, wie sie sich heute präsentiert, ist mit einer Fülle von Lebensformen ausgestattet. In vergangenen Zeitepochen hat es schon Leben gegeben. Zum Teil handelte es sich dabei um die gleichen Formen wie heute, zum Teil um ausgestorbene Arten. Die Biologie hat alle bekannten Lebensformen in ein einheitliches System gestellt. So unterschiedlich die einzelnen Lebensformen auch sind, so entsprechen sie doch einem gemeinsamen Prinzip: Jedes Lebewesen ist aus Zellen aufgebaut. Zellen, die Grundeinheiten des Lebens, sind höchst komplexe biochemische Apparate. Auf Grund der Abstammungslehre muß es irgendwann in der Erdgeschichte eine erste Zelle gegeben haben. Diese Zelle hat sich als Ergebnis der chemischen Evolution auf der Erde herangebildet und wurde zum Ausgangspunkt der biologischen Evolution. Die Frage, wie es zu den ersten Zellen auf der Erde und somit zu den ersten Lebensformen kommen konnte, läßt sich im großen und ganzen mit Hilfe von Experimenten und der Wahrscheinlichkeitsrechnung klären [13]. Das Ergebnis ist, daß Entwicklung und Existenz von Leben praktisch als Konsequenzen der Komplexität der Verhältnisse auf der Früherde anzusehen sind. Sieht man diese Auffassung als richtig an, so ist es durchaus denkbar, daß sich auch in anderen genügend komplexen "Welten" Leben 1) entwickeln kann oder diese "Welten" zumindest eine Existenzmöglichkeit für bestimmte Formen von Leben bieten.
Die Computertechnik hat in den letzten zwei Jahrzehnten gewaltige Fortschritte gemacht. Die Entwicklung immer neuerer und leistungsfähigerer elektronischer Bauelemente ermöglicht den Bau von digitalen Rechenanlagen, deren Kapazität noch vor wenigen Jahren Utopie gewesen wäre. Durch Zusammenschaltung mehrerer Rechenanlagen bis hin zu überregionalen Rechnernetzen [21] ist es möglich, die Kapazität weiter zu steigern. Dem Benutzer stehen somit Systeme zur Verfügung, die er kaum noch überblicken kann. So wird z.B. die Verwaltung von Rechnernetzen durch Hilfscomputer vorgenommen. Insgesamt gibt es also heute schon Rechenanlagen, die wie ein Universum - bestehend aus Schaltkreisen und Bits - wirken. Die Komplexität solcher Rechenanlagen erinnert durchaus an die Komplexität auf der Früherde, ist die Vorstellung richtig, daß die Entstehung bzw. die Existenz von Leben eine Folge der Komplexität ist, so wäre die spekulative Idee von Leben auf Computerebene zumindest denkbar. Bei der Vorstellung, wie ein solches Leben aussehen könnte, kann man sich nur am gegenwärtigen biologischen Leben orientieren, da es das einzig bekannte Leben überhaupt ist. Eingangs haben wir die Zelle als Grundelement des biologischen Lebens angeführt. Ohne Kapitel 7 vorgreifen zu wollen, seien hier die Fähigkeit zur identischen Reproduktion auf eigene Veranlassung (Autoreproduktion) und die Möglichkeit zur fehlerhaften Reproduktion (Mutation) als zwei ckarakteristische Eigenschaften lebender Zellen genannt. Im Hinblick auf diese beiden Eigenschaften scheinen sich auf Computerebene selbstreproduzierende Programme als brauchbares Analogon zu lebenden Zellen zu erweisen. Wir werden in 1.2. selbstreproduzierende Programme als Programme definieren, die in der Lage sind, ihren eigenen Programmtext während ihrer Laufzeit auszugeben, ohne daß ihnen dazu der "Bauplan" ihres Textes von außerhalb mitgeteilt werden muß. Da elektronische Rechenanlagen nicht hundertprozentig fehlerfrei arbeiten, ist die Möglichkeit einer fehlerhaften Ausgabe des Programmtextes, also einer Mutation, automatisch immer vorhanden. Selbstreproduzierende Programme kämen also als Träger von Leben auf Computerebene durchaus in Frage.
Hauptaufgabe dieser Arbeit ist es nicht nur, die Existenz selbstreproduzierender Programme zu beweisen (Kapitel 2), sondern konkrete Beispiele für selbstreproduzierende Programme in verschiedenen Programmiersprachen anzugeben (Kapitel 3 und 6) und deren Eigenschaften zu diskutieren (Kapitel 4 und 5). Reproduktion und Mutation sind Eigenschaften, die zur Evolution befähigen. Evolution tritt ein, wenn Selektion als zusätzliche Komponente mitwirkt. Evolution ist die Ursache für die unerhörte Artenfülle irdischen Lebens und müßte auch bei selbstreproduzierenden Programmen zu immer neuen Programmen mit verschiedensten Eigenschaften führen. Einige Modelle zur Evolution selbstreproduzierender Programme werden in den Kapiteln 8 und 9 erörtert. Zuvor wird jedoch in Kapitel 7 die Frage untersucht werden, inwieweit sich selbstreproduzierende Programme in der "Umwelt" Rechner wirklich mit lebenden Zellen vergleichen lassen.
Die vorliegende Arbeit handelt in erster Linie von Programmen und den. Programmiersprachen, denen diese angehören. Um präzise zu sein, müßte daher an dieser Stelle definiert werden, was unter einer Programmiersprache zu verstehen ist, wie Programme in einer jeweiligen konkreten Programmiersprache aufgebaut sind (Syntax) und wie ein konkretes Programm auf einer konkreten Rechenmaschine zu interpretieren ist (Semantik) (vgl. etwa [9] [14]). Derartige Definitionen würden sicher den Rahmen dieser Arbeit sprengen. In Kapitel 2 werden sie jedoch wenigstens ansatzweise für die abstrakte Programmiersprache PL durchgeführt. Bei konkreten Programmiersprachen wird bzgl. der Syntax auf die jeweiligen Arbeiten verwiesen, in denen die Syntax beschrieben ist. Im Hinblick auf die Semantik wird sich der Begriff der von einem Programm realisierten Funktion als ausreichend erweisen (vgl.(5.1.1)). Im übrigen setzt die Arbeit voraus, daß der Leser mit dem in der Informatik üblichen Sprachgebrauch bzgl. Programmen und Programmiersprachen vertraut ist. Konkrete Programmiersprachen lassen sich allgemein in höhere Programmiersprachen und in Assembler-Sprachen differenzieren. Im Hinblick auf Selbstreproduktion sind folgende Charakteristika wesentlich.
Programme werden im allgemeinen mit den von ihnen berechneten Funktionen identifiziert. Für die vorliegende Arbeit ist jedoch ein anderer Aspekt von Programmen ebenso wichtig:
Programme sind endliche Zeichenketten, also Texte.
Im Verlauf seiner Verarbeitung durch den Rechner liegt ein und dasselbe Programm als unterschiedlicher Text überverschiedenen Alphabeten vor. Ein Programm in Assembler-Sprache unterscheidet sich textuell von seiner Übersetzung in Maschinenkode. Während Assembler-Programme zunächst alphanumerische Texte darstellen, sind Programme in Maschinenkode nur aus den 16 Hexadezimalziffern 0 bis F aufgebaut. Ähnlich liegen die Verhältnisse bei höheren Programmiersprachen. Zwischen dem Quellprogramm in höherer Programmiersprache und dem Objektprogramm im Maschinenkode liegen unter Umständen jedoch noch ein oder mehrere Übergangsformen in irgendwelchen Zwischenkodes.
Gemäß den unterschiedlichen Charakterisierungen für höhere Programmiersprachen und Assembler-Sprachen weisen die Definitionen für selbstreproduzierende Programme in diesen beiden Sprachebenen Unterschiede auf.
Sei zunächst S eine höhere Programmiersprache im üblichen Sinn.
(1.2.1) Definition: Sei
ein (syntaktisch korrektes)
Programm aus S.
keine Eingabe auf, so heißt
(streng)
selbstreproduzierend, falls
(genau) seinen
Programmtext in S ausgibt.
Eingabe auf, so heißt
(streng)
selbstreproduzierend, falls
bei jeder
zulässigen Eingabe (genau) seinen Programmtext
in S ausgibt.Definition (1.2.1) schließt also selbstreproduzierende Programme mit Eingabe nicht grundsätzlich aus, verhindert jedoch, daß der Eingabe Informationen entnommen werden, die zur Selbstreproduktion benötigt werden; da die Selbstreproduktion bei jeder Eingabe erfolgt, erfolgt sie unabhängig von der Eingabe.
Sei nun M eine zu einer konkreten Rechenanlage gehörige Assemüer-Sprache. Die Definition für selbstreproduzierende Assembler-Programme spiegelt die Tatsache wider, daß Assembler-Programme ihren eigenen Maschinenkode lesen können.
(1.2.2) Definition: Sei
ein gültiges Programm aus der Assembler-Sprache M.
keine Eingabe auf, so heißt
(streng)
selbstreproduzierend, falls
(genau) seinen
Maschinenkode ausgibt oder innerhalb des Arbeitsspeichers kopiert.
Eingabe auf, so heißt
(streng)
selbstreproduzierend, falls
bei jeder Eingabe
(genau) seinen Maschinenkode ausgibt oder innerhalb des Arbeitsspeichers kopiert.Im Gegensatz zu höheren Programmiersprachen brauchen die Kopien selbstreproduzierender Assembler-Programme vor der Ausführung nicht in Maschinenkode übersetzt zu werden. Abb. 1.2.A zeigt die Unterschiede, die sich im Hinblick auf Selbstreproduktion zwischen höheren Programmiersprachen und Assembler-Sprachen ergeben, im Zusammenhang.
Aus der Tatsache, daß Assembler-Programme ihren eigenen Maschinenkode im Arbeitsspeicher lesen können, läßt sich bei einiger Kenntnis von Assembler-Sprachen leicht die Existenz selbstreproduzierender Assembler-Programme folgern. Auch die Angabe von Beispielen für seibstreproduzierende Assembler-Programme fällt nicht schwer (Abschnitt 3.4.). Anders liegen jedoch die Verhältnisse bei höheren Programmiersprachen. Hier ist die Existenz selbstreproduzierender Programme durchaus nicht intuitiv klar und muß daher in Kapitel 2 auf theoretischem Weg nachgewiesen werden. Auch die Angabe von realisierbaren Beispielen ist bedeutend schwieriger als bei Assembler-Sprachen. Ganz allgemein liegen im Hinblick auf Selbstreproduktion die Verhältnisse bei Assembler-Sprachen einfacher als bei höheren Programmiersprachen. Aus diesem Grund beschäftigen sich die Kapitel 3, 4 und 5 fast ausschließlich mit der Selbstreproduktion bei höheren Programmiersprachen.
| Höhere Programmier sprachen | Assembler-sprachen |
|---|---|
Programme können Arbeitsspeicher nicht lesen ![]() | Programme können Arbeitsspeicher und damit ihren eigenen Maschinenkode lesen![]() |
Selbstreproduktion Erzeugung des Quellprogramms in der höheren Programmiersprache![]() | Selbstreproduktion Erzeugung direkter Kopie des Maschinenkodes![]() |
| Übersetzung der Kopie erforderlich | Keine Übersetzung der Kopie erforderlich |
Abb. 1.2.A
In diesem Kapitel soll auf theoretischem Weg die Existenz selbstreproduzierender Programme in höheren Programmiersprachen nachgewiesen werden. Wir werden dabei nicht mit Hilfe von realen Programmiersprachen (PASCAL,SIMULA,ALGOL etc.) und deren vielen Eigenarten argumentieren. Statt dessen definieren wir, soweit das in diesem Rahmen möglich ist, eine eigene einfache Programmiersprache, die sich durch besonders einfache Datentypen und allgemein in höheren Programmiersprachen benutzte Konstruktionsprinzipien auszeichnet. Diese Programmiersprache wird PL heißen. Trotz ihrer Einfachheit wird PL die gleiche "Berechenkapazität" haben wie alle gängigen Programmiersprachen. PL wird sich als geeigneter Einstieg in die Theorie der "berechenbaren Funktionen" erweisen. Diese Theorie werden wir nur soweit verfolgen, wie es zum Nachweis selbstreprcduzierender Programme in PL notwendig ist.
Da alle gängigen Programmiersprachen die gleiche "Berechenkapazität" wie PL haben, läßt sich aus der Existenz selbstreproduzierender Programme in PL die Existenz selbstreproduzierender Programme in realen Programmiersprachen - sowohl in höheren Programmiersprachen als auch in Assembler-Sprachen - folgern.
Grundlage ist zunächst ein beliebiges, aber festes, endliches
Alphabet
. Die Menge
aller endlichen
Wörter über
stellt die Menge der Daten dar, auf denen
Programme in PL arbeiten. Das leere Wort
ist dabei als
Datum zugelassen.
(2.2.1) Definition (Ausdrücke):
.
sind Elemente
aus einer festen Menge VR. Jede Variable kann
Werte aus
annehmen.
für jedes
.
Bedeutung:
Xa hat den Wert xa, falls
der Wert
von X ist.
hat den Wert
, falls xa der Wert
von X ist für ein Element
. Andernfalls
hat
den Wert
.
oder
mit
und
.
Bedeutung:
ist genau dann wahr, wenn a der
letzte Buchstabe des Wertes der Variablen
X ist.
ist genau dann wahr, wenn
der
Wert von X ist.
(2.2.2) Definition (Grundanweisungen):
Die Grundanweisungen in PL sind:
für alle Variablen X und Y aus VR und
.
(2.2.3) Definition (Kontrollstrukturen):
Die Kontrollstrukturen in PL sind:

Bedeutung:
Hintereinanderausführung von Anweisungen.
Vergleiche übliche Programmiersprachen.

Bedeutung:
stellt einen bedingten Sprung dar. p steht
für eine Bedingung (vgl. (2.2.1)(iv)).
L ist eine Marke (vgl. (2.2.4)).
Ansonsten wie in üblichen Programmiersprachen.

Bedeutung:
Verzweigung; p ist eine Bedingung. Die Anweisungen P und Q stellen die Alternativen dar. Vergleiche übliche Programmiersprachen.

Bedeutung:
while-Schleife; Bedingungen der Form
,
sind nicht erlaubt. P ist eine Anweisung. Ansonsten wie in üblichen Programmiersprachen.
stellt eine loop-Schleife mit Fallunterscheidung
dar. Bei der Auswertung wird zunächst eine
interne Kopie der Variablen X angelegt. Danach
wird der Wert von X von links nach rechts durchlaufen.
Für jeden Buchstaben (d.h. Element aus A)
des Wertes von X wird die zugehörige Anweisung
ausgeführt. Fehlt für einen Buchstaben
die Vorschrift
in der Liste der
Alternativen, so wird so verfahren, als würde in
der Liste
stehen,
.
(2.2.4) Definition (Marken):
Marken sind Elemente aus einer festen Menge
. Eine Marke kann in der Form
vor jeder Anweisung P stehen.
(2.2.5) Definition (Anweisung):
Eine Anweisung in PL ist entweder eine Grundanweisung,
oder sie besteht aus Grundanweisungen, die
mittels der Kontrollstrukturen
bis
miteinander
verknüpft sind.
(2.2.6) Definition (PL-Programme):
Ein Programm
in PL hat die Form
wobei
eine Anweisung ist.
Die paarweise verschiedenen Variablen
heißen Eingabevariable.
Die paarweise verschiedenen Variablen
heißen Ausgabevariable.
Tritt in
die Kontrollstruktur
auf, so darf L in
nur einmal in der Form
auftreten, wobei P eine Anweisung ist.
(2.2.7) Definition (Ausführung von PL-Programmen):
Die Ausführung eines Programms
in PL beginnt damit,
daß die Eingabevariablen
mit Eingabewerten
belegt werden. Alle anderen in
vorkommenden
Variablen werden mit
initialisiert. Danach
wird
ausgeführt. Nach Ausführung von
liegt
das Ergebnis der Programmausführung in Form der
Werte der Ausgabevariablen
vor.
Hält das Programm nie an, so ist das Ergebnis von
undefiniert.
(2.2.8) Bezeichnung: Prinzipiell haben wir hier nicht genau eine Programmiersprache PL definiert, sondern eine Klasse von Programmiersprachen. Das liegt daran, daß wir noch Freiheit haben in der Wahl der Mengen VR und L und insbesondere in der Wahl des Alphabets A. Während die Elemente von VR und L nur programminterne Bezeichnungen darstellen, bestimmt das Alphabet A die Datenmenge, auf der PL-Programme arbeiten. Je nachdem, welches endliche Alphabet A wir zugrunde legen, werden wir in Zukunft die in den Definitionen (2.2.1) bis (2.2.7) definierte Programmiersprache mit PL(A) bezeichnen.
(2.2.9) Bemerkung: Streng genommen haben wir keine formale Definition von PL(A) vorgenommen. Fehlinterpretationen sind denkbar. Unsere Definition wäre exakt, hätten wir sowohl die Syntax als auch die Semantik von PL(A) mit formalen Methoden beschrieben. Besonders die Beschreibung der Semantik ist sehr mühsam und würde den gegebenen Rahmen sprengen. Es soll aber wenigstens die Syntax von PL(A) in Form einer kontextfreien Grammatik angegeben werden.
Die folgende kontextfreie erzeugende Grammatik
erzeugt alle gültigen PL(A)-Programme
zu gegebenem Alphabet A. Leider werden nicht genau die gültigen
PL-Programme erzeugt, sondern auch Programme, die sich
nicht durchführen lassen. Es sei hier auf Definition (2.2.7)
verwiesen. Dort finden sich einige umgangssprachliche Regeln,
wie z.B. "eine Marke L darf nur einmal in der Form L : P in
auftreten". Derartige Regeln lassen sich nicht mittels
einer kontextfreien Grammatik erfassen. Wir benötigen diese
Regeln, um unter den von G(A) erzeugten Programmen die gültigen
Programme von den nicht durchführbaren zu unterscheiden.
Der gleiche Effekt tritt bei der Beschreibung realer
Programmiersprachen durch kontextfreie Grammatiken auf. Auch
hier kommt man i.a. nicht ohne umgangssprachliche Regeln aus.
Beispiel (SIMULA>: "Sprünge in das Innere von while-Schleifen sind verboten". [17] [7]
(2.3.1) Angabe der Grammatik
:
Die Menge der terminalen Zeichen
ist:
Die Menge der nichtterminalen Zeichen
ist:
Das Startzeichen
ist <program>.
Die Menge P umfaßt die Produktionen:




















Wir können folgende Entsprechungen feststellen:
| Regel 1-5 | | Definition (2.2.6) |
| Regel 6 | | Definition (2.2.4) |
| Regel 7-13 | | Definition (2.2.3),(2.2.5) |
| Hegel 14-20 | | Definition (2.2.1),(2.2.2) |
Die oben erwähnten umgangssprachlichen Regeln in den Definitionen bleiben von G(A) unberücksichtigt.
Sei nun A endliches Alphabet,
.
besitzt
Eingabe-
und
Ausgabevariable. Während der Programmausführung
wird aus der Belegung der Eingabevariablen eine Belegung
der Ausgabevariablen ermittelt, falls das Programm
anhält. Hält das Programm an, was i.a. nicht vorausgesetzt
werden kann, so stellt die letzte Belegung der Ausgabevariablen
das Ergebnis der Programmausführung dar. Hält das Programm
nicht, so ist das Ergebnis undefiniert. In beiden Fällen
interessieren etwaige Zwischenbelegungen irgendwelcher
Variablen während der Programmausführung nicht. Dieser Sichtweise
entspricht Definition (2.4.1).
(2.4.1) Definition: Sei
. Die von
berechnete
Funktion ist
.
ordnet jeder Anfangsbelegung
,
1), der Eingabevariablen ein Ergebnis
, zu,
falls das Programm
anhält. Hält
nicht an, so
ist
undefiniert.
(2.4.2) Bemerkung: Aus Definition (2.4.1) folgt:
ist i.a. eine partielle Funktion.
und
sind ausdrücklich zugelassen.
Die Bedeutung dieser Sonderfälle sei hier
jedoch kurz erläutert. Es bezeichne () das Nulltupel:
, ordnet jedem r-Tupel
das Nulltupel () zu, falls
mit
als Eingabebelegung anhält.

, ordnet dem Nulltupel ()
ein s-Tupel
zu, falls
anhält.

ordnet dem Nulltupel ()
das Nulltupel () zu, falls
hält.

(2.4.3) Definition: Sei A fest gewählt.
,
heißt PL(A)-berechenbar oder kurz berechenbar,
falls ein Programm
existiert mit
.
heißt Menge der
PL(A)-berechenbaren Funktionen.Um den intuitiven Begriff der Berechenbarkeit zu präzisieren,
hat es immer wieder Versuche gegeben, Klassen von
"berechenbaren" Funktionen zu definieren. All diese Versuche
haben zu der gleichen Menge von "berechenbaren" Funktionen
geführt. So ist zum Beispiel die Menge der "mit Turingmaschinen
berechenbaren" Funktionen mit der Menge der
"partiell rekursiven" Funktionen identisch. Mit diesen Mengen
wiederum ist bei festem A die Menge
identisch.
Diese Identitäten geben Anlaß zur Church'schen These.
(2.4.4) Church'sche These:
Jede intuitiv berechenbare Funktion ist PL(A)-berechenbar und umgekehrt.
Aus (2.4.4) folgt: Sind
, und
zwei voneinander verschiedene
endliche Alphabete, so lassen sich offensichtlich die
Mengen
und
identifizieren. Wir geben daher die
Differenzierung nach dem zugrunde liegenden Alphabet auf und
schreiben von nun an einfach
für die Menge der berechenbaren
oder partiell rekursiven Funktionen (siehe auch (2.4.6)).
Wichtig ist die folgende Ergänzung zur Church'schen These.
(2.4.5) Ergänzung zur Church'schen These:
Zu jeder berechenbaren Funktion f läßt sich für
beliebiges endliches A effektiv ein Programm
angeben mit 
(2.4.6) Definition:

ist die Menge der total rekursiven Funktionen.

(2.5.1) Definition: Sei A endliches Alphabet. Eine Menge
, heißt entscheidbar oder auch
rekursiv genau dann, wenn es eine total rekursive
Funktion
gibt mit

(2.5.2) Definition: Seien
, und
endliche Alphabete.
Eine Funktion
heißt genau dann
Kodierung von
durch
, falls gilt:
,
ist injektiv,
ist entscheidbar,
Sei
. Dann kann man
mit den natürlichen Zahlen
einschließlich der Null,
, wie folgt identifizieren.
(2.5.3) Definition: Eine Kodierung
heißt Gödelisierung.
heißt Gödelnummer von
für alle
.
Es soll im folgenden eine Gödelisierung aller PL(A)-Programme
mit festem A angegeben werden. Damit wird gleichzeitig eine
Gödelisierung von
angegeben. Sei
fest gewählt.
In der Menge B listen wir alle Sonderzeichen und alle Buchstaben
auf, aus denen die Wortsymbole "input, if, fi usw."
von PL(A) aufgebaut werden.
Die Mengen der Marken und Variablen in PL(A)-Programmen sind
bzw.
. Dabei bezeichnen
bzw.
, irgendwelche Namen für Variable bzw. Marken. Es
war bisher nicht nötig, die Wahl dieser Namen einzuengen, Für
die folgender, Überlegungen muß jedoch sichergestellt werden,
daß die Namen Wörterüber einem endlichen Alphabet sind. Es
wird daher wie folgt normiert.
ist textuell gleich "L1"
ist textuell gleich "L2" u.s.w.entsprechend
ist textuell gleich "V1" u.s.w.Damit gilt:

Sei nun
. Jedes Programm
läßt
sich somit als Wort aus
und PL(A) selbst als Teilmenge
von
auffassen. Wir geben eine injektive Abbildung
elementweise an:
Die injektive Abbildung H läßt sich zu einer ebenfalls
injektiven Abbildung
erweitern.
(2.5.4) Lemma:
ist eine Kodierung von
durch
.
Beweis:
ist
natürlich
intuitiv berechenbar und auf Grund der
Church'schen These berechenbar.
ist für alle
Elemente aus
definiert. Also ist
total und
insgesamt aus
,
ist trivialerweise injektiv.
. D ist Teilmenge von
. Sei
.
hat endliche Länge
1)
mit
für
.
ist genau dann aus
D, wenn jedes
ein Urbild in C bzgl. H hat
Um festzustellen, ob
ist, sind also höchstens
Tests nötig. Es existiert
also eine total rekursive Funktion
mit
(Jedes Element von
hat unter H Urbild in C)
.
Also ist
entscheidbar.
effektiv das Urbild in
ermitteln
kann. Also ist
überall dort, wo es definiert
ist, auch berechenbar. Also 
Aus (i) - (iv) folgt:
ist Kodierung.
Wir betrachten nun die total rekursive Funktion 
mit 
wobei
die j-te Primzahl ist,
Behauptung: f ist bijektiv.
Beweis:
mit
eine Primzahlzerlegung hat, in der mindestens
ein Primfaktor vorkommt.Mit
als Kodierung von
durch
und
als bijektiver
Funktion von
nach
folgt Lemma (2.5.5).
(2.5.5) Lemma: Die Funktion
ist
Gödelisierung von
durch
.
Jedem Wort w aus
und somit jedem Programm aus PL(A) ist
also eindeutig eine Zahl
aus
zugeordnet. Da
injektiv und f bijektiv ist, ist die Abbildung g eine bijektive
Gödelisierung von
.
(2.5.6) Lemma: Die Menge
ist
entscheidbar.
Beweis:
. Dann läßt sich i eindeutig in der Form
darstellen (
).
Existiert für eines der
kein Urbild
bzgl. der Funktion H. so ist i nicht aus dem
Bildbereich, von g und damit auch nicht aus T.
Sei nun jedes
aus dem Bildbereich von H. Dann
existiert ein
mit g(w)=i. Aus der Grammatik
G aus 2.3. und den umgangssprachlichen Regeln
wie "Die Eingabevariablen sind paarweise verschieden."
läßt sich ein Programm konstruieren
(vgl. : "Formale Sprachen", "Compilerbau"),
das bei jeder Eingabe wenn
hält und
ausgibt
genau dann, wenn
ist. Insgesamt existiert
also eine total rekursive Funktion, deren Ergebnis
genau dann gleich
ist, wenn das Urbild eines
Elementes aus
, falls es existiert, ein
gültiges PL(A)-Programm ist. Also ist T entscheidbar.(2.5.7) Definition:
, heißt aufzählbar genau dann,
wenn B Wertebereich einer partiell rekursiven Funktion
ist.
(2.5.8) Lemma:
, entscheidbar
B ist
aufzählbar.
Beweis: Sei
entscheidbar. Nach Definition (2.5.1)
existiert eine total rekursive Funktion

Aus
läßt sich eine partiell rekursive Abbildung

Dann ist die Abbildung
mit
, partiell rekursiv
und hat als Wertebereich die Menge B.1)
(2.5.9) Korollar: T ist aufzählbar.
Beweis: Folgt aus Lemma (2.5.7), da T entscheidbar ist.
Wie im Beweis von (2.5.6) kann man zeigen, daß auch für jedes
die Menge
entscheidbar ist. Man braucht dem Entscheidungsalgorithmus
im Beweis von (2.5.6) nur noch einen Test, ob ein Programm
genau m Eingabe- und k Ausgabevariable aufweist,
hinzuzufügen. Aus der Entscheidbarkeit von
folgt die
Aufzählbarkeit von
und damit die Existenz einer partiell
rekursiven Funktion von
nach
, die die Menge
als Wertebereich hat. Da
ist, folgt sogar die
Existenz einer total rekursiven Funktion (vgl.[5] Seite 82)

Es hat also Sinn, wieder vom i-ten Element aus
zu sprechen.
Für alle
läßt sich also auch die Menge aller
Programme mit m Eingabe- und k Ausgabevariablen in der Form
hinschreiben. Dabei ist
dasjenige
Programm aus PL(A) mit
.
Insgesamt existiert also für alle
eine total rekursive Funktion
,
mit der "Umkehrung"
mit

Mit
, ist natürlich auch die Menge
für alle
entscheidbar und damit aufzählbar. Die Menge
läßt sich
also in der Form
hinschreiben, wobei für
jedes
gilt:
. Die Gödelnummer von
. überträgt
sich dabei auf
. In der obigen Aufzählung von
kommen alle Funktionen aus
mehrfach vor. Das bedeutet
aber, daß die Funktionen aus
, mehrere Gödelnummern besitzen.
Es gilt sogar:
(2.5.10) Lemma: Für alle
gilt: f hat bzgl. der Gödelisierung
g unendlich viele Gödelnummern (
).
Beweis: Seien
. f wird realisiert durch das
Programm

Es gilt
. f wird aber auch realisiert
durch die Programme 

Es gilt 
Wegen
hat f unendlich viele
Gödelnummern.
(2.5.11) Definition: Sei
eine Menge von Wortfunktionen,
und sei
.
Eine Funktion
heißt universell für
,
wenn gilt:
.1)
(2.5.12) Satz: Für alle
gilt:
Es gibt zu
eine universelle Funktion
.
Beweis: (mittels Church'scher These)
Die Menge aller Programme mit m Eingabe- und k Ausgabevariablen
liege in aufgezählter Form, etwa
durch
, vor:

Dann ist die Funktion
![\psi_{m,k}:=\lambda x,\overline{y}[\varphi_{\pi_{\overline\gamma_{m,k}(x)}(\overline{y})}],\ y\in(A^*)^m](/img/cache/a8ebb48f0f2fb4b6dc3469e15843a0a8.gif)
universell für
, und
ist intuitiv berechenbar.
Wegen der Church'schen These gibt es ein
mit m+1 Eingabe- und k Ausgabevariablen
mit
.
(2.5.13) Bemerkung: Man kann (2. 5.12) auch beweisen, indem
man auf komplizierte Weise direkt
konstruiert.

Wir wollen eine weitere Gödelisierung von
einführen.
Dazu definieren wir zunächst, was unter der lexikographischen
Ordnung auf
zu verstehen ist.
(2.6.1) Definition: Sei
. Die Nachfolgerfunktion
ist definiert durch:
![\nu(\varepsilon) = a_1\\
\nu(xa_i) = xa_{i+1}\\
\nu(xa_n) = \nu(x)a_1\text{\ \ f\ddot{u}r }i\in[n-1],\ x \in A^*,\ a_i \in A](/img/cache/14bab7cef4713e8e9a9660c1498d28f9.gif)
(2.6.2) Lemma: Die Nachfolgerfunktion
ist
bijektiv.
Beweis: Zunächst ist
injektiv, da zwei Elemente aus
nur dann den gleichen Nachfolger haben können,
wenn sie gleich sind.
ist surjektiv, da man
durch wiederholte Anwendung von
jedes Wort aus
auf das leere Wort reduzieren kann. Also
.
Wegen
für jedes Element
, aus
erhält man
eine Ordnung auf
. [5]
(2.6.5) Definition: Seien
und
aus
,
dann ist
genau dann, wenn
gilt.
Diese Ordnung heißt lexikographische Ordnung auf
.
Man kann also alle Wörter aus
eindeutig in lexikographischer
Reihenfolge auflisten:
.
(2.6.4) Satz: Sei
und
. Sei
die Abbildung, die jedem
die Nummer von x in der lexikographischen
Reihenfolge zuordnet, also
mit
.
Dann ist
eine bijektive Gödelisierung.
Beweis:
ist total, da
auf ganz
definiert ist.
Für jedes x läßt sich
durch endlich viele
Anwendungen der Definition von
effektiv
ermitteln. Also ist
.
ist injektiv, da es keine zwei Elemente aus
gibt mit gleicher Stellung in der lexikographischen
Reihenfolge.
ist
natürlich
entscheidbar.
mit Hilfe von
effektiv alle Worte aus
bis zum i-ten Wort in lexikographischer Reihenfolge
erzeugen. Dieses i-te Wort ist das Urbild
von i. Also ist
berechenbar und wegen
sogar total. Also
.Aus (i) bis (iv) folgt:
ist Gödelisierung.
Wegen (ii) und
folgt:
ist bijektiv.
(2.6.5) Lemma: Seien
und
zwei Alphabete, dann ist die Funktion
eine bijektive Kodierung von
durch
.
Beweis: Offensichtlich.
Wir wollen zeigen, daß es möglich ist, jedes Programm
aus PL(A) mit r Eingabe- und s Ausgabevariablen in ein
"äquivalentes" Programm
mit nur jeweils einer Eingabe-
und Ausgabevariablen zu transformieren. Wegen der Entsprechung
von
und PL(A) genügt es demnach also, die
Funktionen aus
zu betrachten, um ganz
zu behandeln.
Die universelle Funktion für
ist in diesem Sinne dann
universell für ganz
.
Sei nun
mit r Eingabe- und s Ausgabevariablen,
. Dann hat
folgenden Aufbau.

Als Eingabebelegung für
kommt jedes Element
aus
vor.
kann man auch wie folgt darstellen:
, dabei sei
.
In dieser Form wird
gleichwertiges
Programm
mit nur einer Eingabe- und einer Ausgabevariablen
benutzt.
![\begin{align}
\pi = &&\text{\underline{input}} X\\
&&[X_1:=x_1;\dots X_r:=x_r];\\
&&AW_\pi;\\
&&[Z:=z_1|\dots|z_s];\\
&&\text{\underline{output}} Z
\end{align}](/img/cache/e0122e68eca5013e4ae7745b3de83f4d.gif)
Die Programmteile in Klammern lassen sich wie folgt realisieren:
![[X_1:=x_1;\dots. X_r:=x_r]](/img/cache/5e1c474bd320de8939f3d0c4345c8979.gif)
durch:

und ![[Z:=z_1|\dots|z_s]](/img/cache/ccdf4f774310cd28d49eaa7bb9eea469.gif)
durch

ist nicht Element aus PL(A), da das zugrunde liegende
Alphabet nicht A sondern
ist. Wir können aber
aus
ein ebenfalls zu
gleichwertiges Programm
mit nur einer Ein- und einer Ausgabevariablen gewinnen,
indem wir
durch
kodieren. Als Kodierung können
wir die Funktion

benutzen, wobei die Funktionen
und
in 2.6.
definiert sind.
Im wesentlichen lassen sich also alle Programme aus
PL(A) auf eine Eingabe- und eine Ausgabevariable reduzieren,
falls überhaupt Ein- bzw. Ausgabevariable vorhanden
sind. Auf Grund der Church'schen These genügt es also,
statt
die Menge
zu betrachten. Die universelle Funktion
für
ist in diesem Sinne universell für ganz
. Um diesen Tatbestand deutlich zu machen, führen wir die
folgende Schreibweise ein.
(2.7.1) Definition: Sei
universelle Funktion für
.
,
.
Dabei ist
.
Im folgenden werden wir das Rekursionstheorera beweisen,
das uns ermöglicht, die Existenz selbstreproduzierender
PL(A)-Programme nachzuweisen. Sei A so gewählt, daß jedes
PL(A)-Programm in
liegt (Vermeidung von Umkodierungen).
(2.8.1) Satz (s-m-n-Theorem):
Für alle
gibt es eine Funktion
,
die für alle
folgende Gleichung erfüllt:

Beweis: Seien
fest gewählt.
undefiniert. In diesem Falle muß
auch undefiniert sein. Es wird deshalb
gesetzt. Nun ist auch
kein gültiger Programmtext, und es gilt:

. Dann hat x den Aufbau:

Mit
wird gesetzt:
![\begin{align}
s^m_n(x,\overline{y}) = &&\text{\underline{input}} Z_1,\dots,Z_n;\\
&& [Y_1:=y_1];\dots;[Y_m:=y_m];\\
&& AW_x;\\
&&\text{\underline{output}} W
\end{align}](/img/cache/fa4e1910f1dca602b480986d6ca6ffd8.gif)
Die Programmteile in eckigen Klammern lassen
sich leicht - wie am Beispiel von
gezeigt - realisieren:
ist Element aus
und hat somit endliche
Länge 
mit
.
Damit wird
realisiert durch

Auf Grund der Cnurch'schen These ist
.
(2.8.2) Korollar: Es gibt ein
, so daß für alle
gilt:
für alle
.
Beweis: Da f eine berechenbare Funktion ist, gibt es ein
Programm
, mit
. Aus (2.3.1) folgt
.
Setzt man
, so folgt das
Korollar.
(2.8.3) Bezeichnung: Sei
. Dann existiert ein
Programm
mit
.
Wir führen nun folgende Notation ein:

Es gilt mit dieser Notation:
für alle
.
Sei
und
für ein
, so
ist nach obiger Notation die Funktion
überall undefiniert.
Wir sind nun in der Lage, das Kleene'sche Rekursionstheorem in der folgenden Fassung zu beweisen:
(2.8.4) Satz (Pekursionstheorem, Formulierung wie in [5]):
Zu jeder Funktion
gibt es einen Text
,
so daß gilt:

Beweis: Die Funktion
![g=\lambda y,x[\varphi_{\varphi_y(y)}(x)]](/img/cache/e78c5b6b8ad7ebe86741bf5d0b3cde24.gif)
liegt in
mit
. In Korollar (2.8.2)
wurde gezeigt, daß ein
, existiert mit

Sei nun
. Da
ist, kann man die
Hintereinanderausführung von f und h betrachten.
liegt ebenfalls in
. Auf Grund der Church'schen
These kann man zu
effektiv einen Programmtext
aus PL(A) angeben mit

Aus (1) und (2) folgt dann zusammen:

Damit ist
das gesuchte x.
(2.8.5) Definition: Sei
. Ein Element
heißt
Fixpunkt zu f, falls gilt
.
(2.8.6) Korollar: Zu jeder Funktion
existiert ein
Text
mit
.
Beweis: Nach Korollar (2.8.2) existiert eine Funktion
mit
für alle
.
h hat nach dem Rekursionstheorem einen Fixpunkt
mit 
(2.8.7) Satz: Es existiert in
eine Funktion mit einem
Programmtext
, der für jede Eingabe
seinen eigenen Text
ausgibt.
Beweis: Die Funktion
mit
für alle
ist trivialerweise
aus 
Aus Korollar (2.8.6) folgt damit, daß die Gleichung
eine Lösung
besitzt. Es
existiert also ein
mit
![\varphi_{x_0} = g_{x_0} = \lambda y [x_0] \Rightarrow \varphi_{x_0}(y) = x_0\ \ \forall y \in A^*](/img/cache/55131545a411da72c0d64772842ad5f9.gif)
ist also eine Funktion, die bei jeder
Eingabe
ihren eigenen Programmtext
ausgibt.
Mit
(trivial) ist der Satz vollständig
bewiesen.
Der folgende Satz ist eine Verallgemeinerung von Satz (2.8.7).
(2.8.8) Satz: Sei
aus
. Dann existiert
in
eine Funktion mit einem Programmtext
, der für jede Eingabe den Wert
ausgibt.
Beweis: Sei
. Die Funktion
mit
,
liegt in
. Dies folgt aus der Abgeschlossenheit
von
gegenüber der Kombination und der Substitution
von Funktionen (vgl. etwa [5]). Aus (2.8.6)
folgt damit, daß die Gleichung
eine
Lösung
besitzt. Es existiert also ein
mit
![\varphi_{x_0}=g_{x_0}=\lambda y[f(x_0)]\Rightarrow\varphi_{x_0}(y)=f(x_0)\ \ \forall y \in A^*](/img/cache/3dc7734aae8ee4271907ade74cf2fc52.gif)
Da
eine konstante Funktion ist, liegt
trivialerweise in
.
ist die gesuchte
Funktion.
Aus Satz (2.8.8) folgt, daß es PL(A)-Programme gibt, die sich, nicht nur einfach selbstreproduzieren, sondern ihren eigenen Text mehrmals ausgeben.
(2.8.9) Korollar: Für jedes
existiert eine Funktion
mit einem Programmtext
, der für jede Eingabe
seinen eigenen Text
i-mal hintereinander
ausgibt.
Beweis: Sei
. Dann ergibt sich der Beweis aus dem
Beweis von Satz (2.8.8) mit

(2.8.10) Bemerkung: Satz (2.8.7) ergibt sich als Spezialfall von Satz (2.8.8) mit f = id.
Mit Hilfe der vorangegangenen Sätze haben wir die Existenz
selbstreproduzierender PL(A)-Programme auf theoretischem
Wege nachgewiesen. Die Beweise sind zwar konstruktiv, jedoch
lassen sich die Konstruktionen nicht nachvollziehen,
um ein konkretes selbstreproduzierendes PL(A)-Programm zu
erzeugen. In 2.5. haben wir gesehen, daß die Menge
aller PL(A)-Programme aufzählbar ist. Zählt man die Menge
aller PL(A)-Programme auf, etwa in lexikographischer
Reihenfolge, so garantiert Satz (2.8.7) die Existenz einer
Zahl
mit
ist selbstreproduzierend. Für die
Zahl
ist jedoch eine Größenordnung zu erwarten, die
Aufzählung als Mittel zur Gewinnung eines selbstreproduzierenden
PL(A)-Programms ausschließt.
Die Bedeutung von Kapitel 2 liegt darin, daß es nicht prinzipiell sinnlos ist, selbstreproduzierende Programme in höheren Programmiersprachen zu suchen; sie existieren wirklich.
(2.8.11) Bemerkung: In 4.3. werden zyklisch selbstreproduzierende Programme behandelt (vgl. Definition (4.3.1)). Die Existenz zyklisch selbstreproduzierender Programme läßt sich wahrscheinlich ebenfalls aus dem Rekursionstheorem folgern.
In Kapitel 2 wurde gezeigt, daß in der fiktiven Programmiersprache PL(A) selbstreproduzierende Programme existieren. Da PL(A) die gleiche "Berechenkapazität" wie alle gängigen Programmiersprachen hat, müssen auch in konkreten Programmiersprachen selbstreproduzierende Programme existieren. Ausgehend von praktischen Überlegungen werden im folgenden einige Beispiele für möglichst kurze selbstreproduzierende Programme in den höheren Programmiersprachen SIMULA und PASCAL konstruiert. Wir werden dabei sowohl auf selbstreproduzierende Programme stoßen, die sich ohne weiteres auf realen Rechenanlagen implementieren lassen, als auch Programme finden, die zwar syntaktisch korrekt sind, sich aber aus verschiedensten Gründen nicht realisieren lassen. Wo es möglich ist, werden aus Letzteren Programmen impiementierbare Versionen gewonnen.
In Abschnitt 3.4. werden einige Beispiele für selbstreproduzierende Programme in einer maschinenorientierten Sprache (SIEMENS-Assemblersprache) angegeben (vgl. 3.4.).
In diesem Abschnitt sollen selbstreproduzierende Programme in der Programmiersprache SIMULA entwickelt werden. SIMULA steht hier als Beispiel für eine blockorientierte Programmiersprache. Die in 3.3. behandelte Sprache PASCAL ist dagegen nicht blockorientiert. Für uns wird sich jedoch ein anderes Unterscheidungsmerkmal als wichtiger erweisen. Es handelt sich dabei um die Verfügbarkeit von Textvariablen. Während PASCAL nur einfache Textkonstanten kennt, kann in SIMULA mit echten Textvariablen operiert werden. Durch Integration in das SIMULA-Klassenkonzept kann die Bearbeitung von Variablen des Typs text in SIMULA sehr komfortabel sein. Dies nutzen wir in Abschnitt 3.2.5. aus.
Um eine Vorstellung von der Problematik, ein selbstreproduzierendes
SIMULA-Programm
anzugeben, zu erhalten, betrachten
wir folgenden naiven Ansatz:
enthält im wesentlichen nur eine Ausgabeanweisung.
Diese Anweisung gibt den ganzen Programmtext von
aus.
Ein solcher Ansatz führt zu folgendem Programm
:
= begin OUTTEXT("....................") end; ↑ An dieser Stelle muß der Programm- text von
erscheinen, also: begin OUTTEXT("..........") end; ↑ siehe oben
![]()
![]()
Insgesamt entsteht also ein sich rekursiv aufblähendes Programm, das sich auch wie folgt schreiben läßt:
= begin OUTTEXT("BEGIN OUTTEXT("BEGIN OUTTEXT("BEGIN OUTTEXT("...... .............................. .............END") END") END") end
ist natürlich kein endlicher Text und damit kein
Programm mehr. Die "Unmöglichkeit" von
läßt sich
auch an der Unerfüllbarkeit der Textgleichung
X = begin OUTTEXT("x") end
zwischen dem Text x und den Konstanten begin OUTTEXT(" und ") end ablesen: Texte verschiedener Länge können nicht gleich sein!
Aus 3.2.1. folgt, daß ein selbstreproduzierendes SIMULA-programm
seinen eigenen Text nicht en bloc mit einer
einzigen Ausgabeanweisung ausgeben kann.
muß seinen
Text also in mehreren Schritten aus einigen Teilstrings
zusammensetzen. Es muß also eine
vorgenommen werden. Da wir über die Art der Zerlegung
nichts wissen, versuchen wir es zunächst mit der totalen
Zerlegung von
, das heißt, wir zerlegen
in einzelne
Zeichen. Belassen wir es bei dieser Maßnahme, so kommen
wir zu folgendem Programm.
= begin OUTTEXT("B"); OUTTEXT("E"); OUTTEXT("G"); OUTTEXT("I"); OUTTEXT("N"); OUTTEXT("
"); OUTTEXT("O");
![]()
![]()
Es ist klar, daß
einen unendlichen Text darstellt
und damit kein Programm sein kann.
Die Unendlichkeit von
liegt darin begründet,
daß zur Ausgabe eines Zeichens eine Anweisung - und
damit auch ein Text - bestehend aus insgesamt 13 Zeichen
notwendig ist. Damit ist ein rein sequentielles
Programm wie
zum Scheitern verurteilt, wenn der Programmtext
in einzelne Buchstaben zerlegt wird. Die Wahl
eines der Zerlegung des Programmtextes entsprechend
strukturierten
ist ein bedeutendes Kriterium, das bei der praktischen Konstruktion selbstreproduzierender Programme beachtet werden muß.
(i) und (ii) stellen die beiden wichtigsten Aspekte selbstreproduzierender Programme dar. Bei den folgenden Konstruktionen selbstreproduzierender Programme wird es also darum gehen, eine geschickte Zerlegung des Programmtextes und einen geeigneten Ausgabealgorithmus zu finden.
Wir greifen mit Programm
die Idee von der totalen
Zerlegung des Textes
in einzelne Zeichen aus 3.2.2. auf.
Diese Zerlegung wird aber nicht wie in
explizit sichtbar,
sondern sie äußert sich im verwendeten Algorithmus.
Dieser Algorithmus setzt den Text von
, aus einzelnen
Zeichen zusammen. Die Menge der zulässigen Zeichen steht
im Algorithmus in Form eines Feldes
character array C [0 : maxchar]
zur Verfügung. Jedes Element von C enthält genau ein Zeichen, das zur Erstellung von SIMULA-Programmen verwendet werden darf. Alle derartigen Zeichen sind in C enthalten.
![\text{\underline{character array } C [0 : maxchar];}\\
\vdots\\
\vdots\\
\left. C[0]:=\quote{A}\quote;\\C[1]:=\quote{B}\quote;\\\vdots\\\vdots\\C[25]=\quote{Z}\quote; \right}\text{Buchstaben}\\
\left. C[26]:=\quote 0 \quote;\\\vdots\\\vdots\\C[35]:=\quote 9 \quote; \right}\text{Ziffern}\\
\left. C[36]:=\quote ; \quote;\\C[37]:=\quote : \quote;\\\vdots\\\vdots\\C[\text{maxchar}]:=\quote*\quote; \right}\text{Sonderzeichen}](/img/cache/7567b1a16997005774b583e3859b3806.gif)
Der Algorithmus hat die Aufgabe, sukzessive Komponenten
aus C auszugeben, so daß nsgesamt der Programmtext
,
gedruckt wird:
while not p do | I ist vom Typ
begin <berechne neues I>; | integer, p ist
OUTCHAR(C[I]); | ein Prädikat,
<setze p> | das den Algorithmus
end | stoppt, sobald
| der Text
,
| gedruckt ist.
![\begin{array}{.rl.c.}
\hdash \text{\underline{begin}} & \text{\underline{integer} I}\\ & \vdots\\ & \vdots & \text{Ia}\\
\hdash & C[0]:=\quote A\quote;\\ & C[1]:=\quote B\quote;\\ &\vdots\\ & \vdots\\ & C[\text{maxchar}]=\quote*\quote; & \text{II}\\
\hdash &
\begin{array}{rl}
\text{\underline{while}}& \text{\underline{not} p \underline{do}}\\
\text{\underline{begin}}& \text{<berechne neues I>;}\\
& \text{OUTCHAR(C[I]);}\\
& \text{<setze p>}\\
\text{\underline{end}}
\end{array}
& \text{III}\\
\hdash \text{\underline{end}} & & \text{Ib}\\
\hdash & &
\end{array}](/img/cache/a500e36a3933aff3fdd5415f19c78f9b.gif)
Das Programm
, gliedert sich in 4 Teile. Man erkennt
neben den initialisierenden und abschließenden Teilen
Ia und Ib einen Teil II, der den Aufbau der Druckzeichentabelle
vornimmt, und einen Teil III, der den Algorithmus
realisiert.
Die Programmteile Ia,Ib und II bereiten sicherlich keine Schwierigkeiten. Auch der Algorithmus von Teil III macht einen, durchsichtigen Eindruck. Es bleiben eigentlich nur noch die beiden Anweisungen <berechne neues I> und <setze p> durch SIMULA-statements zu ersetzen. Das Ersetzen von <berechne neues I> ist dabei sicherlich die schwierigere Aufgabe.
Wir wollen zunächst genauer untersuchen, was der Algorithmus aus Teil III und insbesondere die Anweisung <berechne neues I> leisten müssen.
(3.2.3.1) Definition: Sei D die Menge aller in SIMULA-Programmen zulässigen Zeichen:
D := {a,b,...,z,0,1,...,9,;,:,...,*}
Dann ist
die Zahl
der Index, unter
dem das Zeichen
in der Tabelle C abgelegt
ist: ![\alpha = C[i_\alpha]](/img/cache/98db853351a107e17ce1b21502bf7af2.gif)
(3.2.3.2) Lemma: Die Abbildung
mit

ist Kodierung von
durch
.
Beweis:
ist für jedes
definiert. Also ist
total,
ist trivialerweise berechenbar.
ist injektiv.
aus
,
ist genau dann
aus
, wenn jedes
, aus
{0,.....,maxchar} ist. Also ist
entscheidbar.
aus
. Mit Hilfe der
Tabelle C läßt sich für jedes
, das
Zeichen aus D ermitteln, das durch
kodiert
wird. Mit höchstens
Vergleichen
läßt sich so das Urbild von
unter
ermitteln.
Also ist
berechenbar.Aus (i) bis (iv) folgt:
ist Kodierung (vgl.(2.5.2)).
(3.2.3.3) Bemerkung: Jedes SIMULA-Programm
hat als endliches
Wort aus
eine Kodierung
in
.
Bei jedem Durchlauf durch die while-Schleife im Algorithmus
von
wird ein neuer Wert für I berechnet. I nimmt
also im Verlauf des Programms eine Folge von Werten an,
die sich als Wort aus
auffassen läßt:
![I = i_1,i_2,\dots\ \dots,i_{l(\pi_2)}\ \ i_j \in \mathbb{N}_0\text{ f\ddo{u}r alle }j \in [l(\pi_2)]](/img/cache/ea95089062d6a088d8d537abe46c3c1b.gif)
Damit
seinen eigenen Text ausgeben kann, muß gelten:
![C[i_1]\ C[i_2] \dots\ \dots C[i_{l(\pi_2)}]\overset!=\pi_2](/img/cache/a0470d90a9878259d94c5466cb170b3f.gif)
Es gilt daher:
bezüglich
.
ist die
Dekodierung der ermittelten Kodierung, also die Realisierung von
.Die Berechnung der
, ist das noch verbleibende
Problem. Die
müssen iterativ mittels einer Funktion
erzeugt werden:
![\fbox{
\text{Setze i_1;\\
i_{j+1} := F(i_j);\ \ j\in[l(\pi_2)-1]
}}](/img/cache/384528912a3fcca26d9ff4286e823b7f.gif)
Die Funktion F läßt sich als Funktionsprozedur realisieren
und innerhalb von Teil Ia von
vereinbaren. Die Anweisung
<berechne neues I> wird dann zu der Prozeduranweisung
I := F(I)
Da es unser Ziel ist, ein selbstreproduzierendes SIMULA-Programm anzugeben, das sich auch auf einer konkreten Rechenmaschine implementieren läßt, müssen an F folgende Forderungen gestellt werden:
Es ist möglich, daß ein konkretes F nicht von I abhängt.
In diesem Abschnitt werden zwei Funktionen diskutiert, die als Iterationsfunktion denkbar wären.
Wir erweitern die Kodierung
zu einer Gödelisierung
(vgl. (2.5.3)). Dazu definieren wir die Abbildung
.
(3.2.4.1.1) Definition: Die Abbildung
sei wie folgt definiert:

Ist
, so ist jedes
, kleiner oder gleich
(maxchar+1). Die Restriktion von
auf
ist somit
injektiv und kodiert die Elemente von
durch
. Es
folgt somit:
(3.2.4.1.2) Lemma: Die Abbildung
mit
ist Gödelisierung von
.
Beweis: Offensichtlich
Von Interesse ist für uns die Tatsache, daß man aus der
Zahl f(x) für jedes
effektiv die Komponenten von
zurückberechnen kann. Dies gilt insbesondere für
, und wir gewinnen mit

eine Iterationsvorschrift zur Erzeugung von
, wenn
wir für X den Startwert
wählen.
Da der Startwert von X, also
, von
nicht
eingelesen werden darf, muß
die Zuweisung

enthalten.
ist eine ganze Zahl und damit textueller
Bestandteil von
. Zum Zeitpunkt der Erstellung von
ist die Zahl
unbekannt, sie kann erst nachträglich
ermittelt werden. Beim Aufschreiben des Programms
muß in
der Anweisung
die Zahl
zunächst
ausgelassen werden. Erst nach Erstellung des Programms - das
immer noch nicht enthält - läßt sich dann
q := f(
ohne den string
") errechnen. Mit der
Zahl q als Startwert für X wird
nur seinen Text ohne
die Zahl q reproduzieren können. Diesen Mißstand beseitigen
wir, indem wir den Algorithmus von
, abändern:
Es läßt sich leicht feststellen, nach dem wievielten
Schritt des Algorithmus die Zahl
ausgegeben werden
muß. Es sei dies der r-te Iterationsschritt. Die Zahl r
wird Bestandteil des Programms. Der Algorithmus von
lautet dann:
X:=q;
Y:=1;
while Y<=l("
ohne den String q") do
begin I:=F;
OUTCHAR(C[I]);
if Y=r then OUTINT(q,...);
Y:=Y+1;
end
und das Gesamtprogramm ist
= begin integer I,X,Y; character array C[1:maxchar]; integer procedure F; begin F:=X mod(maxchar+1); X:=X//(maxchar+1) end; C[0]:="A";
![]()
C[maxchar]:="*"; X:=q; Y:=1; while Y<=l("
ohne den String q") do begin I:=F; OUTCHAR(C[I]); if Y=r then OUTINT(q,...); Y:=Y+1 end end
Die Tabelle C braucht natürlich nur die Zeichen enthalten,
die auch wirklich in
vorkommen. Dementsprechend kann
die Zahl maxchar möglichst klein gehalten werden. Die Zahlen
r,q und l("
ohne den String q") lassen sich ermitteln,
nachdem das übrige Programm erstellt wurde. Es ist
leicht einzusehen, daß gilt:
reproduziert sich selbst.
Das Programm
ist zwar ein syntaktisch richtiges
Programm, aber dennoch nicht auf Rechenmaschinen realisierbar,
Das liegt an der Größenordnung der Zahl q. q liegt bei weitem
außerhalb des darstellbaren Zahlenbereichs üblicher
Rechenmaschinen. Um dies einzusehen, schätzen wir die Zahl q
nach unten ab.
Wie man leicht feststellt, kommen im Programm
mindestens 32 verschiedene Zeichen vor. Damit gilt maxchar≥32.
Für die Länge von
gilt, wenn man nur die unbedingt
nötigen blanks, die als Trennzeichen fungieren, mitrechnet:
l("
ohne die Zahl q") > 700
Aus Definition (3.2.4.1.1) und der Definition von q folgt
damit: 
Trotz dieser sehr groben Abschätzung von q zeigt sich, daß q in herkömmlichen Rechnern nicht darstellbar ist.
In Abschnitt 2.5. wurde die Gödelisierung
eingeführt. Auf völlig analoge Weise kann man eine Gödelisierung
konstruieren, indem man C durch
D und die Abbildung
durch die Abbildung
mit
für alle
ersetzt. Wie man aus jeder Gödelnummer
, effektiv
das Urbild w bestimmen kann, so kann man das gleiche
auch für jede Gödelnummer
, durchführen.
Damit läßt sich wie in 3.2.4.1. eine Prozedur F' entwickeln,
mit deren Hilfe es möglich ist,
iterativ
zu berechnen, wenn
als Startwert für die Iteration gewählt wird. Sir erhalten
dann ein ähnliches selbstreproduzierendes Programm
wie
in 3.2.4.1.. Auch dieses Programm ist syntaktisch korrekt,
aber ebensowenig realisierbar wie das Programm aus 3.2.4.1.
Diese Tatsache liegt an der Nichtdarstellbarkeit der Zahl
q'. Wir schätzen q' grob nach unten ab.
Die Länge von
beträgt mindestens 650 Zeichen.
Dann ist

Da schon die fünfte Primzahl, nämlich 11, größer als 10
ist und das Zeichen a mit
nur wenig in
auftritt,
gilt sicherlich:

Damit ist q' ebenso wie q nicht in üblichen Rechenanlagen darstellbar

In Abschnitt 3.2.4. wurden selbstreproduzierende Programme
und
entworfen, die zwar syntaktisch richtig waren,
sich aber nicht auf konkreten Rechenanlagen realisieren
ließen. Wir wollen keine weiteren Anstrengungen unternehmen,
realisierbare Iterationsfunktionen und Startwerte zu finden,
sondern ändern vielmehr Textzerlegung und Algorithmus der
Programme aus 3.2.4. ab. Wir gewinnen aus
das Programm
, indem wir folgende Änderungen vornehmen:
wird
nicht in
einzelne Zeichen, sondern in größere Teilstrings zerlegt.
Aus character array C[1:maxchar] wird
text array C[1:maxtext].
Damit findet erstmals das SIMULA-Textkonzept in unseren
Überlegungen seine Anwendung.
besteht darin, den Programmtext
aus Teilstrings, die
in dem Feld C gespeichert sind, zusammenzusetzen. Jede
Feldkomponente wird durch ihren Index kodiert. Der Text
läßt sich dann als Folge von Indizes kodieren:

Diese Folge von Indizes schreiben wir als Text in die
text-Variable X. Mittels der text-Prozeduren SUB und
GETINT1) ist der Zugriff auf die einzelnen Zahlen
im
Text X gewährleistet. Der Algorithmus von
braucht
also nur noch den Text X sequentiell zu durchlaufen
und für jedes
aus X den Text
auszugeben.
Durch eine derartige Ausnutzung des Text-Konzepts der
Programmiersprache SIMULA umgehen wir die Repräsentation von
durch eine ganze Zahl, wie dies in
und
der Fall
war, und damit auch die nicht mehr darstellbaren Startwerte
q bzw. q'.
Der Text X enthält jedoch nicht seine eigene Kodierung. Aus
diesem Grund muß das Ausdrucken des Textes X im Algorithmus
von
eine Sonderstellung einnehmen. In Analogie zu
3.2.4.1. - dort machte die Ausgabe der Zahl X ähnliche
Schwierigkeiten - wird die Ausgabe von X durch die einfach
zu ermittelnde Zahl r gesteuert:
X:-COPY("
,...,
");
for I:=1 step 1 until k do
begin
<ermittle nächstes
aus X>;
OUTTEXT(C[
]);
if I=r then OUTTEXT(X)
end;
= 1) begin integer I,S,Z; text X; 2) text array C[1:34]; 3) C[1]:-COPY("BEGIN INTEGER I,S,Z; TEXT X;"); 4) C[2]:-COPY("TEXT ARRAY C[1:34];"); 5) C[3]:-COPY("X:-COPY("""); 6) C[4]:-COPY("FOR I:=1 STEP 1 UNTIL 105 DO "); 7) C[11]:-COPY("BEGIN S:=X.SUB(Z+1,2).GETINT;"); 8) C[12]:-COPY("OUTTEXT(C[S]));"); 9) C[13]:-COPY("Z:=IF S<10 THEN 2 ELSE 3)+Z;"); 10) C[14]:-COPY("IF I=99 THEN OUTTEXT(X) END END"); 11) C[21]:-COPY("C[); 12) C[22]:-COPY("]:-COPY("""); 13) C[23]:-COPY(""");"); { Die blanks sind nur 14) C[24]:-COPY(""""); { zur besseren Gliederung 15) C[31]:-COPY("1"); +-------------------- { eingefügt. Der 16) C[32]:-COPY("2"); | { Algorithmus beachtet 17) C[33]:-COPY("3"); | { sie nicht. 18) C[34]:-COPY("4"); | 19) X:-COPY("1,2, v 21, 31,22, 1, 23, 21, 32,22, 2, 23, 21, 33,22, 3,24,23, 21, 34,22, 4, 23, 21,31,31,22, 11, 23, 21,31,32,22, 12, 23, 21,31,33,22, 13, 23, 21,31,34,22, 14, 23, 21,32,31,22, 21, 23, 21,32,32,22, 22,24,23, 21,32,33,22,24,23, 23, 21,32,34,22,24,24, 23, 21,33,31,22, 31, 23, 21,33,32,22, 32, 23, 21,33,33,22, 33, 23, 21,33,34,22, 34, 23, 3,23,4,11,12,13,14,"); 20) for I:=1 step 1 until 105 do 21) begin S:=X.SUB(Z+1,2).GETINT; [ Bewirkt das 22) OUTTEXT(C[S]); [ scannen 23) Z:=(if S<10 then 2 else 3)+Z; [ des Textes X 24) if I=99 then OUTTEXT(X) end end
Verifikation von 
Der algorithmische Teil des Programms arbeitet sequentiell eine Folge von Zahlen ab. Diese Zahlen sind in dem Text X gespeichert. Es sind genau 105 Zahlen. Jede Zahl j bewirkt das Ausdrucken eines Textes C[j]. Zunächst werden die Texte C[1] und C[2] ausgedruckt. Damit sind die ersten beiden Programmzeilen kopiert. Mit den folgenden 96 Zahlen werden die Programmzeilen 3 bis 18 ausgedruckt. Diese 96 Zahlen bestehen aus 16 Gruppen. Jede Gruppe ist durch das Zahlenpaar 21,...,23 begrenzt und druckt genau eine Programmzeile aus. Jede dieser Gruppen hat folgenden allgemeinen Aufbau:
21,C[ [Zahl,]
Ziffer 1 bzw. 2 bzw. 3 Zahl,
Ziffer 1 bzw. 2 bzw. 3 bzw 4. 22,
]:-copy(" [24,]
" Zahl,
text [24,]
" 23,
");
Damit entspricht der Aufbau der Zahlengruppen genau dem allgemeinen Aufbau einer der Programmzeilen 3 bis 18. Berücksichtigt man die im Programm vorkommende Kodierung, so ist klar, daß diese Zahlengruppen die Prograramzeilen 3 bis 18 ausdrucken.
Nach diesen 96 Zahlen wird die Zahl 3 abgearbeitet.
Dadurch wird das Drucken von x:-copy(" bewirkt. Gleichzeitig
hat die Laufvariable I der for-Schleife nun den
Wert 99 (99 Zahlen sind ja abgearbeitet). Deshalb wird nun
der Text X gedruckt. Die Abarbeitung der Zahl 23 schließt
Prograramzeile 19 ab. Die restlichen Programmzeilen 20 bis
24 werden durch Abarbeitung der restlichen Zahlen 4,11,12,
13 und 14 kopiert. Die Laufvariable hat dann den Wert 105,
und der Algorithmus bricht ab.
Verbesserung von 
C[21] = C[
C[22] = ]:-copy("
C[23] = ");
C[24l = "
C[31] = 1
C[32] = 2
C[33] = 3
C[34] = 4
Diese Strings stellen in ihrer Gesamtheit die "Bauelemente"
dar, aus denen das Gerippe von
aufgebaut ist. Auf sie
kann nicht verzichtet werden. Bei den anderen Teilstrings
ist eigentlich nicht einzusehen, warum sie gerade so aufgeteilt
sind. So könnten zum Beispiel C[1] und C[2] zusammengelegt
werden. Grundsätzlich ist zu sagen, daß maximale
Teilstrings gebildet werden können, die kein " enthalten.
Der String xxx"xxx müßte z.B. als
k) C[j]J:-copy("xxx""xxx");
vereinbart werden. Die Zahl j in dem Text X bewerkstelligt dann zwar das Ausdrucken von xxx"xxx, aber es läßt sich keine Zahlenfolge finden, die die Zeile k) druckt:
21,......22,j,23
bewirkt
C[j]:-copy("xxx"xxx") ;
Hier fehlt ein ". Es kann nicht
durch Ausgabe des Textes C[24]
eingefügt werden, da es mitten
im Text von C[j] fehlt.
Das Einfügen der Zahl 24 in X kann nur dann zum Erfolg führen, wenn das Hochkomma am Anfang oder am Ende von C[j] steht. Vergleiche dazu die Programmzeilen 12),13) und 14) und die dazugehörenden Zahlengruppen im Text X.
text arrsy C
und einem text X. Sowohl die Komponenten von C als auch X
enthalten nur Textkonstanten. Eine Sonderstellung von X
ist also nicht aufrechtzuerhalten. Die Konsequenz: Wir
erweitern das Feld C um eine Komponente C[x]. C[x] bekommt
den Wert von X zugewiesen. Damit wird auch die algorithmische
Sonderstellung des Textes X aufgegeben. Die if-Anweisung
in der for-Schleife entfällt. Der ehemalige Text X,
der jetzt in C[x] steht, wird einfach durch Abarbeitung
der Zahl x ausgedruckt. x ist dabei selbst Element von
C[x].Führt man die Verbesserungen (i) bis (iii) an Programm
konsequent durch, so erhält man das folgende Programm
.
Die Feldkomponenten C[1] und C[3l] zeigen insbesondere
sehr schön die Bildung "maximaler" Texte (vgl.(i)).
begin integer I,S,Z; text array C[1:31]; C[1]:-COPY("BEGIN INTEGER I,S,Z; TEXT ARRAY C[1:31]; C[1]:-COPY("""); C[2]:-COPY("C["); C[3]:-COPY("]:-COPY("""); C[11]:-COPY(""");"); C[12]:-COPY(""""); C[13]:-COPY("1"); C[21]:-COPY("2"); C[22]:-COPY("3"); C[23]:-COPY("1,1,12,11, 2, 21,3, 2, 11, 2, 22,3, 3,12,11, 2,13,13,3,12,11, 11, 2,13,21,3,12,12, 11, 2,13,22,3, 13, 11, 2,21,13,3, 21, 11, 2,21,21,3, 22, 11, 2,21,22,3, 23, 11, 2,22,13,3, 31, 11,31,"); C[31]:-COPY("FOR I:=1 STEP 1 UNTIL 60 DO BEGIN S:=C[23].SUB (Z+1,2).GETINT;OUTTEXT(C[S]);Z:=(IF S<10 THEN 2 ELSE 3)+Z END END"); for I:=1 step 1 until 60 do begin S:=C[23].SUB(Z+1,2).GETINT; OUTTEXT(C[S]); Z:=(if S<10 then 2 else 3)+Z end end
Diese Version von
ist in ihrer logischen Funktionalität
nicht mehr zu verbessern. Strebt man aber "textuell" kurze
Programme an, so gibt es noch eine weitere Verbesserungsmöglichkeit:
| Adresse | Auftreten in C[23] | Zeichen insgesamt |
|---|---|---|
| 1 | 2 | 1 × 2 = 2 |
| 2 | 10 | 1 × 10 = 10 |
| 3 | 10 | 1 × 10 = 10 |
| 11 | 10 | 2 × 10 = 20 |
| 12 | 4 | 2 × 4 = 8 |
| 13 | 6 | 2 × 6 = 12 |
| 21 | 8 | 2 × 8 = 16 |
| 22 | 5 | 2 × 5 = 10 |
| 23 | 1 | 2 × 1 = 2 |
| 31 | 2 | 2 × 2 = 4 |
Um "optimal" zu adressieren, müssen wir erreichen, daß die 3 einstelligen Adressen am häufigsten auftreten. Wie die Tabelle zeigt, ist das bisher nicht, der Fall. Adresse 1 tritt nur 2-mal auf, während die zweistellige Adresse 11 10-mal auftritt. Wir erreichen eine "optimale" Adressierung, wenn wir die Inhalte von C[1] und G [11] vertauschen und den Inhalt von C[23] entsprechend korrigieren. Ersparnis: 8 Zeichen.

Das Programm
gibt seinen Programmtext über die
Standarddatei SYSOUT aus. Da diese Ausgabe in Form eines
einzigen Strings ohne jede Blockung erfolgt, reicht die
voreingestellte Pufferlänge von SYSOUT nicht aus. Die Pufferlänge
muß im Programm
erhöht werden, damit keine
Laufzeitfehler auftreten.
wird daher um die Anweisung
SYSOUT.IMAGE:-BLANKS(200);
ergänzt. Entsprechend wird die Textkonstante C[31] erweitert.
Das resultierende Programm
zeigt Anhang A.1..
Der zur Verfügung stehende SIMULA-Compiler hat die
Eingabelänge 72. Die Ausgabe von
bzw.
ließe sich nur
dann kompilieren, wenn sie in Blöcke zu jeweils höchstens
72 Zeichen unterteilt wäre. Dies ist aber weder bei
noch bei
der Fall. Anhang A.2. zeigt eine Version
von
, deren Ausgabe in Zeilen a 72 Zeichen unterteilt
ist. Dies wird durch einen komplizierten Anweisungsteil
erreicht. Die Ausgabe von
läßt sich erneut übersetzen.
Sie stellt ein lauffähiges SIMULA-Programm dar,
das gleich
ist.

In 3.2.5. wurde ein selbstreproduzierendes Programm
,
konstruiert, das seinen Text in Teilstrings zerlegt enthielt.
Diese Teilstrings brauchten von
nur noch in der
richtigen Reihenfolge ausgedruckt zu werden. In Form von
Programm
lernen wir nun ein selbstreproduzierendes
SIMULA-Programm kennen, das die Abspeicherung seiner Teilstrings
direkt mit der Ausgabe dieser Strings koppelt. Statt C[Adresse]:-copy("text"); in
schreiben wir procedure name;OUTTEXT("text"); in
,
Die Zerlegung des Programmtextes von
, entspricht dabei
der Zerlegung des Programmtextes von
. Der Algorithmus
von
besteht nur noch aus einer Folge von Prozeduraufrufen.
Mit Programm
lösen wir uns wieder vom eigentlichen
SIMUIA-Textkonzept. Wir benötigen lediglich die
Möglichkeit, Textkonstanten als Argumente für Ausgabeanweisungen
zu benutzen.
1) begin
2) procedure AA;OUTTEXT("BEGIN ");
3) procedure C;OUTTEXT("PROCEDURE ");
4) procedure A;OUTTEXT(";OUTTEXT(""");
5) procedure B;OUTTEXT(""");");
6) procedure AC;OUTTEXT("""");
7) procedure BA;OUTTEXT("A");
8) procedure BB;OUTTEXT("B");
9) procedure BC;OUTTEXT("C");
10) procedure AB;OUTTEXT("AA;C;BA;BA;A;AA;B;C;BC;A;C;B;C;BA
;A;A;AC;B;C;BB;A;AC;B;B;C;BA;BC;A;AC;AC;B;C;BB;BA;A;
BA;B;C;BB;BB;A;BB;B;C;BB;BC;A;BC;B;C;BA;BB;A;AB;B;AB
END");
11) AA;
12) C;BA;BA;A; AA; B;
13) C;BC; A; C; B;
14) C;BA; A; A;AC;B;
15) C;BB; A;AC; B; B;
16) C;BA;BC;A;AC;AC; B;
17) C;BB;BA;A; BA; B;
18) C;BB;BB;A; BB; B;
19) C;BB;BC;A; BC; B;
20) C;BA;BB;A; AB; B;
21) AB
22) end
Verifikation von 
AA; ist das erste statement des Anweisungsteils von
.
Es bewirkt die Ausgabe der ersten Programmzeile. Die nächsten
9 Programmzeilen werden durch, die Prozeduraufrufe der
9 Programmzeilen 12) bis 20) ausgegeben, was sich mit Hilfe
der tabellarischen Schreibweise des Anweisungsteils von
leicht nachvollziehen läßt. Das folgende und gleichzeitig
letzte statement ist ein Aufruf der Prozedur AB. Dieser Aufruf
bewirkt die Ausgabe der restlichen Programmzeilen 11)
bis 22), da die Textkonstante der Prozedur AB den algorithmischen
Teil, von
enthält. Durch Ausführung der Prozedur
AB holt die Ausgabe des Programms
die Ausführung von
ein.
(3.2.7.1) Bemerkung: Das selbstreproduzierende SIMULA-Program
benötigt als Daten nur Textkonstanten. Zur
Strukturierung verwendet
neben der Hintereinanderausführung
von Anweisungen nur das Prozedurkonzept. Insgesamt gesehen verwendet
nur
Elemente, die die meisten höheren Programmiersprachen
zur Verfügung stellen. Daher gesehen müssen dem
Programm
ähnelde selbstreproduzierende Programme
in fast allen höheren Programmiersprachen
existieren.

Für die Implementierung des Programms
gelten die gleichen
Bemerkungen, die zur Implementierung von
in 3.2.6.
gemacht wurden. Aus
läßt sich mit geringem Aufwand ein
lauffähiges selbstreproduzierendes Programm
gewinnen,
indem die Anweisung
SYSOUT.IMAGE:-BLANKS(200);
in den Anweisungsteil von
bzw. in die Textkonstante der
Prozedur AB engefügt wird.
Aus
läßt sich wie in 3.2.6. ein selbstreproduzierendes
Programm
ableiten, dessen Ausgabe so formatiert ist,
daß ein lauffähiges Programm entsteht. Erreicht wird dies
durch
procedure Q;OUTIMAGE;
AB auf die Prozeduren AB,CA,CB,CC,AAA und AABDie Ausgabe der zusätzlichen Prozeduren CA bis AAB bewirkt
einen vergrößerten Anweisungsteil in
.
Anhang A.3. und Anhang A.4. demonstrieren die aus
resultierenden Programme
bzw.
.
In diesem Abschnitt sollen selbstreproduzierende Programme
in der Programmiersprache PASCAL vorgestellt werden. PASCAL
ist neben der Tatsache, daß es nicht blockorientiert ist,
eine Programmiersprache, die keine Textvariablen kennt;
PASCAL sieht nur Textkonstanten vor. Von daher gesehen ist
es nicht ohne weiteres möglich, aus dem SIMULA-Programm
aus 3.2.5. ein entsprechendes selbstreproduzierendes PASCAL-programm
zu gewinnen. Auf Grund von Bemerkung (3.2.7.1) wird
es jedoch keine Schwierigkeiten bereiten, das Programm
aus 3.2.6. nach PASCAL zu übertragen.

Wir versuchen trotz des Fehlens von Textvariablen in PASCAL,
das Programm
in ein selbstreproduzierendes PASCAL-Programm
zu übertragen. Dazu gibt es verschiedene Möglichkeiten,
von denen zwei genannt sein sollen:
vorkommenden Texte durch
character arrays. Auf diese Weise wird das Feld C zweidimensional
var C : array [1..maxtext,1..maxlength] of char,wobei maxlength gleich der Länge des längsten Teilstrings ist, in die wir das PASCAL-Programm
zerlegen.
Jede Zeile von C beinhaltet genau einen String
der Zerlegung von
.
Nachdem die textuelle Speicherung der Zerlegung
geklärt ist, können wir uns dem algorithmischen Teil von
zuwenden. Da keine Texte und somit auch keine
Prozedur GETINT zur Verfügung stehen, behelfen wir uns wie
folgt:
Wir kodieren jeden "Text" C[j,...] durch einen Buchstaben des Alphabets in der folgenden Weise:
![\begin{array}{lcl}
\text{C[1,\dots]}&\longr&a\\
\text{C[2,\dots]}&\longr&b\\
\text{C[3,\dots]}&\longr&c\\
\text{C[4,\dots]}&\longr&d\\
\vdots&&\vdots\\
\text{C[maxtext,..]}&\longr&\text{maxtext-ter Buchstabe.}
\end{array}](/img/cache/a1989ff6967007a06cc83b987f10a499.gif)
Der Programmtext
läßt sich mittels der Zeilen von
C zusammensetzen und daher auf eindeutige Weise durch
eine endliche Folge von Buchstaben beschreiben. Diese
Buchstabenfolge ist der Inhalt von C[maxtext,...].
Der Algorithmus braucht dann nur noch diese Buchstabenfolge
in eine Folge von Druckanweisungen umzusetzen:
for I: = 1 to <Länge von C[maxtext,...]> do
begin case C[maxtext,I] of
'a' : <Ausgabe von C[1,...]>
'b' : <Ausgabe von C[2,...]>
.
.
.
.
.
end
Leider treten auf den linken Seiten der case-Alternativen
viele Hochkommata ' auf. Das Zeichen ' spielt in
PASCAL die gleiche Rolle wie das Zeichen " in der
Programmiersprache SIMULA. Der Algorithmus müßte also als
Text in sehr viele Teilstrings zerlegt werden (vgl.
3.2.5.), was zu einem unüberschaubaren Programm führen
würde. Einen Ausweg bietet die Transferfunktion ORD
von char nach integer:
for I: = 1 to <Länge von C[maxtext,...]> do
begin HELP:=ORD(C[maxtext,I])
case HELP of
<ORD(a)> : <Ausgabe von C[1,...]>
<ORD(b)> : <Ausgabe von C[2,...]>
.
.
.
.
.
end
Die Realisierung von
nach der bisher entworfenen
Methode enthält noch einige Schwierigkeiten. Z.B.:
,
enthalten sein.Insgesamt würde ein durchaus korrektes, aber auch
unübersichtliches Programm
entstehen.
nicht in
einem, zweidimensionalen character array, sondern wir
verwenden die implizite Speicherung mittels Ausgabeprozeduren
wie im SIMULA-Programm
aus 3.2.7.
Der Algorithmus von
bleibt der gleiche wie der
Algorithmus unter (i), wenn man statt der Zeilen von
C nur die Ausgabeprozeduren durch Buchstaben kodiert.
Bei der Realisierung von
durch Alternative (ii) bleibt
das Programm überschaubar. Mit

und der Kodierung

ergibt sich:
= program SELF(OUTPUT); var I,HELP : integer; X : array [1..72] of char; procedure A; begin WRITE('PROGBAM SELF(OUTPUT);VAR I,HELP : INTEGER; X : ARRAY [1..72] OF CHAR;') end; procedure B; begin WRITE(''';F0R I:=1 TO 72 DO BEGIN HELP :=ORD(X[I]); CASE HELP OF 193:A;194:B;195:C;196:AA;197 :AB;198:AC;199:BA;200:BB;201:BC;202:CA;203:CB; END; END; WRITELN END.') end; procedure C; begin WRITE('PROCEDURE ') end; procedure AA;begin WRITE('; BEGIN WRITE(''') end; procedure AB;begin WRITE(''') END;') end; procedure AC;begin WRITE('''') end; procedure BA;begin WRITE('A') end; procedure BB;begin WRITE('B') end; procedure BC;begin WBITE('C') end; procedure CA;begin WRITE('BEGIN X:=''') end; procedure CB;begin WRITE('ACGDAECHDFBECIDCECGGDDFECGHDFEE CGIDFFECHGDGECHHDHECHIDIECIGDJF ECIHDKEJKB') end; begin X:='ACGDAECHDFBECIDCECGGDDFECGHDFEECGIDFFECHGDGECHHDHECHIDIECIGDJFECIHDKEJKB'; for I: = 1 to 72 do begin HELP:=ORD(X[I]); case HELP of 193 : A; 194 : B; 195 : C; 196 : AA; 197 : AB; 198 : AC; 199 : BA; 200 : BB; 201 : BC; 202 : CA; 203 : CB; end; end; WRITELN end.
Verifikation von 
Die Bedeutung der for-Schleife von Programm
wurde oben
erläutert. Für jeden Buchstaben der Textkonstanten X wird
eine Alternative der case-Anweisung ausgeführt und somit
ein String der Zerlegung des Programmtextes von
ausgegeben.
Einfaches Nachvollziehen der Abarbeitung von X
bestätigt, daß
sich, selbst reproduziert (vgl. Verifikation
von
).

wird so implementiert, daß die Ausgabe von
in
Zeilen zu höchstens 132 Zeichen formatiert ist. Daher wird
zunächst die Prozedur
procedure Q; begin WRITELN end;
in
eingefügt.
Die Prozeduren A und B werden wegen ihrer relativ langen Textkonstanten in mehrere Prozeduren aufgespalten:

Die zusätzlichen Prozeduren bewirken eine Verlängerung
der Kodierung von
. Dadurch wird eine Aufspaltung der
Prozedur CB ebenfalls notwendig:

In
enthält die Variable X die Kodierung des Programms.
Die neu hinzugekommenen Prozeduren verursachen eine solche
Zunahme der Kodierung, daß eine Variable (bedingt durch
die vorhandene PASCAL-Implementierung) nicht mehr ausreicht,
um die Kodierung aufzunehmen. Es wird neben X die Variable
Y : array [1..68] of char zur Aufnahme der Kodierung von
notwendig, was die Einführung der Prozedur CCA bewirkt.
Der Algorithmus wird entsprechend geändert. Anhang A.5.
zeigt das so veränderte Programm
im einzelnen. Die
neuen Prozeduren sind dort wie folgt kodiert:


Alle in Programm
aus Abschnitt 3.2.7. verwendeten
Sprachelemente finden sich auch in der Programmiersprache
PASCAL. Damit läßt sich
direkt in ein selbstreproduzierendes
PASCAL-Programm
übersetzen.
= program PI6(OUTPUT); procedure AA;begin WRITE('PROGRAM PI6(OUTPUT); PROCEDURE AA; BEGIN WRITE(''') end; procedure C;begin WRITE('PROCEDURE ') end; procedure A;begin WRITE('; BEGIN WRITE(''') end; procedure B;begin WRITE(''') END;') end; procedure AC;begin WRITE('''') end; procedure BA;begin WRITE('A') end; procedure BB;begin WRITE('B') end; procedure BC;begin WRITE('C') end; procedure AB;begin WRITE('BEGIN AA;AA;AC;B;C;BC;A;C;B;C;BA ;A;A;AC;B;C;BB;A;AC;B;B;C;BA;BC;A;AC;AC;B;C;BB;BA;A;BA;B ;C;BB;BB;A;BB;B;C;BB;BC;A;BC;B;C;BA;BB;A;AB;B;AB;WRITELN END') end; begin AA; AA;AC;B; C;BC; A; C; B; C;BA; A; A;AC;B; C;BB; A;AC; B; B; C;BA;BC;A;AC;AC; B; C;BB;BA;A; BA; B; C;BB;BB;A; BB; B; C;BB;BC;A; BC; B; C;BA;BB;A; AB; B;AB;WRITELN end.
Verifikation von 
Die Verifikation von
ergibt sich direkt aus der
Verifikation von
in 3.2.7.

Programm
schreibt seinen Text hintereinander ohne
Blockung auf die Ausgabedatei OUTPUT. Das Ergebnis von
ist ein einziger String. Dieser String ist sowohl für den
Puffer des SIEMENS-Schnelldruckers, als auch für den Puffer
des PASCAL-Compilers zu lang. Der String kann also weder
ausgedruckt noch erneut kompiliert werden.
Um ein sichtbares Ergebnis zu erhalten, benötigen wir
eine Ausgabe, die in Blöcke von höchstens 132 (=Pufferlänge
des Schnelldruckers) Zeichen unterteilt ist. Es muß also in
das Programm
wiederholt die Prozedur WRITELN eingefügt
werden. Wir kürzen die Prozedur wie folgt ab:
procedure Q; begin WRITELN end;
Da mit dieser Prozedurvereinbarung der Vereinbarungsteil von
größer wird, muß die Prozedur AA entsprechend
ageändert werden. Die lange Textkonstante von Prozedur AB
wird auf zwei Prozeduren verteilt. Zu diesem Zweck muß eine
weitere Prozedur CA in das Programm aufgenommen werden.
Anhang A.6. protokolliert das so veränderte Programm
.
In diesem Abschnitt werden Beispiele für selbstreproduzierende Programme in einer Assembler-Sprache angegeben. Die Beispiele verwenden den SIEMENS-Asserabler. Die Tatsache, daß Assembler-Programme in der Lage sind, den Speicherbereich, in dem sie sich befinden, zu adressieren und zu lessen, vereinfach das Schreiben selbstreproduzierender Assembler-Programme bedeutend. Selbstreproduzierende Proramme in Assembler brauchen nicht ihren Programmtext ebenfalls in Assembler auszugeben, sondern können direkt ihren Maschinenkode im Arbeitsspeicher kopieren (vgl.1.2.).
Alle in den folgenden Beispielen vorkommenden Adressierungen beziehen sich auf den Programmzähler PCR und sind somit relativ. Dadurch wird gewährleistet, daß die Funktionen der Kopien die gleichen sind wie die der jeweiligen Ursprungsprogramme. Die Kopien sind daher ebenfalls selbstreproduzierend.
Die Beispielprogramme sind soweit erläutert, wie es der Rahmen dieser Arbeit zuläßt. Nähere Angaben bzgl. des SIEMENS-Assemblers entnehme man den Schriften [22] und [23].
| Zeilennummer | Name | mnemot. Op.-Kode | Operanden | Befehlsformat | Befehlslänge (in Byte) | |
|---|---|---|---|---|---|---|
| 01 | PROG1 | START | ||||
| 02 | BALR | 1,00 | RR | 2 | ||
| 03 | LA | 2,2(0,0) | RX | 4 | ||
| 04 | SR | 1,2 | RR | 2 | ||
| 05 | LM | 4,8,0(1) | RS | 4 | ||
| 06 | STM | 4,8,64(1) | RS | 4 | ||
| 07 | SVC | X'5B' | RR | 2 | ||
| 08 | END | |||||
| Programmlänge in Byte 18 | ||||||
Die beiden Assembler-Anweisungen START und END
erzeugen keinen Maschinenkode und brauchen daher beim
Kopierprozeß nicht berücksichtigt zu werden.
Der erste ausführbare Befehl des Programms ist
BALR 1,00
Dieser Befehl lädt in das Mehrsweckregister R1 den aktuellen Wert des Befehlszählers PCR. Da der Befehlszähler vor Ausführung eines Befehls um die Länge des betreffenden Befehls hochgezählt wird, enthält Register R1 nach Ausführung des BALR-Befehls die Startadresse von PROG1 im Arbeitsspeicher plus der Länge des BALR-Befehls. Der BALR-Befehl hat das Format RR und somit die Länge 2. Der Befehl
LA 2,2(0,0)
stellt in Register R2 die Zahl 2 bereit. Der SR (Subtrahieren Register)-Befehl
SR 1,2
subtrahiert den Inhalt des Registers R2 vom Inhalt des Registers R1. Nach Ausführung dieses Befehls enthält demnach Register R1 genau die Startadresse des Programms. R1 wird nachfolgend als Basisregister verwendet. Der Befehl in Zeile 05 ist ein LM(Laden mehrfach)-Befehl
LM 4,8,0(1)
LM-Befehle können aufeinanderfolgende Mehrzweckregister - also höchstens 16 - mit aufeinanderfolgenden Worten aus dem Arbeitsspeicher laden. Die ersten beiden Operanden bezeichnen das erste und das letzte der benutzten Mehrzweckregister. Der letzte Operand stellt die Adresse des ersten der zu transferierenden Arbeitsspeicherworte dar. In unserem Fall ist diese Adresse die Startadresse von PROG1. Deshalb wird der dritte Operand aus der Distanzadresse 0 und dem Register R1 als Basisregister zusammengesetzt. Das Programm PPOG1 umfaßt 18 Bytes. Da ein Arbeitsspeicherwort 4 Bytes umfaßt, genügen also die 5 Mehrzweckregister R4 bis R8, um das gesamte Programm zu laden. Der nächste Befehl
STM 4,8,64(1)
ist ein STM(Speichern mehrfach)-Befehl. Dieser Befehl ist das Gegenstück zum LM-Befehl und legt die Inhalte der Register R4 bis R8 beginnend bei der Adresse, die der dritte Operand angibt, hintereinander im Arbeitsspeicher ab. Der dritte Operand des STM-Befehls benutzt wieder das Register R1 als Basisregister, die Distanzadresse ist 64. Nach Ausführung des STM-Befehls liegt also die Kopie von PROG1 bereits im Arbeitsspeicher vor. Sie ist 64 Bytes vom Ursprungsprogramm entfernt. Der letzte Befehl
SVC X'5B'
dient nur dazu, PROG1 ordnungsgemäß zu beenden. Ein ausführliches Protokoll von PPOG1 befindet sich in Anhang B.1..
Das folgende Beispielprogramm PROG2 ist um 2 Bytes kürzer als PROG1. Erreicht wird dies durch Ersetzung des LM- und des STM-Befehls durch einen MVC(übertragen Zeichenfolge)-Befehl. PPOG2 ist in der Lage, außer sich selbst noch einen gewissen, auf das Programm folgenden Speicherbereich mitzukopieren.
| Zeilennummer | Name | mnemot. Op.-Kode | Operanden | Befehlsformat | Befehlslänge (in Byte) | |
|---|---|---|---|---|---|---|
| 01 | PROG2 | START | ||||
| 02 | BALR | 1,00 | RR | 2 | ||
| 03 | LA | 2,2(0,0) | RX | 4 | ||
| 04 | SR | 1,2 | RR | 2 | ||
| 05 | MVC | 64(60,1),0(1) | SS | 6 | ||
| 06 | SVC | X'5B' | RR | 2 | ||
| 07 | END | |||||
| Programmlänge in Byte 16 | ||||||
Die Programmzeilen 01 bis 04 sind mit denen von PROG1 identisch. Sie bewirken, daß die Startadresse in das Register R1 geladen wird. Der MVC-Befehl in Zeile 05 bewirkt, daß beginnend bei der Adresse
Inhalt des Basisregisters R1 } vgl. 2-ter plus Distanzadresse 0 } Operand 60 aufeinanderfolgende Bytes des } Arbeitsspeichers in den mit der } Adresse } vgl. 1-ter Inhalt des Basisregisters R1 } Operand plus Distanzadresse 64 }
beginnenden Arbeitsspeicherbereich geschrieben
werden. Da PROG2 selbst nur 16 Bytes lang ist,
werden durch den MVC-Befehl 44 zusätzliche Bytes
mitkopiert. Mit einem MVC-Befehl lassen sich sogar
maximal
Bytes transferieren, wenn die Operandenlänge
entsprechend angegeben wird (im Beispiel:
60).
Die Programmzeilen 06 und 07 entsprechen den Zeilen 07 und 08 in PROG1. Rechnerprotokoll siehe Anhang B.2..
Die Zeilen 02 bis 05 von PROG2 stellen einen Programmteil
dar, durch den sich andere Assemblerprogrammabschnitte
(oder ganze Programme) zu selbstreproduzierenden Programmen
(bzw. Programmabschnitten) ergänzen lassen (siehe
Abb. 4.4.A). Die Länge des resultierenden Programmabschnitts
in Byte) wird als Operandenlänge für den MVC-Befshl
verwendet. Auf diese Weise können Programmabschnitte (bzw.
Programme) bis zu einer Länge von
Bytes im Arbeitsspeicher
kopiert werden. Entsprechend der Länge des Programmabschnitts
muß die Distanzadresse, die die Lage der Kopie
bestimmt, gewählt werden.

Abb. 3.4.A.
Das folgende Beispielprogramm PPOG3 ist ein selbstreproduzierendes Assembler-Programm, das nach seiner Abarbeitung die Kontrolle an die Kopie übergibt. Erreicht wird dies durch einen unbedingten Sprung zur Startadresse der Kopie. Da die Kopie das gleiche Verhalten zeigt wie PROG3, iteriert sich dieser Prozeß. Der zur Verfügung stehende Arbeitsspeicher wird also mit Kopien von PPOG3 vollgeschrieben. Die einzelnen Kopien folgen mit konstantem Abstand aufeinander.
| Zeilennummer | Name | mnemot. Op.-Kode | Operanden | Befehlsformat | Befehlslänge (in Byte) | |
|---|---|---|---|---|---|---|
| 01 | PROG3 | START | ||||
| 02 | BALR | 1,00 | RR | 2 | ||
| 03 | LA | 2,2(0,0) | RX | 4 | ||
| 04 | SR | 1,2 | RR | 2 | ||
| 05 | MVC | 64(60,1),0(1) | SS | 6 | ||
| 06 | LA | 2,64(0,0) | RX | 4 | ||
| 07 | AR | 1,2 | RR | 2 | ||
| 08 | BR | 1 | RR | 2 | ||
| 09 | END | |||||
| Programmlänge in Byte 22 | ||||||
Die Zeilen 01 bis 05 sind mit denen von Programm PROG2 identisch und bewirken bereits das Kopieren von PPOG3. Die Kopie wird beginnend beim 64-ten auf den ersten Befehl von PROG3 folgenden Byte im Arbeitsspeicher abgelegt. Der LA(Laden Adresse)-Befehl in Zeile 06
LA 2,64(0,0)
stellt in Register R1 die Zahl 64 bereit. Der folgende AR(Addierer Register)-Befehl
AR 1,2
erhöht den Inhalt des Basisregisters R1 um 64. R1 enthält nach Abarbeitung des AR-Befehls die Startadresse der Kopie. Daher erfolgt durch den BR(Spribgen unbedingt)-Befehl
BR 1
ein Sprung zum ersten Befehl der Kopie und damit die Abarbeitung der Kopie. Die Kopie legt darauf eine erneute Kopie an u.s.w.
Anhang B.3. demonstriert PROG3. Da PROG3 eine nicht abbrechende Programmfolge erzeugt, kommt es wegen Speichererschöpfung zu einem Fehlerabbruch.
In den vorangegangenen Beispielprogrammen erfolgte das Kopieren der Programme en bloc mit Hilfe des MVC-Befehls bzw. des LM- und des STM-Befehls. Das folgende Beispiel zeigt ein Programm, das seinen Kode explizit in Abschnitten zu je 4 Bytes kopiert. Dieses Programm ist algorithmisch etwas aufwendiger und dementsprechend länger als die bisherigen Beispielprogramme dieses Abschnitts.
| Zeilennummer | Name | mnemot. Op.-Kode | Operanden | Befehlsformat | Befehlslänge (in Byte) | |
|---|---|---|---|---|---|---|
| 01 | PROG4 | START | ||||
| 02 | BALR | 1,00 | RR | 2 | ||
| 03 | LA | 2,2(0,0) | RX | 4 | ||
| 04 | SR | 1,2 | RR | 2 | ||
| 05 | LA | 3,4(0,0) | RX | 4 | ||
| 06 | LA | 4,48(0,0) | RX | 4 | ||
| 07 | LA | 10,22(0,0) | RX | 4 | ||
| 08 | AR | 10,1 | RR | 2 | ||
| 09 | MVC | 64(4,1),0(1) | SS | 6 | ||
| 10 | AR | 1,3 | RR | 2 | ||
| 11 | SR | 4,3 | RR | 2 | ||
| 12 | BRP | 10 | RR | 2 | ||
| 13 | SVC | X'5B | RR | 2 | ||
| 14 | END | |||||
| Programmlänge in Byte 36 | ||||||
Die Befehle der Programmzeilen 02 bis 04 bewirken, daß das Register R1 die Anfangsadresse von PROG4 im Arbeitsspeicher enthält. Register R1 wird fortan als Basisregister benutzt. Die Befehle der Zeilen 05 bis 07 stellen in den Mehrzweckregistern R3, R4 und R10 die Werte 4, 48 und 22 bereit. 48 ist die Gesamtzahl der Bytes, die das Programm PPOG4 im Arbeitsspeicher kopiert. Der Befehl
AR 10,1
erhöht den Inhalt des Registers R10 um die Startadresse des Programms PROG4. Nach Ausführung dieses AR-Befehls enthält Register R10 die Sprungadresse, zu der der BRP(Springen, falls positiv)-Befehl in Zeile 12 verzweigt. Es handelt sich dabei um die Adresse des MVC-Befehls
MVC 64(4,1)0(1)
in Programmzeile 09. Der MVC-Befenl kopiert die ersten 4 Bytes des Maschinenkodes von PROG4 im Arbeitsspeicher. Die Kopie wird 64 Bytes vom ersten Befehl von PROG4 entfernt angelegt. Der MVC-Befehl benutzt zur Adressierung das Basisregister R1. Der Inhalt von R1 wird im darauffolgenden Befehl
AR 1,3
um den Inhalt des Registers R3, also nur den Wert 4, erhöht. Der nächste Befehl
SR 4,3
subtrahiert vom Inhalt des Registers R4, der gleich der momentanen Anzahl der noch, zu kopierenden Bytes ist, den Wert 4. Hat diese Subtraktion einen positiven Wert ergeben, so sind noch nicht alle der insgesamt 48 Bytes kopiert, und es wird mittels
BRP 10 (s.o.)
zum MVC-Befehl in Zeile 09 zurückgesprungen. Der MVC-Befehl kopiert dann die nächsten 4 Bytes von PROG4, da das Basisregister R1 bereits um 4 Bytes erhöht worden ist. Das Programm bricht ab, nachdem alle 48 Bytes kopiert worden sind. Da PROG4 nur 36 Bytes lang ist, werden also 12 zusätzliche, sich an PROG4 anschließende Bytes mitkopeirt. Der Befehl
SVC X'5B'
in Zeile 13 beendet PROG4. Anhang B.4. demonstriert PROG4.
Entsprechend PROG2 in Beispiel (3.4.2) lassen sich durch die Zeilen 01 bis 12 größere Abschnitte anderer Assembler-Programme (bzw. ganze Programme) zu selbstreproduzierenden Programmabschnitten (bzw. Programmen) ergänzen (siehe Abb. 3.4.B. Die Selbstreproduktion erfolgt jedoch nicht en sondern in Abschnitten zu je 4 Bytes. Die Länge des ergänzten Abschnitts (bzw. Programms) in Byte braucht dann nur durch den Befehl in Zeile 06 in Register R4 bereitgestellt zu werden. Entsprechend der Länge des zu kopierenden Programmabschnitts (bzw. Programms) muß die Distanzadresse, die die Lage der Kopie im Arbeitsspeicher bestimmt, in Zeile 09 (MVC-Befehl) gesetzt werden.

Abb 3.4.B
Im Gegensatz zu der aus PPOG2 abgeleiteten Methode zur
Selbstreproduktion größerer Programmabschnitte lieg keine
Begrenzung auf
Bytes vor.
In diesem Kapitel sei S eine beliebige höhere Programmiersprache im üblichen Sinn (vgl. 1.2.).
In Abschnitt 1.2. haben wir eine Definition selbstreproduzierender Programme angegeben. Diese Definition lautete singemäß:
Sei
aus S.
heißt selbstreproduzierend, wenn
ohne
Benutzung von Eingabe seinen Programmtext in S ausgibt.
Betrachtet man diese Definition etwas differenzierter, so
ergeben sich zwei. Anforderungen an die Ausgabe eines selbstreproduzierenden.
Programms
aus S:
muß ein syntaktisch korrektes Programm
aus der Programmiersprache S enthalten.
muß gleich
sein.Läßt man die Forderung b) fallen, so ist das Programm i.a. nicht mehr selbstreproduzierend; es ist allenfalls als "reproduzierend" zu bezeichnen.
Sei nun
"reproduzierend", dann sind zum Beispiel folgende
Möglichkeiten denkbar:
gibt das Programm
aus.
seinerseits gibt das Programm
aus, und es gilt
.
und
sind dann sicher für sich nicht selbstreproduzierend.
Trotzdem liegt aber ein gewisser Selbstreproduktionsmechanismus mit "Zwischenstufe" vor.
gibt das Programm
aus,
seinerseits das Programm
u.s.w.. Allgemein:
gibt
aus,
.
Für alle
gilt
, falls
.Andererseits könnte man die obige Definition der Selbstreproduktion verschärfen, indem man gewisse Zusatzforderungen stellt.
Insgesamt sind also einige interessante Varianten zur Selbstreproduktion denkbar. Einige dieser Varianten sollen in diesem Kapitel präsentiert und in bezug auf die realen Programmiersprachen SIMULA und PASCAL an Hand von Beispielen erläutert werden.
(4.2.1) Definition: Sei
ein (syntaktisch korrektes)
Programm aus S.
keine Eingabe auf, so heißt
(streng) reproduzierend, wenn
(genau)
ein syntaktisch korrektes Programm
aus
S ausgibt.
Eingabe auf, so heißt
(streng)
reproduzierend, wenn
bei jeder zulässigen
Eingabe (genau) ein syntaktisch korrektes Programm
aus S ausgibt.(4.2.2) Bemerkung: Jedes (streng) selbstreproduzierende Programm ist selbstverständlich (streng) reproduzierend.
Aus (4.2.2) folgt, daß es in den Programmiersprachen SIMULA und PASCAL reproduzierende Programme gibt, da in diesen Sprachen selbstreproduzierende Programme existieren.
(4.2.3) Lemma: In den Programmiersprachen SIMULA und PASCAL existieren unendlich viele reproduzierende Programme, die nicht selbstreproduzierend sind.
Beweis:
ist das SIMULA-Programm
reproduzierend, da die Textkonstante, die von= begin OUTTEXT("BEGIN INTEGER I; I:=k; OUTINT(k, <Stelligkeit von k>) END") end
ausgegeben wird, ein gültiges SIMULA-Programm
darstellt.= program T(OUTPUT); begin WRITE('PROGRAM T(OUTPUT); BEGIN WRITE(k) END.') end.
(4.2.4) Definition: Sei
eine
(unendliche) Folge von Programmen aus der Programmiersprache
S.
heißt Reproduktionsfolge,
falls gilt
reproduziert
für alle
.
Aus (4.2.4) folgt, daß jedes Programm einer Reproduktionsfolge als Startprogramm einer neuen Reproduktionsfolge aufgefaßt werden kann. Man braucht nur die entsprechende Teilfolge zu bilden. Dies rechtfertigt die folgende Definition.
(4.2.5) Definition: Sei
eine Reproduktionsfolge
aus der Programmiersprache S. Sei
, ein
Element dieser Folge.
heißt unendlich reproduzierend.
von
mit
für alle
heißt die
Reproduktionsfolge von
.
Abb.: 4.2.A
(4.2.6) Bemerkung: Jedes selbstreproduzierende Programm
ist unendlich reproduzierend. Die Reproduktionsfolge
von
ist konstant.
(4.2.7) Satz: Es existiert ein unendlich reproduzierendes PASCAL-Programm, in dessen Reproduktionsfolge kein Programm mehrfach vorkommt.
Satz (4.2.7) wird durch das folgende Beispielprogramm
,
das den Forderungen des Satzes genügt, bewiesen.
(4.2.8) Beispiel:
= program UR(OUTTPUT); var I,K : integer; procedure Z(J : integer); begin WRITE(J+1) end; procedure AA; begin WRITE('PROGRAM UR(OUTPUT); VA R I,K : INTEGER; PROCEDURE Z(J : INTEGER); BEG IN WRITE(J+1) END; PROCEDURE AA; BEGIN WRITE(' '') end; procedure C; begin WRITE('PROCEDURE ') end; procedure A; begin WRITE('; BEGIN WRITE(''') end; procedure B; begin WRITE(''') END;') end; procedure AC; begin WRITE('''') end; procedure BA; begin WRITE('A') end; procedure BB; begin WRITE('B') end; procedure BC; begin WRITE('C') end; procedure CA; begin WRITE('BEGIN K:=') end; procedure AB; begin WRITE(';FOR I:=1 TO K DO BEGI N WRITELN(I,I*I,I*I*I) END;AA;AA;AC;B;C;BC;A;C ;B;C;BA;A;A;AC;B;C;BB;A;AC;B;B;C;BA;BC;A;AC;AC ;B;C;BB;BA;A;BA;B;C;BB;BB;A;BB;B;C;BB;BC;A;BC; B;C;BC;BA;A;CA;B;C;BA;BB;A;AB;B;CA;Z(K);AB;WRI TELN END.') end; begin K:=0; for I:=1 to K do begin WRITELN(I,I*I,I*I*I) end; AA;AA;AC;B; C;BC; A; C; B; C;BA; A; A;AC;B; C;BB; A;AC;B; B; C;BA;BC;A;AC;AC; B; C;BB;BA;A; BA; B; C;BB;BB;A; BB; B; C;BB;BC;A; BC; B; C;BC;BA;A; CA; B; C;BA;BB;A; AB; B;CA;Z(K);AB; WRITELN end.
ist ein unendlich reproduzierendes Programm, in dessen
Reproduktionsfolge kein Programm mehrfach auftritt.
Verifikation:
entspricht im wesentlichen dem selbstreproduzierenden
programm
aus 3.3.2. Daß
nicht ebenfalls selbstreproduzierend
ist, wird durch Erhöhung der Obergrenze der Laufvariablen
I um 1 in der Kopie
von
verhindert. Diese
Erhöhung wird durch Aufruf der Prozedur Z erreicht, deren
Text in den Programmkopf integriert ist. Durch die Erhöhung
der Obergrenze der Laufvariablen, ist die Kopie von
sowohl
textuell, als auch im Hinblick auf die Bedeutung des
Programms, von
verschieden. Da die Kopie sich lediglich
in einer integer-Konstanten von
unterscheidet, bleibt
sie ein lauffähiges reproduzierendes Programm. In gleicher
Weise unterscheidet sich die Kopie
des Programms
von
. Die Obergrenze der Laufvariablen I hat in
einen
um 2 größeren Wert als in
. Insgesamt gilt:
ist ein unendlich reproduzierendes Programm. In jedem
Element
, der Reproduktionsfolge von
hat die Obergrenze
der Laufvariablen I den Wert j.
(4.2.9) Bemerkung:
sind reproduzierend, aber
nicht streng reproduzierend. Aus den Programmen
lassen sich aber durch Streichung der Anweisung
WRITELN(I,I*I,I*I*I)streng reproduzierende Programme gewinnen. Satz (4.2.7) ließe sich also in dieser Hinsicht auch schärfer formulieren.
gewonnenen Reproduktionsfolge
enthalten alle den kompletten Selbstreproduktionsmechanismus
von Programm
aus 3.3.2. Gefordert
war jedoch nur eine schwächere Eigenschaft,
nämlich Reproduktion. Um nur Reproduktion zu erhalten,
hatten wir den Selbstreproduktionsmechanismus
durch Hinzunahme des zusätzlichen Programmteils
for I:=1 to ... do begin ... endabgeschwächt. Diese Vorgehensweise erscheint auf den ersten Blick widersinnig zu sein. Die Programme der Folge
benötigen aber anscheinend den
Selbstreproduktionsmechanismus, um unendlich viele
voneinander verschiedene syntaktisch korrekte
Programme zu erzeugen. Wünschenswert wäre eine
Reproduktionsfolge mit Programmen, die mit schwächeren
Mechanismen als dem Selbstreproduktionsmechanismus
auskommen. Die Schwierigkeit, solche Folgen zu finden,
kann als Hinweis darauf interpretiert werden,
daß unendlich viele sukzessive auseinander hervorgehende
Programme irgendwie "dicht" beieinander
liegen müssen; so dicht, daß "Quasi-Selbstreproduktion"
nötig ist, um sie überhaupt zu erzeugen.
enthält nur Sprachkonzepte, die auch
in der Programmiersprache SIMULA enthalten sind.
Daher läßt sich Satz (4.2.7) auch entsprechend für
die Programmiersprache SIMULA formulieren.
Programm
schreibt seine gesamte Ausgabe unformatiert in
eine Zeile. Diese Zeile ist sowohl für den Puffer des
Schnelldruckers als auch für den Eingabepuffer des PASCAL-Compilers
zu lang. Für eine ausreichende Demonstration des
Programms
ist es aber wünschenswert, die Ausgabe von
, nämlich
, zu übersetzen und auszuführen. Wir
verfahren deshalb wie in 3.3.3. und führen zur Formatierung
der Eingabe die Prozedur Q ein:
procedure Q; begin WRITELN end;
Die relativ lange Textkonstante aus Prozedur AB wird auf
4 Prozeduren aufgespalten. Zu diesem Zweck werden die
Prozeduren AAA, CB und CC zusätzlich in das Programm aufgenommen.
Anhang A.7. demonstriert das so veränderte Programm
.
(4.3.1) Definition: Sei
ein unendlich reproduzierendes
Programm aus der Programmiersprache S. Sei
die Reproduktionsfolge von
.
mit
, so heißt
zyklisch
selbstreproduzierend.
zyklisch selbstreproduzierend, so heißt das
kleinste
mit
die Zykluslänge von
.
Abb.: 4.3.A
(4.3.2) Bemerkung: Jedes Programm
aus der Reproduktionsfolge
eines zyklisch selbstreproduzierenden Programms
ist zyklisch selbstreproduzierend und
hat die gleiche Zykluslänge wie
.
(4.3.3) Satz: In der Programmiersprache PASCAL existiert für
jedes
ein zyklisch selbstreproduzierendes Programm
mit der Zykluslänge k.
Beweis: Das PASCAL-Programm
aus 4.3. ist unendlich
reproduzierend. Man kann aber sehr einfach aus
ein
zyklisch selbstreproduzierendes Programm
für
jedes
herleiten, indem man
procedure Z(J : integer); begin WRITE(J+1) end;
durch
procedure Z(J : integer); begin WRITE((J+1) mod k) end;
ersetzt.
Die Programme aus der Reproduktionsfolge von
unterscheiden sich gerade in dem von Z ausgegebenen
Wert. Die geänderte Prozedur Z stellt sicher, daß
für jedes
gilt
. Mit
als
gilt der Satz.
Wir wollen noch ein Beispiel für zyklisch selbstreproduzierende Programme angeben.
(4.3.4) Beispiel: Das folgende Programm
ist, abgesehen
von einigen Umbenennungen, eine Abwandlung von
aus Abschnitt 3.3.2.
soll sich erst nach einem
Zyklus von N = 9 Schritten selbstreproduzieren. Dies
wird dadurch erreicht, daß
einige seiner
Prozeduren in einer anderen Reihenfolge ausgibt. Das
resultierende Programm
verfährt mit den
Prozeduren in analoger Weise. Erst nach 9 Schritten
ist die Ausgangskonstellation der Prozeduren erreicht
und
liegt wieder vor.
hat gegenüber
einen erweiterten
Vereinbarungsteil durch:
integer I,K; procedure Z(J : integer); begin WRITE(J) end;
druckenden Prozedur in zwei Prozeduren BC
und CA.Der Anweisungsteil von
muß bewirken, daß sich
die direkte Kopie
von
unterscheidet.
Erst nach 9 Schritten darf
wieder hergestellt
sein. Der Anweisungsteil von
muß in allen
Kopien "fast" der gleiche, aber doch variabel sein.
Daher kann der Anweisungsteil von
nicht en
bloc kopiert werden. Daraus resultiert auch die
unter (ii) angegebene Aufspaltung. Mit den folgenden
Prozeduraufrufen wird der Algorithmus von
und seiner Kopien angegeben.

= program ZYKLUS(OUTPUT); var I,K : integer; procedure Z(J : integer); begin WRITE(J) end; procedure A; begin WRITE('PROGRAM ZYKLUS(OUTPUT); VAR I,K : INTEGER;PROCEDURE Z(J : INTEGER); BEGIN WRITE(J) END; PRO CEDURE A; BEGIN WRITE('') end; procedure B; begin WRITE(PROCEDURE ') end; procedure C; begin WRITE('; BEGIN WRITE(''') end; procedure AA; begin WRITE(''') END;') end; procedure AB; begin WRITE('''') end; procedure AC; begin WRITE('A') end; procedure BA; begin WRITE('B') end; procedure BB; begin WRITE('C') end; procedure BC; begin WRITE(BEGIN A;A;AB;AA;K:=') end; procedure CA; begin WRITE('; FOR I:=1 TO 9 DO BEGIN B;CASE K OF 0:BEGIN BA;C;B END;1:BEGIN BB;C;C;BA END;2:BEGIN AC;AC ;C;AB;AA END;3:BEGIN AC;BA;C;AB;AB END;4:BEGIN AC;BB;C;AC END;5:BEGIN BA;AC;C;BA END;6:BEGIN BA;BA;C;BB END;7:BE GIN BA;BB;C;BC END;8:BEGIN BB;AC;C;CA END END;AA;K:=(K+1) MO D 9 END;BC;Z((K+1) MOD 9);CA;WRITELN END.') end; begin A;A;AB;AA; K:=1; for I:=1 to 9 do begin B; case K of 0:begin BA;C;B end; 1:begin BB;C;C;BA end; 2:begin AC;AC;C;AB;AA end; 3:begin AC;BA;C;AB;AB end; 4:begin AC;BB;C;AC end; 5:begin BA;AC;C;BA end; 6:begin BA;BA;C;BB end; 7:begin BA;BB;C;BC end; 8:begin BB;AC;C;CA end end; AA; K:=(K+1) mod 9 end; BC;Z((K+1) mod 9);CA; WRITELN end.
Verifikation
Die Programme
stimmen bis auf
die Reihenfolge der Prozeduren B,...,CA und den Startwert
von K textuell überein. Die Ausgabefolge dieser Prozeduren
wird über die Variable k gesteuert. Wir betrachten dazu
die folgende Tabelle:
Startwert k in
Startwert k, der von ![]() an weitergegeben wird
durchläuft | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| I=1 | I=2 | I=3 | I=4 | I=5 | I=6 | I=7 | I=8 | I=9 | ||
![]() | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 |
![]() | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 |
![]() | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 |
![]() | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 |
![]() | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
![]() | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
![]() | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
![]() | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |
![]() | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
In jeder Zeile der Tabelle kommen alle Werte von 0 bis 8
¦n den Spalten "I=1" bis "I=8" genau einmal vor. Damit ist
auf Grund der case-Anweisung sichergestellt, daß jedes
alle Prozeduren B bis CA ausgibt. Aus der letzten Spalte
folgt, daß der Startwert von k in jeder Kopie
verschieden ist. Ebenfalls aus der letzten Spalte folgt,
daß der Startwert von k in der Kopie von
gleich dem
Startwert von k in
ist. Da sich die Anweisungsteile
der
nur in dem Startwert von k unterscheiden, gilt:
.(4.3.5) Bemerkung:
Bemerkung
(4.2.9)II. für das unendlich reproduzierende Programm
. Überhaupt haben unsere Beispielprogramme
für unendlich reproduzierende und zyklisch selbstreproduzierende
Programme keine Vereinfachung des
Selbstreproduktionsmechanismus von Programm
gebracht.(4.3.6) Beispiel: Als Beispiel für ein zyklisch selbstreproduzierendes
SIMULA-Programm sei hier die SIMULA-Version
des Programms
angegeben.
begin
integer I,K;
procedure Z(J); integer J; OUTINT(J,1);
procedure A; OUTTEXT("BEGIN INTEGER I,K; PROCEDURE
Z(J); INTEGER J; OUTINT(J,1); PROCEDURE A; OUTTE
XT(""");
procedure B; OUTTEXT("PROCEDURE ");
procedure C; OUTTEXT("; OUTTEXT(""");
procedure AA; OUTTEXT(""");");
procedure AB; OUTTEXT("""");
procedure AC; OUTTEXT("A");
procedure BA; OUTTEXT("B");
procedure BB; OUTTEXT("C");
procedure BC; OUTTEXT("A;A;AB;AA;K:=");
procedure CA; OUTTEXT(";FOR I:=1 STEP 1 UNTIL 9 DO
BEGIN B;IF K=0 THEN BEGIN BA;C;B END ELSE IF K=1
THEN BEGIN BB;C;C;AB END ELSE IF K=2 THEN BEGIN
AC;AC;C;AB;AA END ELSE IF K=3 THEN BEGIN AC;BA;C
;AB;AB END ELSE IF K=4 THEN BEGIN AC;BB;C;AC END
ELSE IF K=5 THEN BEGIN BA;AC;C;BA END ELSE IF K=
6 THEN BEGIN BA;BA;C;BB END ELSE IF K=7 THEN BEG
IN BA;BB;C;BC END ELSE BEGIN BB;AC;C;CA END;");
A;A;AB;AA;
K:=1 ;
for I:=1 step 1 until 9 do
begin B;
if K=0 then begin BA;C;B end
else if K=1 then begin BB;C;C;AB end
else if K=2 then begin AC;AC;C;AB;AA end
else if K=3 then begin AC;BA;C;AB;AB end
else if K=4 then begin AC;BB;C;AC end
else if K=5 then begin BA;AC;C;BA end
else if K=6 then begin BA;BA;C;BB end
else if K=7 then begin BA;BB;C;BC end
else begin BB;AC;C;CA end;
AA;
K:=(K+1) mod 9;
end;
BC;Z((K+1) mod 9);CA
end;
Verifikation
Die Verifikation dieses SIMULA-Programms ist identisch mit
der des PASCAL-Programms
.

Fü die Implementierung von
gelten die gleichen
Bemerkungen wie in Abschnitt 4.2.1. zur Implementierung von Programm
. Näheres ist aus Anhang A.8. ersichtlich.

Auch für die Implementierung von
gelten die Bemerkungen
von Abschnitt 4.2.1. Die Textkonstante, die den Algorithmus
von
darstellt, muß aus Gründen der Formatierung
auf noch mehr Prozeduren aufgespalten werden, als dies
etwa in
der Fall ist. Alles Weitere siehe Anhang A.9.
In Abschnitt 4.3. haben wir zyklisch selbstreproduzierende
Programme als spezielle unendlich reproduzierende Programme
kennengelernt. Unendlich reproduzierende Programme sind
ihrerseits reproduzierende Programme. Nach Definition (4.2.1)
gibt ein reproduzierendes Programm
ein Programm
aus.
Dabei sind
und
Programme aus derselben
Programmiersprache S. Wir hätten reproduzierende Programme auch anders
definieren können, indem wir
aus einer Programmiersprache
zugelassen hätten. Eine solche Definition wäre
allgemeiner als Definition (4.2.1). Entsprechend allgemeiner
wären dann auch die Definitionen für unendlich reproduzierende
und zyklisch selbstreproduzierende Programme ausgefallen.
Daß eine solche Verallgemeinerung durchaus sinnvoll
wäre, soll das folgende Beispiel demonstrieren. Beispiel
(4.4.1) stellt ein Programm vor, das nicht nur ein Programm
in einer anderen Programmiersprache ausgibt, sondern sich
auch noch zyklisch selbstreproduziert.
(4.4.1) Beispiel: Wir gehen aus von dem SIMULA-Programm
aus 3.2.6. und dem PASCAL-Programm
aus 3.3.2..
Beide Programme sind nahezu identisch, da sie praktisch
ihre gegenseitigen Übersetzungen darstellen.
Aus beiden Programmen kombinieren wir jeweils ein
PASCAL-Programm
und ein SIMULA-Programm
mit:

und
sind also zyklisch
selbstreproduzierende Programme mit Wechsel der Programmiersprachen.
= program X(OUTPUT); var T,F:boolean; procedure A(Z:boolean);begin if Z then WRITE('BEGIN BOOLEAN T,F;') else WRITE('PROGRAM X(OUTPUT);VAR T,F:BOOLEAN;') end; procedure B(Z:boolean);begin if Z then WRITE('PROCEDUEE ') else WRITE('PROCEDURE ') end; procedure C(Z:boolean);begin if Z then WRITE('(Z);BOOLEAN Z;IF Z THEM OUTTEX("') else WRITE('(Z: BOOLEAN);BEGIN IF Z THEN WRITE(''') end; procedure AA(Z:boolean);begin if Z then WRITE('") ELSE OUTTEXT("') else WRITE(''') ELSE WRITE(''') end; procedure AB(Z;boolean);begin if Z then WRITE('");') else WRITE(''') END;') end; procedure CB(Z:boolean);begin if Z then WRITE('"') else WRITE('''') end; procedure BA(Z:boolean);begin if Z then WRITE('A') else WRITE('A') end; procedure BB(Z:boolean);begin if Z then WRITE('B') else WRITE('B') end; procedure BC(Z:boolean);begin if Z then WRITE('C') else WRITE('C') end; procedure AC(Z:boolean);begin if Z then WRITE('T:=TRUE;F:=FALSE;
END') else WRITE('BEGIN T:=TRUE;F:=FALSE;
; WRITELN END.') end; begin T:=true;F:=false; A(T); \ B(T);BA(T); C(T); A(F);AA(T); A(T); AB(T); \ B(T);BB(T); C(T); B(T);AA(T); B(T); AB(T); \ B(T);BC(T); C(T); C(F);AA(T); C(T);CB(T);AB(T); \ B(T);BA(T);BA(T);C(T);AA(F);AA(T);CB(T);AA(T);CB(T);AB(T); \ B(T);BA(T);BB(T);C(T);AB(F);AA(T);CB(T);AB(T); AB(T); \ B(T);BC(T);BB(T);C(T);CB(F);AA(T); CB(T); AB(T); /
B(T);BB(T);BA(T);C(T);BA(T);AA(T); BA(T); AB(T); / B(T);BB(T);BB(T);C(T);BB(T);AA(T); BB(T); AB(T); / B(T);BB(T);BC(T);C(T);BC(T);AA(T); BC(T); AB(T); / B(T);BA(T);BC(T);C(T);AC(F);AA(T); AC(T); AB(T); / AC(T) / ;WRITELN end.
gibt das SIMULA-Programm
aus:
= begin boolean T,F; procedure A(Z);boolean Z;if Z then OUTTEXT("PROGRAM X(OUTPUT);VAR T,F:BOOLEAN;") else OUTTEXT("BEGIN BOOLEAN T,F;"); procedure B(Z);boolean Z;if Z then OUTTEXT("PROCEDURE ") else OUTTEXT("PROCEDURE "); procedure C(Z);boolean Z;if Z then OUTTEXT("(Z:BO0LEAN);BEGIN IF Z THEN WRITE('") else OUTTEXT("(Z);BOOLEAN Z; IF Z THEN OUTTEXT("""); procedure AA(Z);boolean Z;if Z then OUTTEXT("') ELSE WRITE('") else OUTTEXT(""") ELSE OOTTEXT("""); procedure AB(Z);boolean Z;if then OUTTEXT("') END;") else OUTTEXT(""");"); procedure CB(Z);boolean Z;if Z then OUTTEXT("'") else OUTTEXT(""""); procedure BA(Z);boolean Z;if Z then OUTTEXT("A") else OOTTEXT("A"); procedure BB(Z);boolean Z;if Z then OUTTEXT("B") else OUTTEXT("B"); procedure BC(Z);boolean Z;if Z then OUTTEXT("C") else OUTTEXT("C"); procedure AC(Z);boolean Z;if Z then OUTTEXT("BEGIN T:=TBUE;F:=FALSE;
;WRITELN END.") else OUTTEXT("T:=TRUE;F:=FALSE;
END"); T:=true;F:=false;
end
Verifikation
und
enthalten jeweils alle Teilstrings -
sowohl der Zerlegung von
als auch der Zerlegung von
- in den Prozeduren A bis AC. Da sich die Teilstrings
der Zerlegungen von
und
eins zu eins
entsprechen, können die Teilstrings alternativ in den
Prozeduren abgelegt werden. Jede Prozedur von
hat dann
den allgemeinen Aufbau:
procedure <name> (Z:boolean);
begin if Z then WRITE('<Teilstring s aus
>')
else WRITE('<dem Teilstring s entsprechender Teilstring s' aus
>')
end;
Einige Teilstrings von
sind gleich ihren Entsprechungen
¦n
. Die Prozeduren, die diese Teilstrings bearbeiten,
enthalten natürlich Redundanz. Beispiel:
procedure BA(Z:boolean);
begin if Z then WRITE('A') else WRITE('A') end;
Die Redundanz, wird aber zugunsten eines einheitlichen
Prozedurschemas in Kauf genommen. Die Auswahl, welche Alternative
ausgegeben werden soll, wird beim Aufruf der Prozeduren durch
ihren aktuellen Parameter getroffen. Das PASCAL-Programm enthält
die SIMULA-Teilstrings immer im then-Zweig der Prozeduren
und die PASCAL-Teilstrings immer im else-Zweig. Beim
SIMULA-Programm sind die Verhältnisse genau umgekehrt.
Dadurch wird erreicht, daß eine Prozedur, die im PASCAL-Programm mit
true aufgerufen wird, auch im SIMULA-Programm mit
true aufgerufen werden kann. Daraus folgt, daß die Anweisungsteile
von
und
im wesentlichen identisch sind. Aus
dem bisher Gesagten und der Tatsache, daß
und
bis
auf die alternativen Prozeduren in
und
identisch sind,
folgt:
reproduziert
und umgekehrt.
In Abschnitt 4.2. haben wir Reproduktion als Abschwächung der Selbstreproduktion kennengelernt. Wir wollen nun die k-fache Selbstreproduktion von Programmen als Verschärfung der einfachen Selbstreproduktion einführen:
(4.5.1) Definition: Sei k>1. Sei
aus S. (syntakt. korrekt).
keine Eingabe auf, so heißt
k-fach
selbstreproduzierend, falls
seinen Programmtext
in S k-mal ausgibt.
Eingabe auf, so heißt
k-fach
selbstreproduzierend, falls
bei jeder zulässigen
Eingabe seinen Programmtext in S k-mal ausgibt.
bezeichnet die Menge aller k-fach
selbstreproduzierenden Programme aus S.
Abb.: 4.5.A
Die Existenz k-fach selbstreproduzierender Programme folgt bereits aus Korollar (2.8.9).
(4.5.2) Satz: Die Programmiersprache PASCAL enthält für
jedes k>1 ein k-fach selbstreproduzierendes Programm
.
Wir geben ein Beispiel eines fUr jedes k>1 k-fach selbstreproduzierenden Programms an. Dieses Beispiel beweist Satz (4.5.2).
(4.5.3) Beispiel:
= program PIK(OUTPUT); var I:integer; procedure AA;begin WRITE('PROGRAM PIK(OUTPUT);VAR I:INTEGER ;PROCEDURE AA;BEGIN WRITE(''') end; procedure C;begin WRITE('PROCEDURE ') end; procedure A;begin WRITE(';BEGIN WRITE(''') end; procedure B;begin WRITE(''') END;') end; procedure AC;begin WRITE('''') end; procedure BA;begin WRITE('A') end; procedure BB;begin WRITE('B') end; procedure BC;begin WRITE('C') end; procedure AB;begin WRITE('BEGIN FOR I:=1 TO 5 DO BEGIN AA;A A;AC;B;C;BC;A;C;B;C;BA;A;A;AC;B;C;BB;A;AC;B;B;C;BA;BC;A; AC;AC;B;C;BB;BA;A;BA;B;C;BB;BB;A;BB;B;C;BB;BC;A;BC;B;C;B A;BB;A;AB;B;AB;WRITELN END END.') end; begin for I:=1 to 5 do begin AA; AA;AC;B; C;BC; A; C; B; C;BA; A; A;AC;B; C;BB; A;AC; B; B; C;BA;BC;A;AC;AC; B; C;BB;BA;A; BA; B; C;BB;BB;A; BB; B; C;BB;BC;A; BC; B; C;BA;BB;A; AB; B;AB;WRITELN end end.
Verifikation
Die Verifikation von
ergibt sich direkt aus der Verifikation
von Programm
aus 3.3.2.. Der Unterschied zwischen
und
besteht im wesentlichen nur in der for-Schleife
for I:=1 to k do begin ... end,
in die der Ausgabealgorithmus eingebettet ist. Der Ausgabealgorithmus
von
wird also in
gerade k-mal ausgeführt.
Dadurch wird
zum k-fach reproduzierenden Programm.
(4.5.4) Bemerkung
ist
natürlich selbstreproduzierend, aber nicht streng
selbstreproduzierend. Außerdem ist ein k-fach
selbstreproduzierendes Programm zyklisch selbstreproduzierend
mit der Zykluslänge 1.
in ein entsprechendes SIMULA-Programm.
Das geht ohne Schwierigkeiten, da
keine
pascalspezifischen Konstruktionen enthält.
Zur Implementierung von
sind die gleichen Bemerkungen
wie in Abschnitt 3.3.3. zu machen. Anhang A.10. zeigt die
Implementierung von
mit k=5.
In den vorangegangenen Abschnitten haben wir für eine beliebige Programmiersprache S die Mengen
definiert. Für diese Mengen gilt
,
wobei SR(S) die Menge der selbstreproduzierende Programme aus S ist. Im allgemeinen werden die Inklusionen echt sein, wie wir am Beispiel der Programmiersprache PASCAL gesehen haben. Es gilt nämlich




Daraus folgt:
Abbildung 4.6.A erläutert dieses Ergebnis graphisch.
Abb.: 4.6.A
(4.6.1) Definition: Für jede Programmiersprache S heißt die Inklusionenreihe (1) Reproduktionshierarchie von S.
In Kapitel 3 haben wir einige Beispiele für selbstreproduzierende Programme kennengelernt. Diesen Beispielprogrammen ist gemeinsam, daß sie außer der Ausgabe ihres eigenen Textes keinerlei Funktion ausführen. Eine interessante Fragestellung ist aber etwa:
oder konkreter
Gibt es in S selbstreproduzierende Programme, die zusätzlich einen Suchalgorithmus realisieren, oder die Primzahlzerlegung ausführen, oder ein Datenbanksystem verwalten, oder ... ?"
Angenommen, Frage (1) ließe sich für die Programmiersprache S positiv beantworten, so könnte man etwas schärfer fragen:
aus S ein selbstreproduzierendes
Programm
aus S, das die gleiche Funktion
realisiert wie
?"Ist die letzte Frage für die Programmiersprache S zu bejahen,
so ist intuitiv klar, daß ein selbstreproduzierendes Programm
, das eine gegebene Funktion realisiert, umfangreicher und
komplizierter ist als ein nicht selbstreproduzierendes Programm
, das die gleiche Funktion realisiert. Daher ist es
vielleicht einfacher, auf der Suche nach
zunächst ein nicht
selbstreproduzierendes Programm
zu entwickeln, und dieses
anschließend in eine selbstreproduzierende Version
zu
transformieren. In diesem Zusammenhang drängt sich die folgende
Frage auf:
aus S ein
selbstreproduzierendes Programm
aus S liefert, das die
gleiche Funktion realisiert wie
?"Will man die Beantwortung der Fragen (1) bis (3) in Angriff
nehmen, so muß zunächst geklärt werden, was unter der "von
einem Programm
aus S realisierten Funktion" zu verstehen
ist. Wegen der Vielfalt an realen Programmiersprachen, deren
unterschiedlichen Datentypen und der unterschiedlichen
Interpretation auf verschiedenen Rechenanlagen dürfte es
unmöglich sein, den obigen Begriff formal exakt und zudem
noch allgemeingültig zu definieren. Für unsere Zwecke sollen
jedoch die folgenden Überlegungen und Definitionen
genügen.
Auf realen Rechenanlagen verarbeiten Programme aus konkreten
Programmiersprachen in der Regel Daten, die auf mehreren
Eingabedateien stehen, und geben Ergebnisse auf mehrere
Ausgabedateien aus. Auf jeder dieser Dateien stehen
Zeichenketten, die als ganze Zahlen, reelle Zahlen, Texte
u.s.w. von einem Programm
aus der Sprache S interpretiert
werden können. Diese Interpretation kann natürlich nur dann
erfolgen, wenn die Zeichen, die auf den Dateien stehen, aus
dem für Daten für Programme aus S zulässigen endlichen
Alphabet
stammen. Der Inhalt einer Datei kann als Wort aus
aufgefaßt werden. Dieser Sichtweise entspricht die
folgende Definition, die zudem den Fall zuläßt, daß während
der Laufzeit von
einige Dateien sowohl als Eingabe- als
auch als Ausgabedatei benutzt werden.
(5.1.1) Definition: Sei
ein Programm aus S mit
Einund Ausgabedateien, von denen
, Dateien
als Ausgabedateien benutzt werden. Die von
realisierte
Funktion
ist eine partielle Funktion von
nach
, die jeder Belegung der p Ein- und
Ausgabedateien mit Worten aus
genau eine Belegung
der q Ausgabedateien mit Worten aus
zuordnet.
(5.1.2) Beispiel: Gegeben sei das PASCAL-Programm
= program X(INPUT,OUTPUT); var I : integer; Y : real; begin for I:=1 to 10 do begin READ(Y); WRITELN(SQRT(Y)) end end.
liest also 10 reelle Zahlen aus der Eingabedatei
INPUT ein und gibt deren Quadratwurzeln auf die Ausgabedatei
OUTPUT aus. Sei
die Menge aller Zeichen,
die ein PASCAL-Programm verarbeiten kann.
Dann liefert Definition (5.1.1):

Läßt sich der Anfang von x nicht als Folge von 10
reellen Zahlen interpretieren, so ist
undefiniert.
Andernfalls ist
ein Wort aus
,
dessen Anfang sich als Folge von ebenfalls 10 reellen
Zahlen interpretieren läßt. Diese Folge ist
gleich der Folge der Quadratwurzeln der reellen Zahlen
der Eingabefolge.
Eine exakte Beschreibung von
würde die explizite
Einführung von Konvertierungsfunktionen von
nach
und von
nach
voraussetzen.
(5.1.3) Bemerkung:
Aus Definition (5.1.1) folgt, daß ein selbstreproduzierendes
Programm
aus S, das ohne zusätzliche Eingabe die
"gleiche" Funktion realisiert wie ein anderes, nicht selbstreproduzierendes
Programm
aus S, natürlich eine ganz andere
Funktion realisiert als
, da die Ausgaben von
und
verschieden sind. Um diesen verwirrenden Sprachgebrauch
zu umgehen, geben wir Definition (5.1.4) an. Zuvor sei jedoch
bemerkt, daß man jede Funktion
,
als m-Tupel
von Funktionen
,
i=1,...,m, auffassen kann. Dabei ist M eine beliebige Menge.
Es gilt:
für alle
.
(5.1.4) Definition: Sei
ein Programm aus S. Ein Programm
aus S heißt selbstreproduzierende Version von
,
falls für die von
und
realisierten Funktionen
und
(i) oder (ii) gilt
und
und
genau ein
mit

wobei 
und
und

Definition (5.1.4) stellt sicher, daß
unabhängig von der
Eingabe seinen eigenen Text ausgibt.
hängt seinen Text
entweder an ein Ausgabewort, das auch
ausgibt (Fall(i)),
oder
gibt seinen Text als zusätzliches Wort aus (Fall(ii)).
(5.1.5) Bemerkung: I.a. ist die selbstreproduzierende Version
eines Programms
aus S nicht eindeutig.
Mit Hilfe von Definition (5.1.4) sind wir in der Lage, die Fragestellungen (2) und (3) exakter zu formulieren:
aus einer gegebenen
Programmiersprache S eine selbstreproduzierende Version
von
?"
aus S eine
selbstreproduzierende Version
von
liefert?"Wir werden im folgenden die Fragen (1) bis (3) für die Programmiersprachen SIMULA und PASCAL explizit beantworten.
Frage (1) aus 5.1. läßt sich für die Programmiersprache PASCAL durch das folgende Beispiel beantworten.
(5.2.1) Beispiel: Wir geben eine selbstreproduzierende
Version
zu dem Programm
aus Beispiel (5.1.2) an.
Wir gehen dabei aus von unserem kürzesten PASCAL-Programm
aus Abschnitt 3.3.2. und versuchen,
und
zu einer selbstreproduzierenden Version
zu kombinieren. Zu diesem Zweck vergegenwärtigen
wir uns noch einmal das Programm
.
enthält
in den Prozeduren A,...,AC seinen eigenen Text in
Form von Teilstrings. Mehrfach vorkommende Teilstrings
sind natürlich nur einmal gespeichert.
Der Text von
läßt sich aber durch Aneinanderreihen
dieser Teilstrings zusammensetzen. Der
erste Teilstring
von
enthält die das
Programm einleitenden Phrasen bis zum ersten '. Der
letzte, in der Prozedur AB enthaltene Teilstring
beinhaltet den kompletten Anweisungsteil von
. Abbildung 5.2.A verdeutlicht diesen
Zusammenhang.

Abb.: 5.2.A
Idee: Wir integrieren den Programmkopf von 
program X(INPUT,OUTPUT); var I : integer; Y : real;
in den String
und den Anweisungsteil von 
for I:=1 to 10 do begin READ(Y); WRITELN(SQRT(Y)) end;
in den String
.
Wir erhalten die Teilstrings
und
mit
= program PI6X(INPUT,OUTPUT); var I : integer; Y : real; procedure AA; begin WRITE('
= begin for I:=1 to 10 do begin READ(Y); WRITELN(SQRT(Y)) end; AA;AA;AC;B; .......... AB; WRITELN end end.
Es liegt auf der Hand, daß die Ersetzung von
und
durch
bzw.
in Programm
wieder zu einem syntaktisch
korrekten selbstreproduzierenden Programm
führt.
führt
zuerst die for-Schleife von
aus und reproduziert sich
anschließend selbst. Es gilt für die von
realisierte
Funktion
:
für alle 
Damit genügt
Definition (5.1.4)(i), und es gilt:
ist
eine selbstreproduzierende Version von
. Anhang A.11.
zeigt Programm
in implementierter Form, die aus der
implementierten Form von Programm
abgeleitet ist.
Die Konstruktion von
aus den beiden Programmen
und
zeigte keine Aspekte, die darauf hindeuten, daß diese
Konstruktion von irgendwelchen speziellen Eigenschaften von
abhängt. Die Konstruktion müßte sich also für beliebige
PASCAL-Programme verallgemeinern lassen. Um diese Verallgemeinerung
komfortabel durchführen zu können, benötigen wir
noch zwei Vereinbarungen:
In [10] ist eine kontextfreie Grammatik
soweit
dies überhaupt möglich ist (vergleiche 2.3.), für die
Programmiersprache PASCAL angegeben worden. Wir werden uns
im folgenden an dieser Grammatik orientieren.
(5.2.2) Vereinbarung: Sei
ein nichtterminales Zeichen
aus
und
ein gültiges PASCAL-Programm, so bezeichnen
wir mit
den Teilstring des Programmtextes
,
der sich aus dem nichtterminalen Zeichen
ableiten
läßt. Kommt das Zeichen
im Ableitungsbaum von
nicht vor, so identifizieren wir
mit dem leeren Wort.
Der Teilstring
ist natürlich abhängig von der
Position von
im Ableitungsbaum von
. Dieser
Umstand wird für uns aber keine Bedeutung erlangen.
Durch die hier eingeführte Schreibweise lassen
sich aus den Produktionen der Grammatik
Gleichungen gewinnen.
Beispiel:
enthält die Produktion
<program>::=<program heading><block>
Für jedes gültige PASCAL-Programm
gilt
damit die Gleichung
= <program>
= <program heading>
<block>
![]()
Bei der Kombination von Programm
und Programm
zu
waren keine Konflikte mit Bezeichnern aufgetreten. Das
heißt, sämtliche Prozedurnamen von
waren von den
Variablennamen aus
verschieden. Dies kann i.a. jedoch nicht
vorausgesetzt werden. Um den Test, ob in einem PASCAL-Programm
Bezeichner auftreten, die mit einem Prozedurnamen
aus
identisch sind, zu vereinfachen, normieren wir die
Prozedurnamen aus
, indem wir festlegen, daß jeder
Prozedurname aus
nur mit Hilfe des Buchstaben A gebildet
werden darf. Alle Prozedurnamen aus
sind also Elemente
aus
und unterscheiden sich nur in ihrer Länge. Wir
werden später sehen, daß es bei einigen Programmen nötig ist,
neue Prozeduren zu generieren. Die Namen dieser Prozeduren
werden wir ebenfalls aus
wählen. Durch diese Normierung
der Prozedurnamen werden einige Namen sehr lang. Um
Schreibarbeit zu sparen, treffen wir die folgende Vereinbarung.
(5.2.3) Vereinbarung:
ein Element aus
,
dann schreiben wir statt dessen kürzer
.
der Prozedur
ab durch
.Unter Benutzung von Vereinbarung (5.2.3) präsentiert sich
nach der Umbenennung der Prozedurnamen in der folgenden
Weise:
program PI6(OUTPUT);
procedure A;begin WRITE('PROGRAM PI6(OUTPUT);PROCEDURE A;BE
GIN WRITE(''') end;
procedure
;begin WRITE('PROCEDURE ') end;
procedure
;begin WRITE(';BEGIN WRITE(''') end;
procedure
;begin WRITE(''') END;') end;
procedure
;begin WRITE('''') end;
procedure
;begin WRITE('A') end;
procedure
;begin WRITE('BEGIN
WRITELN END.') end;
begin
WRITELN
end.
Nach diesen Vorbemerkungen sind wir nun in der Lage, den Selbstreproduktionssatz für PASCAL-Programme zu beweisen.
(5.2.4) Satz (Selbstreproduktionssatz für PASCAL-Programme)
Zu jedem syntaktisch, korrekten PASCAL-Programm
existiert eine selbstreproduzierende Version
.
Beweis
Der Beweis gliedert sich in zwei Teile. In Teil A
wird eine Konstruktion für ein Programm
für
beliebiges
angegeben. In Teil B wird gezeigt, daß
das so konstruierte
eine selbstreproduzierende
Version von
ist. Der Beweis setzt die Grammatik
voraus.
Sei nun
ein beliebiges gültiges PASCAL-Programm.
Enthält
Bezeichner aus
, so werden
diese Bezeichner durch andere Bezeichner ersetzt,
die nicht aus
sind. Das resultierende Programm
ist textuell von
verschieden und wird mit
bezeichnet. Enthält
keine Bezeichner aus
, 1)
so wird
gesetzt.
Teil A
Nach
hat
den folgenden Aufbau:
= <programm heading>
<block>
,
wobei <program heading>
und <block>
ungleich dem leeren
Wort sind. Entsprechendes gilt für
und das zu konstruierende
:
= <program heading>
<block>
![]()
= <program heading>
<block>
![]()
Wir erhalten das Programm
, indem wir
<program heading>aus <program heading>
und <program heading>
![]()
bzw.
<block>aus <block>
und <block>
![]()
kombinieren.
Aus
folgt, daß für <program heading>
die allgemeine
Beziehung
<program heading)= program
;
wobei
PASCAL-gültige Bezeichner sind,
gilt.
stellt den Namen des Programms dar, die
bezeichnen
die von
benutzten Dateien. Benutzt
die Standarddatei
OUTPUT, so sei o.B.d.A.
= OUTPUT.
Für
gilt:
<program heading>= program Pl6(OUTPUT);
Damit kombinieren wir:
<program heading>= program P(
,OUTPUT);
mit

Aus
folgt, daß für <block>
gilt:
<block>= <label declaration part>
<constant declaration part>
<type definition part>
<variable declaration part>
<procedure and function declaration part>
<statement part>
![]()
Alle Strings bis auf <statement part>
können leer sein.
Die Programme
und
haben einen entsprechenden Aufbau.
Da <label declaration part>
,...,<variable declaration
part>
gleich dem leeren Wort sind, setzen wir:
<label declaration part>:= <label declaration part>
<konstant declaration part>
:= <konstant declaration part>
<type definition part>
:= <type definition part>
<variable declaration part>
:= <variable declaration part>
![]()
In 3.2.5. war bemerkt worden, daß es in SIMULA nicht möglich
ist, Texte, die das Zeichen " enthalten, en bloc auszudrucken.
Die gleichen Schwierigkeiten macht in PASCAL das
Zeichen '. Enthält
das Zeichen ' ein- oder mehrmals, so
muß der Text
entsprechend zerlegt werden.
Es wird gesetzt:
S := <label declaration part><constant declaration part>
<type definition part>
<procedure and function declaration part>
T := (<statement part>
ohne die klammernden, terminalen Zeichen begin und end.)
Mittels der Strings S und T läßt sich der Programmtext
wie folgt darstellen:
= <program heading)
![]()
S
begin
T
end.
1. Fall: S ist ungleich dem leeren Wort (d.h.
hat einen
nichtleeren Vereinbarungsteil)
Zerlegung von S in eine Folge von
Teilstrings
mit
![s_i = \ ' \text{ oder } s_i \not\ni \ ',\ i\in[n]](/img/cache/eadfe10c8f918a1351d2920c3149a029.gif)
![s_i \not\ni \ ' \Rightarrow s_{i+1} = \ ',\ i\in[n-1]](/img/cache/dfbd5beb98ff965358b514150be77658.gif)

Sei p die Anzahl der Teilstrings von S, die ungleich '
sind. Es gilt: 
Für jeden Teilstring ungleich ' , mit Ausnahme von
,
wird eine Prozedur generiert:
procedure;begin WRITE('
') end; j = 2,...,p
wobei
der j-te Teilstring ungleich ' ist.
Sei AP die Menge der Namen der generierten Prozeduren.
Dann gilt:
.
Sei
die Menge der Teilstrings der
Zerlegung von S.
Einführung der Funktionen
und
:
(Zur Erinnerung:
ist die Prozedur, die in
das Zeichen
' ausgibt.)
Da weder <label declaration part>noch <konstant declaration part>
noch <type definition part>
noch <procedure and function declaration part>
![]()
mit dem Zeichen ' anfangen oder enden können, gilt:

Der String T wird in einen String T' transformiert, indem
T mit dem Zeichen ; konkateniert wird: T' := T;
T' wird analog zu S in
Teilstrings
zerlegt. Für
die Zerlegung von T' gilt:
![t_i=\ '\text{ oder } t_i\not\ni\ ',\ i\in[m]](/img/cache/8bbc738084687cad7b6106b3f731cbcd.gif)
![t_i\not\ni\ '\Rightarrow t_{i+1}=\ '\ i\in[m-1]](/img/cache/f06974098850c6049b909b0e04193ffd.gif)

Sei q die Anzahl der Teilstrings von T', die ungleich '
sind. Es gilt:
.
Für jeden Teilstring
ungleich ', mit Ausnahme von
,
wird eine Prozedur generiert:
procedure; begin WRITE('
') end;
für j=2,...,q-1, wobei
der j-te Teilstring
' ist
bzw.
procedure;begin WRITE('BEGIN
') end;
für j=1.
Dabei ist
der j-te Teilstring von T' ungleich '.
Entsprechend
und
werden
und
definiert:
Das erste Zeichen nach dem einleitenden begin von
<statement part>
kann nicht gleich ' sein. Daraus ergibt
sich nach Definition von 
Das letzte Zeichen von T' ist ; . Daraus folgt: 
Es ist nun möglich, die beiden noch fehlenden Programmteile
von
, nämlich
<procedure and function declaration part>und <statement pari>
![]()
abzugeben:
<procedure and function declaration part>= <procedure and fuuction declaration part>
procedure
;begin ..... end;
![]()
procedure
;begin ..... end; procedure A;begin WRITE('<program heading>
') end;
![]()
procedure
;begin WRITE('
END.') end; <statement part>
= begin
end.
steht dabei als Abkürzung für die Aufruffolge der Prozeduren
A bis
, die die Ausgabe von
bewirkt.
Damit ergibt sich insgesamt:
= program P(
,,OUTPUT);
procedure
;begin WRITE('
') end; procedure
;begin WRITE('
') end; .......................................... procedure
;begin WRITE('
' ) end; procedure
;begin WRITE(BEGIN
' ) end; procedure
;begin WRITE('
') end; .......................................... procedure
;begin WRITE('
') end; procedure A;begin WRITE('PROGEAM P(
,OUTPUT);
') end; procedure
;begin WRITE('PROCEDURE ') end; procedure
;begin WRITE(';BEGIN WRITE(''') end; procedure
;begin WRITE(''') END;') end; procedure
;begin WRITE('''') end; procedure
;begin WRITE('A') end; procedure
;begin WRITE('
END.') end; begin
![]()
![]()
2. Fall: Der String S ist gleich dem leeren Wort (d.h. der
Vereinbarungsteil von
ist leer)
Dieser Fall ist ein Spezialfall von Fall 1. Wir erhalten
das resultierende Programm aus dem in Fall 1 angegebenen
Programm
durch Streichung der den String S betreffenden
Konstruktion. Im Einzelnen
bis 
procedure A;begin WRITE('PROGRAM P(
,OUTPUT);')
end;
bis 
Teil B
1. Fall: S ist ungleich dem leeren Wort.
Die Konstruktion in Teil A liefert ein syntaktisch korrektes
PASCAL-Programm
. Es bleibt zu zeigen, daß
eine
selbsreproduzierende Version von
ist.
realisiert eine Funktion
.
Der Vereinbarungsteil von
wird in Form des Textes
in das Programm
unverändert aufgenommen.
Im Anweisungsteil von
wird der in der Form
übernommene Anweisungsteil von
zuerst
ausgeführt. Alle anderen Anweisungen sind nur Aufrufe von
Prozeduren, die nicht in S vereinbart sind. Bei jedem Aufruf
dieser Prozeduren wird genau eine Textkonstante auf die
Datei OUTPUT ausgegeben. Da
nur endlich viele Prozeduraufrufe
aufweist, wird insgesamt ein endlicher Text, also
ein Wort y aus
, auf die Datei OUTPUT ausgegeben. Die
Aufrufe dieser Ausgabeprozeduren erfolgen jedoch erst,
nachdem der Anweisungsteil T' abgearbeitet worden ist.
realisiert also die folgende Funktion:
![f_{\tilde\pi}\ :\ (A^*_{\text{PAS}})^r \longr (A^*_{\text{PAS}})^u\ o\le u\le r\\
\text{mit}\\
(f_{\tilde\pi})_i(\overline{x}) = \left\{
\begin{array}{ll}
(f_\pi)_i(\overline{x}) & \text{f\ddot{u}r }i\in[r-1]\\
(f_\pi)_i\circ y & \text{f\ddot{u}r }i = r
\end{array} \right\} {\overline{x}\in(A^*_{\text{PAS}})^r}](/img/cache/302703a7306010b98980bf979327408b.gif)
falls
= OUTPUT, d.h.
gibt y auf eine Ausgabedatei
aus, die auch
benutzt.
![\text{bzw.}\\
f_{\tilde\pi}\ :\ (A^*_{\text{PAS}})^{r+1} \longr (A^*_{\text{PAS}})^u\ o\le u\le r+1\\
\text{mit}\\
(f_{\tilde\pi})_i(\overline{x}) = \left\{
\begin{array}{ll}
(f_\pi)_i(\overline{x}) & \text{f\ddot{u}r }i\in[r]\\
y & \text{f\ddot{u}r }i = r+1
\end{array} \right\} {\overline{x}\in(A^*_{\text{PAS}})^{r+1}}](/img/cache/979ea44e4aab4a439ded7f4d641d5156.gif)
falls
= OUTPUT, d.h.
gibt y auf die Datei OUTPUT
aus, die von
nicht als Ausgabedatei benutzt wird.
erfüllt also genau dann Definition (5.1.4), wenn der
Text
Teilstring von y ist.
Es gilt aber sogar
, denn:
Nach Abarbeitung von
gibt
zunächst durch
Aufruf der Prozedur A seinen eigenen Programmkopf
<programm heading>
und
aus. Die nächsten Prozeduraufrufe
... bis ...
erledigen die Ausgabe von
... bis ...
.
Die Prozeduraufrufe der Zeilen
bis
und
bis
bewirken die Ausgabe der Prozedurvereinbarungen von
bis
bzw. von A bis
. Es fehlt nur noch de
Ausgabe von <statement part>
. Diese Ausgabe wird jedoch
durch die Folge
bewirkt. Das nachfolgende
WRITELN leert nur den Puffer der Datei OUTPUT.
Es gilt also
. Damit ist
selbstreproduzierende
Version von
.
2. Fall: S ist gleich dem leeren Wort
Fall 2 ergibt sich als Spezialfall von Fall 1. Es gilt
somit auch in diesem Fall, daß das erhaltene Programm
selbstreproduzierende Version von
ist.
Damit ist der Satz vollständig bewiesen.
Dem Beweis von Satz (5.2.4) laßt sich direkt ein
Algorithmus entnehmen, der zu jedem beliebigen PASCAL-Programm
eine selbstreproduzierende Version
findet.
(5.2.5) Algorithmus:
.
vorkommenden
Bezeichner aus
ist. Gegebenenfalls
Umbenennung vornehmen.
aus
<program heading>
unter Verwendung der
Standarddatei OUTPUT.S = <label declaration part>in Teilstrings<constant declaration part>
<type definition part>
<variable declaration part>
![]()
und Ermittlung der
Anzahl p der Teilstrings
ungleich ' .
Anschließend Formulierung der p-1 Prozeduren
bis
und Aufstellung der Wertetabellen
von
und
.
ohne klammerndes begin
end.) gleich ; , so wird T':=T gesetzt,
andernfalls T':=T;.
Zerlegung von T' in
und Ermittlung der
Zahl q. Anschließend Formulierung der q-1 Prozeduren
bis
und Aufstellung der
Wertetabellen von
und
.
in das im Beweis angegebene Programmschema.
des Programms
.(5.2.6) Beispiel: Gegeben sei das in [28] Seite 17 zu findende Programm.
= program CONVERT(OUTPUT); const ADDIN=32;MULBY=1.8;LOW=0;HIGH=39; SEPARATOR='__________'; var DEGREE : LOW .. HIGH; begin WRITELN(SEPARATOR); for DEGRSE:=LOW to HIGH do begin WRITE(DEGREE,'C',ROUND(DEGREE*MULBY+ADDIN),'F'); if ODD(DEGREE) then WRITELN end; WRITELN; WRITELN(SEPARATOR) end.
Anwendung von Algorithmus (5.2.5):
enthält keinen Bezeichnen aus
. Es sind
also keine Umbenennungen nötig.
wird auf
program CONVERT(OUTPUT);gesetzt.
S =Es gilt n=5, p=3mit
= const ADDIN=32;MULBY=1.8;LOW=0;HIHG=39; SEPARATOR=
= '
= ----------
= '
= ;var DEGREE:LOW..HIGH;
procedureWertetabellen von;begin WRITE('__________') end; procedure
;begin WRITE(';VAR DEGREE:L0W.. HIGH;') end;
und
:
T=Es gilt: m=9, q=5mit
= WRITELN(SEPARATOR);FOR DEGREE:=LOW TO HIGH DO BEGIN WRITE('DEGREE,
= '
= C
= '
= ROUND(DEGBEE*MULBY+ADDIN),
= '
= F
= '
= );IF ODD(DEGREE) THEN WRITELN END; WRITELN;WRITELN(SEPARATOR);
procedureWertetabellen von;begin WRITE('BEGIN WRITELN(SEPARATOR); FOR DEGREE:=LOW TO HIGH DO BEGIN WRITE(DEGREE),') end; procedure
;begin WRITE('C') end; procedure
;begin WRITE('ROUND(DEGREE*MULBY+ADDIN),') end; procedure
;begin WRITE('F') end;
und
:
= program CONVERTX(OUTPUT); const ADDIN=32;MULBT=1.8;LOW=0;HIGH=39;SEPARATOR='__________'; var DEGREE:LOW..HIGH; procedure
;begin WRITE('__________') end; procedure
;begin WRITE(';VAR DEGREE:LOW..HIGH;') end; procedure
;begin WRITE('BEGIN WEITELN(SEPARATOR);FOR DEGREE:=LOW TO HIGH DO BEGIN WRITE(DEGREE)') end; procedure
;begin WRITE('C') end; procedure
;begin WRITE(,ROUND(DEGREE*MULBY+ADDIN),' ) end; procedure
;begin WRITE('F') end; procedure A;begin WRITE('PROGRAM CONVERTX(OUTPUT);CONST ADDIN=32;MULBY=1.8;LOW=0;HIGH=39;SEPARATOR=') end; procedure
;begin WRITE('PROCEDURE ') end; procedure
;begin WRITE(';BEGIN WRITE(''') end; procedure
;begin WRITE(''') END;') end; procedure
;begin WBITE('''') end; procedure
;begin WRITE('A') end; procedure
;begin WRITE(');IF ODD(DEGREE) THEN WRITELN END;WRITELN;WRITELN(SEPARATOR);
END.') end; begin WRITELN(SEPARATOR); for DEGREE:=LOW to HIGH do begin WRITE(DEGREE,'C',ROUND(DEGREE*MULBY+ADDIN),'F'); if ODD(DEGREE) then WRITELN end; WRITELN; WRITELN(SEPARATOR);
end.
Die Bedeutung von Satz (5.2.4) ist in erster Linie theoretischer
und nicht praktischer Art. Satz (5.2.4) beweist
zwar die Existenz einer selbstreproduzierenden Version
für jedes gültige PASCAL-Programm
und gibt auch eine
Konstruktion für ein syntaktisch richtiges
an, jedoch
garantiert die syntaktische Korrektheit noch, nicht die Realisierbarkeit
von
auf einer konkreten Rechenmaschine.
Die Implementierung eines von Algorithmus (5.2.5) gelieferten
Programms
kann zu folgenden Schwierigkeiten
führen:
ist
.
ist p+q+5 Zeichen lang. Jedes dieser Zeichen ist
signifikant, da auch, der Prozedurname
mit der
Länge p+q+4 in
vorkommt. Die zulässige Signifikanz
von Bezeichnern ist bei implementierten PASCAL-Compilern
aber beschränkt. Die Zahlen p und q sind jedoch
nur endlich, was zur Folge hat, daß bei großen
p und q einige Prozeduren nicht unterschieden werden
können.
, ist für die
Gesamtheit aller PASCAL-Programme
nicht beschränkt.
Damit ist auch die Länge einer Programmzeile nicht
beschränkt. Die Länge einer Programmzeile ist auf
realen Rechenanlagen aber oft durch die Länge des
Eingabepuffers des implementierten PASCAL-Compilers
beschränkt.Die Schwierigkeiten (i) und (ii) lassen sich bei vielen in der Praxis vorkommenden Programmen vermeiden, indem man Algorithmus (5.2.5) um zwei "praxisorientierte" Schritte ergänzt.
.
a ist gleichzeitig die Anzahl der Prozedurnamen vom
Typ
. Dann wähle manzwei natürliche Zahlen
und
mit
Nun können die Prozedurnamen
bis
durch
neue Namen ersetzt werden, die maximal b Zeichen lang
sind und aus den c ersten Buchstaben des Alphabets
zusammengesetzt sind. Außer dem Buchstaben A können
also c-1 weitere Buchstaben zur Bildung von Prozedurnamen
herangezogen werden. Zu diesen c-1 Buchstaben
müssen aber c-1 neue Prozeduren generiert werden, die
jeweils einen neuen Buchataben ausdrucken:

Für diese Prozeduren werden aber auch Namen benötigt.
Daher müssen die Zahlen c und b auch die Relation
erfüllen.
, die
Textkonstanten der Prozeduren
(diese Prozeduren
sind möglicherweise in Schritt 6 bereits umbenannt
worden). Für jedes
muß die folgende
Berechnung ausgeführt werden:
Ist
1), so bleibt
unverändert.
Andernfalls wird
in
Teilstrings
zerlegt mit
. Dabei sei
minimal
gewählt.
Die Prozedur
wird durch
neue Prozeduren ersetzt:

Entsprechend der neu eingeführten Prozeduren wird die
Aufruffoige der Prozeduren, die die Ausgabe von
bewirkt, ergänzt.
Die schritte 6 und 7 führen jedoch nicht immer zum Ziel.
Ist die Eingabepufferlänge d des zur Verfügung stehenden
PASCAL-Compilers relativ gering, so werden in Schritt 7
in der Regel sehr viele neue Prozeduren generiert. Sicherlich
wird dabei auch die Textkonstante der - möglicherweise
in Schritt 6 umbenannten - Prozedur
, die den
Ausgabealgoritnmus für
enthält, auf mehrere neue
Prozeduren aufgespalten. Neue Prozeduren bedingen einen längeren
Ausgabealgorithmus, wenn
selbstreprcduzierend bleiben
soll. Das bedeutet aber, daß noch mehr Prozeduren zur Aufnahme
des Ausgabealgorithmus nötig sind. Noch mehr Prozeduren
bewirken aber eine erneute Verlängerung des Ausgabealgorithmus,
was noch mehr Prozeduren bewirkt, u.s.w.
Ist d nun relativ gering, so kann es geschehen, daß sich
dieser Prozeß nicht stabilisiert und Schritt 7 zu einem
unendlichen Programm führt. Das ist genau dann der Fall, wenn
die Textkonstanten der den Ausgabealgorithmus enthaltenden
Prozeduren durchschnittlich weniger Prozeduraufrufe enthalten,
als zur Ausgabe der Prozedurvereinbarung einer Ausgabeprozedur
erforderlich ist. Das sprunghafte Anwachsen der
Anzahl der Ausgabeprozeduren kann zu einer wiederholten
Durchführung von Schritt 6 führen. Noch komplizierter werden
die Verhältnisse, wenn die Ausgabe von
formatiert werden
soll.
(5.2.7) Beispiel: Das in Beispiel (5.2.6) enthaltene
Programm
soll implementiert werden.
weist 13 Prozedurnamen vom Typ
auf.
Der vorhandene PASCAL-Compiler wertet nur die
ersten 8 Zeichen eines Bezeichners als signifikant.
Einige der
müssen also umbenannt werden.
Die Prozeduren
und
stellen zufällig
die beiden Buchstaben C und F zur Verfügung. Zur
Umbenennung der 13 Prozeduren
sollen
aber insgesamt 4, Buchstaben herangezogen werden.
Es wird deshalb zusätzlich die Prozedur
procedure BB;begin WRITE('B') end;
in das Programm
aufgenommen.
Mit den 4 Buchstaben A,B,C und F lassen sich
4 verschiedene Namen der Länge 1,
16 verschiedene Namen der Länge 2 und
64 verschiedene Namen der Länge 3 bilden.
Auch wenn Schritt 7 weitere Prozeduren liefern sollte, ist anzunehmen, daß mit c=4 und b=3 genügend viele Namen zur Verfügung stehen. Wir werden versuchen, mit Namen der Längen 1 und 2 auszukommen.
Die Prozeduren
, werden wie folgt
umbenannt:
in AA
in AF
in A
in CB
in B
in CC
in C
in BC
in F
in CF
in BA
in BF
in AC
bewirkt, daß insgesamt 4 neue Prozeduren
FA,FB,FC und FF eingeführt werden müssen.
Anhang A.12. zeigt das durch die Schritte 6
und 7 veränderte Programm
. Zur Formatierung
der Ausgabe wurde in das Programm die aus 3.3.4.
bekannte Prozedur Q eingefügt.
Die in den Kapiteln 3 und 4 vorgestellten Beispielprogramme
in SIMULA und PASCAL entsprechen sich weitgehend. Zum
selbstreproduzierenden PASCAL-Programm
aus (3.3.2.)
existiert ein nahezu identisches SIMULA-Programm
in
3.2.7. . Da der Beweis von Satz (5.2.4) in wesentlichen
auf der Existenz von
beruht, ist anzunehmen, daß bezüglich
der Programmiersprache SIMULA ein entsprechender Satz
gilt. Der Beweis dieses Satzes wird sich wie der Beweis
von (5.2.4) in zwei Teile A und B gliedern. In Teil A wird
die Konstruktion der selbstreproduzierenden Version
eines
beliebigen SIMULA-Programms
erfolgen. Trotz der Entsprechung
von
und
muß diese Konstruktion explizit angegeben
werden, da SIMULA im Gegensatz zu PASCAL eine blockorientierte
Programmiersprache ist. Das aus Teil A resultierende
Programm
wird aber weitgehend dem in Teil A von
dem Beweis zu (5.2.4) konstruierten Programm entsprechen.
Zum Nachweis, daß
selbstreproduzierende Version von
ist,
wird in Teil B ein Verweis auf Teil B vom Beweis zu (5.2.4)
genügen. Der Beweis wird sich an der in [19] angegebenen
SIMULA-Grammatik orientieren. Diese Grammatik sei mit
bezeichnet. Für
übernehmen wir die Vereinbarung (5.2.2).
Außerdem übernehmen wir Vereinbarung (5.2.3) für die
Prozedurnamen von
. Damit präsentiert sich
, in der Form:
= begin procedure A;OUTTEXT("BEGIN PROCEDURE A;OUTTEXT("""); procedure
;OUTTEXT("PROCEDURE "); procedure
;OUTTEXT(" ;OUTTEXT("""); procedure
;OUTTEXT(""");"); procedure
;OUTTEXT(""""); procedure
;OUTTEXT("A"); procedure
;OUTTEXT("
![]()
![]()
END");
![]()
end
(5.3.1) Satz (Selbstreproduktionssatz für SIMULA-Programme)
Zu jedem syntaktisch korrekten SIMULA-Programm
existiert eine selbstreproduzierende Version
.
Beweis
Teil A
Das Programm
hat laut Grammatik
den folgenden
Aufbau:
= begin <Vereinbarung> -Folge
<Anweisung> -Folge
end
Sei
ein beliebiges SIMULA-Programm. Dann hat
den
Aufbau:
= <Klassenbezeichnung>
<akt. Parameterteil> -option
begin <Vereinbarung> -Folge
<Anweisung> -Folge
end
Dabei können
<Klassenbezeichnung,
,
<akt. Parameterteil> -option
bzw. <Vereinbarung> -Folge
leer sein (vgl.
).
Besteht
nur aus
begin <Anweisung> -Folgeend,
so nennt man
eine Verbundanweisung. Andernfalls ist
ein
Block. Sowohl Verbundanweisungen als auch Blöcke sind an jeder
Stelle von <Anweisung> -Folge
zulässig, an der eine
Anweisung zulässig ist. Dies wird im folgenden ausgenutzt.
Kombination von
aus
, und 
Ist <Klassenbezeichnung>
nicht leer, so ist zunächst zu
testen, ob <Klassenbezeichnung>
aus
ist. Ist dies
der Fall, so wird <Klassenbezeichnung>
umbenannt. Es
resultiert das Programm
, das die gleiche Funktion
realisiert wie
. Andernfalls wird
gesetzt. Wegen
des Konzepts der lokalen Gültigkeit von Bezeichnern ist
eine Umbenennung der in - falls vorhanden - <Vereinbarung> -Folge
und <Anweisung> -Folge
vorkommenden
Beseichner auf jeden Fall nicht nötig.

Es brauchen nur noch die Programmteile
(zusätzliche Vereinbarungen)
und (zusätzliche Anweisungen)
realisiert zu werden.
Sei T gleich
mit angefügtem ; . Also
. Der String
T wird analog zum String T' aus dem Beweis zu (5.2.4) in
eine Folge von
Teilstrings
zerlegt. Für diese
Zerlegung von T gilt:
![t_i=\quot\text{ oder }t_i\not\ni\quot\ ,\ \ i\in[m]](/img/cache/57538bf985eea91a4cc789c499f4a0db.gif)
![t_i\not\ni\quot\ \Rightarrow t_{i+1}=\quot\ ,\ \ i\in[m-1]](/img/cache/13b2e212b881ff5168d7580bad74df4e.gif)

Sei q die Anzahl der Teilstrings
von T, die ungleich "
sind. Es gilt:
.
Für jeden Teilstring
ungleich ", mit Ausnahme von
,
wird eine Prozedur generiert:
procedure;OUTTEXT("
");
wobei
der j-te Teilstring von T ungleich " ist.
Die Menge der erzeugten Prozedurnamen ist
. Sei
.
Wie im Beweis zu (5.2.4) werden die Funktionen
und
definiert
![\begin{array}{lcl}
\tau\ : & [q] & \longr \calT\\
& j & \longr t_k\text{, mit t_k = j-ter Teilstring \ne\quot}\\
\tilde\tau\ :
& [m] & \longr AQ\cup\{A^5\}\\
& j & \longr {
\left\{
\perp\text{, falls j=q}\\
A^{7+i}\text{, falls t_j = i_ter Teilstring \ne\quot}\\
A^5\text{, falls t_j = \quot}
\right.
}
\end{array}](/img/cache/37de1ab75c77bc58efac83fa8d4d7f84.gif)
ist ungleich ", da
nicht mit " anfangen kann. Da das
letzte Zeichen von T gleich ; ist, ist auch
ungleich ".
wird in die Prozedur
integriert.
Der Programmteil (zusätzliche Vereinbarungen) besteht aus
den q-1 Prozedurvereinbarungen von
bis
.
Der Programmteil (zusätzliche Anweisungen) besteht aus der
Folge von Prozeduraufrufen, die nötig sind, die q-1 zusätzlichen
Prozedurvereinbarungen auszugeben. Die Prozedur
wird entsprechend erweitert.
= begin procedure A;OUTTEXT("BEGIN PROCEDURE A; OUTTEXT("""); procedure
;OUTTEXT("
"); ................................. procedure
;OUTTEXT("
"); procedure
;OUTTEXT("PROCEDURE "); procedure
;OUTTEXT(" ;OUTTEXT("""); procedure
;OUTTEXT(""");"); procedure
;OUTTEXT(""""); procedure
;OUTTEXT("A"); procedure
;OUTTEXT("
![]()
![]()
![]()
![]()
END");
end
Teil B
Die Konstruktion von
in Teil A führt zu einem syntaktisch
korrekten SIMULA-Programm. Wegen der sehr engen Entsprechung
von den SIMULA-Programm
und dem PASCAL-Programm
entspricht
dem im Beweis von (5.2.4) erzeugten PASCAL-Programm
weitgehend. Zum Nachweis, daß
wirklich selbstreproduzierende
Version von
ist, kann wegen der völligen Analogie
auf den Beweis von (5.2.4), Fall 2, verwiesen werden.
Aus dem Beweis zu Satz (5.3.1) läßt sich direkt ein Algorithmus
herleiten, der zu jedem gültigen SIMULA-Programm
eine selbstreproduzierende Version
angibt.
(5.3.2) Algorithmus:
.
- falls
überhaupt vorhanden - ein Bezeichner
aus
ist. Gegebenenfalls Umbenennung
vornehmen.
in Teilstrings
und Ermittlung der Anzahl q
der Teilstrings
ungleich ".
bis
und Aufstellung
der Wertetabellen von
und
.
in das im Beweis angegebene Programmschema.
des
Programms
.Wegen der Analogie zu (5.2.5) sei an dieser Stelle auf ein Beispiel für die Anwendung von Algorithmus (5.3.2) verzichtet. Zur Gewinnung implementierbarer selbstreproduzierender Versionen muß (5.3.2) analog zu (5.2.5) um zwei "praxisorientierte" Schritte erweitert werden.
Kapitel 5 hat insgesamt ergeben, daß sich die eingangs (s.o. 5.1.) gestellten Fragen (1), (2) und (3) bezüglich der Programmiersprachen SIMULA und PASCAL positiv beantworten lassen. Bei der Beantwortung werden keine simula- bzw. pascalspezifischen Sprachelemente bemüht. Diese Tatsache läßt den Schluß zu, daß sich die Fragen (1) bis (3) im Falle jeder höheren Programmiersprache, die über
verfügt, positiv beantworten lassen.
Auch bezüglich der in 3.4. behandelten SIEMENS-Assemblersprache fallen die Antworten auf die drei Fragen positiv aus. Die Antworten wurden bereits durch Beispiel (3.4.1) geliefert. Wenige Zeilen Assembler-Kode genügen, um aus einem beliebigen Assembler-Programmabschnitt einen selbstreproduzierenden Programmabschnitt zu machen. Die die Selbstreproduktion ausmachenden Zeilen sind im wesentlichen immer gleich.
In den Kapiteln 3,4 und 5 haben wir Beispiele für selbstreproduzierende Programme in höheren Programmiersprachen kennengelernt. Alien Beispielen ist gemeinsam, daß sie algorithmisch nicht sehr aufwendig sind. Der jeweilige Kontrollfluß alier bisherigen Belspielpragramme ist recht einfach. Es wäre also interessant zu klären, wie einfach Programmiersprachen strukturiert sein können, um noch selbstreproduzierende Programme zu ermöglichen. Die folgenden Betrachtungen werden also in erster Linie den in Programmiersprachen üblichen Kontrollstrukturen gelten und sich nicht auf eine konkrete Programmiersprache beziehen. Die Loslösung von konkreten Programmiersprachen wird dadurch zum Ausdruck gebracht, daß wir unsere Überlegungen auf der Basis der fiktiven Programmiersprache PL(A) aus Kapitel 2 durchführen.
In Kapitel 2 wurde die Menge der durch PL(A)-Programme
realisierbaren Funktionen mit
bezeichnet. Schränkt man
die in PL(A) zur Verfügung stehenden Grundanweisungen und
Kontrollstrukturen etwa auf

oder auf

ein, so erhält man Programmiersprachen, die nur "goto-Programme"
bzw. nur "while-Programme" ermöglichen. Die Theorie
zeigt jedoch (vgl. dazu etwa [5]), daß die Menge der
mit while-Programmen realisierbaren Funktionen gleich der
Menge der mit goto-Programmen realisierbaren Funktionen
gleich der Menge
ist. (Unsere bisherigen Beispielprogramme
für selbstreproduzierende Programme in SIMULA und
PASCAL benutzen Prozeduren. Wollte man diese Programme in
PL(A)-Programme transformieren, so würden goto-Programme
entstehen.) Erst die Einschränkung von PL(A) auf

also auf reine "loop-Programme", führt zu Programmen, mit
denen sich nicht mehr alle Funktionen aus
realisieren
lassen. Wir werden im folgenden untersuchen, unter welchen
Voraussetzungen selbstreproduzierende loop-Programme
möglich sind.
(6.2.1) Definition: Sei
ein endliches
Alphabet. Sei PL(A) die in 2.2. definierte, zu A
gehörige Programmiersprache. LP(A) ist die
Programmiersprache, die entsteht, indem man aus PL(A)
alle Programme streicht, die Grundanweisungen vom
Typ
, oder eine der
Kontrollstrukturen

enthalten.
(6.2.2) Bezeichnung:
das einzige
Konstruktionselement für Programme aus LP(A) dar. Die Programme
aus LP(A) werden daher auch als loop-Programme
bezeichnet.
bezeichnet.
heißt auch Menge der
primitiv rekursiven Funktionen. [5]Aus (6.2.1) ergibt sich, daß LP(A) eine echte Teilmenge von
PL(A) ist. Daß auch
eine echte Teilmenge von
ist,
ergibt sich schon aus der Tatsache, daß loop-Programme immer
halten und somit die von loop-Programmen realisierten
Funktionen total sind. Es läßt sich aber auch zeigen, daß
eine
echte Teilmenge von
(vgl. (2.4.6)) ist, indem man die
Existenz einer total rekursiven Funktion, die nicht primitiv
rekursiv ist, nachweist (vgl. [5] Seite 41).
Der Vollständigkeit halber sei hier eine kontextfreie Grammatik G'(A) für LP(A) angegeben. G'(A) entsteht durch Einschränkung der Grammatik G(A) für PL(A)-Programme aus 2.3..
(6.3.1) Angabe der Grammatik 
Die Menge der Terminalzeichen ist
![\begin{array}{ll}
V_T'=&A\cup VR\cup\{\text{\underline{input},\underline{output},\underline{loop},\underline{case},\underline{end},}\\
&\longr\ ,\ ;\ ,\ ,\ ,\ \tiny{\rotate{-90}]}\ ,\ \varepsilon,\ \overline\varepsilon\ ,\ :\ ,\ =\ \},
\end{array}](/img/cache/b243d28d56a0fc79f2cd84a518e9651e.gif)
wobei VR die Menge der zulässigen Variablennamen ist.
Die Menge der nicht terminalen Zeichen ist

Das Startsymbol
ist <program>
Die Menge P' der Produktionen ist gleich der Menge P der Produktionen der Grammatik G(A) aus (2.3.1) ohne die Produktionen mit den Nummern 6,8,9,10,13,14,15 und 20.
In Kapitel 2 wurde die Existenz selbstreproduzierender
Programme in PL(A) theoretisch bewiesen. Sin analoger Beweis
für die Existenz von selbstreproduzierenden Programmen in
LP(A) scheitert daran, daß es in
keine universelle
Funktion gibt (siehe [5] Seite 47). Wir werden uns daher dem
Problem der Existenz selbstreproduzierender Programme in
LP(A) von der praktischen Seite aus nähern. Das bedeutet
allerdings nicht, daß es prinzipiell unmöglich ist, die
Existenz selbstreproduzierender LP(A)-Programme auf
theoretischem Wege zu beweisen.
Um das praktische Schreiben von selbstreproduzierenden LP(A)-Programmen für uns zu ermöglichen, erweitern wir die Programmiersprache LP(A) um eine zusätzliche Grundanweisung. Diese Erweiterung soll aber nicht bedeuten, daß es ohne sie prinzipiell unmöglich ist, selbstreproduzierende LP(A)-Programme zu schreiben.
und nicht nur mit
zu
initialisieren. Wir führen daher die Grundanweisung
ein:
Es soll nicht ausgeschlossen werden, daß
sein darf.
Damit ist aber auch
für beliebiges
zulässig.
In höheren Programmiersprachen ist es üblich, daß Texttrennzeichen, wenn sie innerhalb von Textkonstanten vorkommen, doppelt geschrieben werden müssen. Dieser Umstand hatte uns in den Kapiteln 3 und 5 das Schreiben von selbstreproduzierenden Programmen in PASCAL und SIMULA sehr erschwert. Wir treffen daher eine andere Vereinbarung:
Auf eine Grundanweisung
muß zwingend ein Semikolon folgen.
Das Ende einer Textkonstanten wird demnach durch
'; angezeigt. Der Einfachheit halber verbieten wir das
Auftreten des Strings '; als Teil einer Textkonstanten.
Um die Koppelung des Semikolons an Textkonstanten
deutlich zu machen, beziehen wir das Semikolon in die
Definition von
ein.
![\begin{array}{ll}
\gamma_6\ :\ & X:=\ 'a_{i_1} \dots a_{i_k}\ ',\ k\ge1\\
& X\in VR,\ a_{i_j}\in A\text{ f\ddot{u}r }j\in[k] .
\end{array}](/img/cache/cdfa724514363198adedd9685b8f489f.gif)
, so ist folgende Anweisung vom Typ
möglich:


interpretiert werden. Um
Doppeldeutigkeiten1) zu vermeiden, ersetzen wir
durch
die Grundanweisung
:
ist die gleiche wie die von
.(6.4.2.) Definition: Sei A ein endliches Alphabet. LP(a) ist
diejenige Programmiersprache, die durch Erweiterung
um die Grundanweisung
und durch Ersetzung der
Grundanweisung
durch
aus der Sprache LP(A)
entsteht.
Aus der Grammatik G'(A) für die Sprache LP(A) laßt sich
leicht eine kontextfreie Grammatik
für die Sprache
herleiten:
wird um ' und
| erweitert.


(6.4.3) Definition: (loop-Hierarchie der
-Programme)
Sei A ein endliches Alphabet.
die Klasse der Programme
, deren Anweisungsteil
durch beliebiges
Hintereinanderschreiben von Anweisungen vom Typ
und
ersteht.
enthalte alle Programme
, deren
Anweisungsteile
durch Hintereinandersetzen von
Anweisungsteilen von Programmen aus
und
Anweisungsteilen der Form![\fbox{
\begin{array}{rlccc}
\text{\underline{loop} X} & \text{\underline{case}} &a_1 &\longr & AW_{\pi_1},\\
& & \vdots & & \vdots\\
& & \vdots & & \vdots\\
& &a_n &\longr & AW_{\pi_n},\\
& \text{\underline{end}}\\
\end{array}\\
\text{a_j \in A f\ddot{u}r jedes j \in [n]}
}](/img/cache/06169913c73bd671fad901c5e4b1ee05.gif)
Anweisungsteile von
Programmen aus
sind, entstehen (
).
Sei
ein - falls es existiert - selbstreproduzierendes
-Programm. Im Anweisungsteil von
muß
schrittweise der Text
aufgebaut werden. Die einzelnen
Buchstaben von
müssen auf der rechten Seite von
Wertzuweisungen auftreten. Auf den rechten Seiten von Wertzuweisungen
stehen aber außer Variablennamen nur Buchstaben aus
A. Es muß also gelten:
. Um dies zu gewährleisten,
wird folgende Forderung an das Alphabet A gestellt:
Forderung (1): Für jedes Programm
gilt:

Jedes Alphabet, das Forderung (1) erfüllt, muß alle Zeichen
enthalten, die zur Konstruktion von
-Programmen
zulässig sind. Das kleinste, Forderung (1) erfüllende Alphabet
ist demnach
:= { a,c,d,e,i,l,n,o,p,s,t,u,
,
,
,:,=,;,,,
,|,'}
Die Definition von
schränkt die Wahl der Variablenmenge
VR in keiner Weise ein. Aus Forderung (1) ergibt sich
jedoch, daß auch für die Variablennamen eines selbstreproduzierenden
Programms
nur Buchstaben aus A in
Frage kommen.
Forderung (2):
.
Dabei ist
die
Menge der Sonderzeichen.
In einem
-Programm, das Forderung (2) erfüllt, muß
streng zwischen dem Variablennamen x und dem Zeichen x
unterschieden werden, wobei x ein Buchstabe aus A ist. Die Definition
von
schließt Fehlinterpretationen jedoch aus.
(6.5.2) Satz: Sei A endliches Alphabet mit
. Dann
existiert in
ein selbstreproduzierendes Programm,
falls
Forderung (2) erfüllt.
Beweis: Betrachte das Programm 

![\begin{array}{lllll}
\text{ } & & \text{u \longr loop i}&\text{case} &\text{a \longr t:=t|a,}\\
& & & &\text{c \longr t:=t|c,}\\
& & & &\text{d \longr t:=t|d,}\\
& & & &\text{e \longr t:=t|e,}\\
& & & &\text{i \longr t:=t|i,}\\
& & & &\text{l \longr t:=t|l,}\\
& & & &\text{n \longr t:=t|n,}\\
& & & &\text{o \longr t:=t|o,}\\
& & & &\text{p \longr t:=t|p,}\\
& & & &\text{s \longr t:=t|s,}\\
& & & &\text{t \longr t:=t|t,}\\
& & & &\text{u \longr t:=t|u,}\\
& & & &\text{: \longr t:=t|:,}\\
& & & &\text{= \longr t:=t|=,}\\
& & & &\text{\' \longr t:=t|\',}\\
& & & &\text{; \longr t:=t|;,}\\
& & & &\text{\longr \longr t:=t|\longr,}\\
& & & &\text{\rotate{-90}] \longr t:=t|\rotate{-90}],}\\
& & &\text{end,}\\
&\text{end},\\
&\text{output t\';;}\\
\text{loop e} &\text{case} & \text{l \longr loop a}&\text{case} &\text{ i \longr t:=t|i,}\\
& & & &\text{n \longr t:=t|n,}\\
& & & &\text{p \longr t:=t|p,}\\
& & & &\text{u \longr t:=t|u,}\\
& & & &\text{t \longr t:=t|t,}\\
& & & &\text{; \longr t:=t|;,}\\
& & & &\text{a \longr t:=t|a,}\\
& & & &\text{: \longr t:=t|:,}\\
& & & &\text{= \longr t:=t|=,}\\
& & &\text{end,}\\
& & \text{n \longr loop d}&\text{case} &\text{\' \longr t:=t|\',}\\
& & &\text{end,}\\
& & \text{o \longr t:=t|;,}\\
& & \text{c \longr t:=t|c,}\\
& & \text{p \longr loop c}&\text{case} &\text{: \longr t:=t|:,}\\
& & & &\text{= \longr t:=t|=,}\\
& & & &\text{\' \longr t:=t|\',}\\
& & &\text{end,}\\
\end{array}](/img/cache/2d4d8748027a02ff26ba8e71dc66c7f0.gif)
ist offensichtlich ein gültiges
-Programm.
Zu zeigen:
reproduziert sich selbst.
Da
keine Eingabe besitzt, ist die Behauptung, daß sich
selbstreproduziert, gleichwertig mit der Aussage, daß
der Inhalt der Variablen t bei Ausführung der letzten Anweisung
"output t" gleich
ist.
.
Die Abkürzung [t]:=[t]x hingegen bedeutet das
Anhägen des Zeichens
an den Inhalt von [t].
in der folgenden Form formulieren:
input; a:='input;a:=';; c:=':='';; d:=''';; e:='lnlnoocppnoodpnnooepsnooipunoou';; i:='loop e case l[t]:=[t][a], n
[t]:=[t][d], o
[t]:=[t];, c
[t]:=[t]c, p
[t]:=[t][c], d
[t]:=[t]d, e
[t]:=[t]e, s
[t]:=[t][e], i
[t]:=[t]i, u
[t]:=[t][i], end;output t';; [i]
Die äußere loop-Schleife arbeitet nun die Laufvariable e ab.
e enthält genau die stringweise Kodierung von
. Die
Kodierung ist durch Hinschreiben der Alternativenliste gegeben.
Die äußere loop-Schleife selbst dekodiert [e] und erzeugt
sukzessive
. In
kommen nur Zeichen aus
vor.
Daher ist
für jedes
, falls
Forderung (2) erfüllt.
Da die Schachtelungstiefe der loop-Schleifen in
2 ist,
folgt der Satz.
Aus dem Programm
aus dem obigen Beweis läßt sich ein
Programm
gewinnen, daa mit der loop-Schachtelungstiefe 1
auskommt.
Wir konstruieren
aus
, indem wir die äußere
loop-Schleife eliminieren. Die äußere loop-Schleife arbeitet
den Inhalt der Variablen e ab. Der Inhalt von e ist 31 Zeichen
lang. Wir listen nun für jedes der 31 Zeichen den Anweisungsteil
der Alternativenliste auf, den es kodiert. Da e seine
Kodierung enthält und die Variable e bei Eliminierung der
äußeren loop-Schleife überflussig wird, reduziert sich die
Anzahl dieser Anweisungsteile auf 25. Bei nunmehr 25 Zeichen
und insgesamt 10 Alternativen ist klar, daß einige Alternativen
mehrfach geschrieben werden müssen. Damit wird gleichzeitig
deutlich, daß die äußere loop-Schleife von
nur
abkürzenden Charakter besitzt.
= input; a:='input;a:=';; c:=':='';; d:=''';; i:='<Alternative für l>; <Alternative für n>; <Alternative für l>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für c>; <Alternative für p>; <Alternative für p>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für d>; <Alternative für p>; <Alternative für n>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für i>; <Alternative für p>; <Alternative für u>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für u>; output t';; <Alternative für l>; <Alternative für n>; <Alternative für l>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für c>; <Alternative für p>; <Alternative für p>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für d>; <Alternative für p>; <Alternative für p>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für i>; <Alternative für p>; <Alternative für u>; <Alternative für n>; <Alternative für o>; <Alternative für o>; <Alternative für u>; output t
Dabei sind die Teile in spitzen Klammern zu ersetzen:

![\begin{array}{ll}
\text{<Alternative f\ddot{u}r u> durch}\\
& \fbox {
\begin{array}{llll}
\text{loop i} & \text{case} & a & \longr t:=t|a,\\
& & c & \longr t:=t|c,\\
& & d & \longr t:=t|d,\\
& & e & \longr t:=t|e,\\
& & i & \longr t:=t|i,\\
& & l & \longr t:=t|l,\\
& & n & \longr t:=t|n,\\
& & o & \longr t:=t|o,\\
& & p & \longr t:=t|p,\\
& & s & \longr t:=t|s,\\
& & t & \longr t:=t|t,\\
& & u & \longr t:=t|u,\\
& & : & \longr t:=t|:,\\
& & = & \longr t:=t|=,\\
& & \text{\'} & \longr t:=t|\text{\'},\\
& & ; & \longr t:=t|;,\\
& & , & \longr t:=t|,,\\
& & \longr & \longr t:=t|\longr,\\
& & \rotate{-90}] & \longr t:=t|\rotate{-90}],\\
& \text{end}\\
\end{array}
}
\end{array}](/img/cache/cb62778f95aa7d717f08cbe708e37669.gif)
Offensichtlich gilt:
, reproduziert sich selbst. Da
, können wir den folgenden Satz formulieren:
(6.5.3) Satz: Sei A endliches Alphabet mit
, Dann
existiert in
ein selbstreproduzierendes Programm,
falls
Forderung (2) erfüllt.
Nach der recht einfachen Konstruktion von
aus
könnte man versucht sein, aus
ein selbstreproduzierendes
Programm
gewinnen zu wollen, das ganz ohne loop-Schleifen
auskommt. Zu diesem Zweck müßten in
die
noch verbleibenden loop-Schleifen
<Alternative für l>;
<Alternative für n>;
<Alternative für p>;
<Alternative für u>;
eliminiert werden. Die erste dieser loop-Schleifen ließe
sich ohne weiteres in eine Folge von Grundanweisungen zerlegen,
da sie, wie schon die äußere loop-Schleife von
,
nur abkürzenden Charakter hat. Schwierigkeiten ergeben sich
bei <Alternative für n>. <Alternative für n> ließe sich
ohne loop wie folgt schreiben:

Da auf <Alternative für n) ein Semikolon folgt, würde die
Textkonstante von i den Teilstring t:=t|'; und damit die
für Textkonstanten verbotene Kombination '; enthalten
(vgl. 6.4.). <Alternative für n> läßt sich also nicht durch
einen sequentiellen Programmteil ersetzen. Dieser Umstand
liegt jedoch nur an der in 6.4. vorgenommenen Definition
der Textkonstanten in
-Programmen. Es ist durchaus
denkbar, daß er sich bei einer anderen Definition der Textkonstanten
vermeiden ließe. Ähnliches gilt für <Alternative
für p>.
Anders liegen allerdings die Verhältnisse bei <Alternative für u>. Diese loop-Schleife dient dazu, den Inhalt der Variablen i an. den Inhalt der Variablen t zu hängen. <Alternative für u) ist nun aber selbst textueller Bestandteil des Inhalts von i.
i:='..........<Alternative für u>..........'
<Alternative für u> laßt sich nicht durch eine Sequenz von
Grundanweisungen ersetzen. Es läßt sich aus
kein
selbstreproduzierendes Programm gewinnen, das ohne loop-Schleifen
auskommt. Es gilt sogar:
(6.5.4) Satz: Für jedes endliche Alphabet A gilt:
Es existiert kein selbstreproduzierendes Programm
in 
Beweis: Sei
über dem endlichen Alphabet A vorgelegt.
Sei die notwendige Forderung (2) erfüllt.
Annahme: Es existiert selbstreproduzierendes Programm
. Dann hat
den Aufbau:
In
muß der Text
aufgebaut werden. Da
keine loop-Schleifen zur Verfügung stehen, sind
nur zwei Möglichkeiten zur Erzeugung des Textes
in
gegeben.
1. Fall: Der Text
wird, en bloc mit Hilfe einer Grundanweisung
vom Typ
erzeugt. Dann gilt für
die
Textgleichung

Diese Gleichung kann aber von keinem endlichen
Text
erfüllt werden. Widerspruch!
2. Fall: Der Text
wird in
zeichenweise mit
Anweisungen vom Typ
aufgebaut. Da
ungleich dem
leeren Wort seih muß, kommt in
mindestens
einmal die Anweisung t:=t|x; mit
vor. Diese
Anweisung umfaßt 7 Zeichen. Als String interpretiert
ist sie textueller Bestandteil von
. Die Anweisung
kann nur höchstens eines seiner 7 Zeichen an
die Ausgabevariable t hängen. Daraus folgt, daß
mindestens 6 Zeichen unbearbeitet bleiben. Für diese
6 Zeichen sind dann weitere 6 Befehle vom Typ
notwendig. Diese 6 Anweisungen hinterlassen ihrerseits
36 unbearbeitete Zeichen, u.s.w.
Um also einen Text der Länge
mit Anweisungen
vom Typ
zu erzeugen, braucht man mindestens
ein Programm der Länge
.
Damit gibt es kein endliches Programm der Länge
k, das nur mit Anweisungen vom Typ
einen
endlichen Text der Länge k aus dem leeren Wort
aufbauen kann, insbesondere nicht seinen eigenen Text.
ist also nicht endlich und damit kein Programm.
Widerspruch!
(6.5.5) Bemerkung: In Kapitel 2 wurde die Existenz
selbstreproduzierender PL(A)-Programme nachgewiesen
(Satz (2.8.7)). Dieser Nachweis beruhte neben dem
- T45 -
Rekursionstheorem (Satz (2.8.4)) auf dar Existenz
einer universellen Funktion für die Funktionenklasse
.
Die Klasse aller Wortfunktionen

die sich mittels
-Programmen berechnen lassen,
ist eine Funktionenklasse, die nur aus totalen
Funktionen besteht;
-Programme halten immer an.
In [5] Seite 47 wird gezeigt, daß es für
-berechenbare
Funktionen keine universelle
-berechenbare
Funktion geben kann. Trotzdem gibt es in
selbstreproduzierende Programme.
Universalität kann also keine notwendige Voraussetzung für
Selbstreproduktion sein. Es muß also auch andere
(direktere!) Wege als der in Kapitel 2 beschrittene
Weg geben, um die Existenz selbstreproduzierender
Programme theoretisch nachzuweisen.
-ProgrammeIn Kapitel 5 zeigten, die Sätze (5.2.4) und (5.3.1) die
Existenz selbstreproduzierender Versionen beliebiger SIMULA-
bzw. PASCAL-Programme. Ein analoger Satz läßt sich auch für
-Programme beweisen. Ersetzt man in Abschnitt 5.1. die
Sprechweise "Eingabedatei" und "Ausgabedatei" wieder durch
"Eingabevariable" bzw. "Ausgabevariable", so ist auch die
selbstreproduzierende Version für
-Programme erklärt.
Sei A ein beliebiges endliches Alphabet, sei
.
Möglicherweise existiert in
keine selbstreproduzierende
Version
zu
(etwa weil die in
verwendeten
Variablennamen nicht aus
sind), sondern erst in der Sprache
mit einem entsprechend "großen" Alphabet
. Nach
Definition (5.1.4) wäre ein solches
keine
selbstreproduzierende Version von
, da es mit einem anderen
Datenbereich arbeitet. Definition (5.1.4) ist aber erfüllt,
wenn man
ebenfalls als Programm aus
auffaßt, was ja
wegen
durchaus zu vertreten ist: Die von
realisierte
Funktion ist gleich der Restriktion der von
als
-Programm realisierten Funktion auf
(vgl.
Definition (5.1.1)).
Dieser Sichtweise entspricht Satz (6.6.1).
(6.6.1) Selbstreproduktionssatz für
-Programme
Seien A ein endliches Alphabet,
. Dann gibt
es ein endliches Alphabet
, so daß gilt:
von
(wobei
als Element aus
aufzufassen ist).
Beweis: Seien A beliebiges endliches Alphabet,
.
O.B.d.A. seien alle Variablennamen aus
nicht aus
{c,d,e,i,t}.
Konstruktion der selbstreproduzierenden Version 
hat den folgenden Aufbau
Sei
die Menge aller Zeichen, aus denen das Programm
zusammengesetzt ist. Der String
sei wie folgt definiert:
S:=input
;
;
(hiermit ist natürlich der Text des
Anweisungsteils von
gemeint)
Es gilt:
.
S wird in eine Folge von
Teilstrings
zerlegt mit:
ist nicht in
enthalten
enthält '; nicht 

(Zur Erinnerung: '; dient als Endemarkierung von Textkonstanten und darf selbst nicht Teiistring einer Textkonstanten sein.)
Weitere Vorbereitungen:
Menge der Teilstrings.
.
seien Zeichen, die weder in {c,d,e,i,t}
noch als Variablennamen in
vorkommen.
schreiben, wobei
die
Kardinalität von B ist.
und
:![\begin{array}{lcll}
\calG\ :& [q] & \longr & \calJ\\
& i & \longr & \text{s_j, wobei s_j der i-te Teilstring ungleich \'; ist.}\\
\tilde\calG\ :
& [n] & \longr & B^*\\
& i & \longr & {
\left\{
\text{no, falls s_i=\';}\\
\text{x_j, falls s_i der j-te Teilstring ungleich '; ist.}
\right. }
\end{array}](/img/cache/9c0d97d3e64fad21f8c82a42da60ad85.gif)

Nach diesen Vorbereitungen läßt sich
angeben:
=
.....
![]()
![]()
:='
';;
:='
';; .............
:='
';; c:=':='';; d:='''; e:='
.....
![]()
noo ............
noo cppnoodpnnooepsnooipunoou';; i:='loop e case
![]()
t:=t|
,
![]()
t:=t|
, ...................
![]()
t:=t|
, c
t:=t|c, d
t:=t|d, e
t:=t|e, i
t:=t|i,
![]()
loop
,
![]()
loop
, .....................
![]()
loop
, n
loop d case '
t:=t|', end, o
t:=t|;, p
loop c case :
t:=t|:, =
t:=t|=, '
t:=t|', end, s
loop e, u
loop i, end; output
t ';; loop e case
![]()
t:=t|
,
![]()
t:=t|
, ...................
![]()
t:=t|
, c
t:=t|c, d
t:=t|d, e
t:=t|e, i
t:=t|i,
![]()
loop
,
![]()
loop
, .....................
![]()
loop
, n
loop d case '
t:=t|', end, o
t:=t|;, p
loop c case :
t:=t|:, =
t:=t|=, '
t:=t|', end, s
loop e, u
loop i, end; output
t
Behauptung:
ist selbstreproduzierende Version von
.
Programm
beginnt mit der Eingabe der Eingabevariablen
von
und der Abarbeitung des vollständigen Anweisungsteils
von
. Am Ende von
werden die Ausgabevariablen von
ausgegeben. Diese Ausgabevariablen
werden nicht
durch Anweisungen außerhalb des Anweisungsteils von
verändert.
gibt zusätzlich die Variable t aus. Zum Nachweis,
daß
selbstrenroduzierende Version von
ist, genügt es
also zu zeigen, daß am Ende der Programmausführung der Inhalt
von t gleich
ist.
Die Variablen
und i enthalten - bis
auf einige einzelne Zeichen - den Programmtext
in zerlegter
Form. Die Aufgabe der loop-Schleife von
ist es,
die in den Variablen gespeicherten Teilstrings zum Text
zusammenzufügen. Die äußere loop-Schleife
loop e case ..... end;
wird durch die Variable e gesteuert, e enthält den Text
in kodierter Form. Die Kodierung ist direkt aus der Alternativenliste
ersichtlich. Für jedes Zeichen der Textkonstanten
e wird genau ein Teilstring des Programms
an
den Inhalt der Variablen t gehängt. Die Textkonstante e
läßt sich grob in drei Teile gliedern:
Teil I :.....
Teil II :
noo ............
noo Teil III: cppnoodpnnooepsnooipunoou
Teil I bewirkt, daß
input
an den Inhalt der zunächst leeren Variablen t gehängt wird.
Teil II verlängert den Inhalt von t um die Programmzeilen
:='
';; bis
:='
';;
Teil III bewirkt, daß der restliche Programmtext von
an
den Inhalt von t gehängt wird. Dies folgt aus der völligen
Analogie zu
aus dem Beweis von Satz (6.5.2).
Mit Teil III ist die Variable e vollständig abgearbeitet,
und die Ausführung der äußeren loop-Schleife bricht ab.
Damit stoppt auch das Gesamtprogramm, und
wird als Inhalt
von t ausgegeben.
erfüllt also Definition (5.1.4)(ii) und
ist somit selbstreproduzierende Version von
.
Die "reproduzierende" loop-Schleife in
hat die
loop-Schachtelungstiefe 2 und steht neben dem Anweisungsteil von
.
Die loop-Schachtelungstiefe von
ist daher mindestens 2,
aber beschränkt durch die loop-Schachtelungstiefe von
.
Damit ist auch die zweite Aussage des Satzes erfüllt.
(6.6.2) Bemerkung:
-Programm
gewinnen. Dieser Algorithmus ist jedoch
stark verbesserungsbedürftig.
Beispiele:
loop venthalten viele unnütze Alternativen, die im Beweis zugunsten einer einheitlichen Schreibweise in Kauf genommen werden.
aus 6.5.
Eine Konstruktion mit Hilfe des
-Programms
würde zu selbstreproduzierenden Versionen
führen mit
.In den vorangegangenen Kapiteln wurde die Existenz selbstreproduzierender Programme sowohl in Assembler-Sprachen als auch in höheren Programmiersprachen nachgewiesen. Speziell Kapitel 5 zeigt, daß es nicht nur unendlich viele selbstreproduzierende Programme gibt, sondern daß sich jede Programmieraufgabe effektiv mit einem selbstreproduzierenden Programm bewältigen läßt; Grenzen sind nur durch die technisch physikalischen Gegebenheiten einer konkreten Rechenanlage gesetzt.
Elektronische Datenverarbeitungsanlagen arbeiten nicht hundertprozentig fehlerfrei. Schalt- und übertragungsfehler sind jederzeit möglich, wenn auch sehr unwahrscheinlich.
Beispiel: Aus Gründen der Effizienzsteigerung und der besseren Nutzbarmachung einzelner hardware-Komponenten werden immer häufiger einzelne Rechner zu Rechnernetzen [21] zusammengeschaltet. Da die Entfernung der Einzelrechner zueinander oft mehrere Hundert Kilometer beträgt, stellt die übertragung der Daten zwischen den Rechnern eines Netzes ein besonderes Problem dar. Je nach Art des gewählten physikalischen übertragungsweges liegt die Fehlerrate bei der Datenübermittlung zwischen 10-4 und 10-7 bit/sec (10-5 bit/sec beim öffentlichen Telefonnetz) [21] [12]. Durch hard- und softwaremäßige Maßnahmen (z.B. Verwendung fehlerkorrigierender Kodes [11], Kommunikationsprotokolle [21]), die in ihrer Gesamtheit als Fehlerkontrolle bezeichnet werden, kann die Rate der unerkannten Fehler niedriger gehalten werden. So liegt z.B. Die Bitfehlerrate für Bitübertragung beim ARPA-Netz [12] bei 10-12 bit/sec.
Es besteht die Möglichkeit, daß bei der Selbstreproduktion eines Programms
Fehler unterlaufen (z.B. bei der übertragung der Kopie aus dem Arbeitsspeicher in den Hintergrundspeicher). Diese Fehler können dazu führen, daß effektiv ein anderes Programm
reproduziert wird. Falls
ein syntaktisch korrektes Programm ist, kann
durchaus wieder selbstreproduzierend sein und dabei eine andere Funktion realisieren als
. Dieser Sachverhalt erinnnert stark an Reproduktion und Mutation lebender Zellen in der Biologie. Reproduktion und Mutation gehören nach Ansicht der Biologie zu den Grundeigenschaften alles Lebendigen. Es drängt sich in diesem Zusammenhang die Frage auf, ob sich Programmen noch weitere lebenskennzeichnende Prozesse zuordnen lassen. Ist es vielleicht sogar möglich, in Anlehnung an die Biologie von lebendigen Programmen zu sprechen? Die Beantwortung dieser Fragestellungen stößt auf eine Vielzahl von Schwierigkeiten, von denen die beiden folgenden wohl zu den bedeutsameren gehören.
Die Suche nach "Leben" bei Programmen wird also sicherlich von philosophischen Problemen und Problemen der theoretischen Biologie begleitet sein. Es liegt daher auch nicht in der Absicht dieses und der beiden letzten Kapitel, "Leben" bei Programmen zu definieren. Die abschließenden Kapitel der vorliegenden Arbeit sind eher als ein erster Versuch zur Erschließung des dargelegten Problemkreises, verbunden mit einigen Denkmöglichkeiten, zu verstehen.
Die moderne Biologie ist immer noch auf der Suche nach einer einheitlichen Definition des Lebens. Aus der Vielzahl rezenter und ausgestorbener Lebensformen lassen sich jedoch einige gemeinsame Eigenschaften alles Lebendigen extrahieren. So sind nach einer weitverbreiteten Auffassung
die Schlüsselprozesse des Lebens. Diese Schlüsselprozesse dienen der Erhaltung der Individuen, der Vermehrung und dem Erbwandel (vgl. [13] Seite 24 ff). Es gibt Auffassungen von Leben, die auch Reizbarkeit und Bewegung als charakteristische Aspekte des Lebendigen anführen (vgl. [15] Seite 335)
StoffwechselDie "Grundeinheit" des Lebens ist die Zelle. Alle. Lebewesen sind aus Zellen aufgebaut. Sowohl Zellen als auch Lebewesen stellen begrenzte Stoffsysteme dar. Eine Zelle nimmt aus ihrer Umgebung ständig Stoffe auf, wandelt sie intern um und gibt sie in veränderter Form wieder an ihre Umwelt ab. Da jede Zelle auf diese Weise ständig von Stoffen durchströmt wird, wird das System "Zelle" als Fließsystem (Abb. 7.2.A) bezeichnet [13]. Fließsysteme sind offene Systeme [2]. Die Stoffumwandlungen in Zellen laufen in geordneten Bahnen ab. Es stellt sich ein sogenanntes Fließgleichgswicht ein. (In [2] Seite 158 wird die Auffassung vertreten, daß alle charakteristischen Eigenschaften lebender Organismen direkte Konsequenzen des Fließgleichgewichts sind). Offene Systeme im Fließgleichgewicht streben unabhängig von den Anfangsbedingungen einem konstanten Zustand entgegen. Dieser Zustand heißt stationärer Zustand. Stofflich gleiche Fließsysteme streben, sofern sie sich in einer gleichen Umgebung befinden, dem gleichen stationären Zustand entgegen, auch wenn die Anfangsbedingungen unterschiedlich sein mögen. Man kann also von einer gewissen Selbstregulationsfähigkeit der Lebewesen bzgl. des Stoffwechsels sprechen.
Abb. 7.2.A
Schema eines chemischen Fließsystems: Die Stoffe Ai treten in das System ein. Innerhalb des Systems werden mittels Binnenreaktionen die Stoffe Bj erzeugt. Die (Abfall-) Produkte Ck treten aus dem System aus.
Der Stoffwechsel wird häufig, rein heuristisch, in den Baustoffwechsel und den EnergiestoffWechsel differenziert. Während der Baustoffwechsel dem materiellen Aufbau bzw. dem Wachstum der Lebewesen dient, liefert der Energiestoffwechsel die zur Aufrechterhaltung der Lebensprozesse notwendige Energie.
Reproduktion und Mutation
Bei lebenden Organismen beruht die Vermehrung auf Zellteilung. Die Teilung einer Zelle erfolgt dabei so, daß die entstehenden Tochterzellen, die gleiche Struktur und das gleiche Ablaufschema der Stoffwechselreaktionen erhalten wie die Elterzelle(n) (Singular bei ungeschlechtlicher, Plural bei geschlechtlicher Vermehrung). Aus dem oben über Fließsysteme Gesagten folgt, daß die Tochterzellen dem gleichen stationären Zustand zustreben wie die Elterzelle(n), vorausgesetzt, die Umweltbedingungen sind während und nach der Zellteilung identisch. Auf diese Weise "ererben" die Tochterzellen den Zustand der Elterzelle(n). Die Struktur einer Zelle und die in der Zelle ablaufenden Stoffwechselreaktionen werden durch Proteine bestimmt. Damit eine Tochterzelle den gleichen stationären Zustand wie die Elterzelle(n) bei konstanten Umweltverhaltnissen erreichen kann, genügt es also, bei der Zellreproduktion dafür zu sorgen, daß
Die zur Synthese der Proteine notwendige Information enthält jede Zelle in Form speziell strukturierter Nukleinsäuremoleküle. Diese Moleküle werden als DNS, einzelne funktionelle Molekülabschnitte als Gene [27] bezeichnet. Damit die Tochterzellen in der Lage sind, die gleichen Proteine zu bilden wie die Elterzelle(n), bekommt jede Tochterzelle bei der Reproduktion eine identische KoDie der DNS-Moleküle der Elterzelle, also identische Gene mit; bei geschlechtlicher Vermehrung handelt es sich um eine Kombination der DNS-Moleküle der Elterzellen (allele Gene). Die Elterzeilen vererben also den Bauplan der in ihnen gebildeten Proteine. Unterlaufen bei der Replikation der DNS-Moleküle Fehler und werden die fehlerhaften Kopien an die Tochterzellen weitergegeben, so werden in den Tochterzellen andere Proteine erzeugt als in den Elterzellen. Es werden dann i.a. in den Tochterzellen andere Binnenreaktionen erfolgen. In den Tochterzellen wird sich trotz sonst gleicher Umweltbedingungen ein anderes Fließgleichgewicht als in den Elterzellen einstellen. Auch der stationäre Zustand der Tochterzellen wird ein anderer sein. Man bezeichnet bei lebenden Organismen solche sprunghaften änderungen des Erbgutes (Genom) als Mutation. Mutationen erfolgen immer zufällig und ungerichtet. Mutationen werden nicht nur durch fehlerhafte Kopierprozesse hervorgerufen, sondern können auch bei bereits "fertigen" Seilen durch spontane änderungen der DNS-Moleküle entstehen.
Diese beiden extrem kurzen und nicht annähernd vollständigen überblicke über Stoffwechsel, Reproduktion und Mutation von Lebewesen sollen als Grundlage zu den folgenden überlegungen dienen.
Im Gegensatz zu naturlichen Lebewesen sind Programme in erster Linie Informationen und als solche nicht stofflich. Damit Information verfügbar ist, muß sie in einer interpretierbaren Form zugänglich sein.
Beispiele:
Programme werden in der Regel erstellt, um sie von einer konkreten Rechenmaschine ausführen zu lassen. Im Rechner sind dann Programme digital dargestellt und für den Rechner interpretierbar, vorausgesetzt sie werden als syntaktisch und semantisch1) korrekt vom vorhandenen Rechner akzeptiert. Gehen wir einmal von der vertrauten Darstellung der Programme im Rechner aus, so müssen wir uns dennoch ständig im Klaren sein, daß Programme in ihrer Existenz an keine der möglichen Darstellungsformen gebunden sind. Wegen ihres mehr abstrakten als stofflichen Daseins benötigen Programme auch keinen Stoffwechsel, um ihre Existenz zu erhalten. Die Tatsache, daß Energie benötigt wird, um ein Programm
auf einer Rechenanlage auszuführen, kann natürlich nicht als (Energie-) Stoffwechsel betrachtet werden, da die Zufuhr von Energie
aktiv gesteuert wird,
, sondern der Interpretation von
dient.Programme sind auf Rechenanlagen in irgendwelchen Speichermedien abgespeichert. Es gibt Speichertypen, gewisse Halbleiterspeicher (Charge-Coupled Devices), die in gewissen Zeitabständen eine Erneuerung der enthaltenen Information benötigen [11] . In solchen Speichern abgelegte Programme benötigen also regelmäßig Energie, um verfügbar zu bleiben. Auch eine solche Energiezufuhr kann man, aus den gleichen Gründen wie oben, nicht im entferntesten als Energiestoffwechsel ansehen.
Es hat also wenig Sinn, im Hinblick auf Programme, auch wenn man von der festen Darstellung auf einer konkreten Rechenanlage ausgeht, ein Analogen zum Stoffwechsel lebender Organismen zu suchen.
Anders liegen die Verhältnisse allerdings bzgl. Reproduktion und Mutation. Die vielen Beispiele selbstreproduzierender Programme in den vorangegangenen Kapiteln zeigen, daß es durchaus Programme gibt, die zur identischen Reproduktion fähig sind. Allen Beispielprogrammen in höheren Programmiersprachen war gemeinsam,
daß sie an irgendeiner Stelle ihren eigenen Bauplan in kodierter Form enthalten (vgl. etwa Inhalt der Komponente C[23] in
3 aus Abschnitt 3.2.5., Textkonstante der Prozedur AB in
4 aus Abschnitt 3.2.7.). Dieser Bauplan läßt einen Vergleich mit der DNS lebender Zellen zu. Der Zusammenbau der Kopien selbstreproduzierender Programme mittels des Bauplans ist vergleichbar (zugegeben sehr gewagt) mit der Proteinsynthese bei Zellen. Man sollte sich jedoch einschränkend vergegenwärtigen, daß die Selbstreproduktion von Programmen im strengen Sinne keine Autoreproduktion darstellt, wie dies bei Organismen der Fall ist. Dies liegt daran, daß die Reproduktion von Programmen von außen veranlaßt wird (Steuerung durch das Betriebssystem) und die Initiative nicht beim Programm selbst liegt.
Mögliche Schalt- und Ubertragungsfehler in elektronischen Rechenanlagen können dazu führen, daß bei der Selbstreproduktion von Programmen Fehler entstehen (vgl. 7.1.). Mutationen sind also in diesem Sinne jederzeit möglich.
Insgesamt ergibt sich also, daß sich von den biologisches Leben ausmachenden Schlüsselprozessen bei Programmen nur Entsprechungen bzgl. Reproduktion und Mutation finden lassen. Systeme, die nur die Eigenschaften der Reproduktion und Mutation enthalten, sind daher im Sinne der Biologie nicht als lebendig zu bezeichnen. Insofern sind auch selbstreproduzierende Programme nicht lebendig. Selbstreproduzierende Programme lassen sich somit auch nicht mit lebendigen Organismen vergleichen. Die Biologie kennt jedoch Strukturen, die durchaus einen Vergleich mit selbstreproduzierenden Programmen zulassen.
Viren wurden lange Zeit als einfachste Organismen angesehen. Sie sind sehr viel einfacher gebaut als einzellige Lebewesen. In Wirklichkeit stellen Viren jedoch keine vollständigen Organismen dar, sondern sind subzellulare Gebilde, die fast nur aus DNS bestehen. Bei manchen Viren sind die DNS-Moleküle noch mit einer Hülle aus Proteinen, Fettstoffen und anderen organischen Substanzen umgeben. Viren verfügen über keinen eigenen Stoffwechsel. Erst wenn Viren in eine lebende Zelle eindringen, zeigen sie Lebenserscheinungen in Form von Reproduktion und Mutation. Sie benötigen zu ihrer eigenen Vermehrung also den Stoffwechsel echter Organismen. Außerhalb lebender Organismen sind Viren tot, sie können sich dann sogar zu Kristallen anordnen, was von Lebewesen nicht bekannt ist. Von den Schlüsselprozessen des Lebens weisen Viren also nur Reproduktion und Mutation auf und das auch nur dann, wenn eine fremde Stoffwechselmaschinerie Baustoffe und Energie zur Verfügung stellt. Diese Zusammenhänge sind in ähnlicher Form auch bei selbstreproduzierenden Programmen festzustellen. Solange ein selbstreproduzierendes Programm sich nicht im Speicher einer Rechenanlage befindet, kommt ihm bis auf seinen Informationsgehalt keine Bedeutung zu. Erst im Rechner und dann auch erst , wenn das Programm wirklich läuft ist ein selbstreproduzierendes Programm in der Lage zur Reproduktion und Mutation. Dem Programm steht dann Energie, die vom Rechner geliefert wird, zur Verfügung. Es bleibt jedoch bei aller ähnlichkeit zu beachten, daß ein Virus aktiv seine Reproduktion einleitet, indem es in das Baustoff und Energie liefernde System "Zelle" eindringt. Das kann ein selbstreproduzierendes Programm nicht, auch wenn es sich im Speicherplatz und Energie liefernden System "Rechner" befindet. Es bleibt auf Aktivierung durch das Betriebssystem angewiesen.
Wie die Biologie lehrt, sind lebende Organismen vielschichtigen Konkurrenzkämpfen unterworfen. Diese Konkurrenzkämpfe betreffen nicht nur einzelne Individuen, sondern ganze Arten (bzw. Populationen [24] Seite 337 ). Um erfolgreich zu sein, müssen diese Arten eine gewisse Variabilität ihres Erbgutes (Genom) aufweisen. Nur so können sie sich einerseits gegenüber der unbelebten Umwelt, die sich ständig verändert, und andererseits gegenüber der Konkurrenz anderer Arten behaupten. Die Eigenschaften der Arten und Individuen sind also ständig in Beziehung zur belebten und unbelebten Umwelt zu sehen (ökologie, vgl. [27] Seite 199 ff).
Selbstreproduzierende Programme, die sich in einer Rechenanlage befinden, sind von der "Umwelt" Rechner (= hardware + Systemsoftware) umgeben. Das Speichermedium, das die Programme enthält, ist sogar ein Teil dieser Umwelt. Als "belebte" Umwelt lassen sich andere, ebenfalls im Rechner befindliche selbstreproduzierende Programme ansehen. Die Möglichkeit der Mutation (s.o. 7.3. ) befähigt selbstreproduzierende Programme zur Evolution (s.u. 9.1. ). Es ist also nicht auszuschließen, daß die Wechselwirkungen selbstreproduzierender Programme miteinander und mit dem umgebenden Rechnersysterm zu anderen selbstreproduzierenden Programmen mit immer neuen Eigenschaften führen können. Die folgenden (spekulativen!) Modelle sollen versuchen, eine Vorstellung von derartigen auf Wechselwirkungen beruhenden Verhaltensweisen selbstreproduzierender Programme zu vermitteln.
Das nachfolgend beschriebene Grundmodell MOD1 geht von dem Hintergrund einer herkömmlichen Rechenanlage mit "von Neu-man Architektur" aus [12]. Eine solche Rechenanlage zeichnet sich in moderner Sicht durch einen (Zentral-)Prozessor
und ein oder mehrere E/A-Kanäle (extrem: E/A-Prozessoren) aus. Es herrscht multiprogramming Betrieb: K Programme
1, ...,
k, können zeitlich verzahnt, jedoch nicht durchgehend parallel verarbeitet werden. Die Programme sind nur zeitlich alternierend aktiv. In diesem Zusammenhang sind auch Begriffe wie time slicing und time sharing zu erwähnen [1].
Selbstreproduzierende Programme werden in MOD1 durch 2 Größen charakterisiert.
1, ...,
NUM initialisiert. Jedes Programm
erhält zyklisch für einen Zeittakt die "Aktivität" zugeteilt. Diese zyklische "Aktivierung" ist möglich, da sich zu jedem Zeitpunkt nur endlich viele Programme im Speicher aufhalten. Wächst die Anzahl der Programme durch Reproduktionen an, so vergrößert sich der Zyklus entsprechend. Jedes Programm im Speicher ist nach einer individuellen Anzahl von Zeittakten, in denen es "aktiv" war (Reproduktionszeit), in der Lage, sich selbst zu reproduzieren.MOD1 vermeidet Kollisionen. Die Programme können sich nicht gegenseitig in Bedrängnis bringen. Es gibt keine ausgezeichneten Programme, die in der Lage sind, andere Programme zu zerstören, indem sie deren Speicher beanspruchen. In diesem Sinne sind alle Programme äquivalent. Die Vermeidung von Kollisionen wird durch die Unendlichkeit des Speichers unterstützt. Jedes Programm (Individuum) ist beständig und produziert während seines ewigen Daseins identische Kopien (Nachkommen). Die Menge der vorhandenen Programme (Population) steigt ständig an. Bildhaft gesprochen gibt es in MOD1 keinen "Kampf ums Dasein", sondern friedliche Koexistenz. In einem solchen Modell gibt es keine Evolution, Die Motoren der Evolution, Mutation und Selektion, sind ohne Bedeutung, da es keinen Selektionsdruck gibt (s.u.).
Programme:
Umsetzung des Programme bestimmenden Tripels in die SIMULA-Struktur:
call PROGRAM;
begin
integer DELY, DISTANCE, IDENT;
end;
DELY
Reproduktionszeit
DISTANCE
Mindestentfernung der Kopie
IDENT
Identifizierung des Programms
Speicher:
Jede Speicherzelle ist in der Lage, ein Objekt vom Typ PROGRAM aufzunehmen. Sie ist außerdem mit ihren beiden Nachbarzellen verbunden. Diesen Eigenschaften trägt die SIMULA-Struktur CELL Rechnung:
class CELL;
begin
ref (PROGRAM) CONTENS;
ref (CELL) LEFT,RIGHT;
integer TIMECOUNT;
end;
(bzgl. TIMECOUNT s.u.)
Der Speicher selbst wird also als doppelt verkettete lineare Liste dargestellt ( [28] Seite 233 ff). Anfangs wird ein völlig leerer Speicher der festen Länge N angelegt. Je nach Bedarf werden an seine Enden neue Speicherzellen angehängt, so daß der Speicher potentiell unendlich ist, aber zu jedem Zeitpunkt eine feste Länge aufweist. Die beiden Zeiger
FIRST und LAST vom Typ ref (CELL) markieren das jeweils aktuelle linke bzw. rechte Ende der Liste. Die Funktionsprozeduren
ref (CELL) procedure ADDLEFT;und
ref (CELL) procedure ADDRIGHT;
bewerkstelligen das Anhängen einer neuen Speicherzelle an die bisherige Liste.
Beispiel:
Situation vor Aufruf von ADDLEFT
Situation nach Aufruf von ADDLEFT
Analog ADDRIGHT.
Zeitverhalten:
Startsituation: Zu Beginn der Simulation wird der noch leere Speicher mit einer festen Anzahl von Programmen (Objekten des Typs PROGRAM)
i, i=1,...,NUM
initialisiert. Es gibt M
NUM verschiedene Programme. Daraus ergibt sich, daß schon anfangs Programme mehrfach im Speicher vorhanden sein können. Da in den Speicherzellen die Programme nicht explizit stehen, sondern durch Verweise repräsentiert werden, müssen die Programme
j irgendwo ausführlich gespeichert sein. Zu diesem Zweck dient ref (PROGRAM) array P[1:M]; über den Zeiger P[j] besteht immer Zugriffsmöglichkeit auf das Programm
. Das Kopieren eines Programms
j wird durch Setze eines weiteren Zeigers auf
j realisiert. Diese Vorgehensweise zwingt fast dazu, vom "Programmtyp"
j zu sprechen, während die Zeiger auf
j die eigentlichen Programme oder Exemplare dieses Typs darstellen. Der Sprachgebrauch ist hier nicht eindeutig festzulegen. Ohne sprachliche Verwirrung zu stiften, werden wir deshalb im folgenden
j sowohl als Programm als auch als Programmtyp bezeichnen, je nachdem, welche Bezeichnung gerade angebracht erscheint. Das Feld integer array ST[1:M] enthält zu jedem Zeitpunkt der Simulation in den Komponenten ST[j] die momentane Anzahl der Exemplare des Programms P[j]. Zu Beginn der Simulation gilt also
Einlesen der NUM Zahlenpaare (PI,WHERE) liefert die raumliche Anordnung der NUM Programme: Das Programm P[PI] steht in der vom Zeiger LEFT aus gerechnet WHERE-ten Speicherzelle. (siehe Abbildung 8.2.2.A)
Abb. 8.2.2.A
Simulation: TIME-mal wird der Speicher von links nach rechts mittels des Zeigers C vom Typ ref (CELL) durchlaufen. Bei jeder Zelle wird getestet, ob sie leer ist oder nicht. Ist die Zelle leer, so geschieht nichts. Ist die Zelle durch ein Programm belegt, so wird weiter getestet, ob bei dieser Zelle
TIMECOUNT+1 = CONTENS.DELY
gilt. Im Ja-Fall wird eine Kopie des betreffenden Programms angelegt und TIMECOUNT wieder auf 0 gesetzt (ein neuer Reproduktionszyklus des betreffenden Programms kann beginnen). Andernfalls wird TIMECOUNT um 1 erhöht. Es kann geschehen, daß zum Anlegen einer Kopie der Speicher am rechten Ende verlängert werden muß; dann ist darauf zu achten, daß der Speicher nur bis zu seinem rechten Ende zu Beginn des betreffenden Durchlaufs durchlaufen wird. Erst der Durchlauf, der den nächsten Zyklus simuliert, erfaßt den nun zusätzlichen Speicherbereich. Dies wird durch die Variable
ref (CELL) OLD_LAST
unterstützt.
for T:=1 step 1 until TIME do
begin
C:-FIRST;
OLD_LAST:-LAST;
while C=/=OLD_LAST.RIGHT do
begin
[Erhöhe C.TIMECOUNT um 1];
if C.TIMECOUNT=C.CONTENS.DELY
then [Kopiere das Programm C.CONTENS; Setze C.TIMECOUNT zurück auf 0;]
C:-C.RIGHT
end
end;
Räumliches Verhalten:
Sei nun beim i-ten Durchlauf, i
TIME, durch den Speicher der Zeiger C auf eine Speicherzelle gestoßen, deren Programm reproduktionsbereit ist, das heißt:
= C.CONTENS
C.TIMECOUNT+1 = C.CONTENS.DELY
j wird nun kopiert. Ob die Kopie rechts oder links von der Zelle, auf die C zeigt, angelegt wird, entscheidet die Prozedur COPY mit Hilfe der SIMULA-Zufallszahlenfimktion RANDINT.1)
procedure COPY(C); ref (CELL) C; if RANDINT (1,2,U) = 1 then COPY_LEFT(C) else COPY_RIGHT(C);
Entsprechend der getroffenen Entscheidung wird also die Prozedur COPY_LEFT bzw. COPY_RIGHT aufgerufen, dieden eigentlichen Kopierprozeß durchführt.
procedure COPY_RIGHT(C); ref (CELL) C; begin ref (CELL) HELP; [Setze HELP auf c]; [Bewege HELP um soviele Zellen nach rechts, wie die Komponente DISTANCE des Programmsangibt. Wird dabei vorzeitig das Ende des Speichers erreicht, so erweitere mittels ADDRIGHT den Speicher um entsprechend viele Zellen an seinem rechten Ende. ] if HELP.CONTENS==none then [Lege die Kopie(=C.CONTENS)
in der leeren Zelle ab, auf die HELP Zeigt (= HELP.CONTENS:-P[j])] else [Bewege HELP solange im Speicher weiter nach rechts, bis HELP auf eine leere Speicherzelle zeigt, oder das rechte Ende des Speichers erreicht ist. Ist letzteres der Fall, so setze
Abb. 8.2.2.B
HELP:-ADDRIGHT; Lege die Kopie von
in der Zelle ab, auf die HELP zeigt. ]
end;
Anhang C.1. zeigt MODI in ausführlicher Form als lauffähiges SIMULA-Programm. Die Datenstrukturen dieses Programms verdeutlicht Abbildung 8.2.2.B..
Eingabeparameter des SIMULA-Programms für MOD1:
N
M
DELY,DISTANCE
NUM
PI,WHERE
TIMESimulationsmodelle bzw. -programme haben in der Regel experimentellen Charakter. Die Erkenntnisse, die sich mittels MOD1 gewinnen lassen, sind beschränkt und größtenteils vorherberechenbar; sie benötigen kein Experiment. Der einzige Nichtdeterminismus liegt in der zufälligen Wahl der Richtung, in der die Kopie eines Programms im Speicher angelegt wird. MOD1 ist als Grundmodell zu werten, auf das weitere Modelle mit mehr Möglichkeiten aufbauen. Außerdem demonstriert MOD1 einen gewissen Satz von Grundelementen, die auch den weiteren Modellen M0D2 und MOD3 zu eigen sind. Es handelt sich dabei um
Durch änderung einer oder mehrerer dieser 4 Komponenten lassen sich andere Grundmodelle erzielen; besonders (iv) dürfte sehr viele Variationsmöglichkeiten bieten, (i) bis (iv) sind nicht ganz unabhängig von einander. Die Charakterisierung der Programme durch die Größen DELY und DISTANCE bestimmt das zeitliche Verhalten (iii) (mittels DELY) und das räumliche Verhalten (iv) (mittels DISTANCE) wesentlich mit.
Die Wahl von (i) bis (iv) ist auch vor dem Hintergrund der unterstellten "von Neuman Architektur" des Rechners zu sehen . Eine charakteristische Eigenschaft der von Neuman-Rechner ist die Tatsache, daß es zu jedem Zeitpunkt nur jeweils einen Strom von Instruktionen und Daten gibt. Man spricht daher auch von SISD-Maschinen (single-instruction single-data stream) [12]. Für moderne Rechnersysteme trifft diese Charakterisierung jedoch nicht ganz zu, da durch Hinzunahme weiterer Prozessoren, speziell E/A-Prozessoren, das SISD-Prinzip durchbrochen wird; es liegt eigentlich MIMD-Organisation (multiple-instruction multiple-data stream) vor. Trotzdem wird man heutige Rechner kaum als MIMD-Rechner bezeichnen, da die Anzahl der gleichzeitig arbeitenden Prozessoren sehr klein ist. Die Idee, die hinter MIMD steht, ist jedoch eine große Zahl (ca. 100 bis 1000) [26] unabhängiger Prozessoren, um ein Höchstmaß an Parallelverarbeitung zu erzielen. Neben SISD-und MIMD-Maschinen gibt es außerdem noch die Klassen der SIMD (single-instruction multiple-data stream)- und der MISD (multiple-instruction single-data stream)-Maschinen. Nahezu alle heutigen Rechner sind im weitesten Sinne SISD-Maschinen. Es entsteht also die Frage:
Welche Modelleigenschaften müßte MOD1 haben, wenn MODT als Grundmodell für unorthodoxe Rechenanlagen (=nicht SISD-Hechner) [6] gedacht wäre?
Voraussetzung ist narürlich die Existenz selbstreproduzierender Programme auf solchen Maschinen.
j, j
[M]:
Die Anzahl Sj(T) der Exemplare nach dem T-ten Speicherdurchlauf beträgt
j(0) * 2(T
DELY-Komponente von
)
wobei Sj(0) die Anzahl der Exemplare von
j vor Beginn der Simulation ist.
j nach jedem WHEN_CON-ten Speicherdurchlauf mittels
procedure CONTROL;
in tabellarischer Form ausgedruckt werden.
procedure DUMP;
DUMP gibt den Inhalt des gesamten Speichers von links nach rechts aus, indem für eine leere Zelle das Zeichen "
" und für eine besetzte Zelle die Komponente IDENT des gespeicherten Programms ausgedruckt wird.
procedure AVERAGE;
AVERAGE gibt in tabellarischer Form die durch¬schnittliche Entfernung der Exemplare der jeweiligen Programmtypen an. Grundlage ist der Abstand 1 für direkt benachbarte Speicherzellen.
Die Aufrufe von DUMP und AVERAGE werden durch die integer-Variablen WHEN_DUM und WHEN_AVE gesteuert. DUMP wird nach jedem WHEN_DUM-ten Speicherdurchlauf aufgerufen, entsprechend AVERAGE.
Aus I und II ergibt sich, daß die in Anhang C.1. wiedergegebene Implementierung von MOD1 drei mo¬dellunabhängige Eingabeparameter, nämlich
WHEN_CON WHEN_DUM WHEN_AVE
enthält, die die Ausgabe steuern.
Aufwand:
Speicherplatz: In MOD1 ist ile Anzahl der vorhandenen Programmtypen konstant. Damit haben auch die Felder ST und P während der Simulation eine konstante Größe. Nur die den Speicher darstellende Liste wird - bei hinreichend großer Anzahl TIME der Speicherdurchläufe - während der Simulation anwachsen. Wie stark dieses Wachstum während eines Speicherdurchlaufs ist, hängt von den vorhandenen Programmtypen ab. Bei kleinen Reproduktionszeiten (Komponente DELY) der Programme und großen Entfernungen der Kopien (Komponente DISTANCE) erfolgt die Zu nahme besonders schnell. Da die Gesamtzahl der vorhandenen Programraexemplare (siehe I.) exponentiell ansteigt, wächst auch die Länge des Speichers im Verlauf der Simulation insgesamt exponentiell; die vorgenannten Kriterien machen daher nur einen Faktor aus.
Laufzeit: Die Laufzeit des SIMULA-Programms für MOD1 hängt von allen Modellparametern ab. Eine genaue Abschätzung kann im Rahmen dieser Arbeit nicht mehr vorgenommen werden. Da der Zeitaufwand für einen Speicherdurchlauf von der Länge des Speichers abhängt, ergibt sich auf jeden Fall ein exponentieller Zusammenhang zwischen der Anzahl der Speicherdurchläufe und der Laufzeit von MOD1.
Das exponentielle Verhalten des Aufwands macht MOD1 für statistische Zwecke wenig brauchbar und unterstreicht die Bedeutung von MOD1 als ein ledigliches Grundmodell. Das ungehinderte exponentielle Anwachsen an Programmexemplaren wird in den folgenden Modellen durch ein geändertes räumliches Verhalten und durch Einführung von konkurrierendem Verhalten verhindert.
Im Grundmodell MOD1 kann jedes reproduktionsfähige Programm
seine Kopie
ungehindert in einer freien Speicherzelle ablegen. Insofern gibt es zwischen den Programmen keine echten Konfliktsituationen und damit keine Konkurrenz. Das Fehlen von Konkurrenz in MOD1 macht das Eintreten von Evolution unmöglich. Ein weiterer Aspekt von MOD1 ist die Beständigkeit der Programme.
In Form von MOD2 soll nun MOD1 dahingehend erweitert werden, daß Programme in der Lage sind, ihre Kopien in bereits durch andere Programme besetzte Speicherzellen zu schreiben. Dabei werden die alten Inhalte der Speicherzellen, also Programme, gelöscht. Es wird zweierlei erreicht:
Konkurrierendes Verhalten ist ein spezielles Verhalten von Programmen untereinander. Wir fuhren daher ganz allgemein
(v) Verhalten der Programme untereinander
als weitere Modellkomponente ein. In 8.3.1. erfolgt eine detaillierte Beschreibung von MOD2.
Programme: Die einzige charakteristische Größe eines Programms ist seine Laufzeit (=Reproduktionszeit). Die Laufzeit ist gleich der Anzahl von Zeittakten, die das Programm jeweils aktiv sein muß, um sich reproduzieren zu können.
Das Modell eines Programms ist somit ein 2-Tupel, bestehend aus der Programmidentifikation und der Laufzeit.
seine Kopie
ablegt, soll nicht beliebig von diesem abgegrenzten Speicherhereich entfernt liegen, sondern nur um eine konstante Anzahl von Zellen. Es ergibt sich also als Zielbereich für eine Kopie ein durch L(t) und R(t) abgegrenzter Speicherbereich (Abb. 8.3.1.A). Innerhalb dieses Speicherbereichs ist jede Zelle gleichwahrscheinliches Ziel für die Kopie
.
Abb.: 8.3.1.A
Ein derartiges räumliches Verhalten garantiert eine kontrollierte Ausbreitung der Programme. Es können nicht plötzlich beliebig weit entfernte und isolierte "Populationen" entstehen.
reproduktionsfähig, so wird gemäß (iv) eine beliebige Speicherzelle ausgewählt, in der die Kopie
abgelegt werden soll. Ist diese Speicherzelle leer, so tritt kein Konflikt auf. Andernfalls ist die Speicherzelle bereits mit einem Programm
besetzt, und ein Entscheidungsmechanismus muß herangezogen werden um zu bestimmen, ob
das Programm
überschreiben darf oder nicht. Fällt die Entscheidung positiv aus, so überschreibt
das Programm
, ist sie negativ, so hat
keine Ausweichmöglichkeit und wird eliminiert. Ein Konfliktfall endet also immer für eines der beteiligten Programme "tödlich".Erst durch Angabe des in (v) genannten Entscheidungsmechanismus wird die Beschreibung von MOD2 vollständig. Es sind sicherlich sehr viele Entscheidungsmechanismen für MOD2 denkbar, die auf unterschiedlichsten Faktoren beruhen. Wir wollen, um MOD2 möglichst einfach zu halten, einen Entscheidungsmechanismus angeben, der nur auf den beiden jeweils aufeinandertreffenden Programmen beruht. Damit dieser Entscheidungsmechanismus nicht zu starr wird, wird er mit Wahrscheinlichkeiten belegt, was indirekt doch eine Berücksichtigung weiterer, allerdings unbekannter, Faktoren bedeutet.
(8.3.1.1) Definition: Sei n
N. Eine n
n-Matrix
V = (vij)
n(
) (Ring der n-reihigen Matrizen über dem Körper der reellen Zahlen) heißt n-reihige Vorrangmatrix, falls gilt:
Vij
[0,1]
für alle i,j
[n]
Sei
:= {
1,...,
M] die Menge der in MOD2 vorkommenden Programmtypen. Eine M-reihige Vorrangmatrix zusammen mit einer entsprechenden Interpretation liefert einen Entscheidungsmechanismus für MOD2.
(8.3.1.2) Definition: Sei M die Anzahl der in MOD2 vorkommenden Programmtypen. Sei V = (vij) eine M-reihige Vorrangmatrix. Die Komponenten vij werden wie folgt interpretiert:
Soll die Kopie
eines Programms
vom Typ
i in einer Speicherzelle abgelegt werden, in der sich bereits ein Programm
des Typs
j befindet, so bedeutet vij:
Mit der Wahrscheinlichkeit vij überschreibt
das Programm
.
Mit der Wahrscheinlichkeit (1-vij) überschreibt
das Programm
nicht,
bleibt erhalten und
wird eliminiert.
Als Entscheidungsmechanismen für MDD2 sind genau die M-reihigen Vorrangmatrizen zugelassen. Die Vorrangmatrix ist also ein Parameter von MOD2. Durch die Vorrangrmatrix erhält MOD2 einen nichtdeterministischen Charakter.
Im Gegensatz zu MOD1 werden. Programme durch die einfachere SIMULA-Struktur
class PROGRAM; begin integer IDERT,DELY; end;
IDENT
Identifizierung
DELY
Reproduktionszeit
dargestellt.
Die Realisierung des Speichers ist mit Schwierigkeiten verbunden. Einerseits muß der Speicher potentiell unendlich sein (Listenkonzept), andererseits ist wegen 8.3.2.(iv) direkter Zugriff auf die Speicherzellen wünschenswert (Arraykonzept). Da Listenkonzept und Arraykonzept nicht miteinander vereinbar sind, muß bei einer Kompromißlösung irgendwo die Priorität gesetzt werden. Direkter Zugriff wirkt sich günstig auf die Laufzeit von MOD2 aus. Wir setzen deshalb hier die Priorität und stellen den Speicher als array dar. Um der geforderten Unendlichkeit des Speichers wenigstens gerecht zu werden, muß es sich dabei um dynamische arrays handeln. Dynamische arrays sind in SIMULA im Rahmen des Klassenkonzepts möglich:
class STORAGE(Q); integer Q; begin ref (CELL) array ELEMENT(1:Q); end;
wobei die einzelnen Speicherzellen (Typ : CELL) wie in MOD1 dargestellt werden:
class CELL; begin ref (PROGRAM) CONTENS; integer TIMECOUNT; end;
Zugriff auf den Speicher liefert der globale Zeiger ref (STORAGE) STORSPOINTER.
Zu Beginn der Simulation wird der Speicher mit N Speicherzellen initialisiert. Dies geschieht durch die Zuweisung
STOREPOINTER: new STORAGE(N);
Während der Simulation wird der Speicher immer dichter mit Programmen "besiedelt" und muß von Zeit zu Zeit erweitert werden. Wann der Speicher erweitert wird, gibt die integer Variable PERCENT an: Ist der Speicher zu PERCENT % belegt - getestet wird dies mit Hilfe von boolean procedure OVERFLOW - , so wird eine Erweiterung des Speichers vorgenommen. Die Erweiterung des Speichers wird durch die Prozedur
procedure NEW_STORAGE(MORE); integer MORE;
vorgenommen. NEW_STORAGE generiert ein neues Objekt der Länge N+2*MORE vom Typ STORAGE, kopiert den Inhalt des alten Speichers in dieses neue Objekt und setzt den globalen Zeiger STOREPOINTER entsprechend um (Abb. 8.3.2.A). Nach Ablauf von NEW_STORAGE ist der Speicher an jedem Ende um MORE Zellen erweitert und die Variable N, die immer die aktuelle Länge des Speichers angibt, um 2*MORE vergrößert.
Abb.: 8.3.2.A
Die den Mechanismus der Speichererweiterung bestimmenden Größen PERCENT und MORE sind wichtige Parameter von MOD2 als SIMULA-Programm. Je kleiner PERCENT und je größer MORE gewählt sind, desto besser wird die Unendlichkeit des Speichers angenähert. Setzt man PERCENT> 100, so artet die Realisierung von MOD2 in ein Modell mit endlichem Speicher aus.
Zeitverhalten:
Startsituation: Zu Beginn der Simulation werden wie in MOD1 die M Programme (besser: Programmtypen)
1,...
M eingelesen und im Feld
ref (PROGRAM) array P [1:M];
abgespeichert. Das Feld
integer array ST [1:M]
enthält zu jedem Zeitpunkt der Simulation in den Komponenten ST[j] die momentane Anzahl der im Speicher befindlichen Exemplare des Programms
j. Die Anfangsbelegung von ST wird ebenfalls eingelesen, da sie angibt, mit wievielen Exemplaren der einzelnen Programme der Speicher initialisiert wird. Der leere Speicher mit der Startlänge N wird initialisiert, indem für jedes j
[M] die ST [j] Exemplare des Programms
M in den Speicher geschrieben (durch Setzen von Verweisen) werden. Die zufällige Verteilung der Programme im Speicher wird mittels des Zufallszahlengenerators RANDINT(1,N,U) gewährleistet; jede Speicherzelle ist gleichwahrscheinlich. Es wird jedoch verhindert, daß bereits bei Initialisierung Programme überschrieben werden. Selbstverständlich muß gelten:
ST[j]
N
Zum Abschluß der Initialisierung wird die M-reihige Vorrangmatrix eingelesen und im Feld
CONFLICT [1:M,1:M]
abgespeichert.
Simulation: TIME-mal wird der Speicher von rechts nach links bzw. von links nach rechts durchlaufen. Jede Durchlaufrichtung ist gleichwahrscheinlich. Durch zufällige Wahl der Durchlaufrichtung soll eine Bevorzugung einzelner Programme vermieden werden. Während eines Durchlaufs wird für jede nicht leere Speicherzelle die Prozedur MATCH aufgerufen. MATCH testet, ob das in der betreffenden Speicherzelle befindliche Programm reproduktionsfähig ist und legt eventuell eine Kopie des Programms an. Damit ist es möglich, daß ein Aufruf von MATCH die prozentuale Speicherbelegung größer als PEECENT werden läßt und ein Aufruf von NEW_STORAGE notwendig wird:
for T=1 step 1 until TIME do
begin
[Lege Durchlaufrichtung fest];
if [Durchlaufrichtung = 'von rechts nach links']
then
begin
for I:=1 step 1 until N do
if [I-te Zelle ungleich leer]
then
begin
MATCH(I);
if OVERFLOW then NEY_STORAGE(MORE)
end
end
else
for I:=N step -1 until 1 do
if [I-te Zelle ungleich leer]
then
begin
MATCH (I);
if OVERFLOW then NEW_STORAGE(MORE)
end
end + * * SIMULATION * * +;
Funktionsweise der Prozedur MATCH:
procedure MATCH(I); integer I; begin![]()
![]()
boolean IS_COPY; IS COPY:=false; [Erhöhe TTMECOUNT-Komponente der l-ten Speicherzeile um 1 ;] if [TIMECOUNT-Komponente der I-ten Speicherzelle gleich DELY Komponente des in der I-ten Speicherzelle befindlichen Programms] then begin comment * * * Reproduktion des in der I-ten Zelle befindlichen Programms * * * ; [Setze TIMECOUNT-Komponente der I-ten Speicherzelle auf 0]; [Wähle eine zufällige Zelle des Speichers aus. Sei die Wahl auf die W-te Speicherzelle gefallen]; comment * * * siehe dazu unten (iv) * * * ; if [W-te Speicherzelle gleich leer] then begin comment * * * Ungehindertes Ablegen der Kopie* * *; [Schreibe Kopie in die W-te Speicherzelle]; IS_COPY:=true end eise begin end else begin comment * * * W-te Speicherzelle ist bereits besetzt « * * * ; [Treffe Entscheidung mittels der Vorrangmatrix, ob die Kopie des in der I-ten Zelle befindlichen Programms das Programm in der W-ten Zelle überschreiben darf]; comment * * * siehe unten (v) * * * ; if [überschreiben nicht möglich] then comment * * * es geschieht nichts * * * else begin [Schreibe Kopie in die W-te Speicherzelle] IS COPY:=true end end; comment * * * Falls das Programm aus Speicherzelle I seine Kopie im Speicher ablegen konnte, muß noch in Abhängigkeit von der Durchlaufrichtung die Komponente TIMECOUNT der W-ten Speicherzelle gesetzt werden * * * ; if IS_COPY then begin if W
1 then begin if [Durchlaufrichtung = 'von links nach rechts'] then [{TIMECOUNT-Komponente von Zelle W}:=0] else [{TIMECQUNT-Komponente von Zelle W}:=-1] end else if [Durchlaufrichtung = 'von links nach rechts'] then [{TIMECOUNT-Komponente von Zelle W}:=-1] else [{TIMECQUNT-Komponente von Zelle W}:=0] end end end * * * MATCH * * * ;
Räumliches Verhalten:
Die Auswahl der Speicherzelle, in die ein Programm seine Kopie ablegt, erfolgt über die SIMULA-Zufallsfunktion RANDINT in Form des Aufrufs
RANDINT(1,N,U_CELL)
wobei N die aktuelle Länge des Speichers und U_CELL ein von RANDINT benötigter name-Parameter ist. Jede der N Speicherzellen ist gleichwahrscheinlich (vgl. genaue Beschreibung der Funktion RANDINT in [25] ). Die Auswahl der Speicherzellen für die Kopie weicht geringfügig von der in 8.3.1.(iv) beschriebenen ab. Zusammen mit der Speichererweiterungsstrategie aus 8.3.2.(iii) ergibt sich jedoch der in 8.3.1-(iv) beschriebene Gesamteffekt.
Verhalten der Programme untereinander:
In der SIMULA-Version von MOD2 wird die Vorrangmatrix V = (Vij) nicht als Element aus
M(
), sondern als Element aus
M(
) dargestellt:
integer array CONFLICT [1:M,1:M]
Jedes vij(=CONFLICT[i,j]) wird als "vij Hundertstel" interpretiert. Daher nimmt jedes vij höchstens den Wert 100 an. vij = 0 kann aus programmtechnischen Gründen nicht zugelassen werden (Abweichung von 8.3.1.(v)).
Beispiel:
M = 5
Konflikt eines Programms
vom Typ
mit
einem Programm,
vom Typ
, d.h.
versucht
zu überschreiben:
Entscheidung (vgl. Beschreibung der Prozedur MATCH):
if CONFLICT[2,3]<RANDINT(1,100,U_CONFLICT)
then [
überschreibt
nicht]
else [
überschreibt
]
Anhang C.2. zeigt MOD2 als ausführlich kommentiertes SIMULA-Programm. Einen überblick über die in diesem Programm benutzten Datenstrukturen gibt Abb. 8.3.2.B..
Abb. 8.3.2.B
Eingabeparameter des SIMULA-Programms für MOD2:
N
M
DELY,ST [...]
CONFLICT
TIME
MORE,PERCENTDas SIMULA-Programm für MOD2 bietet ein weites Experimentierfeld, was schon aus der Vielzahl der Eingabeparameter ersichtlich ist. Leider kann keine der obigen Fragestellungen im Rahmen dieser Arbeit mehr näher untersucht werden.
Aufwand:
Speicherplatz: Die Anzahl der in MOD2 vorhandenen verschiedenen Programmtypen bleibt während der gesamten Simulation konstant. Damit bleibt auch der durch die Felder CONFLICT, ST und P bedingte Speicherplatzaufwand konstant. Nur das den Speicher simulierende dynamische Feld, auf das der Zeiger STOREPOINTER verweist, kann, während der Simulation größer werden. In welchem Maße dieses Feld wächst, hängt von den Parametern MORE und PERCENT ab (vgl. 8.3.2.(ii)). Ist PERCENT>100 gewählt, so bleibt die Größe des Feldes immer konstant, andernfalls nimmt die Größe im Verlauf der Simulation zu. Die Zunahme erfolgt exponentiell mit der Anzahl der Speicherdurchläufe. Der Faktor (100-PERCENT)/100 (relative Anzahl der freien Speicherzellen) sorgt jedoch dafür, daß diese Zunahme nicht so ungehemmt erfolgt wie im SIMULA-Programm zu MOD1, Zu beachten ist, daß eine Vergrößerung des Feldes immer mit der Generierung eines neuen Objekts vom Typ STORAGE verbunden ist (Aufruf von NEW_STORAGE). Das jeweils alte Objekt bleibt im Speicher vorhanden.
Laufzeit: Die Laufzeit ist im wesentlichen von der Anzahl der Speicherdurchläufe und der Länge des den Speicher simulierenden Feldes abhängig. Da die Größe dieses Feldes exponentiell zur Anzahl der Speicherdurchläufe wächst, hängt auch die Laufzeit exponentiell von der Anzahl der Speicherdurchläufe ab. Auch in bezug auf die Laufzeit hat der Faktor (100-PERCENT)/100 eine hemmende Wirkung. Extremfälle:
Lebende Pflanzen- und Tierorganismen waren nicht immer so beschaffen wie heute. Vielmehr haben sie sich unter langsamer, aber stetiger Abwandlung ihrer Eigenschaften aus anderen (einfacheren) Lebewesen entwickelt. Man bezeichnet diesen Vorgang als biologische Evolution. Evolution findet auch heute noch, allerdings kaum merklich, statt. Eine kausale Erklärung für die biologische Evolution versucht die Evolutionstheorie anzugeben. Die moderne Evolutionstheorie läßt sich in wenigen Worten wie folgt darlegen (vgl. [24] [13] [27] [15]):
Lebewesen erzeugen viel mehr Nachkommen, als zur
Erhaltung ihrer jeweiligen Art notwendig wäre. Diese
Nachkommen variieren in ihrem Genbestand (s. 7.2.). Auch
Nachkommen derselben Eltern sind in der Regel nicht alle
gleich. Die Veränderlichkeit des Genbestands wird durch
die Fähigkeit der Gene zur Mutation (s. 7.2.) bewirkt.
Die Mutationsrate lebender Organismen ist äußerst gering
und liegt bei etwa
bis
pro Gen. (Diese Werte
gelten unabhängig von der Generationsdauer der einzelnen
Arten und sind selbst ein Ergebnis der Evolution:
Sie bewirken eine ausreichende Anpassungsfähigkeit der
Arten, ohne daß die Arten in ihrem Genbestand instabil
werden). Da die Gene die Eigenschaften eines Individuums
ausmachen, unterscheiden sich die überzahlreichen
Nachkommen in ihren Eigenschaften. Die Lebewesen stehen
untereinander in einem ständigen Wettbewerb um günstige
Lebensbedingungen. Es herrscht ein permanenter Kampf ums
Dasein (struggle for life). Es überleben nur die an die
Umwelt bestangepaßten Nachkommen (survival of the fittest).
Nur diese Individuen gelangen zur Fortpflanzung.
Die anhaltende natürliche Auslese (natural selection)
bewirkt, daß die weniger tauglichen Individuen einer
Population ([24] S.337) zurückgedrängt und schließlich
ausgemerzt werden. Der Zwang zur bestmöglichen Anpassung
an die Umwelt (Selektionsdruck) führt zu immer
optimaleren Eigenschaften der Lebewesen (transformierende
Selektion). Ungeachtet, ob eine solche Anpassung - bei
gleichgebliebener Umwelt - bereits eingetreten ist,
entstehen mit konstanter Rate neue Mutationen. Ist die
Anpassung weit fortgeschritten, so nimmt die Wahrscheinlichkeit
für "positive" Mutationen ab. In diesem Fall
sorgt die Selektion dafür, daß die genetische Zusammensetzung
einer Population konstant bleibt, indem auftretende
"negative" Mutationen - wenn diese nicht schon
letal verlaufen sind - wieder beseitigt werden
(stabilisierende Selektion). Entstehen jedoch positive
Mutationen, oder verändert sich die Umwelt erneut, so
tritt wieder transformierende Selektion ein. Mutation
und Selektion stellen die eigentlichen "Motoren" der
Evolution dar. Für die Evolution können allerdings noch
andere Faktoren eine Rolle spielen, z.B. Isolation,
Zufallswirkung ([15] Seite 317 ff.), geschlechtliche
oder ungeschlechtliche Vermehrung.
In 7.4. wurden selbstreproduzierende Programme mit Viren verglichen. Obwohl Viren keine Lebewesen sind, laßt sich an ihnen Evolution beobachten. Die Gründe dafür sind:
Es liegt der Schluß nahe, daß Evolution auch bei selbstreproduzierenden Programmen möglich ist, falls diese Mutation und Selektion gleichzeitig ausgesetzt sind. In 8.3. haben wir mit MOD2 ein Modell für konkurrierendes Verhalten ( = Kampf ums Dasein) von Programmen entwikkelt. Die Programmtypen in MOD2 lassen sich durch ihre Reproduktionszeit und ihre Stellung in der Vorrangmatrix beschreiben. In MOD2 werden sich diejenigen Programme behaupten, die in der Vorrangmatrix eine günstige Stellung einnehmen, also relativ leicht Speicherplatz für ihre Kopien finden, bzw. die eine kurze Reproduktionszeit aufweisen. Es herrscht in MOD2 also Selektionsdruck in Richtung
Würde es einem Programmtyp gelingen, eine kürzere Reproduktionszeit zu erlangen, oder eine bessere Stellung in der Vorrangmatrix einzunehmen, so würden seine einzelnen Exemplare den in MOD2 vorhandenen Konkurrenzkampf besser bestehen können. Als Ursache für solche Veränderungen kommt Mutation in Frage. In 9.2. wird MOD2 dahingehend erweitert, daß Programme die Möglichkeit erhalten zu mutieren. Damit liegt dann ein Modell vor, in dem alle Voraussetzungen für das Eintreten von Evolution gegeben sind. Die SIMULA-Version dieses Modells stellt dann ein Rechnerprogramm zur Simulation von Evolution bei selbstreproduzierenden Programmen dar.
Bei dieser Gelegenheit sei erwähnt, daß Rechnerprogramme ganz allgemein ein adäquates Mittel zur Simulation von Evolutionsprozessen darstellen. Der Grund ist, daß Evolution (biologische, chemische, kosmische,...) in der Regel einen sehr langen Zeitraum benötigt, um merkliche Veränderungen hervorzurufen und daher Simulationsmodelle immer vor dem Problem stehen, diesen Zeitraum, in dem ja ständig etwas "geschieht", zu simulieren. Nur mit schnellen Rechenanlagen, die eine Vielzahl von Operationen in Sekundenbruchteilen durchführen können, ist man in der Lage, diesen Zeitraum auf ein erträgliches Maß zu komprimieren (vgl. [8]).
Wir gehen von der Vorstellung aus, daß während der
Reproduktion eines Programms
mit einer gewissen
Wahrscheinlichkeit
(Modellparameter) Fehler unterlaufen,
so daß die Kopie
von
verschieden ist und in diesem
Sinne eine Mutation des Programms
darstellt. I.a. werden
die Fehler minimal und die Unterschiede von
und
gering sein. Da in MOD3 Programme durch ihre Peproduktionszeit
und ihre Stellung in der Vorrangmatrix
beschrieben werden, müssen sich Mutationen in einer Änderung
dieser Werte nach außen bemerkbar machen, vorausgesetzt,
ist noch ein selbstreproduzierendes Programm.
Führt eine Mutation nicht zu einem selbstreproduzierenden
Programm, so liegt eine Letalmutation vor. Da Mutationen
immer sprunghaft und ungerichtet verlaufen, ist
das Auftreten einer Letalmutation jederzeit möglich. In
MOD3 gibt die Wahrscheinlichkeit
(Modellparameter)
ein Maß für die Häufigkeit der letal ausgehenden
Mutationen an. Jede nicht letal verlaufende Mutation bringt
im Grunde ein erstes Exemplar eines neuen Programmtyps
hervor. Entsprechend werden Mutanten in MOD3 registriert,
ohne daß jedoch die "Abstammung" der Mutante verloren
geht. Jedes Auftreten einer nicht letalen Mutation bewirkt
also in MOD3 immer eine Vergrößerung der Vielfalt
an vorhandenen Programmtypen. Da durch den Konkurrenzkampf
der Programme untereinander ein Selektionsdruck
in Richtung kürzere Reproduktionszeit (höhere
Vermehrungsrate) bzw. günstige Stellung in der Vorrangmatrix
besteht, werden diejenigen Mutanten gegenüber ihren
Originalprogrammen im Vorteil sein, die bzgl. dieser Werte
Verbesserungen aufweisen (Erhöhung der Fitneß). Solche
Mutanten werden - unter gewissen Nebenbedingungen -
in der Lage sein, die Prograramtypen, denen die Ursprungsprogramme
angehören, zu verdrängen (Selektion).
Selbstverständlich stellen durch Mutation entstehende Programmtypen
keine endgültigen Formen dar, sondern können selbst
wieder Mutationen hervorbringen. Da die Reproduktion von Programmen
wie eine "ungeschlechtliche" Vermehrung verläuft,
kann jede Mutante als Ausgangspunkt einer sich potentiell
aufzeigenden "Linie" auseinander hervorgehender
Programme (Typen) (Klons siehe [24] Seite 313) verstanden
werden.
. Mit der Wahrscheinlichkeit
verläuft die Mutation letal. Verläuft die Mutation nicht
letal, so unterscheiden sich Mutante und Originalprogramm
mit der Wahrscheinlichkeit
in der Komponente
DELY. Mit der Wahrscheinlichkeit
liegt der
Unterschied im Konfliktverhalten (Vorrangmatrix) gegenüber
anderen Programmen. Das Auftreten einer nicht
letalen Mutation bewirkt die Erhöhung der Anzahl M
der momentanen Programmtypen in MOD3 um 1. Stellt die
Kopie eines Programms eine Mutation dar, so wird mit
der Mutante weiter verfahren, als handele es sich um
eine korrekte Kopie.
class PROGRAM;
begin
integer IDENT,DELY,MUT;
text PROGNAME;| |
end; | | | |
| | | Anzahl der Mutationen
| | Reproduktionszeit
| Identifizierung
Name des Programms
dargestellt. Die Komponenten DELY und PROGNAME
ergeben sich aus der Beschreibung in 9.2.1.(i).
Die Komponente PROGNAME würde zur Identifizierung
der einzelnen Programmtypen ausreichen. Trotzdem
kann auf die Größe IDENT aus programmtechnischen
Gründen (array-Zugriffe) nicht verzichtet werden.
Die Komponente MUT gibt zu jedem Zeitpunkt die
Anzahl der Mutanten an, die aus dem dargestellten
Programm hervorgegangen sind.class PROG(P);integer P; ] anstelle von begin ] ref (PROGRAM) ref (PROGRAM) array VECTOR[1:P]; ] array P[1:M] end; ] ] ref (PROG) PROGPOINTER; ] class ST(P);integer P; ] anstelle von begin ] integer array integer array S[1:P] ] ST[1:M] end; ] ] ref (ST) STPOINTER; ] class CONFLICT(P);integer P; ] anstelle von begin ] integer array integer array MAT[1:P,1:P]; ] CONFLICT[1:M,1:M] end; ] ] ref (CONFLICT) CONPOINTER; ]
Startsituation Die Beschreibung der Startsituation
überträgt sich aus 8.3.2.(iii) unter Berücksichtigung
der gerade beschriebenen organisatorischen Änderungen
der Datenstrukturen. Es bleibt nur zu vermerken,
wie die beiden zusätzlichen Komponenten MUT
und PROGNAME initialisiert werden. Sei
die Menge der anfangs vorkommenden Programmtypen,
dann wird bei der Initialisierung
auf 0 gesetzt
, "P2" für den
Programmtyp
, u.s.w., zugewiesen.Simulation: Die Beschreibung der Simulation kann im wesentlichen aus 8.3.2.(iii) übernommen werden.
Da MOD3 eine echte Erweiterung von MOD2 darstellt, bedarf es jedoch einiger Ergänzungen, die die Erzeugung und Behandlung von Mutationen betreffen. Diese Ergänzungen äußern sich in einem Satz von Prozeduren, die sämtlich von der Prozedur MATCH aufgerufen werden. Bevor wir die so erweiterte Prozedur MATCH angeben können, müssen diese zusätzlichen Prozeduren erläutert werden.
Die modellwirksamen Eigenschaften eines Programms sind die Komponente DELY und die Stellung des Programms in der Vorrangmatrix. Nur Mutationen in einer dieser beiden Eigenschaften haben in MOD3 einen Selektionswert. In der SIMULA-Version von MOD3 werden Mutationen von Programmen mittels der Funktionsprozedur
ref (PROGRAM) procedure MUTANT(X); ref (PROGRAM) X;
erzeugt. MUTANT liefert als Ergebnis einen Zeiger auf ein Objekt vom Typ PROGRAM. Dieses Objekt unterscheidet sich geringfügig in einer der oben genannten modellwirksamen Eigenschaften von dem in Form des Zeigers X an die Prozedur übergebenen Originalprogramm und stellt in diesem Sinne eine Mutante dar. Das Auftreten einer Mutation bewirkt immer das Erscheinen eines neuen Programmtyps und macht die Erhöhung der Variablen M, die zu jedem Zeitpunkt die Anzahl der im Modell vorhandenen Programmtypen angibt, um 1 erforderlich. Diese Erhöhung wird bereits vor dem Aufruf der Prozedur MUTANT vorgenommen.
Funktionsweise von MUTANT:
ref (PROGRAM) HELP;
HELP:-new PROGRAM;
HELP.MUT:=0;
HELP.IDENT:=M;
HELP.PROGNAME:-CREATE_NAME;
comment Beschreibung von CREATE_NAME s.u.;
X.MUT:=X.MUT+1;
comment *** Die Komponente MUT des. Original-
programms X wird erhöht, um die
Mutation dieses Programms zu re-
gistrieren. *** ;
class FIELD(P); integer P;
begin
integer array V[1:2,1:P];
comment *** V[1,...] entspricht der Spalte
V[2,...] entspricht der Zeile ***;
end;
zusammengefaßt. MUTANT erzeugt ein Objekt vom
Typ FIELD und weist es der globalen Variablen
CHANGE.CONFLICT zu:
CHANGE_CONFLICT:-new FIELD(M);
Die Komponenten der X.IDENT-ten Zeile bzw. Spalte der Vorrangmatrix regeln die Konflikte zwischen Exemplaren des Programms X und den Exemplaren der anderen Programmtypen. Bzgl. der Konflikte weist die Mutante ein dem Programm X ähnliches Verhalten auf. Daher wird die X.IDENT-te Spalte in die erste, Zeile von CHANGE CONFLICT.V und die X.IDENT-te Zeile in die zweite Zeile von CHANGE_CONFLICT.V kopiert. Siehe Abb. 9.2.2.A.
Abb. 9.2.2.A
CHANGE_CONFLICT.V(1,M),
CHANGE_CONFLICT.V(1,X.IDENT) und
CHANGE_C0NFLICT.V(2,X.IDENT) stellen die Komponenten
dar, die in der erweiterten Vorrangmatrix
die innerartlichen Konflikte zwischen Exemplaren
der Mutante HELP bzw. zwischen Exemplaren der
Mutante und des Originalprogramms X regeln
sollen und werden zu diesem Zweck neu generiert.
Dies geschieht mit Hilfe der Zufallsfunktion
RANDINT. Wegen der engen Verwandschaft zwischen
Mutante und Originalprogramm weichen die Werte
dieser Komponenten um höchstens 100% von der
Komponente in der alten Vorrangmatrix ab, die
die innerartlichen Konflikte zwischen Exemplaren
des Programms X regelt. Bis auf diese 3
otwendigerweise neuen Werte weist die Mutante also
bisher das gleiche Konfliktverhalten auf wie das
Originalprogramm.
auf Programmebene dar). Mit der
Wahrscheinlichkeit PROB_DELY*
mutiert (über
Zufallsfunktion RANDINT) die DELY-Komponente des
Programms X. Mit der Wahrscheinlichkeit
1-PROB_DELY*
erhält die Mutante ein in Bezug
auf einen der anderen in MOD3 vorhandenen Programmtypen
(also nicht X) verändertes Konfliktverhalten
als das Originalprogramm X.
HELP.DELY:=RANDINT(1,2*X.DELY,U_DELY2) while HELP.DELY=X.DELY do HELP.DELY:=RANDINT(1,2*X.DELY,U_DELY2)
integer I,J,K,U_CONFLICT; . . . J:=X.IDENT; while J=X.IDENT do begin J:=RANDINT(1,2*(M-1),U_CONFLICT); if J≤M-1 then I:=1 else begin I:=2; J:=J-(M-1) end end; K:=RANDINT(1,2*CHANGE_CONFLICT.V[I,J],U_CONFLICT); while K=CHANGE_CONFLICT.V[I,J] do K:=RANDINT(1,2*CHANGE_CONFLICT.V[I,J],U_CONFLICT); CHANGE_CONFLICT.V[I,J]:=K;
Beispiel:
text procedure CREATE_NAME(X); ref (PROGRAM) X;gesetzt.
Funktionsweise von CREATE_NAME:
CREATE_MAME besitzt als formalen Eingabeparameter X einen Zeiger auf ein Objekt vom Typ PROGRAM und liefert als Ergebnis einen Text. Dieser Text stellt den Namen einer Mutante des Programms X dar und wird aus den Komponenten X.MUT und X.PROGNAME erzeugt, indem an den Text X.PROGNAME das Zeichen "." gefolgt von der Zahl X.MUT (als Text interpretiert) gehängt wird.
Beispiel


Da beim Auftreten einer Mutation eines Programms dessen Komponente MUT um 1 erhöht wird, liefert dieser Mechanismus für aufeinanderfolgende Mutationen desselben Programms verschiedene Namen. Da der aktuelle Parameter für X selbst eine Mutante sein kann (s. Beispiel b)), läßt sich der Komponente PROGNAME eines Programms stets dessen "stammesgeschichtliche Entwicklung" zurückverfolgen (siehe Abb. 9.2.2.B). Dies wäre an Hand der integer-Komponenten IDENT, die in MOD2 zur Identifizierung der Programme ausreichte, nicht möglich.
Abb. 9.2.2.B
Wie schon wiederholt erwähnt, stellt das Auftreten einer Mutation i.a. eine Vergrößerung der Anzahl der aktuellen Parametertypen dar. Das macht sich schon in der (zunächst vorläufigen) Erhöhung der Variablen M bemerkbar. Kann sich die Mutante etablieren (s.u. Beschreibung der Prozedur MATCH), so müssen die dynamischen arrays erweitert werden, die die Mutante speichern, registrieren bzw. verwalten. Diese Erweiterungen werden durch Aufrufe der Prozeduren
procedure NEW_PROG(P); ref (PROGRAM) P; procedure NEW_ST(T); ref (PROGRAM) T; und procedure NEW_CONFLICT(A); integer array A;
gewährleistet.
Funktionsweise von NEW_PROG:
Der Zeiger PROGPOINTER verweist auf dasjenige Feld, mit dessen Hilfe die eigentliche Abspeicherung der Programme (Typen) erfolgt. Beim Auftreten einer Mutation - die Mutante wird in Form des Zeigers P als Parameter an NEW_PROG übergeben - muß dieses Feld um eine Komponente erweitert werden. Realisiert wird dieses durch Generierung eines neuen Feldes (Objekt vom Typ PROG), einen einfachen Kopierprozeß und anschließendes Umsetzen des Zeigers PROGPOINTER. Siehe Abb. 9.2.2.C.
Abb. 9.2.2.C
Funktionsweise von NEW_ST:
Das Feld, auf das der Zeiger STPOINTER verweist, enthält zu jedem Zeitpunkt der Simulation in der i-ten Komponente die momentane Anzahl der Exemplare des i-ten Programmtyps. Das Feld wird beim Auftreten einer Mutation um eine Komponente zur Registrierung der Exemplare der Mutante erweitert. Die zusätzliche Komponente wird mit 1 initialisiert. Ansonsten analog zu NEW_PROG. Siehe Abb. 9.2.2.D.
Abb. 9.2.2.D
Funktionsweise von NEW_CONFLICT:
Der Zeiger CONPOINTER verweist auf das Feld, das die Vorrangmatrix speichert. Beim Auftreten einer Mutation muß dieses Feld um eine Spalte und eine Zeile erweitert werden. Diese Zeile und Spalte entsprechen dem Konfliktverhalten der Mutante. Zeile und Spalte werden in Form des formalen Parameters integer array A an NEW_CONFLICT übergeben. Der Aufruf von NEW_CONFLICT erfolgt mit dem durch CHANGE_CONFLICT adressierten Feld als aktueller Parameter. Dieses Feld wird vor Aufruf von NEW_CONFLICT von der Prozedur MUTANT generiert (s.o. Funktionsweise der Prozedur MUTANT). Im übrigen erfolgt der Ablauf von NEW_CONFLICT, wie Abb. 9.2.2.E zeigt, analog zu NEW_PROG und NEW_ST.
Abb. 9.2.2.E greift das Beispiel aus der Beschreibung der Prozedur MUTANT auf.
Abb. 9.2.2.E
Nach Erläuterung der der Erzeugung und Behandlung von Mutationen dienenden Prozeduren sind wir in der Lage, die Prozedur MATCH anzugeben. MATCH stellt, wie schon im SIMULA-Programm zu MOD2 (s. 8.3.2.), das Herzstück der Simulation dar. Das übergeordnete Simulationsschema, wie es in 8.3.2.(iii) Seite 182 angegeben ist, kann vollständig übernommen werden.
procedure MATCH(I); integer I;
begin
.
.
.
boolean IS_COPY;
IS COPY:=false;
[ Erhöhe TIMECOUNT-Komponente der I-ten Speicher- ]
[ zelle um 1. ] ;
if [ TIMECOUNT-Komponente der I-ten Speicherzelle ]
[ gleich DELY-Komponente des in der I-ten Spei-]
[ cherzelle befindlichen Programms ]
then
begin
comment *** Reproduktion des in der I-ten Zelle
befindlichen Programms *** ;
[ Setze TIMECOUNT-Komponente der I-ten Speicher- ]
[ zelle auf 0 ] ;
[ Wähle eine zufällige Zelle des Speichers aus. ]
[ Sei die Wahl auf die W-te Speicherzelle gefallen.] ;
comment *** Siehe dazu oben 8.3.2.(iv) *** ;
[ Treffe Entscheidung, ob das in der I-ten Spei- ]
[ cherzelle befindliche Programm mutiert. ] ;
comment *** Die Mutationswahrscheinlichkeit be-
trägt PR0B_MUT*
=
(Modell-
parameter), Die integer-Größe PROB_
MUT stellt den Modellparameter
auf Programmebene dar. *** ;
if [ Programm in der I-ten Speicherzelle mutiert. ]
then
begin
[ Treffe Entscheidung, ob die Mutation letal verläuft. ] ;
comment *** Die Wahrscheinlichkeit für den letalen Ver-
lauf einer Mutation beträgt PROB_LETAL*
=
(Modellparameter). Die integer-Größe
PROB_LETAL stellt den Modellparameter
auf Programmebene dar. *** ;
if [ Letaler Verlauf der Mutation ]
then [ Erhöhe die Komponente MUT des in der I-ten Zelle ]
[ gespeicherten Programms um 1. ] ;
comment *** Dies geschieht zur Registrierung der
Mutation. Im Falle einer nicht letalen
Mutation wird die Erhöhung der Kompo-
nente MUT von der Prozedur MUTANT vor-
genommen. ***
else
begin
comment *** Existenzfähige Mutation *** ;
M:=M+1;
comment *** Rettung der alten Vorrangmatrix und des
alten Programmspeichers *** ;
OLD_CONPOINTER:-CONPOINTER;
OLD_PROGPOINTER:-PROGPOINTER;
[ Erzeuge Mutante des in der I-ten Speicherzelle be- ]
[ findlichen Programms (Aufruf MUTANT). Trage den von ]
[ MUTANT erzeugten neuen Prograramtyp in den Programm-]
[ speicher ein (Aufruf NEW_PROG). Erweitere die Vor- ]
[ rangmatrix (Aufruf NEW_CONFLICT). ]
comment *** CONPOINTER und PROGPOINTER verweisen auf
die neue Vorrangmatrix bzw. den neuen
Programmspeicher *** ;
if [ W-te Speicherzelle leer ]
then
begin
comment *** Ungehindertes Ablegen der erzeugten
Mutante im Speicher ***;
[ schreibe die Mutante in die W-te Speicherzelle ] ;
NEW_ST;
IS_COPY:=true
end
else
begin
comment *** W-te Speicherzelle ist bereits
besetzt. *** ;
[ Treffe Entscheidung mittels der neuen Vorrangmatrix, ]
[ ob die Mutante das in der W-ten Zelle befindliche ]
[ Programm überschreiben darf. ]
comment *** Siehe unten (v) *** ;
if [ Überschreiben nicht möglich]
then
begin
comment *** Vernichtung der Mutante, Wiederherstellung
der alten Tabellen *** ;
M:=M-1;
CONPOINTER:-OLD_CONPOINTER;
PROGPOINTER:-OLD_PROGPOINTER
end
else
begin
comment *** Die Mutante kann das in der W-ten
Zelle befindliche Programm überschreiben. *** ;
[ Schreibe Mutante in die W-te Speicherzelle ] ;
NEW_ST;
IS_COPY:=true
end
end
end
end
else
begin
comment *** Das Programm in der I-ten Speicherzelle
erzeugt eine korrekte Kopie ohne Mutation *** ;
if [ W-te Speicherzelle leer ]
then
begin
comment *** Ungehindertes Ablegen der Kopie *** ;
[ Schreibe Kopie in die W-te Speicherzelle ] ;
IS_COPY:=true
end
else
begin
comment *** W-te Speicherzelle bereits besetzt *** ;
[ Treffe Entscheidung mittels der Vorrangmatrix, ob ]
[ die Kopie des in der I-ten Zelle befindlichen ]
[ Programms das Programm in der W-ten Zelle über- ]
[ schreiben darf. ]
comment *** Siehe unten (v) *** ;
if [ Überschreiben nicht möglich ]
then
comment *** Es geschieht nichts *** ;
else
begin
[ Schreibe Kopie in die W-te Speicherzelle ] ;
IS_COPY:=true
end
end
end;
comment *** Falls das Programm aus Speicherzelle I
seine Mutante/Kopie im Speicher ablegen
konnte, muß noch in Abhängigkeit von
der Durchlaufrichtung die Komponente
TIMECOUNT der W-ten Speicherzelle
gesetzt werden ***;
(s.S.184)
end
end *** MATCH *** ;
der momentanen Vorrangmatrix wird jedoch als "
Tausendstel" interpretiert, was eine Verfeinerung
gegenüber dem Programm für MOD2 darstellt. Die
Elemente der jeweiligen Vorrangmatrix sind somit
Elemente der Menge [1000].Anhang C.3. zeigt die Realisierung von MOD3 als ausführlich kommentiertes SIMULA-Programm. Einen Überblick über die in diesem Programm benutzten Datenstrukturen gibt Abb. 9.2.2.F.
Eingabeparameter des SIMULA-Programms für MOD3:
PROB_LETAL
PROB_DELY![\in[10^3]](/img/cache/6a28ae14b6c25b999c3d29247add94e4.gif)
Abb. 9.2.2.F
WHEN_DUM WHEN_CON und WHEN_AVE (vgl. 8.2.4. I. und II.)
| Prozedur | Aufwand für großes M |
|---|---|
| MUTANT | O(M) |
| CREATE_NAME | konstant |
| NEW_PROG | O(M) |
| NEW_ST | O(M) |
| NEW_CONFLICT | O( ) |
| (M = Aktuelle Anzahl der vorhandenen Programmtypen) | |
Abb. 9.2.3.A
Dieser Mehraufwand fällt jedoch kaum ins Gewicht, zumal es realistisch ist, von kleinen Mutationsraten auszugehen, so daß M ebenfalls klein bleibt.
. Dieser Wert orientiert sich an der
Biologie und ist im Zusammenhang mit Evolution bei
Rechnerprogrammen zumindest fraglich. Es bietet sich daher
an, auch diesen Wert durch einen variablen Eingabeparameter
zu ersetzen.
Analog: kleinstmögliche Rate für Letalmutationen.
1) (p.1) Auf die Schwierigkeiten, die sich bei der Definition von Leben ergeben, gehen wir ausführlich in Kapitel 7 ein.
1) (p.14) Notation:
für jedes
nicht zu verwechseln mit Literaturverweisen.
1) (p.19) Das Symbol l bezeichnet bei beliebigem Alphabet B die Längenfunktion für Elemente aus
.
2) (p.19) "%" wird als Endemarkierung für Beweise benutzt.
1) (p.21)
bezeichnet in dem für n-Tupel üblichen Sinne die Projektion auf die i-te Komponente.
1) (p.23) Zur Lambda-Notation siehe [20] Seite 13.
1) (p.34) SIMULA-Beschreibung in [19].
1) (p.45) Standard-Funktion siehe [19].
1) (p.54) PASCAL-Beschreibung in [10].
1) (p.98)
bezeichnet die Konkatenation von Worten; hier aus
.
1) (p.104) Menge aller Wörter, die aus endlich vielen A zusammengesetzt sind.
1 (p.107) Notation:
bedeutet undefiniert.
1) (p.118) vgl. Fußnote auf Seite 19
1) (p.132) entstehen durch konkrete Wahl von A und traten daher in [...] /one string is out of xerox copied page - herm1t/
1) (p.158) Semantisch hier im Sinne von; keine Laufzeitfehler.
1) (p.168) Siehe Beschreibung von RANDINT [25] Seite 4.-9
[zurück zum Index] [Kommentare (0)]