Selbstreproduktion bei programmen

Jurgen Kraus
Universität Dortmund
Februar 1980

Download PDF (37.66Mb) (Du musst im Forum registriert sein)
[zurück zum Index] [Kommentare (0)]

If you found a typo or want to participate in translation of this document, welcome to the forum - herm1t

Selbstreproduktion bei programmen

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.

J. Kraus

Inhalt

1. Einleitung
- 1.1. Motivation
- 1.2. Definition selbstreproduzierender Programme
2. Existenz selbstreproduzierender Programme
- 2.1. Einleitung
- 2.2. Definition einer einfachen Programmiersprache PL(A)
- 2.3. Eine kontextfreie Grammatik für PL(A)
- 2.4. PL(A)-berechenbare Funktionen, Church'sche These
- 2.5. Kodierungen, Gödelisierungen von $\cal{P}$
- 2.6. Lexikographische Ordnung von $A^*$
- 2.7. Reduktion auf jeweils eine Eingabeund eine Ausgabevariable
- 2.8. s-m-n-Theorem, Rekursionstheorem
3. Selbstreproduzierende Programme in realen Programmiersprachen - Einige Beispiele
- 3.1. Einleitung
- 3.2. Selbstreproduzierende Programme in SIMULA
- 3.3. Selbstreproduzierende Programme in PASCAL
- 3.4. Selbstreproduzierende Programme in SIEMENS-Assembler
4. Varianten zur Selbstreproduktion von Programmen
- 4.1. Motivation
- 4.2. Unendlich reproduzierende Programme
  - 4.2.1. Implementierung des Programms $\overset{\infty}{\pi}_0$
- 4.3. Zyklisch selbstreproduzierende Programme
  - 4.3.1. Implementierung des Programms $\overset{k}{\pi}_0$
  - 4.3.2. Implementierung des Programms $\pi^{zyk}_0$
- 4.4. Unter Wechsel der Programmiersprache sich zyklisch selbstreproduzierende Programme
- 4.5. k-fach selbstreproduzierende Programme
  - 4.5.1. Implementierung fon $\pi(k)$
- 4.6. Reproduktionshierarchie bei Programmen
5. Selbstreproduzierende Programme mit Zusatzeigenschaften
- 5.1. Einleitung
- 5.2. Selbstreproduktionssatz für die Programmiersprache PASCAL
- 5.3. Selbstreproduktionssatz für die Programmiersprache SIMULA
6. Selbstreproduktion bei loop-Programmen
- 6.1. Einleitung
- 6.2. Definition der Programmiersprache LP(A)
- 6.3. Eine kontextfreie Grammatik für LP(A)
- 6.4. Erweiterung der Sprache LP(A)
- 6.5. Selbstreproduzierende Programme in $\overline{\text{LP(A)}}$
- 6.6. Selbstreproduktionssatz für $\overline{\text{LP(A)}}$ -programme
7. Leben bei Programmen?
- 7.1. Einleitung
- 7.2. Biologisches Leben
- 7.3. Selbstreproduzierende Programme und Leben
- 7.4. Selbstreproduzierende Programme und Viren
8. Modelle für konkurrierendes Verhalten selbstreproduzierender Programme
- 8.1. Motivation
- 8.2. Ein einfaches Grundmodell
- 8.3. Ein Modell mit konkurrierenden Verhalten
9. Evolution bei Programmen
- 9.1. Motivation
- 9.2. Ein Modell MOD3 für Evolution selbstreproduzierender Programme
Literaturverzeichnis
Anhang
Anhang A
Anhang A. 1.
Anhang A. 2.
Anhang A. 3.
Anhang A. 4.
Anhang A. 5.
Anhang A. 6.
Anhang A. 7.
Anhang A. 8.
Anhang A. 9.
Anhang A. 10.
Anhang A. 11.
Anhang A. 12.
Anhang B
Anhang B. 1.
Anhang B. 2.
Anhang B. 3.
Anhang B. 4.
Anhang C
Anhang C. 1.
Anhang C. 2.
Anhang C. 3.

Alle in der vorliegenden Diplomarbeit vorkommenden Beispielprogramme wurden auf dem SIEMENS-Rechner, Typ 7738, der Abteilung Informatik an der Universität Dortmund gerechnet.

1. Einleitung

1.1. Motivation

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 ¹⁾ 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.

1.2. Definition selbstreproduzierender Programme

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.

Assembler-Sprachen: sind direkte Produkte der jeweiligen Maschinenstruktur und lassen sich deshalb als maschinenorientiert bezeichnen. Viele Kennzeichen einer konkreten Rechenanlage lassen sich an der zugehörigen Assembler-Sprache ablesen, unter anderem auch die Struktur des Arbeitsspeichers, auf den Assembler-Programme zugreifen können. Ausführbare Assembler-Programme befinden sich in der Form ihres Maschinenkodes im Arbeitsspeicher. Während der Laufzeit können. Assembler-Programme also auf ihren eigenen Maschinenkode zugreifen und ihn auch verarbeiten.
Höhere Programmiersprachen: sind Programmiersprachen, die die physikalische Struktur des Rechners unberücksichtigt lassen und somit auch nicht an eine feste Rechenanlage gebunden sind. Auf der Ebene von höheren Programmiersprachen gibt es daher auch in der Regel keine Zugriffsmöglichkeit auf den Arbeitsspeicher des jeweiligen Rechners. Programme in höheren Programmiersprachen haben also nicht die Möglichkeit, ihren eigenen Maschinenkode zu lesen und zu verarbeiten.

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 $\pi$ ein (syntaktisch korrektes) Programm aus S.

Weist $\pi$ keine Eingabe auf, so heißt $\pi$ (streng) selbstreproduzierend, falls $\pi$ (genau) seinen Programmtext in S ausgibt.
Weist $\pi$ Eingabe auf, so heißt $\pi$ (streng) selbstreproduzierend, falls $\pi$ 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 $\pi$ ein gültiges Programm aus der Assembler-Sprache M.

Weist $\pi$ keine Eingabe auf, so heißt $\pi$ (streng) selbstreproduzierend, falls $\pi$ (genau) seinen Maschinenkode ausgibt oder innerhalb des Arbeitsspeichers kopiert.
Weist $\pi$ Eingabe auf, so heißt $\pi$ (streng) selbstreproduzierend, falls $\pi$ 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 $\Downarrow$	Programme können Arbeitsspeicher und damit ihren eigenen Maschinenkode lesen $\Downarrow$
Selbstreproduktion $\hat=$ Erzeugung des Quellprogramms in der höheren Programmiersprache $\Downarrow$	Selbstreproduktion $\hat=$ Erzeugung direkter Kopie des Maschinenkodes $\Downarrow$
Übersetzung der Kopie erforderlich	Keine Übersetzung der Kopie erforderlich

Abb. 1.2.A

2. Existenzselbstreproduzierender Programme

2.1. Einleitung

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.

2.2. Definition einer einfachen Programmiersprache PL(A)

Grundlage ist zunächst ein beliebiges, aber festes, endliches Alphabet $A=\{a_1,\dots,a_n\}, n\in\mathbb{N}$ . Die Menge $A^*$ aller endlichen Wörter über $A$ stellt die Menge der Daten dar, auf denen Programme in PL arbeiten. Das leere Wort $\varepsilon \in A^*$ ist dabei als Datum zugelassen.

(2.2.1) Definition (Ausdrücke):

Die Konstanten in PL sind die Elemente von $A^*$ .
Die Variablen $X_1,X_2,\dots,Y,Z,W$ sind Elemente aus einer festen Menge VR. Jede Variable kann Werte aus $A^*$ annehmen.
Operationen sind Xa und $\cal{P}(X)$ für jedes $X \in VR, a \in A$ .
Bedeutung:

Xa hat den Wert xa, falls $x \in A^*$ der Wert von X ist.

$\cal{P}(X)$ hat den Wert $x \in A^*$ , falls xa der Wert von X ist für ein Element $a \in A$ . Andernfalls hat $\cal{P}(X)$ den Wert $\epsilon$ .
Bedingiqngen haben die Form $\omega(X)=a$ oder $X=\epsilon$ mit $X \in VR$ und $a \in A$ .
Bedeutung:

$\omega(X)=a$ ist genau dann wahr, wenn a der letzte Buchstabe des Wertes der Variablen X ist. $X=\epsilon$ ist genau dann wahr, wenn $\epsilon$ der Wert von X ist.

(2.2.2) Definition (Grundanweisungen):

Die Grundanweisungen in PL sind:

$\begin{align} &&\text{Die leere Anweisung} &&&\gamma_1 :\ \ \overline\epsilon\\ &&\text{und die Wertzuweisungen}&&&\gamma_2 :\ \ X:=\epsilon\\ && &&&\gamma_3 :\ \ X:=Xa\\ && &&&\gamma_4 :\ \ X:=Y\\ && &&&\gamma_5 :\ \ X:=\cal{P}(X), \end{align}$

für alle Variablen X und Y aus VR und $a \in A$ .

(2.2.3) Definition (Kontrollstrukturen):

Die Kontrollstrukturen in PL sind:

$\chi_1:\ \ P;Q$

Bedeutung:

Hintereinanderausführung von Anweisungen.

Vergleiche übliche Programmiersprachen.

$\chi_2:\ \ \text{\underline{if} p \underline{then goto} L}$

Bedeutung:

$\chi_2$ 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.

$\chi_3:\ \ \text{\underline{if} p \underline{then} P \underline{else} Q \underline{fi}}$

Bedeutung:

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

$\chi_4:\ \ \text{\underline{while} X=\epsilon\ \underline{do} P \underline{od}}$

Bedeutung:

while-Schleife; Bedingungen der Form $\omega(X)=a, X \in VR, a \in A$ , sind nicht erlaubt. P ist eine Anweisung. Ansonsten wie in üblichen Programmiersprachen.

$\begin{array}{rccclBCB} \chi_5:\ \ \text{\underline{loop} X \underline{case}} & a_1 & \longr & P_1,\\ & \vdots & \ \ \ \ \ \ & \vdots\\ & a_n & \longr & P_n,\\ \text{\underline{end}} & & & \end{array}$

$\chi_5$ 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) $a_j$ des Wertes von X wird die zugehörige Anweisung $P_j$ ausgeführt. Fehlt für einen Buchstaben $a_j$ die Vorschrift $a_j \longr P_j$ in der Liste der Alternativen, so wird so verfahren, als würde in der Liste $a_j \longr \overline\epsilon$ stehen, $j \in [n]$ .

(2.2.4) Definition (Marken):

Marken sind Elemente aus einer festen Menge $M = \{L_1,L_2,\dots\}$ . Eine Marke kann in der Form $L\ :\ P$ 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 $\chi_1$ bis $\chi_5$ miteinander verknüpft sind.

(2.2.6) Definition (PL-Programme):

Ein Programm $\pi$ in PL hat die Form

$\begin{array}{rccclBCB} \pi = \text{\underline{input}} & X_1, &\dots,X_r;\\ & AW_\pi; &\\ \text{\underline{output}} & Z_1, &\dots,Z_s & r \ge 0, s\ge 0 \end{array}$

wobei $AW_\pi$ eine Anweisung ist.

Die paarweise verschiedenen Variablen $X_1,\dots,X_r \in VR$ heißen Eingabevariable.

Die paarweise verschiedenen Variablen $Z_1,\dots,Z_s \in VR$ heißen Ausgabevariable.

Tritt in $AW_\pi$ die Kontrollstruktur $\chi_2 :\ \ \text{\underline{if} p \underline{then goto} L$ auf, so darf L in $AW_\pi$ nur einmal in der Form $L\ :\ P$ auftreten, wobei P eine Anweisung ist.

(2.2.7) Definition (Ausführung von PL-Programmen):

Die Ausführung eines Programms $\pi$ in PL beginnt damit, daß die Eingabevariablen $X_1,\dots,X_r$ mit Eingabewerten belegt werden. Alle anderen in $\pi$ vorkommenden Variablen werden mit $\epsilon$ initialisiert. Danach wird $AW_\pi$ ausgeführt. Nach Ausführung von $AW_\pi$ liegt das Ergebnis der Programmausführung in Form der Werte der Ausgabevariablen $Z_1,\dots,Z_s$ vor. Hält das Programm nie an, so ist das Ergebnis von $\pi$ 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.

2.3. Eine kontextfreie Grammatik für PL(A)

Die folgende kontextfreie erzeugende Grammatik $G(A) = (V_T,V_N,s_0,P)$ 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 $AW_\pi$ 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 $G(A)=(V_T,V_S,s_0,P)$ :

Die Menge der terminalen Zeichen $V_T$ ist:

$\begin{align} V_T = A \cup M \cup VR \cup && \big\{ \text{\underline{input}, \underline{output}, \underline{if}, \underline{then}, \underline{goto},} \\ && \text{\underline{else}, \underline{fi}, \underline{while}, \underline{do}, \underline{od}, \underline{loop}, \underline{case},}\\ && \underbrace{ \text{\underline{end},\ :\ ,\ =\ , \longr ,\ ;\ ,\ ,\ , \rotate{-90}],\ (\ ,\ )\ , \cal{P}, \omega, \epsilon, \overline\epsilon} } \big\}\\ && \text{Grundsymbole} \end{align}$

Die Menge der nichtterminalen Zeichen $V_N$ ist:

$\begin{align} V_N = && \big\{\text{<program>, <statement>, <simple statement>,}\\ && \text{<identifier>, <label>, <identifier list>,}\\ && \text{<condition> \big\} \end{align}$

Das Startzeichen $s_0$ ist <program>.

Die Menge P umfaßt die Produktionen:

$\begin{align} \text{<program>} \longr &\text{\underline{input}} &&\text{<identifier list>;}\\ & &&\text{<statement>;}\\ &\text{\underline{output}} &&\text{<identifier list>} \end{align}$
$\text{<identifier list> \longr <identifier list>, <identifier>}$
$\text{<identifier list> \longr <identifier>}$
$\text{<identifier> \longr X, f\ddot{u}r alle X \in VR}$
$\text{<identifier> \longr \epsilon}$
$\text{<statement> \longr <label>\ :\ <statement>}$
$\text{<statement> \longr <statement>\ ;\ <statement>}$
$\text{<statement> \longr \underline{if} <condition> \underline{then goto} <label>}$
$\begin{align} &\text{<statement> \longr \underline{if} <condition>} &\text{\underline{then} <statement>}\\ & &\text{\underline{else} <statement> \underline{fi}}\\ \end{align}$
$\begin{align} &\text{<statement> \longr \underline{while}} & \text{<identifier> = \epsilon\ \underline{do}}\\ & & \text{<statement> \underline{od}} \end{align}$
$\begin{align} &\text{<statement) \longr} & \text{\underline{loop} <identifier> \underline{case}}\\ & & \text{a_1 \longr <statement>},\\ & & \vdots\\ & & \text{a_n \longr <statement>, \underline{end}} \end{align}$
$\text{<statement> \longr <simple statement>}$
$\text{<label> \longr L, f\ddot{u}r alle L \in M}$
$\text{<condition> \longr \omega(X)=a f\ddot{u}r alle a \in A, X \in VR}$
$\text{<condition> \longr X=\epsilon\ f\ddot{u}r alle X \in VR}$
$\text{<simple statement) \longr \overline\epsilon}$
$\text{<simple statement>\longr X:=\epsilon\ f\ddot{u}r alle X \in VR}$
$\text{<simple statement>\longr X:=Xa, f\ddot{u}r alle X \in VR, a \in A}$
$\text{<simple statement>\longr X:=X', f\ddot{u}r alle X,X' \in VR}$
$\text{<simple statement>\longr X:=\cal{P}(X), f\ddot{u}r alle X \in VR}$

Wir können folgende Entsprechungen feststellen:

Regel 1-5	$\hat{=}$	Definition (2.2.6)
Regel 6	$\hat{=}$	Definition (2.2.4)
Regel 7-13	$\hat{=}$	Definition (2.2.3),(2.2.5)
Hegel 14-20	$\hat{=}$	Definition (2.2.1),(2.2.2)

Die oben erwähnten umgangssprachlichen Regeln in den Definitionen bleiben von G(A) unberücksichtigt.

2.4. PL(A)-berechenbare Funktionen, Church'sche These

Sei nun A endliches Alphabet, $\pi \in PL(A)$ . $\pi$ besitzt $r \ge 0$ Eingabe- und $s \ge 0$ 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 $\pi \in PL(A)$ . Die von $\pi$ berechnete Funktion ist $\varphi_\pi : (A^*)^r \longr (A^*)^s, r,s \ge 0$ . $\varphi_\pi$ ordnet jeder Anfangsbelegung $(x_1,\dots,x_r), x_i \in A^*$ , $i \in [r]$ ¹⁾, der Eingabevariablen ein Ergebnis $(z_1,\dots,z_s) = \varphi_\pi(x_1,\dots,x_r), z_j \in A^*, j \in S$ , zu, falls das Programm $\pi$ anhält. Hält $\pi$ nicht an, so ist $\varphi_\pi(x_1,\dots,x_r)$ undefiniert.

(2.4.2) Bemerkung: Aus Definition (2.4.1) folgt:

$\varphi_\pi$ ist i.a. eine partielle Funktion.
Die Sonderfälle und sind ausdrücklich zugelassen. Die Bedeutung dieser Sonderfälle sei hier jedoch kurz erläutert. Es bezeichne () das Nulltupel:
1. $\varphi_\pi : (A^*)^r \longr (A^*)^0, r\ge1$ , ordnet jedem r-Tupel $(x_1,\dots,x_r) \in (A^*)^r$ das Nulltupel () zu, falls $\pi$ mit $(x_1,\dots,x_r)$ als Eingabebelegung anhält.
  $\varphi_\pi(x_1,\dots,x_r)=\{ \text{ (), falls \pi\ h\ddot{a}lt\\ undefiniert sonst}$
2. $\varphi_\pi : (A^*)^0 \longr (A^*)^s, s\ge1$ , ordnet dem Nulltupel () ein s-Tupel $(z_1,\dots,z_s)\in(A^*)^s$ zu, falls $\pi$ anhält.
  $\varphi_\pi() = \{ \text{ (z_1,\dots,z_s)\in(A^*)^s, falls \pi\ h\ddot{a}lt\\ undefiniert sonst }$
3. $\varphi_\pi : (A^*)^0 \longr (A^*)^0$ ordnet dem Nulltupel () das Nulltupel () zu, falls $\pi$ hält.
  $\varphi_\pi()= \{ \text{ (), falls \pi\ h\ddot{a}lt\\ undefiniert sonst }$

(2.4.3) Definition: Sei A fest gewählt.

Eine Wortfunktion $f : (A^*)^r \longr (A^*)^s, r,s\ge0$ , heißt PL(A)-berechenbar oder kurz berechenbar, falls ein Programm $\pi_f \in PL(A)$ existiert mit $\varphi_{\pi_f}=f$ .
Die Menge $\cal{P}(A) := \{ \varphi_\pi | \pi \in PL(A) \}$ 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 $\cal{P}(A)$ 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 $A_1$ , und $A_2$ zwei voneinander verschiedene endliche Alphabete, so lassen sich offensichtlich die Mengen $\cal{P}(A_1)$ und $\cal{P}(A_2)$ identifizieren. Wir geben daher die Differenzierung nach dem zugrunde liegenden Alphabet auf und schreiben von nun an einfach $\cal{P}$ 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 $\pi \in PL(A)$ angeben mit $f = \varphi_\pi$

(2.4.6) Definition:

$\cal{P}^r_s := \{f \in \cal{P} | f : (A^*)^r \longr (A^*)^s, r,s\ge0 \}$
$\cal{R} := \{ f \in \cal{P} |\text{f ist total} \}$ ist die Menge der total rekursiven Funktionen.
$\cal{R}^r_s := \cal{R} \cap \cal{P}^r_s, r,s\ge0$

2.5. Codierungen, Gödelisierungen von $\cal{P}$

(2.5.1) Definition: Sei A endliches Alphabet. Eine Menge $B \subseteq (A^*)^r, r\ge0$ , heißt entscheidbar oder auch rekursiv genau dann, wenn es eine total rekursive Funktion $\chi_B : (A^*)^r \longr A^*$ gibt mit $\chi_B(x_1,\dots,x_r)=\varepsilon \Leftrightarrow (x_1,\dots,x_r)\in B$

(2.5.2) Definition: Seien $A_1$ , und $A_2$ endliche Alphabete. Eine Funktion $\xi : A^*_1 \longr A^*_2$ heißt genau dann Kodierung von $A^*_1$ durch $^*_2$ , falls gilt:

$\xi \in \cal{R}$ ,
$\xi$ ist injektiv,
$\xi(A^*_1)$ ist entscheidbar,
$\xi^{-1} \in \cal{P}$

Sei $A_0=\{1\}$ . Dann kann man $A^*_0$ mit den natürlichen Zahlen einschließlich der Null, $\mathbb{N}_0$ , wie folgt identifizieren.

$\begin{align} \varepsilon & \hat{=} & 0 \\ \underbrace{111.......1111111} & \hat{=} & n \in \mathbb{N}\\ \text{n Einsen} \end{align}$

(2.5.3) Definition: Eine Kodierung $\xi : A^* \longr A^*_0=\{1\}^*\hat{=}\mathbb{N}_0$ heißt Gödelisierung. $\xi(\omega)$ heißt Gödelnummer von $\omega$ für alle $\omega\in A^*_0$ .

Es soll im folgenden eine Gödelisierung aller PL(A)-Programme mit festem A angegeben werden. Damit wird gleichzeitig eine Gödelisierung von $\cal{P}$ angegeben. Sei $A:=\{a_1,\dots,a_n\}$ 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. $B:=\{:,=,\epsilon,\overline\epsilon,\longr,;,,,\rotate{-90}],\omega,\cal{P},(,),a,c,d,e,f,g,h,i,l,n,o,p,s,t,u,w\}$ Die Mengen der Marken und Variablen in PL(A)-Programmen sind $M: = \{L_1,L_2,\dots\}$ bzw. $VR:=\{V_1,V_2,\dots\}$ . Dabei bezeichnen $L_i$ bzw. $V_j,\ i,j\ge1$ , 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.

Der Name $L_1$ ist textuell gleich "L1"
Der Name $L_2$ ist textuell gleich "L2" u.s.w.

entsprechend

Der Name $V_1$ ist textuell gleich "V1" u.s.w.

Damit gilt:

$M\subset\{L,0,1,\dots,9\}^*,\ \ VR \subset\{V,0,1,\dots,9\}^*$

Sei nun $C:=A \cup B \cup \{L,V,0,1,\dots,9\}$ . Jedes Programm $\pi \in PL(A)$ läßt sich somit als Wort aus $C^*$ und PL(A) selbst als Teilmenge von $C^*$ auffassen. Wir geben eine injektive Abbildung $H : C \longr \{1\}* \hat{=} \mathbb{N}_0$ elementweise an:

$\begin{array}{rccclBCB} :&\longr&0&\ &c&\longr&13&\ &u&\longr& 26\\ =&\longr&1&\ &d&\longr&14&\ &w&\longr& 27\\ ;&\longr&2&\ &e&\longr&15&\ &L&\longr& 28\\ ,&\longr&3&\ &f&\longr&16&\ &V&\longr& 29\\ (&\longr&4&\ &g&\longr&17&\ &0&\longr& 30\\ )&\longr&5&\ &h&\longr&18&\ &\vdots\\ \rotate{-90}]&\longr&6&\ &i&\longr&19&\ &\vdots\\ \longr&\longr&7&\ &l&\longr&20&\ &9&\longr& 39\\ \epsilon&\longr&8&\ &n&\longr&21&\ &a_1 &\longr& 40\\ \overline\epsilon&\longr& 9&\ &o&\longr&22&\ &\vdots\\ \cal{P}&\longr& 10&\ &p&\longr&23&\ &\vdots\\ \omega&\longr& 11&\ &s&\longr&24&\ &a_n &\longr& 39+n\\ a&\longr&12&\ &t&\longr&25&\ & \end{array}$

Die injektive Abbildung H läßt sich zu einer ebenfalls injektiven Abbildung $H^* : C^* \longr \mathbb{N}^*_0$ erweitern.

$\begin{array}{rccclBCB} H^*(\varepsilon)&\longr&\varepsilon\\ H^*(\overline{x}y)&\longr&H^*(\overline{x})H(y),& \forall y \in C, \forall \overline{x} \in C^* \end{array}$

(2.5.4) Lemma: $H^*$ ist eine Kodierung von $C^*$ durch $\mathbb{N}^*_0$ .

Beweis:

Nach Definition von H und $H^*$ ist $H^*$ natürlich intuitiv berechenbar und auf Grund der Church'schen These berechenbar. $H^*$ ist für alle Elemente aus $C^*$ definiert. Also ist $H^*$ total und insgesamt aus $\cal{R}$ ,
$H^*$ ist trivialerweise injektiv.
Sei $D := H^*(C^*)$ . D ist Teilmenge von $\mathbb{N}^*_0$ . Sei $\overline{i}\in\mathbb{N}^*_0$ . $\overline{i}$ hat endliche Länge $l(\overline{i}), \overline{i}=m_1 \dots m_{l(\overline{i})}$ ¹⁾ mit $m_j\in\mathbb{N}^*_0$ für $j\in[l(\overline{i})]$ . $\overline{i}$ ist genau dann aus D, wenn jedes $m_j$ ein Urbild in C bzgl. H hat Um festzustellen, ob $\overline{i}\in D$ ist, sind also höchstens $l(\overline{i})\cdot\text{card}(C)$ Tests nötig. Es existiert also eine total rekursive Funktion
$\chi_D : \mathbb{N}^*_0 \longr \mathbb{N}^*_0$ mit
$\chi_D(\overline{i}) = \varepsilon \Leftrightarrow$ (Jedes Element von $\overline{i}$ hat unter H Urbild in C) $\Leftrightarrow \overline{i}\in D$ . Also ist $D = H^*(C^*)$ entscheidbar.
In (iii) wurde schon gezeigt, daß man für jedes $\overline{i}\in H^*(C^*)$ effektiv das Urbild in $C^*$ ermitteln kann. Also ist $(H^*)^{-1}$ überall dort, wo es definiert ist, auch berechenbar. Also $(H^*)^{-1} \in \cal{P}$

Aus (i) - (iv) folgt: $H^*$ ist Kodierung.

%²⁾

Wir betrachten nun die total rekursive Funktion $f : \mathbb{N}^*_0\longr\mathbb{N}_0$

mit $\overline{i}\longr\{ \text{0, falls \overline{i}=\varepsilon\\p_1^{m_1}\dots p_{l(\overline{i})}^{m_{l(\overline{i})}+1} - 1, falls \overline{i}=m_1\dots m_{l(\overline{i})}}$

wobei $p_j$ die j-te Primzahl ist,

Behauptung: f ist bijektiv.

Beweis:

f ist injektiv wegen der Eindeutigkeit der Primfaktorzerlegung.
f ist surjektiv, weil jede Zahl $m\in\mathbb{N}$ mit $m>1$ eine Primzahlzerlegung hat, in der mindestens ein Primfaktor vorkommt.

Mit $H^*$ als Kodierung von $C^*$ durch $\mathbb{N}^*_0$ und $f\in\cal{R}$ als bijektiver Funktion von $\mathbb{N}^*_0$ nach $\mathbb{N}_0$ folgt Lemma (2.5.5).

(2.5.5) Lemma: Die Funktion $g := f \circ H^* : C^* \longr \mathbb{N}_0$ ist Gödelisierung von $C^*$ durch $\mathbb{N}_0$ .

Jedem Wort w aus $C^*$ und somit jedem Programm aus PL(A) ist also eindeutig eine Zahl $f\circ H^*(w)$ aus $\mathbb{N}_0$ zugeordnet. Da $H^*$ injektiv und f bijektiv ist, ist die Abbildung g eine bijektive Gödelisierung von $C^*$ .

(2.5.6) Lemma: Die Menge $T := \{ g(x) | x \in PL(A) \} \subset \mathbb{N}_0$ ist entscheidbar.

Beweis:

i=0 ist nicht aus T, da das leere Wort kein Programm ist.
Sei $i\in\mathbb{N}$ . Dann läßt sich i eindeutig in der Form $i = p_1^{m_1} \dots p_k^{m_k+1}-1$ darstellen ( $k\ge1$ ). Existiert für eines der $m_j (j\in[k])$ kein Urbild bzgl. der Funktion H. so ist i nicht aus dem Bildbereich, von g und damit auch nicht aus T. Sei nun jedes $m_j$ aus dem Bildbereich von H. Dann existiert ein $w\in C^*$ 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 $w\in C^*$ hält und $\varepsilon$ ausgibt genau dann, wenn $w\n PL(A)$ ist. Insgesamt existiert also eine total rekursive Funktion, deren Ergebnis genau dann gleich $\varepsilon$ ist, wenn das Urbild eines Elementes aus $\mathbb{N}_0$ , falls es existiert, ein gültiges PL(A)-Programm ist. Also ist T entscheidbar.

(2.5.7) Definition: $B \subset (A^*)^q, q \ge 0$ , heißt aufzählbar genau dann, wenn B Wertebereich einer partiell rekursiven Funktion ist.

(2.5.8) Lemma: $B\subseteq(A^*)^q,\ q\ge0$ , entscheidbar $\Rightarrow$ B ist aufzählbar.

Beweis: Sei $B\subseteq(A^*)^q$ entscheidbar. Nach Definition (2.5.1) existiert eine total rekursive Funktion

$\chi_B : (A^*)^q\longr A^*\text{ mit}\\ \chi_B(x_1,\dots,x_q)=\varepsilon\Leftrightarrow(x_1,\dots,x_q)\in B$

Aus $\chi_B$ läßt sich eine partiell rekursive Abbildung

$f_B\ :\ (A^*)^q\longr A^*\text{ gewinnenmit}\\f_B(x_1,\dots,x_q)=\{\varepsilon,\text{ falls }\chi_B(x_1,\dots,x_q)=\varepsilon\\\text{undefiniert sonst.}$

Dann ist die Abbildung $g_B\ :\ (A^*)^q\longr (A^*)^q$ mit $g_B(\overline{x})=\Pi^2_1(\overline{x},f_B(\overline{x})),\ \overline{x}\in(A^*)^q$ , partiell rekursiv und hat als Wertebereich die Menge B.¹⁾

(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 $m,k\ge0$ die Menge $T_{m,k} := \{g(\pi)|\pi\in PL(A),\text{ \pi\ hat genau m Eingabe- und k Ausgabevariable\}\subset\mathbb{N}_0$ entscheidbar ist. Man braucht dem Entscheidungsalgorithmus im Beweis von (2.5.6) nur noch einen Test, ob ein Programm $v\in PL(A)$ genau m Eingabe- und k Ausgabevariable aufweist, hinzuzufügen. Aus der Entscheidbarkeit von $T_{m,k}$ folgt die Aufzählbarkeit von $T_{m,k}$ und damit die Existenz einer partiell rekursiven Funktion von $\mathbb{N}_0$ nach $\mathbb{N}_0$ , die die Menge $T_{m,k}$ als Wertebereich hat. Da $T_{m,k}\ne\emptyset$ ist, folgt sogar die Existenz einer total rekursiven Funktion (vgl.[5] Seite 82)

$t_{m,k}\ :\ \mathbb{N}_0 \longr \mathbb{N}_0 \text{ mit }\\ t_{m,k}(\mathbb{N}_0) = T_{m,k}$

Es hat also Sinn, wieder vom i-ten Element aus $T_{m,k}$ zu sprechen. Für alle $m,k\ge0$ läßt sich also auch die Menge aller Programme mit m Eingabe- und k Ausgabevariablen in der Form $\{\pi_0,\pi_1,\pi_2,\dots\}$ hinschreiben. Dabei ist $\pi_j$ dasjenige Programm aus PL(A) mit $t_{m,k}(j) = g(\pi_j)$ .

Insgesamt existiert also für alle $m,k\ge0$ eine total rekursive Funktion

$\gamma_{m,k}\ : \ \mathbb{N}_0 \longr \{ \pi | \pi \in PL(A), \pi\ \text{ hat genau m Eingabe- und k Ausgabevariable \} =: W$ ,

mit der "Umkehrung" $\overline\gamma_{m,k}\ :\ W \longr \mathbb{N}_0$ mit

$\overline\gamma_{m,k}(\pi) := \min\{j|\gamma_{m,k}(j)=\pi\}$

Mit $T_{m,k}$ , ist natürlich auch die Menge $\cal{P}^m_k$ für alle $m,k\ge0$ entscheidbar und damit aufzählbar. Die Menge $\cal{P}^m_k$ läßt sich also in der Form $\{f_0,f_1,f_2,\dots\}$ hinschreiben, wobei für jedes $f_j$ gilt: $f_j = \varphi_{\pi_j}$ . Die Gödelnummer von $\pi_j$ . überträgt sich dabei auf $f_j$ . In der obigen Aufzählung von $\cal{P}^m_k$ kommen alle Funktionen aus $\cal{P}^m_k$ mehrfach vor. Das bedeutet aber, daß die Funktionen aus $\cal{P}^m_k$ , mehrere Gödelnummern besitzen. Es gilt sogar:

(2.5.10) Lemma: Für alle $f\in\cal{P}^m_k$ gilt: f hat bzgl. der Gödelisierung g unendlich viele Gödelnummern ( $m,k\ge0$ ).

Beweis: Seien $m,k\ge0,\ f\in\cal{P}^m_k$ . f wird realisiert durch das Programm

$\begin{align} \pi_0 = &\text{\underline{input}} & X_1,\dots,X_m;\\ & & AW_{\pi_0}\\ &\text{\underline{output}} & Z_1,\dots,Z_k \end{align}$

Es gilt $\gamma_{\pi_0} = f$ . f wird aber auch realisiert durch die Programme $\pi_1,\pi_2,\pi_3,\dots$

$\text{mit }\pi_i\ =\ \text{input}\ X_1,\dots,X_m;\ AW_{\pi_0};\\\underbrace{\overline\varepsilon;\dots\overline\varepsilon;}\ \text{\underline{output}}\ Z_1,\dots,Z_k\\\text{i-mal}$

Es gilt $f = \varphi_{\pi_1} = \varphi_{\pi_2} = \varphi_{\pi_3} = \dots$

Wegen $g(\pi_1)\ne g(\pi_2)\ne\dots$ hat f unendlich viele Gödelnummern.

(2.5.11) Definition: Sei $\cal{F}$ eine Menge von Wortfunktionen, und sei $\cal{F}^r_s := \{ f : (A^*)^r \longr (A^*)^s | f\in\cal{F}\},\ r,s\ge0$ . Eine Funktion $\psi\in\cal{F}^{r+1}_s$ heißt universell für $\cal{F}^r_s$ , wenn gilt:

$\cal{F}^r_s = \{\lambda\overline{y}[\psi(x,\overline{y})]|x\in A^*,\ \overline{y}\in(A^*)^r\}$ .¹⁾

(2.5.12) Satz: Für alle $m,k\ge0$ gilt:

Es gibt zu $\cal{P}^m_k$ eine universelle Funktion $\psi_{m,k}\in\cal{P}^{m+1}_k$ .

Beweis: (mittels Church'scher These)

Die Menge aller Programme mit m Eingabe- und k Ausgabevariablen liege in aufgezählter Form, etwa durch $\gamma_{m,k}$ , vor:

$\pi_0,\pi_1,\pi_2,\dots$

Dann ist die Funktion

$\psi_{m,k}:=\lambda x,\overline{y}[\varphi_{\pi_{\overline\gamma_{m,k}(x)}(\overline{y})}],\ y\in(A^*)^m$

universell für $\cal{P}^m_k$ , und $\psi_{m,k}$ ist intuitiv berechenbar. Wegen der Church'schen These gibt es ein $\pi^{m,k}_u\in PL(A)$ mit m+1 Eingabe- und k Ausgabevariablen mit $\psi_{m,k}=\varphi_{\pi^{m,k}_u}$ .

(2.5.13) Bemerkung: Man kann (2. 5.12) auch beweisen, indem man auf komplizierte Weise direkt $\pi^{m,k}_u$ konstruiert.

2.6. Lexikographische Ordnung von $A^*$

Wir wollen eine weitere Gödelisierung von $A^*$ einführen. Dazu definieren wir zunächst, was unter der lexikographischen Ordnung auf $A^*$ zu verstehen ist.

(2.6.1) Definition: Sei $A=\{a_1,\dots,a_n\}$ . Die Nachfolgerfunktion $\nu : A^* \longr A^*$ 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$

(2.6.2) Lemma: Die Nachfolgerfunktion $\nu : A^* \longr A^*$ ist bijektiv.

Beweis: Zunächst ist $\nu$ injektiv, da zwei Elemente aus $A^*$ nur dann den gleichen Nachfolger haben können, wenn sie gleich sind. $\nu$ ist surjektiv, da man durch wiederholte Anwendung von $\nu$ jedes Wort aus $A^*$ auf das leere Wort reduzieren kann. Also $\{\nu^i(\varepsilon)|i\in\mathbb{N}\}=A^*$ .

Wegen $w_i=\nu^i(\varepsilon)$ für jedes Element $w_i$ , aus $A^*$ erhält man eine Ordnung auf $A^*$ . [5]

(2.6.5) Definition: Seien $w_i=\nu^i(\varepsilon)$ und $w_j=\nu^j(\varepsilon)$ aus $A^*$ , dann ist $w_i\le w_j$ genau dann, wenn $i \le j$ gilt. Diese Ordnung heißt lexikographische Ordnung auf $A^*$ .

Man kann also alle Wörter aus $A^*$ eindeutig in lexikographischer Reihenfolge auflisten:

$\varepsilon=w_0\lt w_1\lt w_2\dots$ .

(2.6.4) Satz: Sei $A=\{a_1,\dots,a_p\}$ und $A_0=\{1\}$ . Sei $C_p:A^*\longr\mathbb{N}_0\hat{=}\{1\}^*$ die Abbildung, die jedem $x \in A^*$ die Nummer von x in der lexikographischen Reihenfolge zuordnet, also

$x \longr i$ mit $\nu^i(\varepsilon) = x$ .

Dann ist $C_p$ eine bijektive Gödelisierung.

Beweis:

$C_p$ ist total, da $C_p$ auf ganz $A^*$ definiert ist. Für jedes x läßt sich $C_p(x)$ durch endlich viele Anwendungen der Definition von $\nu$ effektiv ermitteln. Also ist $C_p\in\cal{R}$ .
$C_p$ ist injektiv, da es keine zwei Elemente aus $A^*$ gibt mit gleicher Stellung in der lexikographischen Reihenfolge.
Wegen $C_p(A^*)=\mathbb{N}_0$ ist $C_p(A^*)$ natürlich entscheidbar.
Beginnend mit dem leeren Wort kann man für jedes $i\in\mathbb{N}_0$ mit Hilfe von $\nu$ effektiv alle Worte aus $A^*$ bis zum i-ten Wort in lexikographischer Reihenfolge erzeugen. Dieses i-te Wort ist das Urbild von i. Also ist $C^{-1}_p$ berechenbar und wegen $C_p(A^*)=\mathbb{N}_0$ sogar total. Also $C^{-1}_p\in\cal{R}$ .

Aus (i) bis (iv) folgt: $C_p$ ist Gödelisierung. Wegen (ii) und $C_p(A^*)=\mathbb{N}_0$ folgt: $C_p$ ist bijektiv.

(2.6.5) Lemma: Seien $A=\{a_1,\dots,a_n\}$ und $B=\{b_1,\dots,b_m\}$ zwei Alphabete, dann ist die Funktion $\xi_{n,m}:=C^{-1}_m\circ C_n:A^*\longr B^*$ eine bijektive Kodierung von $A^*$ durch $B^*$ .

Beweis: Offensichtlich.

2.7. Reduktion auf jeweils eine Eingabe- und eine Ausgabevariable

Wir wollen zeigen, daß es möglich ist, jedes Programm $\pi$ aus PL(A) mit r Eingabe- und s Ausgabevariablen in ein "äquivalentes" Programm $\pi'$ mit nur jeweils einer Eingabe- und Ausgabevariablen zu transformieren. Wegen der Entsprechung von $\cal{P}$ und PL(A) genügt es demnach also, die Funktionen aus $\cal{P}^1_1$ zu betrachten, um ganz $\cal{P}$ zu behandeln. Die universelle Funktion für $\cal{P}^1_1$ ist in diesem Sinne dann universell für ganz $\cal{P}$ .

Sei nun $\pi\in PL(A)$ mit r Eingabe- und s Ausgabevariablen, $r,s\ge1$ . Dann hat $\pi$ folgenden Aufbau.

$\begin{align} \pi = &\text{\underline{input}} & X_1,\dots,X_r;\\ & & AW_\pi;\\ &\text{\underline{output}} & Z_1,\dots,Z_s \end{align}$

Als Eingabebelegung für $\pi$ kommt jedes Element $\overline{x}=(x_1,\dots,x_r)$ aus $(A^*)^r$ vor. $\overline{x}$ kann man auch wie folgt darstellen:

$\overline{x}=x_1|x_2|\dots|x_r\in(A\cup\{|\})^*$ , dabei sei $|\not\in A$ .

In dieser Form wird $\overline{x} als Eingabe für ein zu <tex>\pi$ gleichwertiges Programm $\pi'$ 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}$

Die Programmteile in Klammern lassen sich wie folgt realisieren:

$[X_1:=x_1;\dots. X_r:=x_r]$

durch:

$\fbox{ X_1:=\varepsilon;\dots X_r:=\varepsilon;\\ \begin{array}{rccclBCB} \text{\underline{loop}}X&\text{\underline{case}} & a_1 & \longr& X_r := X_r a_1,\\ & & \vdots& & \vdots\\ & & a_n & \longr& X_r := X_r a_n,\\ & & | & \longr& X_1 := X_2;\\ & & & & X_2 := X_3;\\ & & & & \vdots\\ & & & & X_{r-1} := X_r;\\ & & & & X_r := \varepsilon,\\ &\text{\underline{end}} \end{array} }$

und $[Z:=z_1|\dots|z_s]$

durch

$\fbox{ Z:=\varepsilon;\\ \begin{array}{rccclBCB} \text{\underline{loop}} Z_1 &\text{\underline{case}}&a_1 & \longr&Z:=Za_1,\\ & &\vdots & &\vdots\\ & &a_n &\longr &Z:=Za_n,\\ &\text{\underline{end}}; \end{array}\\ Z:=Z|;\\ \begin{array}{rccclBCB} \text{\underline{loop}} Z_2 &\text{\underline{case}}&a_1 & \longr&Z:=Za_1,\\ & &\vdots & &\vdots\\ & &a_n &\longr &Z:=Za_n,\\ &\text{\underline{end}}; \end{array}\\ Z:=Z|;\\ \vdots\\ Z:=Z|;\\ \begin{array}{rccclBCB} \text{\underline{loop}} Z_s &\text{\underline{case}}&a_1 & \longr&Z:=Za_1,\\ & &\vdots & &\vdots\\ & &a_n &\longr &Z:=Za_n,\\ &\text{\underline{end}}; \end{array}\\ }$

$\pi'$ ist nicht Element aus PL(A), da das zugrunde liegende Alphabet nicht A sondern $A\cup\{|\}\not\in A$ ist. Wir können aber aus $\pi'$ ein ebenfalls zu $\pi$ gleichwertiges Programm $\pi''\in PL(A)$ mit nur einer Ein- und einer Ausgabevariablen gewinnen, indem wir $\{A\cup\{|\}\}^*$ durch $A^*$ kodieren. Als Kodierung können wir die Funktion

$\xi_{n+1,n}:=C^{-1}_n \circ C_{n+1}$

benutzen, wobei die Funktionen $C^{-1}_n$ und $C_{n+1}$ 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 $\cal{P}$ die Menge $\cal{P}^1_1$ zu betrachten. Die universelle Funktion $\psi_{1,1}$ für $\cal{P}^1_1$ ist in diesem Sinne universell für ganz $\cal{P}$ . Um diesen Tatbestand deutlich zu machen, führen wir die folgende Schreibweise ein.

(2.7.1) Definition: Sei $\psi_{1,1}$ universelle Funktion für $\cal{P}^1_1$ . $\varphi^k_x:=\lambda y_1,\dots,y_k[\psi_{1,1}(x,\xi_{n+1,n}(y_1|\dots|y_k)]$ , $x,y_1,\dots,y_k\in A^*$ .

Dabei ist $\varphi^k_x : (A^*)^k \longr A^*$ .

2.8. s-m-n-Theorem, Rekursionstheorem

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 $A^*$ liegt (Vermeidung von Umkodierungen).

(2.8.1) Satz (s-m-n-Theorem):

Für alle $m,n\in\mathbb{N}$ gibt es eine Funktion $s^m_n\in\cal{R}^{m+1}_1$ , die für alle $x\in A^*,\ \overline{y}\in(A^*)^m,\ \overline{z}\in(A^*)^n$ folgende Gleichung erfüllt:

$\varphi^{m+n}_x(\overline{y},\overline{z})=\varphi^n_{s^m_n(x,\overline{y})}(\overline{z})$

Beweis: Seien $n,m\in\mathbb{N}$ fest gewählt.

Fall: x ist kein gültiger Programmtext. Dann ist $\varphi^{m+n}_x$ undefiniert. In diesem Falle muß $\varphi^n_{s^m_n(x,\overline{y})}$ auch undefiniert sein. Es wird deshalb $s^m_n(x,\overline{y}) = \varepsilon$ gesetzt. Nun ist auch $s^m_n(x,\overline{y})$ kein gültiger Programmtext, und es gilt:
$\varphi^{m+n}_x(\overline{y},\overline{z}) = \varphi^n_{s^m_n(x,\overline{y})}(\overline{z}) =\text{undefiniert}.$
Fall: x ist ein gültiger Programmtext. Also $x \in PL(A)$ . Dann hat x den Aufbau:
$\begin{align} x = &\text{\underline{input}} & Y_1,\dots,Y_m,Z_1,\dots,Z_n\\ & & AW_x;\\ &\text{\underline{output}} & W \end{align}$

Mit $\overline{y} = (y_1,y_2,\dots,y_m)$ 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}$

Die Programmteile in eckigen Klammern lassen sich leicht - wie am Beispiel von $[Y_1:=y_1]$ gezeigt - realisieren:

$y_1$ ist Element aus $A^*$ und hat somit endliche Länge $l(y_1)\in\mathbb{N}_0$

$y_1 = a_{1_1}\dots a_{1_{l(y_1)}}$ mit $a_{1_j}\in A^*$ .

Damit wird $[Y_1:=y_1]$ realisiert durch

$Y_1:=\varepsilon;\\ Y_1:=Y_1 a_{1_1}\\ \vdots\\ Y_1:=Y_1 a_{1_{l(y_1)}};$

Auf Grund der Cnurch'schen These ist $s^m_n\in\cal{R}^{m+1}_1$ .

(2.8.2) Korollar: Es gibt ein $h\in\cal{R}^m_1$ , so daß für alle $f\in\cal{R}^{m+n}_1$ gilt:

$f(\overline{y},\overline{x})=\varphi^n_{h(\overline{y})}(\overline{x})$ für alle $\overline{x}\in(A^*)^m,\ \overline{y}\in(A^*)^n$ .

Beweis: Da f eine berechenbare Funktion ist, gibt es ein Programm $\pi_0\in A^*$ , mit $f=\varphi^{m+n}_{\pi_0}$ . Aus (2.3.1) folgt

$f(\overline{y},\overline{x})=\varphi^{m+n}_{\pi_0}(\overline{y},\overline{x})=\varphi^n_{s^m_n(\pi_0,\overline{y})}(\overline{x})$ .

Setzt man $h := \lambda\overline{y}[s^m_n(\pi_0,\overline{y})]$ , so folgt das Korollar.

(2.8.3) Bezeichnung: Sei $g\in\cal{P}^{k+1}_1$ . Dann existiert ein Programm $x\in A^*$ mit $g=\varphi^{k+1}_x$ .

Wir führen nun folgende Notation ein:

$g_x:=\varphi^k_{s^1_k(x,y)}$

Es gilt mit dieser Notation:

$g_x(\overline{y})=g(x,\overline{y})$ für alle $\overline{y}\in(A^*)^k$ .

Sei $h\in\cal{P}^r_1$ und $h(\overline{x})=\text{undefiniert}$ für ein $\overline{x}\in(A^*)^r$ , so ist nach obiger Notation die Funktion $g_{h(\overline{x})}$ ü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 $f\in|cal{P}^1_1$ gibt es einen Text $x\in A^*$ , so daß gilt:

$\varphi_x=\varphi_{f(x)}$

Beweis: Die Funktion

$g=\lambda y,x[\varphi_{\varphi_y(y)}(x)]$

liegt in $\cal{P}^2_1$ mit $x,y \in A^*$ . In Korollar (2.8.2) wurde gezeigt, daß ein $h\in\cal{R}^1_1$ , existiert mit

$(1)\ \ \varphi_{h(y)} = g_y =\varphi_{\varphi_y(y)}\ \ \text{f\ddot{u}r alle } y\in A^*$

Sei nun $f\in\cal{P}^1_1$ . Da $h\in\cal{R}^1_1$ ist, kann man die Hintereinanderausführung von f und h betrachten. $f \circ h$ liegt ebenfalls in $\cal{P}^1_1$ . Auf Grund der Church'schen These kann man zu $f \circ h$ effektiv einen Programmtext $\pi$ aus PL(A) angeben mit

$(2)\ \ \varphi_\pi = f \circ h$

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

$\varphi_{h(\pi)} \overset{(1)}{=} \varphi_{\varphi_\pi(\pi)} \overset{(2)}{=} \varphi_{f(h(\pi))}$

Damit ist $x = h(\pi)$ das gesuchte x.

(2.8.5) Definition: Sei $f\in\cal{P}^1_1$ . Ein Element $x \in A^*$ heißt Fixpunkt zu f, falls gilt $\varphi_x = \varphi_{f(x)}$ .

(2.8.6) Korollar: Zu jeder Funktion $g\in\cal{P}^2_1$ existiert ein Text $x_0 \in A^*$ mit $\varphi_{x_0} = g_{x_0}$ .

Beweis: Nach Korollar (2.8.2) existiert eine Funktion $h\in\cal{R}^1_1$ mit $\varphi_{h(y)} = g_y$ für alle $y\in A^*$ .

h hat nach dem Rekursionstheorem einen Fixpunkt $x_0$ mit $\varphi_{x_0}=\varphi_{h(x_0)}=g_{x_0}$

(2.8.7) Satz: Es existiert in $\cal{P}^1_1$ eine Funktion mit einem Programmtext $x_0\in A^*$ , der für jede Eingabe $y\in A^*$ seinen eigenen Text $x_0$ ausgibt.

Beweis: Die Funktion $g = \Pi^2_1 : (A^*)^2 \longr A^*$ mit $g(x,y):=x$ für alle $x,y \in A^*$ ist trivialerweise aus $\cal{P}^2_1$

Aus Korollar (2.8.6) folgt damit, daß die Gleichung $\varphi_x = g_x$ eine Lösung $x_0$ besitzt. Es existiert also ein $x_0 \in A^*$ mit

$\varphi_{x_0} = g_{x_0} = \lambda y [x_0] \Rightarrow \varphi_{x_0}(y) = x_0\ \ \forall y \in A^*$

$\varphi_{x_0}$ ist also eine Funktion, die bei jeder Eingabe $y \in A^*$ ihren eigenen Programmtext $x_0$ ausgibt. Mit $\varphi_{x_0}\in\cal{P}^1_1$ (trivial) ist der Satz vollständig bewiesen.

Der folgende Satz ist eine Verallgemeinerung von Satz (2.8.7).

(2.8.8) Satz: Sei $f\ :\ A^* \longr A^*$ aus $\cal{P}^1_1$ . Dann existiert in $\cal{P}^1_1$ eine Funktion mit einem Programmtext $x_0 \in A^*$ , der für jede Eingabe den Wert $f(x_0)$ ausgibt.

Beweis: Sei $f\in\cal{P}^1_1$ . Die Funktion $g\ :\ (A^*)^2 \longr A^*$ mit

$g(x,y):=\Pi^2_1(f(x),y)=f(x),\ \ x,y \in A^*$ ,

liegt in $\cal{P}^2_1$ . Dies folgt aus der Abgeschlossenheit von $\cal{P}$ gegenüber der Kombination und der Substitution von Funktionen (vgl. etwa [5]). Aus (2.8.6) folgt damit, daß die Gleichung $\varphi_x = g_x$ eine Lösung $x_0$ besitzt. Es existiert also ein $x_0 \in A^*$ mit

$\varphi_{x_0}=g_{x_0}=\lambda y[f(x_0)]\Rightarrow\varphi_{x_0}(y)=f(x_0)\ \ \forall y \in A^*$

Da $\varphi_{x_0}$ eine konstante Funktion ist, liegt $\varphi_{x_0}$ trivialerweise in $\cal{P}^1_1$ . $\varphi_{x_0}$ 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 $i\in\mathbb{N}$ existiert eine Funktion mit einem Programmtext $x_{i_0} \in A^*$ , der für jede Eingabe $y \in A^*$ seinen eigenen Text $x_{i_0}$ i-mal hintereinander ausgibt.

Beweis: Sei $i\in\mathbb{N}$ . Dann ergibt sich der Beweis aus dem Beweis von Satz (2.8.8) mit

$\begin{array}{rccclBCB} f = & f_i\ :\ A^* \longr A^*\\ & f_i(x) := x_i & ( = \underbrace{x \dots\dots x} ).\\ & & i-mal \end{array}$

(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 $i_0\in\mathbb{N}_0$ mit $\pi_{i_0}$ ist selbstreproduzierend. Für die Zahl $i_0$ 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.

3. Selbstreproduzierende Programme in realen Programmiersprachen - Einige Beispiele

3.1. Einleitung

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.).

3.2. Selbstreproduzierende Programme in SIMULA¹⁾

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.

3.2.1. Naiver Ansatz

Um eine Vorstellung von der Problematik, ein selbstreproduzierendes SIMULA-Programm $\pi$ anzugeben, zu erhalten, betrachten wir folgenden naiven Ansatz:

$\pi$ enthält im wesentlichen nur eine Ausgabeanweisung. Diese Anweisung gibt den ganzen Programmtext von $\pi$ aus.

Ein solcher Ansatz führt zu folgendem Programm $\pi_0$ :

 = 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

$\pi_0$ ist natürlich kein endlicher Text und damit kein Programm mehr. Die "Unmöglichkeit" von $\pi_0$ 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!

3.2.2. Textzerlegung und Algorithmus

Aus 3.2.1. folgt, daß ein selbstreproduzierendes SIMULA-programm $\pi$ seinen eigenen Text nicht en bloc mit einer einzigen Ausgabeanweisung ausgeben kann. $\pi$ muß seinen Text also in mehreren Schritten aus einigen Teilstrings zusammensetzen. Es muß also eine

Zerlegung des Textes $\pi$
vorgenommen werden. Da wir über die Art der Zerlegung nichts wissen, versuchen wir es zunächst mit der totalen Zerlegung von $\pi$ , das heißt, wir zerlegen $\pi$ 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ß $\pi_1$ einen unendlichen Text darstellt und damit kein Programm sein kann.

Die Unendlichkeit von $\pi_1$ 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 $\pi_1$ zum Scheitern verurteilt, wenn der Programmtext in einzelne Buchstaben zerlegt wird. Die Wahl eines der Zerlegung des Programmtextes entsprechend strukturierten
Algorithmus
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.

3.2.3. Ein tabellengesteuertes Programm

Wir greifen mit Programm $\pi_2$ die Idee von der totalen Zerlegung des Textes $\pi_2$ in einzelne Zeichen aus 3.2.2. auf. Diese Zerlegung wird aber nicht wie in $\pi_1$ explizit sichtbar, sondern sie äußert sich im verwendeten Algorithmus. Dieser Algorithmus setzt den Text von $\pi_1$ , 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}$

Der Algorithmus hat die Aufgabe, sukzessive Komponenten aus C auszugeben, so daß nsgesamt der Programmtext $\pi_2$ , 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}$

Das Programm $\pi_2$ , 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 $\forall\alpha\in D$ die Zahl $i_\alpha\in\mathbb{N}_0$ der Index, unter dem das Zeichen $\alpha\in D$ in der Tabelle C abgelegt ist: $\alpha = C[i_\alpha]$

(3.2.3.2) Lemma: Die Abbildung $\delta\ :\ D^*\longr\mathbb{N}^*_0$ mit

$\delta(\varepsilon) = \varepsilon\\\delta(w\alpha) = \delta(w)i_\alpha\ \ \ \ \forall w\in D^*,\ \alpha\in D$

ist Kodierung von $D^*$ durch $\mathbb{N}^*_0$ .

Beweis:

$\delta(x)$ ist für jedes $x \in D^*$ definiert. Also ist $\delta$ total, $\delta$ ist trivialerweise berechenbar.
Da in der Tabelle C jedes Zeichen aus D genau einmal gespeichert ist, folgt: $\delta$ ist injektiv.
Sei $\overline{j} = j_1\dots j_n$ aus $\mathbb{N}^*_0$ , $\overline{j}$ ist genau dann aus $\delta(D^*)$ , wenn jedes $j_k, k\in[n]$ , aus {0,.....,maxchar} ist. Also ist $\delta(D^*)$ entscheidbar.
Sei $\overline{j} = j_1\dots j_n$ aus $\delta(D^*)$ . Mit Hilfe der Tabelle C läßt sich für jedes $j_k, k\in[n]$ , das Zeichen aus D ermitteln, das durch $j_k$ kodiert wird. Mit höchstens $\text{n \cdot maxchar}$ Vergleichen läßt sich so das Urbild von $\overline{j}$ unter $\delta$ ermitteln. Also ist $\delta^{-1}$ berechenbar.

Aus (i) bis (iv) folgt: $\delta$ ist Kodierung (vgl.(2.5.2)).

(3.2.3.3) Bemerkung: Jedes SIMULA-Programm $\pi$ hat als endliches Wort aus $D^*$ eine Kodierung $\delta(\pi)$ in $\mathbb{N}^*_0$ .

Bei jedem Durchlauf durch die while-Schleife im Algorithmus von $\pi_2$ 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 $\mathbb{N}^*_0$ 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)]$

Damit $\pi_2$ seinen eigenen Text ausgeben kann, muß gelten:

$C[i_1]\ C[i_2] \dots\ \dots C[i_{l(\pi_2)}]\overset!=\pi_2$

Es gilt daher:

Die Funktion von <berechne neues I> ist die sukzessive Ermittlung der Kodierung von $\pi_2$ bezüglich $\delta$ .
Die Funktion des gesamten Algorithmus von $\pi_2$ ist die Dekodierung der ermittelten Kodierung, also die Realisierung von $\delta^{-1}$ .

Die Berechnung der $i_j,\ j\in[l(\pi_2)]$ , ist das noch verbleibende Problem. Die $i_j$ müssen iterativ mittels einer Funktion $F\ :\ \mathbb{N}_0\longr\mathbb{N}_0$ erzeugt werden:

$\fbox{ \text{Setze i_1;\\ i_{j+1} := F(i_j);\ \ j\in[l(\pi_2)-1] }}$

Die Funktion F läßt sich als Funktionsprozedur realisieren und innerhalb von Teil Ia von $\pi_2$ 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:

F muß in vertretbarer Zeit berechenbar sein und
die von F benutzten Zwischenergebnisse müssen im darstellbaren Zahlenbereich der Rechenmaschine liegen.

Es ist möglich, daß ein konkretes F nicht von I abhängt.

3.2.4. Vahl der Iterationsfunktion F

In diesem Abschnitt werden zwei Funktionen diskutiert, die als Iterationsfunktion denkbar wären.

3.2.4.1. Eine Iterationsfunktion mittels Modulo-Bildung

Wir erweitern die Kodierung $\delta$ zu einer Gödelisierung (vgl. (2.5.3)). Dazu definieren wir die Abbildung $f_\delta$ .

(3.2.4.1.1) Definition: Die Abbildung $f_\delta\ :\ \mathbb{N}^*_0\longr\mathbb{N}_0$ sei wie folgt definiert:

$f_\delta(\overline{i}) = \left{ \text{\emptyset, falls \overline{i} = \varepsilon\\ \sum^k_{j=1} i_j(maxhar+1)^{j-1}\text{, falls \overline{i}=i_1\dots i_k} \right.$

Ist $\overline{i}\in\delta(D^*)$ , so ist jedes $i_j,\ j\in[k]$ , kleiner oder gleich (maxchar+1). Die Restriktion von $f_\delta$ auf $\delta(D^*)$ ist somit injektiv und kodiert die Elemente von $\delta(D^*)$ durch $\mathbb{N}_0$ . Es folgt somit:

(3.2.4.1.2) Lemma: Die Abbildung $f\ :\ D^*\longr\mathbb{N}_0$ mit $f := f_\delta\circ\delta$ ist Gödelisierung von $D^*$ .

Beweis: Offensichtlich

Von Interesse ist für uns die Tatsache, daß man aus der Zahl f(x) für jedes $x\in D^*$ effektiv die Komponenten von $\delta(x)$ zurückberechnen kann. Dies gilt insbesondere für $f(\pi_2)$ , und wir gewinnen mit

$\text{\underline{integer procedure} F;}\\ \begin{array}{rll} \text{\underline{begin}}& \text{F := X} &\text{\underline{mod}(maxchar+1);}\\ & \text{X := X}//&\text{(maxchar+1);}\\ \text{\underline{end}} & &\searrow\\ & &\text{ ganzzahlige Division} \end{array}$

eine Iterationsvorschrift zur Erzeugung von $\delta(\pi_2)$ , wenn wir für X den Startwert $f(\pi_2)$ wählen.

Da der Startwert von X, also $f(\pi_2)$ , von $\pi_2$ nicht eingelesen werden darf, muß $\pi_2$ die Zuweisung

$X := f(\pi_2)$

enthalten. $f(\pi_2)$ ist eine ganze Zahl und damit textueller Bestandteil von $\pi_2$ . Zum Zeitpunkt der Erstellung von $\pi_2$ ist die Zahl $f(\pi_2)$ unbekannt, sie kann erst nachträglich ermittelt werden. Beim Aufschreiben des Programms $\pi_2$ muß in der Anweisung $X:=f(\pi_2);$ die Zahl $f(\pi_2)$ zunächst ausgelassen werden. Erst nach Erstellung des Programms - das $f(\pi_2)$ immer noch nicht enthält - läßt sich dann q := f( $\pi_2$ ohne den string $f(\pi_2)$ ") errechnen. Mit der Zahl q als Startwert für X wird $\pi_2$ nur seinen Text ohne die Zahl q reproduzieren können. Diesen Mißstand beseitigen wir, indem wir den Algorithmus von $\pi_2$ , abändern:

Es läßt sich leicht feststellen, nach dem wievielten Schritt des Algorithmus die Zahl $f(\pi_2)$ ausgegeben werden muß. Es sei dies der r-te Iterationsschritt. Die Zahl r wird Bestandteil des Programms. Der Algorithmus von $\pi_2$ 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 $\pi_2$ vorkommen. Dementsprechend kann die Zahl maxchar möglichst klein gehalten werden. Die Zahlen r,q und l(" $\pi_2$ ohne den String q") lassen sich ermitteln, nachdem das übrige Programm erstellt wurde. Es ist leicht einzusehen, daß gilt:

$\pi_2$ reproduziert sich selbst.

Das Programm $\pi_2$ 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 $\pi_2$ mindestens 32 verschiedene Zeichen vor. Damit gilt maxchar≥32.

Für die Länge von $\pi_2$ gilt, wenn man nur die unbedingt nötigen blanks, die als Trennzeichen fungieren, mitrechnet:

l(" $\pi_2$ ohne die Zahl q") > 700

Aus Definition (3.2.4.1.1) und der Definition von q folgt damit: $q>32^{700-1}$

Trotz dieser sehr groben Abschätzung von q zeigt sich, daß q in herkömmlichen Rechnern nicht darstellbar ist.

3.2.4.2. Eine Iterationsfunktion basierend auf der Gödelisierung g aus 2.5.

In Abschnitt 2.5. wurde die Gödelisierung $g\ :\ C^*\longr\mathbb{N}_0$ eingeführt. Auf völlig analoge Weise kann man eine Gödelisierung $g_D\ :\ D^*\longr\mathbb{N}_0$ konstruieren, indem man C durch D und die Abbildung $H\ :\ C\longr\mathbb{N}_0$ durch die Abbildung $H_D\ :\ D\longr\mathbb{N}_0$ mit $H_D(\alpha) : = i_\alpha$ für alle $\alpha\in D$ ersetzt. Wie man aus jeder Gödelnummer $g(w),\ w\in C^*$ , effektiv das Urbild w bestimmen kann, so kann man das gleiche auch für jede Gödelnummer $g_D(v),\ v\in D^*$ , durchführen.

Damit läßt sich wie in 3.2.4.1. eine Prozedur F' entwickeln, mit deren Hilfe es möglich ist, $\delta(\pi_2')$ iterativ zu berechnen, wenn $q' := g_D(\quote\pi_2'\text{ ohne die Zahl \pi_2'\quote})$ als Startwert für die Iteration gewählt wird. Sir erhalten dann ein ähnliches selbstreproduzierendes Programm $\pi_2'$ 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 $\pi_2'$ beträgt mindestens 650 Zeichen. Dann ist

$q>p_1^{i_B}\cdot p_2^{i_E}\cdot p_3^{i_G}\cdot p_4^{i_I}\cdot p_5^{i_N}\cdot\dots\cdot p_{588}^{i_\alpha+1} \overset.-1,\ \alpha\in D$

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

$q' > 10^{600}$

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

3.2.5. Ein textgesteuertes SIMULA-Programm $\pi_3$

In Abschnitt 3.2.4. wurden selbstreproduzierende Programme $\pi_2$ und $\pi_2'$ 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 $\pi_2$ das Programm $\pi_3$ , indem wir folgende Änderungen vornehmen:

Zerlegung: Im Gegensatz zu $\pi_2$ wird $\pi_3$ 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.
Algorithmus: Die Aufgabe des Algorithmus von $\pi_3$ besteht darin, den Programmtext $\pi_3$ aus Teilstrings, die in dem Feld C gespeichert sind, zusammenzusetzen. Jede Feldkomponente wird durch ihren Index kodiert. Der Text $\pi_3$ läßt sich dann als Folge von Indizes kodieren:
$\pi_3\longr i_1,\dots,i_k,\ \ i_j\in\{1,\dots,\text{maxtext}\}$

Diese Folge von Indizes schreiben wir als Text in die text-Variable X. Mittels der text-Prozeduren SUB und GETINT¹⁾ ist der Zugriff auf die einzelnen Zahlen $i_j$ im Text X gewährleistet. Der Algorithmus von $\pi_3$ braucht also nur noch den Text X sequentiell zu durchlaufen und für jedes $i_j$ aus X den Text $C[i_j]$ auszugeben.

Durch eine derartige Ausnutzung des Text-Konzepts der Programmiersprache SIMULA umgehen wir die Repräsentation von $\pi_3$ durch eine ganze Zahl, wie dies in $\pi_2$ und $\pi_2'$ 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 $\pi_3$ 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 $\pi_3$

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 $\pi_3$

Die Textvariablen C[1],...,C[33] und X enthalten die Teilstrings des Programms. Besonders wichtig sind dabei die mehrfach auftretenden Teilstrings. Es sind dies:
```
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 $\pi_3$ 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.
Das obige Programm arbeitet mit einem 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].

Die Punkte (i) und (ii) deuten schon an, daß sich viel Programmtext und Komponenten von C einsparen lassen. Weniger Komponenten bedeutet aber, daß wir mit weniger Ziffern auskommen, um die Komponenten zu adressieren. Möglicherweise kann die Programmzeile 18 weggelassen werden, da die Ziffer 4 gar nicht zur Adressierung benötigt wird.

Führt man die Verbesserungen (i) bis (iii) an Programm $\pi_3$ konsequent durch, so erhält man das folgende Programm $\pi_3'$ . 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 $\pi_3$ 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:

Die Komponenten von C können so adressiert werden, daß die in C[23] häufig auftretenden Adressen möglichst kurz sind.

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.

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

3.2.6. Implementierung des Programms $\pi_3$

Das Programm $\pi_3$ 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 $\pi_3$ erhöht werden, damit keine Laufzeitfehler auftreten. $\pi_3$ wird daher um die Anweisung

SYSOUT.IMAGE:-BLANKS(200);

ergänzt. Entsprechend wird die Textkonstante C[31] erweitert. Das resultierende Programm $\pi_3'$ zeigt Anhang A.1..

Der zur Verfügung stehende SIMULA-Compiler hat die Eingabelänge 72. Die Ausgabe von $\pi_3$ bzw. $\pi_3'$ 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 $\pi_3$ noch bei $\pi_3'$ der Fall. Anhang A.2. zeigt eine Version $\pi_3''$ von $\pi_3$ , deren Ausgabe in Zeilen a 72 Zeichen unterteilt ist. Dies wird durch einen komplizierten Anweisungsteil erreicht. Die Ausgabe von $\pi_3''$ läßt sich erneut übersetzen. Sie stellt ein lauffähiges SIMULA-Programm dar, das gleich $\pi_3''$ ist.

3.2.7. Ein prozedurgesteuertes Programm $\pi_4$

In 3.2.5. wurde ein selbstreproduzierendes Programm $\pi_3$ , konstruiert, das seinen Text in Teilstrings zerlegt enthielt. Diese Teilstrings brauchten von $\pi_3$ nur noch in der richtigen Reihenfolge ausgedruckt zu werden. In Form von Programm $\pi_4$ 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 $\pi_3$ schreiben wir procedure name;OUTTEXT("text"); in $\pi_4$ , Die Zerlegung des Programmtextes von $\pi_4$ , entspricht dabei der Zerlegung des Programmtextes von $\pi_5$ . Der Algorithmus von $\pi_4$ besteht nur noch aus einer Folge von Prozeduraufrufen. Mit Programm $\pi_4$ 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 $\pi_4$

AA; ist das erste statement des Anweisungsteils von $\pi_4$ . 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 $\pi_4$ 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 $\pi_4$ enthält. Durch Ausführung der Prozedur AB holt die Ausgabe des Programms $\pi_4$ die Ausführung von $\pi_4$ ein.

(3.2.7.1) Bemerkung: Das selbstreproduzierende SIMULA-Program $\pi_4$ benötigt als Daten nur Textkonstanten. Zur Strukturierung verwendet $\pi_4$ neben der Hintereinanderausführung von Anweisungen nur das Prozedurkonzept. Insgesamt gesehen verwendet $\pi_4$ nur Elemente, die die meisten höheren Programmiersprachen zur Verfügung stellen. Daher gesehen müssen dem Programm $\pi_4$ ähnelde selbstreproduzierende Programme in fast allen höheren Programmiersprachen existieren.

3.2.8. Implementierung des Programms $\pi_4$

Für die Implementierung des Programms $\pi_4$ gelten die gleichen Bemerkungen, die zur Implementierung von $\pi_3$ in 3.2.6. gemacht wurden. Aus $\pi_4$ läßt sich mit geringem Aufwand ein lauffähiges selbstreproduzierendes Programm $\pi_4'$ gewinnen, indem die Anweisung

SYSOUT.IMAGE:-BLANKS(200);

in den Anweisungsteil von $\pi_4$ bzw. in die Textkonstante der Prozedur AB engefügt wird.

Aus $\pi_4$ läßt sich wie in 3.2.6. ein selbstreproduzierendes Programm $\pi_4''$ ableiten, dessen Ausgabe so formatiert ist, daß ein lauffähiges Programm entsteht. Erreicht wird dies durch

Einführung der Prozedur
```
procedure Q;OUTIMAGE;
```
Aufspalten der Textkonstanten der Prozedur AB auf die Prozeduren AB,CA,CB,CC,AAA und AAB

Die Ausgabe der zusätzlichen Prozeduren CA bis AAB bewirkt einen vergrößerten Anweisungsteil in $\pi_4''$ .

Anhang A.3. und Anhang A.4. demonstrieren die aus $\pi_4$ resultierenden Programme $\pi_4'$ bzw. $\pi_4''$ .

3.3. Selbstreproduzierende Programme in PASCAL¹⁾

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 $\pi_3$ 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 $\pi_4$ aus 3.2.6. nach PASCAL zu übertragen.

3.3.1. Ein textgesteuertes PASCAL-Programm $\pi_5$

Wir versuchen trotz des Fehlens von Textvariablen in PASCAL, das Programm $\pi_3$ in ein selbstreproduzierendes PASCAL-Programm $\pi_5$ zu übertragen. Dazu gibt es verschiedene Möglichkeiten, von denen zwei genannt sein sollen:

Wir simulieren die in 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 $\pi_5$ 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}$

Der Programmtext $\pi_5$ 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 $\pi_5$ nach der bisher entworfenen Methode enthält noch einige Schwierigkeiten. Z.B.:
- Es müßte eigens eine Ausgabeprozedur für die statements vom Typ <Ausgabe C[I,...]> in $\pi_5$ , enthalten sein.
- Die Zeilen von C sind in der Regel mit blank-Zeichen aufgefüllt. Die Ausgabe dieser blanks ist zu vermeiden.
Insgesamt würde ein durchaus korrektes, aber auch unübersichtliches Programm $\pi_5$ entstehen.
Um die in (i) entstandenen Schwierigkeiten zu vermeiden, speichern wir die Teilstrings von $\pi_5$ nicht in einem, zweidimensionalen character array, sondern wir verwenden die implizite Speicherung mittels Ausgabeprozeduren wie im SIMULA-Programm $\pi_4$ aus 3.2.7.
Der Algorithmus von $\pi_5$ 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 $\pi_5$ durch Alternative (ii) bleibt das Programm überschaubar. Mit

$\left. \begin{eqnarray} ORD(a)&=&193\\ ORD(b)&=&194\\ ORD(c)&=&195\\ ORD(d)&=&196\\ ORD(e)&=&197\\ ORD(f)&=&198\\ ORD(g)&=&199\\ ORD(h)&=&200\\ ORD(i)&=&201\\ ORD(j)&=&202\\ ORD(k)&=&203\\ \end{eqnarray} \right} \text{bezogen auf die zur\\Verf\ddot{u}gung stehende\\PASCAL-Implementierung}$

und der Kodierung

$\begin{eqnarray} \text{\underline{procedure}\ \ A\ } &\longr& a\\ \text{\underline{procedure}\ \ B\ } &\longr& b\\ \text{\underline{procedure}\ \ C\ } &\longr& c\\ \text{\underline{procedure} AA} &\longr& d\\ \text{\underline{procedure} AB} &\longr& e\\ \text{\underline{procedure} AC} &\longr& f\\ \text{\underline{procedure} BA} &\longr& g\\ \text{\underline{procedure} BB} &\longr& h\\ \text{\underline{procedure} BC} &\longr& i\\ \text{\underline{procedure} CA} &\longr& j\\ \text{\underline{procedure} CB} &\longr& k\\ \end{eqnarray}$

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 $\pi_5$

Die Bedeutung der for-Schleife von Programm $\pi_5$ 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 $\pi_5$ ausgegeben. Einfaches Nachvollziehen der Abarbeitung von X bestätigt, daß $\pi_5$ sich, selbst reproduziert (vgl. Verifikation von $\pi_3$ ).

3.3.2. Implementierung des Programms $\pi_5$

$\pi_5$ wird so implementiert, daß die Ausgabe von $\pi_5$ in Zeilen zu höchstens 132 Zeichen formatiert ist. Daher wird zunächst die Prozedur

procedure Q; begin WRITELN end;

in $\pi5$ eingefügt.

Die Prozeduren A und B werden wegen ihrer relativ langen Textkonstanten in mehrere Prozeduren aufgespalten:

$\begin{array}{cc} \begin{array}{ccl} & & A\\ &\nearrow& \\ A& &\\ &\searrow&\\ & & CC \end{array} & \begin{array}{ccl} & & B\\ &\nearrow& \\ B&\rightarrow & AAA\\ &\searrow&\\ & & AAC \end{array} \end{array}$

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

$\begin{array}{ccl} & & CB\\ &\nearrow& \\ CB& &\\ &\searrow&\\ & & AAB \end{array}$

In $\pi_5$ 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 $\pi_5$ notwendig, was die Einführung der Prozedur CCA bewirkt. Der Algorithmus wird entsprechend geändert. Anhang A.5. zeigt das so veränderte Programm $\pi_5$ im einzelnen. Die neuen Prozeduren sind dort wie folgt kodiert:

$\begin{array}{rclcrcl} CC & \longr & l &\ & AAB & \longr & n\\ AAA & \longr & m &\ & CCA & \longr & q\\ AAC & \longr & p &\ & Q & \longr & o\\ \text{mit}\\ ORD(l) & = & 211 &\ & ORD(o) & = & 214\\ ORD(m) & = & 212 &\ & ORD(p) & = & 215\\ ORD(n) & = & 213 &\ & ORD(q) & = & 216\\ \end{array}$

3.3.3. Ein prozedurgesteuertes PASCAL-Prograjam $\pi_6$

Alle in Programm $\pi_4$ aus Abschnitt 3.2.7. verwendeten Sprachelemente finden sich auch in der Programmiersprache PASCAL. Damit läßt sich $\pi_4$ direkt in ein selbstreproduzierendes PASCAL-Programm $\pi_6$ ü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 $\pi_6$

Die Verifikation von $\pi_6$ ergibt sich direkt aus der Verifikation von $\pi_4$ in 3.2.7.

3.3.4. Implementierung des Programms $\pi_6$

Programm $\pi_6$ schreibt seinen Text hintereinander ohne Blockung auf die Ausgabedatei OUTPUT. Das Ergebnis von $\pi_6$ 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 $\pi_6$ 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 $\pi_6$ 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 $\pi_6$ .

3.4. Selbstreproduzierende Programme in SIEMENS-Assembler

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].

(3.4.1) Beispiel:

Das selbstreproduzierende Assembler-Programm PROG1 legt eine Kopie seines Maschinenkodes ab dem 64-ten auf den ersten Befehl von PROG1 folgenden Byte im Arbeitsspeicher an.

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.

(3.4.2.) Beispiel:

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 $2^8$ 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 $2^8-16$ Bytes im Arbeitsspeicher kopiert werden. Entsprechend der Länge des Programmabschnitts muß die Distanzadresse, die die Lage der Kopie bestimmt, gewählt werden.

$\begin{array}{llll} 01 & PROGRAM & CSECT\\ 02 & & BALR & 1,00\\ 03 & & LA & 2,2,(0,0)\\ 04 & & SR & 1,2\\ 05 & & MVC & \begin{array}{cc} \left\langle \text{Distanzadresse\\der kopie} \right\rangle & \left(\left\langle \text{Anzahl der zu\\kopierenden Bytes} \right\rangle, 1\right),0,(1)\\ \end{array}\\ {06\\07\\\vdots\\\vdots\\\vdots} & & \left. {\vdots \\ \vdots \\ \vdots\\ \vdots} \right\} & \text{Der zu kopierende Programmabschnitt\\(maximal 2^8-16 Bytes)}\\ \end{array}\\$

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.

(3.4.3) Beispiel:

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.

(3.4.4) Beispiel:

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.

$\begin{array}{lllll} 01 & PROGRAM & CSECT\\ 02 & & BALR & 1,00\\ 03 & & LA &2,2(0,0)\\ \vdots & & \vdots\\ 06 & & LA & 4, <L\ddot{a}nge des Gesamtabschnitts> (0,0)\\ 07 & & LA & 10,22(0,0)\\ \vdots & & AR & 10,1\\ \vdots & & MVC & <Distanzzadresse der Kopie>(4,1),0(1)\\ \vdots & & \vdots\\ \vdots & & \vdots\\ 12 & & BRP & 10\\ {13\\\vdots\\\vdots\\\vdots\\\vdots} & & \left. {\\\vdots\\\vdots\\\vdots\\\vdots} \right\} & \text{Der zu kopierende Programmabschnitt}\\ \vdots & & END \end{array}$

Abb 3.4.B

Im Gegensatz zu der aus PPOG2 abgeleiteten Methode zur Selbstreproduktion größerer Programmabschnitte lieg keine Begrenzung auf $2^8-16$ Bytes vor.

4. Varianten zur Selbstreproduktion von Programmen

In diesem Kapitel sei S eine beliebige höhere Programmiersprache im üblichen Sinn (vgl. 1.2.).

4.1. Motivation

In Abschnitt 1.2. haben wir eine Definition selbstreproduzierender Programme angegeben. Diese Definition lautete singemäß:

Sei $\pi$ aus S. $\pi$ heißt selbstreproduzierend, wenn $\pi$ 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 $\pi$ aus S:

Die Ausgabe von $\pi$ muß ein syntaktisch korrektes Programm $\pi'$ aus der Programmiersprache S enthalten.
$\pi'$ muß gleich $\pi$ 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 $\pi$ "reproduzierend", dann sind zum Beispiel folgende Möglichkeiten denkbar:

Das Programm $\pi$ gibt das Programm $\pi'$ aus. $\pi'$ seinerseits gibt das Programm $\pi''$ aus, und es gilt $\pi''=\pi$ . $\pi$ und $\pi'$ sind dann sicher für sich nicht selbstreproduzierend. Trotzdem liegt aber ein gewisser Selbstreproduktionsmechanismus mit "Zwischenstufe" vor.
Das Programm $\pi=\pi^0$ gibt das Programm $\pi^1$ aus, $\pi^1$ seinerseits das Programm $\pi^2$ u.s.w.. Allgemein: $\pi^i$ gibt $\pi^{i+1}$ aus, $j\ge0$ . Für alle $i,j\ge0$ gilt $\pi^i\ne\pi^j$ , falls $i\ne j$ .

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. Unendlich reproduzierende Programme

(4.2.1) Definition: Sei $\pi$ ein (syntaktisch korrektes) Programm aus S.

1. Weist $\pi$ keine Eingabe auf, so heißt $\pi$ (streng) reproduzierend, wenn $\pi$ (genau) ein syntaktisch korrektes Programm $\pi'$ aus S ausgibt.
2. Weist $\pi$ Eingabe auf, so heißt $\pi$ (streng) reproduzierend, wenn $\pi$ bei jeder zulässigen Eingabe (genau) ein syntaktisch korrektes Programm $\pi'$ aus S ausgibt.
R(S) bezeichnet die Menge aller reproduzierenden Programme aus S.

(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:

Für Jedes ist das SIMULA-Programm
```
 = 
begin
OUTTEXT("BEGIN INTEGER I;
         I:=k;
         OUTINT(k, <Stelligkeit von k>)
         END")
end
```
reproduzierend, da die Textkonstante, die von ausgegeben wird, ein gültiges SIMULA-Programm darstellt.

Ein analoges Programm läßt sich in PASCAL angeben:

 = 
program T(OUTPUT);
begin
WRITE('PROGRAM T(OUTPUT);
       BEGIN
       WRITE(k)
       END.')
end.

(4.2.4) Definition: Sei $(\pi_i)_{i\in\mathbb{N}_0}=\pi_0,\pi_1,\pi_2,\dots$ eine (unendliche) Folge von Programmen aus der Programmiersprache S. $(\pi_i)_{i\in\mathbb{N}_0}$ heißt Reproduktionsfolge, falls gilt $\pi_j$ reproduziert $\pi_{j+1}$ für alle $j\in\mathbb{N}_0$ .

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 $(\pi_i)_{i\in\mathbb{N}_0}$ eine Reproduktionsfolge aus der Programmiersprache S. Sei $\pi_j,\ j\in\mathbb{N}_0$ , ein Element dieser Folge.

$\pi_j$ heißt unendlich reproduzierend.
Die Teilfolge $(\pi_k)^j_{k\in\mathbb{N}_0}$ von $(\pi_i)_{i\in\mathbb{N}_0}$ mit $\pi_k=\pi_{j+k}$ für alle $k\in\mathbb{N}_0$ heißt die Reproduktionsfolge von $\pi_j$ .
U(S) bezeichnet die Menge aller unendlich reproduzierenden Programme aus S.

$\begin{array}{r} \text{Reproduktionsfolge von \pi_0}\\ \pi_0\longr\dots\longr\pi_{j-1}\longr\pi_j\longr\pi_{j+1}\longr\dots\\ \text{Reproduktionsfolge von \pi_j}\\ \pi_j\longr\pi_{j+1}\longr\dots\\ \end{array}$

Abb.: 4.2.A

(4.2.6) Bemerkung: Jedes selbstreproduzierende Programm $\pi$ ist unendlich reproduzierend. Die Reproduktionsfolge von $\pi$ 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 $\overset\infty\pi_0$ , 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.

$\overset\infty\pi_0$ ist ein unendlich reproduzierendes Programm, in dessen Reproduktionsfolge kein Programm mehrfach auftritt.

Verifikation:

$\overset\infty\pi_0$ entspricht im wesentlichen dem selbstreproduzierenden programm $\pi_6$ aus 3.3.2. Daß $\overset\infty\pi_0$ nicht ebenfalls selbstreproduzierend ist, wird durch Erhöhung der Obergrenze der Laufvariablen I um 1 in der Kopie $\overset\infty\pi_1$ von $\overset\infty\pi_0$ 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 $\overset\infty\pi_0$ sowohl textuell, als auch im Hinblick auf die Bedeutung des Programms, von $\overset\infty\pi_0$ verschieden. Da die Kopie sich lediglich in einer integer-Konstanten von $\overset\infty\pi_0$ unterscheidet, bleibt sie ein lauffähiges reproduzierendes Programm. In gleicher Weise unterscheidet sich die Kopie $\overset\infty\pi_2$ des Programms $\overset\infty\pi_1$ von $\overset\infty\pi_1$ . Die Obergrenze der Laufvariablen I hat in $\overset\infty\pi_2$ einen um 2 größeren Wert als in $\overset\infty\pi_0$ . Insgesamt gilt:

$\overset\infty\pi_0$ ist ein unendlich reproduzierendes Programm. In jedem Element $\overset\infty\pi_j$ , der Reproduktionsfolge von $\overset\infty\pi_0$ hat die Obergrenze der Laufvariablen I den Wert j.

(4.2.9) Bemerkung:

Die Programme 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.
Die Programme der mittels 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 ... end
```
abgeschwä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.
Programm $\overset\infty\pi_0$ 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.
Satz (4.2.7) hat in erster Linie theoretische Bedeutung. In der Praxis gibt es zwar unendlich reproduzierende Programme, aber nicht die entsprechenden Folgen, denn bei endlicher Speicherkapazität lassen sich auch nur endlich viele verschiedene Programme darstellen.

4.2.1. Implementierung des Programms $\overset\infty\pi_0$

Programm $\overset\infty\pi_0$ 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 $\overset\infty\pi_0$ ist es aber wünschenswert, die Ausgabe von $\overset\infty\pi_0$ , nämlich $\overset\infty\pi_1$ , 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 $\overset\infty\pi_0$ .

4.3. Zyklisch selbstreproduzierende Programme

(4.3.1) Definition: Sei $\pi_0$ ein unendlich reproduzierendes Programm aus der Programmiersprache S. Sei $(\pi_i)_{i\in\mathbb{N}_0}$ die Reproduktionsfolge von $\pi_0$ .

Existiert $j\ge1$ mit $\pi_j=\pi_0$ , so heißt $\pi_0$ zyklisch selbstreproduzierend.
Ist $\pi_0$ zyklisch selbstreproduzierend, so heißt das kleinste $j\ge1$ mit $\pi_j=\pi_0$ die Zykluslänge von $\pi_0$ .
Die Menge aller zyklisch selbstreprodusierenden Programme aus S wird mit Z(S) bezeichnet.

$\begin{array}{lcr} \pi_0 & \longr \pi_1 \longr \dots \longr & \pi_{j-1}\\ \uparrow & & \downarrow\\ \hline \end{array}$

Abb.: 4.3.A

(4.3.2) Bemerkung: Jedes Programm $\pi_j$ aus der Reproduktionsfolge eines zyklisch selbstreproduzierenden Programms $\pi_0$ ist zyklisch selbstreproduzierend und hat die gleiche Zykluslänge wie $\pi_0$ .

(4.3.3) Satz: In der Programmiersprache PASCAL existiert für jedes $k\ge1$ ein zyklisch selbstreproduzierendes Programm $\overset{k}\pi$ mit der Zykluslänge k.

Beweis: Das PASCAL-Programm $\overset\infty\pi_0$ aus 4.3. ist unendlich reproduzierend. Man kann aber sehr einfach aus $\overset\infty\pi_0$ ein zyklisch selbstreproduzierendes Programm $\overset{k}\pi_0$ für jedes $k\ge1$ 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 $\overset\infty\pi_0$ unterscheiden sich gerade in dem von Z ausgegebenen Wert. Die geänderte Prozedur Z stellt sicher, daß für jedes $k\ge1$ gilt $\overset{k}\pi_0=\overset{k}\pi_k$ . Mit $\overset{k}\pi_0$ als $\overset{k}\pi$ gilt der Satz.

Wir wollen noch ein Beispiel für zyklisch selbstreproduzierende Programme angeben.

(4.3.4) Beispiel: Das folgende Programm $\pi_0^{\text{zyk}}$ ist, abgesehen von einigen Umbenennungen, eine Abwandlung von $\pi_6$ aus Abschnitt 3.3.2. $\pi_0^{\text{zyk}}$ soll sich erst nach einem Zyklus von N = 9 Schritten selbstreproduzieren. Dies wird dadurch erreicht, daß $\pi_0^{\text{zyk}}$ einige seiner Prozeduren in einer anderen Reihenfolge ausgibt. Das resultierende Programm $\pi_1^{\text{zyk}}$ verfährt mit den Prozeduren in analoger Weise. Erst nach 9 Schritten ist die Ausgangskonstellation der Prozeduren erreicht und $\pi_0^{\text{zyk}}$ liegt wieder vor.

$\pi_0^{\text{zyk}}$ hat gegenüber $\pi_6$ einen erweiterten Vereinbarungsteil durch:

integer I,K;
procedure Z(J : integer); begin WRITE(J) end;

Aufspaltung der den Algorithmus von $\pi_0^{\text{zyk}}$ druckenden Prozedur in zwei Prozeduren BC und CA.

Der Anweisungsteil von $\pi_0^{\text{zyk}}$ muß bewirken, daß sich die direkte Kopie $\pi_1^{\text{zyk}}$ von $\pi_0^{\text{zyk}}$ unterscheidet. Erst nach 9 Schritten darf $\pi_0^{\text{zyk}}$ wieder hergestellt sein. Der Anweisungsteil von $\pi_0^{\text{zyk}}$ muß in allen Kopien "fast" der gleiche, aber doch variabel sein. Daher kann der Anweisungsteil von $\pi_0^{\text{zyk}}$ nicht en bloc kopiert werden. Daraus resultiert auch die unter (ii) angegebene Aufspaltung. Mit den folgenden Prozeduraufrufen wird der Algorithmus von $\pi_0^{\text{zyk}}$ und seiner Kopien angegeben.

$\begin{array}{ccc} \underbrace{\text{BC ; Z((}} & k & \underbrace{\text{+2) mod 9) ; CA}}\\ \uparrow & \uparrow & \uparrow\\ \text{konstant} & | & \text{konstant}\\ \end{array}\\ \text{\ \ \ \ variabel}$

 = 
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 $\pi_0^{\text{zyk}},\pi_1^{\text{zyk}},\dots,\pi_8^{\text{zyk}}$ 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:

$\downarrow$ Startwert k in $\pi_i^{\text{zyk}}$ Startwert k, der von $\pi_i^{\text{zyk}}$ an $\pi_{i+1}^{\text{zyk}}$ weitergegeben wird $\downarrow$ Die Wertefolge, die k in $\pi_i^{\text{zyk}}$ durchläuft
	I=1	I=2	I=3	I=4	I=5	I=6	I=7	I=8	I=9
$\pi_0^{\text{zyk}}$	2	3	4	5	6	7	8	0	1	2
$\pi_1^{\text{zyk}}$	3	4	5	6	7	8	0	1	2	3
$\pi_2^{\text{zyk}}$	4	5	6	7	8	0	1	2	3	4
$\pi_3^{\text{zyk}}$	5	6	7	8	0	1	2	3	4	5
$\pi_4^{\text{zyk}}$	6	7	8	0	1	2	3	4	5	6
$\pi_5^{\text{zyk}}$	7	8	0	1	2	3	4	5	6	7
$\pi_6^{\text{zyk}}$	8	0	1	2	3	4	5	6	7	8
$\pi_7^{\text{zyk}}$	0	1	2	3	4	5	6	7	8	0
$\pi_8^{\text{zyk}}$	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 $\pi_i^{\text{zyk}}$ alle Prozeduren B bis CA ausgibt. Aus der letzten Spalte folgt, daß der Startwert von k in jeder Kopie $\pi_i^{\text{zyk}},\ i=0,\dots,8$ verschieden ist. Ebenfalls aus der letzten Spalte folgt, daß der Startwert von k in der Kopie von $\pi_8^{\text{zyk}}$ gleich dem Startwert von k in $\pi_0^{\text{zyk}}$ ist. Da sich die Anweisungsteile der $\pi_i^{\text{zyk}}$ nur in dem Startwert von k unterscheiden, gilt:

$\pi_9^{\text{zyk}}=\pi_0^{\text{zyk}}$ .

(4.3.5) Bemerkung:

Im wesentlichen gilt auch im Falle des zyklisch selbstreproduzierenden Programms $\pi_0^{\text{zyk}}$ Bemerkung (4.2.9)II. für das unendlich reproduzierende Programm $\overset\infty\pi_0$ . Überhaupt haben unsere Beispielprogramme für unendlich reproduzierende und zyklisch selbstreproduzierende Programme keine Vereinfachung des Selbstreproduktionsmechanismus von Programm $\pi_6$ gebracht.
Satz (4.3.3) läßt sich natürlich analog für die Programmiersprache SIMULA formulieren.

(4.3.6) Beispiel: Als Beispiel für ein zyklisch selbstreproduzierendes SIMULA-Programm sei hier die SIMULA-Version des Programms $\pi_0^{\text{zyk}}$ 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 $\pi_0^{\text{zyk}}$ .

4.3.1. Implementierung des Programms $\overset{k}\pi_0$

Fü die Implementierung von $\overset{k}\pi_0$ gelten die gleichen Bemerkungen wie in Abschnitt 4.2.1. zur Implementierung von Programm $\overset\infty\pi_0$ . Näheres ist aus Anhang A.8. ersichtlich.

4.3.2. Implementierung des Programms $\pi_0^{\text{zyk}}$

Auch für die Implementierung von $\pi_0^{\text{zyk}}$ gelten die Bemerkungen von Abschnitt 4.2.1. Die Textkonstante, die den Algorithmus von $\pi_0^{\text{zyk}}$ darstellt, muß aus Gründen der Formatierung auf noch mehr Prozeduren aufgespalten werden, als dies etwa in $\overset\infty\pi_0$ der Fall ist. Alles Weitere siehe Anhang A.9.

4.4. Unter Wechsel der Programmiersprache sich zyklisch selbstreproduzierende Programme

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 $\pi$ ein Programm $\pi'$ aus. Dabei sind $\pi$ und $\pi'$ Programme aus derselben Programmiersprache S. Wir hätten reproduzierende Programme auch anders definieren können, indem wir $\pi'$ aus einer Programmiersprache $S'\ne S$ 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 $\pi_4$ aus 3.2.6. und dem PASCAL-Programm $\pi_6$ 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 $\pi_{\text{PAS}}$ und ein SIMULA-Programm $\pi_{\text{SIM}}$ mit:

$\pi_{\text{PAS}}\text{ gibt }\pi_{\text{SIM}}\text{ aus }\\ \pi_{\text{SIM}}\text{ gibt }\pi_{\text{PAS}}\text{ aus }\\$

$\pi_{\text{SIM}}$ und $\pi_{\text{PAS}}$ 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.

$\pi_{\text{PAS}}$ gibt das SIMULA-Programm $\pi_{\text{SIM}}$ 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

$\pi_{\text{PAS}}$ und $\pi_{\text{SIM}}$ enthalten jeweils alle Teilstrings - sowohl der Zerlegung von $\pi_{\text{PAS}}$ als auch der Zerlegung von $\pi_{\text{SIM}}$ - in den Prozeduren A bis AC. Da sich die Teilstrings der Zerlegungen von $\pi_{\text{PAS}}$ und $\pi_{\text{SIM}}$ eins zu eins entsprechen, können die Teilstrings alternativ in den Prozeduren abgelegt werden. Jede Prozedur von $\pi_{\text{PAS}}$ 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 $\pi_{\text{PAS}}$ sind gleich ihren Entsprechungen ¦n $\pi_{\text{SIM}}$ . 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 $\pi_{\text{SIM}}$ und $\pi_{\text{PAS}}$ im wesentlichen identisch sind. Aus dem bisher Gesagten und der Tatsache, daß $\pi_{\text{SIM}}$ und $\pi_{\text{PAS}}$ bis auf die alternativen Prozeduren in $\pi_4$ und $\pi_6$ identisch sind, folgt: $\pi_{\text{PAS}}$ reproduziert $\pi_{\text{SIM}}$ und umgekehrt.

4.5. k-fach selbstreproduzierende Programme

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 $\pi$ aus S. (syntakt. korrekt).

1. Weist $\pi$ keine Eingabe auf, so heißt $\pi$ k-fach selbstreproduzierend, falls $\pi$ seinen Programmtext in S k-mal ausgibt.
2. Weist $\pi$ Eingabe auf, so heißt $\pi$ k-fach selbstreproduzierend, falls $\pi$ bei jeder zulässigen Eingabe seinen Programmtext in S k-mal ausgibt.
$\text{SR^k(S)}$ bezeichnet die Menge aller k-fach selbstreproduzierenden Programme aus S.

$\begin{array}{cccccc} & & & & & & \vdots\\ & & & & & \pi & \vdots\\ & & & &\nearrow & \vdots& \vdots\\ & & &\pi & &\text{k-mal}& \vdots\\ & & &\vdots&\searrow & \vdots& \vdots\\ &\nearrow& &\vdots & & \pi & \vdots\\ \pi & & &\text{k-mal} & &\vdots & \vdots\\ &\searrow& &\vdots & & \vdots& \vdots\\ & & &\vdots& & \pi & \vdots\\ & & &\vdots &\nearrow & \vdots& \vdots\\ & & &\pi & &\text{k-mal}& \vdots\\ & & & &\searrow & \vdots& \vdots\\ & & & & & \pi & \vdots\\ \end{array}$

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 $\pi(k)$ .

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 $\pi(k)$ ergibt sich direkt aus der Verifikation von Programm $\pi_6$ aus 3.3.2.. Der Unterschied zwischen $\pi(k)$ und $\pi_6$ 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 $\pi_6$ wird also in $\pi(k)$ gerade k-mal ausgeführt. Dadurch wird $\pi(k)$ zum k-fach reproduzierenden Programm.

(4.5.4) Bemerkung

Jedes k-fach selbstreproduzierende Programm $\pi$ ist natürlich selbstreproduzierend, aber nicht streng selbstreproduzierend. Außerdem ist ein k-fach selbstreproduzierendes Programm zyklisch selbstreproduzierend mit der Zykluslänge 1.
Satz (4.5.2) gilt in analoger Formulierung für die Programmiersprache SIMULA. Zum Beweis übersetzt man das Programm $\pi(k)$ in ein entsprechendes SIMULA-Programm. Das geht ohne Schwierigkeiten, da $\pi(k)$ keine pascalspezifischen Konstruktionen enthält.

4.5.1. Implementierung von $\pi(k)$

Zur Implementierung von $\pi(k)$ sind die gleichen Bemerkungen wie in Abschnitt 3.3.3. zu machen. Anhang A.10. zeigt die Implementierung von $\pi(k)$ mit k=5.

4.6. Reproduktionshierarchie bei Programmen

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

$\pi_{\text{PAS(k)}}$: aus Abschnitt 4.2. ist reproduzierend, aber nicht unendlich reproduzierend.
$\overset\infty\pi_0$: aus Abschnitt 4.2. ist unendlich reproduzierend, aber nicht zyklisch selbstreproduzierend.
$\pi_0^{\text{zyk}}$: aus Abschnitt 4.3. ist zyklisch selbstreproduzierend, aber nicht selbstreproduzierend.
$\pi_6$: aus Abschnitt 3.3.2. ist selbstreproduzierend, aber nicht k-fach selbstreproduzierend für ein k > 1.

Daraus folgt: $\text{SR^k(PASCAL)\overset\sub{\rotate{-90}\dagger}SR(PASCAL)\overset\sub{\rotate{-90}\dagger}Z(PASCAL)\overset\sub{\rotate{-90}\dagger}U(PASCAL)\overset\sub{\rotate{-90}\dagger}R(PASCAL)}$ 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.

5. Selbstreproduzierende Programme mit Zusatzegeinschaften

5.1. Einleitung

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:

"Gibt es in der Programmiersprache S Programme, die mehr leisten als nur Selbstreproduktion?"
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:

"Existiert zu jedem Programm $\pi$ aus S ein selbstreproduzierendes Programm $\tilde\pi$ aus S, das die gleiche Funktion realisiert wie $\pi$ ?"

Ist die letzte Frage für die Programmiersprache S zu bejahen, so ist intuitiv klar, daß ein selbstreproduzierendes Programm $\tilde\pi$ , das eine gegebene Funktion realisiert, umfangreicher und komplizierter ist als ein nicht selbstreproduzierendes Programm $\pi$ , das die gleiche Funktion realisiert. Daher ist es vielleicht einfacher, auf der Suche nach $\tilde\pi$ zunächst ein nicht selbstreproduzierendes Programm $\pi$ zu entwickeln, und dieses anschließend in eine selbstreproduzierende Version $\tilde\pi$ zu transformieren. In diesem Zusammenhang drängt sich die folgende Frage auf:

"Gibt es für eine gegebene Programmiersprache S einen Algorithmus, der zu jedem Programm $\pi$ aus S ein selbstreproduzierendes Programm $\tilde\pi$ aus S liefert, das die gleiche Funktion realisiert wie $\pi$ ?"

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 $\pi$ 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 $\pi$ 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 $A_S$ stammen. Der Inhalt einer Datei kann als Wort aus $A_S^*$ aufgefaßt werden. Dieser Sichtweise entspricht die folgende Definition, die zudem den Fall zuläßt, daß während der Laufzeit von $\pi$ einige Dateien sowohl als Eingabe- als auch als Ausgabedatei benutzt werden.

(5.1.1) Definition: Sei $\pi$ ein Programm aus S mit $p\ge0$ Einund Ausgabedateien, von denen $q,\ 0\le q \le p$ , Dateien als Ausgabedateien benutzt werden. Die von $\pi$ realisierte Funktion $f_\pi$ ist eine partielle Funktion von $(A_S^p)^*$ nach $(A_S^q)^*$ , die jeder Belegung der p Ein- und Ausgabedateien mit Worten aus $(A_S^*)$ genau eine Belegung der q Ausgabedateien mit Worten aus $(A_S^*)$ 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.

$\pi_0$ liest also 10 reelle Zahlen aus der Eingabedatei INPUT ein und gibt deren Quadratwurzeln auf die Ausgabedatei OUTPUT aus. Sei $A_{\text{PAS}}$ die Menge aller Zeichen, die ein PASCAL-Programm verarbeiten kann.

Dann liefert Definition (5.1.1):

$\begin{eqnarray} \pi_0\text{ realisiert die Funktion }f_{\pi_0} &:& A_{\text{PAS}}^* \mapsto A_{\text{PAS}}^*\\ && x \mapsto f_{\pi_0}(x),\ x \in A_{\text{PAS}}^* \end{eqnarray}$

Läßt sich der Anfang von x nicht als Folge von 10 reellen Zahlen interpretieren, so ist $f_{\pi_0}(x)$ undefiniert. Andernfalls ist $f_{\pi_0}(x)$ ein Wort aus $A_{\text{PAS}}^*$ , 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 $f_{\pi_0}$ würde die explizite Einführung von Konvertierungsfunktionen von $\mathbb{R}$ nach $A_{\text{PAS}}^*$ und von $A_{\text{PAS}}^*$ nach $\mathbb{R}$ voraussetzen.

(5.1.3) Bemerkung:

Definition (5.1.1) ist natürlich nicht formal exakt, sondern eher als "praxisnah" zu bezeichnen.
Definition (5.1.1) entspricht im wesentlichen der Definition der von PL(A)-Programmen realisierten Funktion in (2.4.1). Im Falle p und/oder q gleich 0 ist wie unter (2.4.2) zu verfahren.

Aus Definition (5.1.1) folgt, daß ein selbstreproduzierendes Programm $\tilde\pi$ aus S, das ohne zusätzliche Eingabe die "gleiche" Funktion realisiert wie ein anderes, nicht selbstreproduzierendes Programm $\tilde\pi$ aus S, natürlich eine ganz andere Funktion realisiert als $\pi$ , da die Ausgaben von $\pi$ und $\tilde\pi$ verschieden sind. Um diesen verwirrenden Sprachgebrauch zu umgehen, geben wir Definition (5.1.4) an. Zuvor sei jedoch bemerkt, daß man jede Funktion $F\ :\ M^n \mapsto M^m,\ m,n\in\mathbb{N}_0$ , als m-Tupel $F = (F_1,\dots,F_m)$ von Funktionen $F_i\ :\ M^n \mapsto M$ , i=1,...,m, auffassen kann. Dabei ist M eine beliebige Menge. Es gilt: $F(x) = (F_1(x),\dots,F_m(x))$ für alle $x\in M^n$ .

(5.1.4) Definition: Sei $\pi$ ein Programm aus S. Ein Programm $\tilde\pi$ aus S heißt selbstreproduzierende Version von $\pi$ , falls für die von $\pi$ und $\tilde\pi$ realisierten Funktionen $f_\pi\ :\ (A^*_S)^{p_1} \mapsto (A^*_S)^{q_1}$ und $f_{\tilde\pi}\ :\ (A^*_S)^{p_2} \mapsto (A^*_S)^{q_2}$ (i) oder (ii) gilt

$p_1 = p_2$ und $q_1 = q_2$ und $\exist$ genau ein $j\in\{1,\dots,q_2\}$ mit
$(f_{\tilde\pi})_i(\overline{x})=(f_{\pi})_i(\overline{x})\ \ \ \text{f\ddot{u}r }i \ne j$

$(f_{\tilde\pi})_j(\overline{x})=(f_{\pi})_j(\overline{x})\circ\alpha\circ\tilde\pi\circ\beta$ ¹⁾

wobei $\overline{x}\in(A^*_S)^{p_1},\ \alpha,\beta\in A^*_S$
$p_2 = p_1$ und $q_2 = q_1+1$ und
$(f_{\tilde\pi})_i(\overline{x}) = (f_\pi)_i(\overline{x})\ \ \ \text{f\ddot{u}r }i\in\{1,\dots,q_1\}\\ (f_{\tilde\pi})_{q_2}(\overline{x}) = \alpha\circ\tilde\pi\circ\beta\text{, wobei }\overline{x}\in(A^*_S)^{p_1},\ \alpha,\beta\in A^*_S$

Definition (5.1.4) stellt sicher, daß $\tilde\pi$ unabhängig von der Eingabe seinen eigenen Text ausgibt. $\tilde\pi$ hängt seinen Text entweder an ein Ausgabewort, das auch $\pi$ ausgibt (Fall(i)), oder $\tilde\pi$ gibt seinen Text als zusätzliches Wort aus (Fall(ii)).

(5.1.5) Bemerkung: I.a. ist die selbstreproduzierende Version $\tilde\pi$ eines Programms $\pi$ aus S nicht eindeutig.

Mit Hilfe von Definition (5.1.4) sind wir in der Lage, die Fragestellungen (2) und (3) exakter zu formulieren:

"Existiert zu jedem Programm $\pi$ aus einer gegebenen Programmiersprache S eine selbstreproduzierende Version von $\pi$ ?"
"Gibt es für eine gegebene Programmiersprache S einen Algorithmus, der für jedes Programm $\pi$ aus S eine selbstreproduzierende Version $\tilde\pi$ von $\pi$ liefert?"

Wir werden im folgenden die Fragen (1) bis (3) für die Programmiersprachen SIMULA und PASCAL explizit beantworten.

5.2. Selbstreproduktionssatz für die Programmiersprache PASCAL

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 $\tilde\pi_0$ zu dem Programm $\pi_0$ aus Beispiel (5.1.2) an. Wir gehen dabei aus von unserem kürzesten PASCAL-Programm $\pi_6$ aus Abschnitt 3.3.2. und versuchen, $\pi_6$ und $\pi_0$ zu einer selbstreproduzierenden Version $\tilde\pi_0$ zu kombinieren. Zu diesem Zweck vergegenwärtigen wir uns noch einmal das Programm $\pi_6$ . $\pi_6$ 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 $\pi_6$ läßt sich aber durch Aneinanderreihen dieser Teilstrings zusammensetzen. Der erste Teilstring $s_1$ von $\pi_6$ enthält die das Programm einleitenden Phrasen bis zum ersten '. Der letzte, in der Prozedur AB enthaltene Teilstring $s_9$ beinhaltet den kompletten Anweisungsteil von $\pi_6$ . Abbildung 5.2.A verdeutlicht diesen Zusammenhang.

$\begin{array}{ccc} \text{\pi_6 = \\\ }& \fbox{\text{\underline{program} PI6(OUTPUT);\\\underline{procedure} AA \underline{begin} WRITE('}} & \text{= s_1\\\ \ \ s_1 '')\underline{end}} \end{array}\\ \begin{array}{cclc} \text{\underline{procedure}} & C; & \text{\underline{begin}} \dots\dots\dots\dots\dots\dots & \text{\underline{end};}\\ & \vdots& & \vdots\\ & \vdots& & \vdots\\ & \vdots& & \vdots\\ \text{\underline{procedure}} & BC; & \text{\underline{begin}} \dots\dots\dots\dots\dots\dots & \text{\underline{end};}\\ \text{\underline{procedure}} & AB; & \text{\underline{begin} WRITE(' s_9 ')} & \text{\underline{end};}\\ \end{array}\\ \fbox{ \text{\underline{begin}\\ AA;AA;AC;B;\\ AB;WRITELN\\ \underline{end\\ end.} }} = s_9$

Abb.: 5.2.A

Idee: Wir integrieren den Programmkopf von $\pi_0$

	program X(INPUT,OUTPUT);
	var I : integer;
	    Y : real;

in den String $s_1$ und den Anweisungsteil von $\pi_0$

	for I:=1 to 10 do
	begin READ(Y); WRITELN(SQRT(Y)) end;

in den String $s_9$ .

Wir erhalten die Teilstrings $s_1'$ und $s_9'$ 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 $s_1$ und $s_9$ durch $s_1'$ bzw. $s_9'$ in Programm $\pi_6$ wieder zu einem syntaktisch korrekten selbstreproduzierenden Programm $\tilde\pi_0$ führt. $\tilde\pi_0$ führt zuerst die for-Schleife von $\pi_0$ aus und reproduziert sich anschließend selbst. Es gilt für die von $\tilde\pi_0$ realisierte Funktion $f_{\tilde\pi_0}\ :\ A^*_{\text{PAS}} \mapsto A^*_{\text{PAS}}$ :
$f_{\tilde\pi_0}(x) = f_{\pi_0}(x)\circ\pi_0$ für alle $x\in A^*_{\text{PAS}}$

Damit genügt $\tilde\pi_0$ Definition (5.1.4)(i), und es gilt: $\tilde\pi_0$ ist eine selbstreproduzierende Version von $\pi_0$ . Anhang A.11. zeigt Programm $\pi_6'$ in implementierter Form, die aus der implementierten Form von Programm $\pi_6$ abgeleitet ist.

Die Konstruktion von $\tilde\pi_0$ aus den beiden Programmen $\pi_6$ und $\pi_0$ zeigte keine Aspekte, die darauf hindeuten, daß diese Konstruktion von irgendwelchen speziellen Eigenschaften von $\pi_0$ 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 $G_{\text{PAS}}$ 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 $\nu$ ein nichtterminales Zeichen aus $G_{\text{PAS}}$ und $\pi$ ein gültiges PASCAL-Programm, so bezeichnen wir mit $\nu\pi$ den Teilstring des Programmtextes $\pi$ , der sich aus dem nichtterminalen Zeichen $\nu$ ableiten läßt. Kommt das Zeichen $\nu$ im Ableitungsbaum von $\pi$ nicht vor, so identifizieren wir $\nu\pi$ mit dem leeren Wort.

Der Teilstring $\nu\pi$ ist natürlich abhängig von der Position von $\nu$ im Ableitungsbaum von $\pi$ . Dieser Umstand wird für uns aber keine Bedeutung erlangen.

Durch die hier eingeführte Schreibweise lassen sich aus den Produktionen der Grammatik $G_{\text{PAS}}$ Gleichungen gewinnen.

Beispiel:

$G_{\text{PAS}}$ enthält die Produktion

<program>::=<program heading><block>

Für jedes gültige PASCAL-Programm $\pi$ gilt damit die Gleichung

 = <program> 
   = <program heading>  <block>

Bei der Kombination von Programm $\pi_6$ und Programm $\pi_0$ zu $\tilde\pi_0$ waren keine Konflikte mit Bezeichnern aufgetreten. Das heißt, sämtliche Prozedurnamen von $\pi_6$ waren von den Variablennamen aus $\pi_0$ verschieden. Dies kann i.a. jedoch nicht vorausgesetzt werden. Um den Test, ob in einem PASCAL-Programm $\pi$ Bezeichner auftreten, die mit einem Prozedurnamen aus $\pi_6$ identisch sind, zu vereinfachen, normieren wir die Prozedurnamen aus $\pi_6$ , indem wir festlegen, daß jeder Prozedurname aus $\pi_6$ nur mit Hilfe des Buchstaben A gebildet werden darf. Alle Prozedurnamen aus $\pi_6$ sind also Elemente aus $\{A\}^+$ 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 $\{A\}^+$ 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:

Sei $\underbrace{A \dots A}\\\text{k-mal}$ ein Element aus $\{A\}^+$ , dann schreiben wir statt dessen kürzer $A^k$ .
Wir kürzen r aufeinanderfolgende Aufrufe $\underbrace{A^j; \dots ;A^j;}\\\text{r-mal}$ der Prozedur $A^j$ ab durch $(A^j;)^r$ .

Unter Benutzung von Vereinbarung (5.2.3) präsentiert sich $\pi_6$ 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 $\pi$ existiert eine selbstreproduzierende Version $\tilde\pi$ .

Beweis

Der Beweis gliedert sich in zwei Teile. In Teil A wird eine Konstruktion für ein Programm $\tilde\pi$ für beliebiges $\pi$ angegeben. In Teil B wird gezeigt, daß das so konstruierte $\tilde\pi$ eine selbstreproduzierende Version von $\pi$ ist. Der Beweis setzt die Grammatik $G_{\text{PAS}}$ voraus.

Sei nun $\pi$ ein beliebiges gültiges PASCAL-Programm. Enthält $\pi$ Bezeichner aus $\{A\}^+$ , so werden diese Bezeichner durch andere Bezeichner ersetzt, die nicht aus $\{A\}^+$ sind. Das resultierende Programm ist textuell von $\pi$ verschieden und wird mit $\pi'$ bezeichnet. Enthält $\pi$ keine Bezeichner aus $\{A\}^+$ , ¹⁾ so wird $\pi':=\pi$ gesetzt.

Teil A

Nach $G_{\text{PAS}}$ hat $\pi'$ den folgenden Aufbau:

 = <programm heading>  <block> ,

wobei <program heading> $\pi'$ und <block> $\pi'$ ungleich dem leeren Wort sind. Entsprechendes gilt für $\pi_6$ und das zu konstruierende $\tilde\pi$ :

	 = <program heading>  <block> 
	 = <program heading>  <block>

Wir erhalten das Programm $\tilde\pi$ , indem wir

<program heading> aus <program heading> 
                    und <program heading>

bzw.

<block>  aus <block> 
           und <block>

kombinieren.

Kombination von <program heading> $\tilde\pi$
Aus $G_{\text{PAS}}$ folgt, daß für <program heading> $\pi'$ die allgemeine Beziehung
```
<program heading) = program ;
```
wobei $\mu,\mu_1,\dots,\mu_r,r\ge0$ PASCAL-gültige Bezeichner sind, gilt. $\mu$ stellt den Namen des Programms dar, die $\mu_i$ bezeichnen die von $\pi'$ benutzten Dateien. Benutzt $\pi'$ die Standarddatei OUTPUT, so sei o.B.d.A. $\mu_r$ = OUTPUT.

Für $\pi_6$ gilt:
```
<program heading> = program Pl6(OUTPUT);
```
Damit kombinieren wir:
```
<program heading> = program P(,OUTPUT);
```
mit $k = \left\{r-1,\text{ falls \mu_r = OUTPUT}\\r\text{ sonst.}\right.$

Kombination von <block> $\tilde\pi$

Aus $G_{\text{PAS}}$ folgt, daß für <block> $\pi'$ 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> $\pi'$ können leer sein. Die Programme $\pi'$ und $\tilde\pi$ haben einen entsprechenden Aufbau. Da <label declaration part> $\pi_6$ ,...,<variable declaration part> $\pi_6$ 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 $\pi'$ das Zeichen ' ein- oder mehrmals, so muß der Text $\pi'$ 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 $\pi'$ wie folgt darstellen:

 = <program heading)  S  begin  T  end.

1. Fall: S ist ungleich dem leeren Wort (d.h. $\pi$ hat einen nichtleeren Vereinbarungsteil)

Zerlegung von S in eine Folge von $n\ge1$ Teilstrings $S_i$ mit

$s_i = \ ' \text{ oder } s_i \not\ni \ ',\ i\in[n]$
$s_i \not\ni \ ' \Rightarrow s_{i+1} = \ ',\ i\in[n-1]$
$s_1\circ s_2\circ\dots\circ s_n = S$

Sei p die Anzahl der Teilstrings von S, die ungleich ' sind. Es gilt: $1 \le p \lt n$

Für jeden Teilstring ungleich ' , mit Ausnahme von $s_1$ , wird eine Prozedur generiert:

procedure ;begin WRITE('') end;   j = 2,...,p

wobei $s_i$ der j-te Teilstring ungleich ' ist.

Sei AP die Menge der Namen der generierten Prozeduren. Dann gilt:
$AP=\{A^{7+1},A^{7+2},\dots,A^{7+p-1}\}$ .

Sei $\cal{J}=\{s_1,\dots,s_n\}$ die Menge der Teilstrings der Zerlegung von S.

Einführung der Funktionen $\cal{G}$ und $\tilde{\cal{G}}$ :

$\begin{array}{cccl} \cal{G}:& [p] & \mapsto & \cal{J}\\ & j & \mapsto & \text{s_k, mit s_k ist der j-te Teilstring \ne '}\\ \tilde{\cal{G}}:&[n]&\mapsto&AP\cup\{A^5\}\\ & j & \mapsto & {\left\{ \perp\text{, falls j=1}\\ A^{7+i-1}\text{, falls s_j der i-te Teilstring von S\ne\ ' ist}\\ A^5\text{, falls s_j=\ '} \right.} \end{array}$ ¹⁾

(Zur Erinnerung: $A^5$ ist die Prozedur, die in $\pi_6$ 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:
$\cal{G}(1) = s_1\text{ und }\cal{G}(p) = s_n$

Der String T wird in einen String T' transformiert, indem T mit dem Zeichen ; konkateniert wird: T' := T; T' wird analog zu S in $m\ge1$ Teilstrings $t_i$ zerlegt. Für die Zerlegung von T' gilt:

$t_i=\ '\text{ oder } t_i\not\ni\ ',\ i\in[m]$
$t_i\not\ni\ '\Rightarrow t_{i+1}=\ '\ i\in[m-1]$
$t_1\circ t_2\circ\dots\circ t_m=T'$

Sei q die Anzahl der Teilstrings von T', die ungleich ' sind. Es gilt: $1\le q \lt m$ . Für jeden Teilstring $t_i$ ungleich ', mit Ausnahme von $t_m$ , wird eine Prozedur generiert:

procedure ; begin WRITE('') end;

für j=2,...,q-1, wobei $t_i$ der j-te Teilstring $\ne$ ' ist bzw.

procedure ;begin WRITE('BEGIN ') end;

für j=1.

Dabei ist $t_j$ der j-te Teilstring von T' ungleich '. Entsprechend $AP,\cal{J},\cal{G}$ und $\tilde\cal{G}$ werden $AQ,\cal{T},\tau$ und $\tilde\tau$ definiert:

$\begin{array}{clcl} AQ &:=& & \{A^{7+p},\dots,A^{7+p+q-1}\} \\ \cal{T} &:=& & \{t1,\dots,t_m\}\\ \tau &: &[q]& \longr \{t_i\}_{i\in[n]}\\ & & j & \longr t_k\text{, mit t_k ist der j-te Teilstring von T' \ne '}\\ \tilde\tau &:&[m]&\longr AQ\cup\{A^5\}\\ & & j & \longr {\left\{ \perp\text{, falls j = q}\\ A^{7+p+i-1}\text{, falls t_j der i-te Teilstring \ne ' ist}\\ A^5\text{, falls t_j = '} \right.} \end{array}$

Das erste Zeichen nach dem einleitenden begin von <statement part> $\pi'$ kann nicht gleich ' sein. Daraus ergibt sich nach Definition von $T'\ :\ \tau(1)=t_1$
Das letzte Zeichen von T' ist ; . Daraus folgt: $\tau(q)=t_m$

Es ist nun möglich, die beiden noch fehlenden Programmteile von $\tilde\pi$ , 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.

$\sout[+1]\otimes$ steht dabei als Abkürzung für die Aufruffolge der Prozeduren A bis $A^{p+q+2}$ , die die Ausgabe von $\tilde\pi$ 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 $\pi$ ist leer)

Dieser Fall ist ein Spezialfall von Fall 1. Wir erhalten das resultierende Programm aus dem in Fall 1 angegebenen Programm $\tilde\pi$ durch Streichung der den String S betreffenden Konstruktion. Im Einzelnen

Streichung der Prozeduren $A^{7+1}$ bis $A^{7+p-1}$

Änderung der Prozedur A in

procedure A;begin WRITE('PROGRAM P(,OUTPUT);')
            end;

Streichung der Programmzeile mit dem Inhalt
$\tilde{\cal{G}}(2);\dots;\tilde{\cal{G}}(n);$
Streichung der Programmzeilen
$k_{7+1}$ bis $k_{7+p-1}$

Teil B

1. Fall: S ist ungleich dem leeren Wort.

Die Konstruktion in Teil A liefert ein syntaktisch korrektes PASCAL-Programm $\tilde\pi$ . Es bleibt zu zeigen, daß $\tilde\pi$ eine selbsreproduzierende Version von $\pi$ ist.

$\pi$ realisiert eine Funktion
$f_\pi\ :\ (A^*_{\text{PAS}})^r \longr (A^*_{\text{PAS}})^u\text{ mit }o\le u\le r$ .

Der Vereinbarungsteil von $\pi$ wird in Form des Textes $S = s_1\ \dots\ s_n$ in das Programm $\pi$ unverändert aufgenommen. Im Anweisungsteil von $\tilde\pi$ wird der in der Form $T'=t_1\ \dots\ t_m$ übernommene Anweisungsteil von $\pi$ 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 $\tilde\pi$ nur endlich viele Prozeduraufrufe aufweist, wird insgesamt ein endlicher Text, also ein Wort y aus $A^*_{\text{PAS}}$ , auf die Datei OUTPUT ausgegeben. Die Aufrufe dieser Ausgabeprozeduren erfolgen jedoch erst, nachdem der Anweisungsteil T' abgearbeitet worden ist. $\tilde\pi$ 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}$
falls $\mu_r$ = OUTPUT, d.h. $\tilde\pi$ gibt y auf eine Ausgabedatei aus, die auch $\pi$ 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}}$
falls $\mu_r$ = OUTPUT, d.h. $\tilde\pi$ gibt y auf die Datei OUTPUT aus, die von $\pi$ nicht als Ausgabedatei benutzt wird.

$\tilde\pi$ erfüllt also genau dann Definition (5.1.4), wenn der Text $\tilde\pi$ Teilstring von y ist.

Es gilt aber sogar $y=\tilde\pi$ , denn:
Nach Abarbeitung von $t_1\ \dots\ t_m$ gibt $\tilde\pi$ zunächst durch Aufruf der Prozedur A seinen eigenen Programmkopf <programm heading> $\tilde\pi$ und $s_1$ aus. Die nächsten Prozeduraufrufe

    ... bis ...  erledigen die Ausgabe von
       ... bis ... .

Die Prozeduraufrufe der Zeilen $k_{7+1}$ bis $k_{7+p+q-2}$ und $k_1$ bis $k_7$ bewirken die Ausgabe der Prozedurvereinbarungen von $A^{7+1}$ bis $A^{7+p+q-2}$ bzw. von A bis $A^7$ . Es fehlt nur noch de Ausgabe von <statement part> $\tilde\pi$ . Diese Ausgabe wird jedoch durch die Folge $\tilde\tau(1);\dots;\tilde\tau(m-1);A^7;$ bewirkt. Das nachfolgende WRITELN leert nur den Puffer der Datei OUTPUT.

Es gilt also $y=\tilde\pi$ . Damit ist $\tilde\pi$ selbstreproduzierende Version von $\pi$ .

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 $\tilde\pi$ selbstreproduzierende Version von $\pi$ 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 $\pi$ eine selbstreproduzierende Version $\tilde\pi$ findet.

(5.2.5) Algorithmus:

Eingabe: Das PASCAL-Programm $\pi$ .
1. Schritt: Test, ob keiner der in $\pi$ vorkommenden Bezeichner aus $\{A\}^+$ ist. Gegebenenfalls Umbenennung vornehmen.
2. Schritt: Formulierung von <program heading> $\tilde\pi$ aus <program heading> $\pi$ unter Verwendung der Standarddatei OUTPUT.
3. Schritt: Zerlegung von
```
S = <label declaration part>
    <constant declaration part>
    <type definition part>
    <variable declaration part>
```
in Teilstrings und Ermittlung der Anzahl p der Teilstrings ungleich ' . Anschließend Formulierung der p-1 Prozeduren bis und Aufstellung der Wertetabellen von und .
4. Schritt: ist das letzte Zeichen von T=(<statement part> $\pi$ ohne klammerndes begin end.) gleich ; , so wird T':=T gesetzt, andernfalls T':=T;.
Zerlegung von T' in $t_1\ \dots\ t_m$ und Ermittlung der Zahl q. Anschließend Formulierung der q-1 Prozeduren $A^{7+p}$ bis $A^{7+p+q-2}$ und Aufstellung der Wertetabellen von $\tau$ und $\tilde\tau$ .
5. Schritt: Einsetzen der erhaltenen Funktionswerte, Prozedurenund Teilstrings $s_1,\dots,s_n,t_1,\dots,t_m$ in das im Beweis angegebene Programmschema.
Aufwand: Der Algorithmus verhält sich linear zur Länge $l(\pi)$ des Programms $\pi$ .

(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):

1. Schritt: $\pi$ enthält keinen Bezeichnen aus $\{A\}^+$ . Es sind also keine Umbenennungen nötig.
2. Schritt: <program heading> wird auf
```
program CONVERT(OUTPUT);
```
gesetzt.

3. Schritt:

S =  mit
 = const ADDIN=32;MULBY=1.8;LOW=0;HIHG=39;
     SEPARATOR=
 = '
 = ----------
 = '
 = ;var DEGREE:LOW..HIGH;

Es gilt n=5, p=3
Die resultierenden Prozeduren sind:

procedure ;begin WRITE('__________') end;
procedure ;begin WRITE(';VAR DEGREE:L0W..
    HIGH;') end;

Wertetabellen von $\calG$ und $\tilde\calG$ :
$\begin{align} \calG(1) = s_1 & \tilde\calG(1) = \perp\\ \calG(2) = s_3 & \tilde\calG(2) = A^5\\ \calG(3) = s_5 & \tilde\calG(3) = A^8\\ & \tilde\calG(4) = A^5\\ & \tilde\calG(5) = A^9\\ \end{align}$

4. Schritt

T= mit
 = 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);

Es gilt: m=9, q=5
Die resultierenden Prozeduren sind:

    
procedure ;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;

Wertetabellen von $\tau$ und $\tilde\tau$ :
$\begin{array}{lll} \tau(1)=t_1 & \tilde\tau(1)=A^{10} & \tilde\tau(6)=A^5 \\ \tau(2)=t_3 & \tilde\tau(1)=A^5 & \tilde\tau(7)=A^{13} \\ \tau(3)=t_5 & \tilde\tau(1)=A^{11} & \tilde\tau(8)=A^5 \\ \tau(4)=t_7 & \tilde\tau(1)=A^5 & \tilde\tau(9)=\perp \\ \tau(5)=t_9 & \tilde\tau(1)=A^{12} & \\ \end{array}$

5. Schritt:
```
 =
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 $\tilde\pi$ für jedes gültige PASCAL-Programm $\pi$ und gibt auch eine Konstruktion für ein syntaktisch richtiges $\tilde\pi$ an, jedoch garantiert die syntaktische Korrektheit noch, nicht die Realisierbarkeit von $\tilde\pi$ auf einer konkreten Rechenmaschine.

Die Implementierung eines von Algorithmus (5.2.5) gelieferten Programms $\tilde\pi$ kann zu folgenden Schwierigkeiten führen:
1. Der längste Prozedurname von $\tilde\pi$ ist $A^{7+p+q-2}$ . $A^{7+p+q-2}$ ist p+q+5 Zeichen lang. Jedes dieser Zeichen ist signifikant, da auch, der Prozedurname $A^{7+p+q-3}$ mit der Länge p+q+4 in $\tilde\pi$ 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.
2. Die Länge der durch (5.2.5) entstehenden Textkonstanten in den Prozeduren $A^j,\ j\in[p+q-2]$ , ist für die Gesamtheit aller PASCAL-Programme $\tilde\pi$ 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.
6. Schritt: Sei g die Anzahl der signifikanten Zeichen von Bezeichnern bei dem vorliegenden PASCAL-Compiler. Sei a:=7+p+q-2=p+q+5 die Länge des Prozedurnamen $A^{p+q+5}$ . a ist gleichzeitig die Anzahl der Prozedurnamen vom Typ $A^j,\ j\in[a]$ . Dann wähle manzwei natürliche Zahlen $c\le26$ und $b\le g$ mit
$(1)\hspace{100} \sum_{k=1}^b c^k \ge a$
Nun können die Prozedurnamen $A^1$ bis $A^{7+p+q-2}$ 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:
$\left. \begin{eqnarray} \text{\underline{procedure}} &\dots&;\text{\underline{begin} WRITE ('B') \underline{end};}\\ \text{\underline{procedure}} &\dots&;\text{\underline{begin} WRITE ('C') \underline{end};}\\ &\vdots&\\ &\vdots&\\ \end{eqnarray} \right\}{c-1}$

Für diese Prozeduren werden aber auch Namen benötigt. Daher müssen die Zahlen c und b auch die Relation
$(1')\hspace{100}\sum_{k=1}^b c^k \ge a+c-1$ erfüllen.
7. Schritt: Sei d die Eingabepufferiänge des zur Verfügung stehenden PASCAL-Compilers. Seien $v_i,\ i\in[p+q-2]$ , die Textkonstanten der Prozeduren $A^i$ (diese Prozeduren sind möglicherweise in Schritt 6 bereits umbenannt worden). Für jedes $i\in[p+q-2]$ muß die folgende Berechnung ausgeführt werden:
Ist $\text{l(WRITE(\'v_i\'))\le d}$ ¹⁾, so bleibt $A^i$ unverändert. Andernfalls wird $v_i$ in $k_i$ Teilstrings $v_{¦j}$ zerlegt mit $\text{l(WRITE(\'v_{ij}\'))\le d,\ \forall j\in[k_i]}$ . Dabei sei $k_i$ minimal gewählt.

Die Prozedur $A^i$ wird durch $k_i$ neue Prozeduren ersetzt:
$\begin{array}{lclc} \text{\underline{procedure}}& \dots& ;\text{\underline{begin} WRITE(\'v_{i1}\')}& \text{\underline{end};}\\ &\vdots& & \vdots\\ &\vdots& & \vdots\\ \text{\underline{procedure}}& \dots& ;\text{\underline{begin} WRITE(\'v_{ik_i}\')}& \text{\underline{end};} \end{array}$

Entsprechend der neu eingeführten Prozeduren wird die Aufruffoige der Prozeduren, die die Ausgabe von $\tilde\pi$ 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 $A^7$ , die den Ausgabealgoritnmus für $\tilde\pi$ enthält, auf mehrere neue Prozeduren aufgespalten. Neue Prozeduren bedingen einen längeren Ausgabealgorithmus, wenn $\tilde\pi$ 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 $\tilde\pi$ formatiert werden soll.

(5.2.7) Beispiel: Das in Beispiel (5.2.6) enthaltene Programm $\tilde\pi$ soll implementiert werden.

6. Schritt: Programm 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 $A^i,\ i\in[13]$ , 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
```
7. Schritt: Die Länge jeder Programmzeile sei auf 132 Zeichen beschränkt. Damit braucht nur die Textkonstante der Prozedur AC auf mehrere Prozeduren aufgespalten zu werden. Der für diese Prozeduren notwendige Verwaltungsaufwand im Algorithmus von $\tilde\pi$ 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 $\tilde\pi$ . Zur Formatierung der Ausgabe wurde in das Programm die aus 3.3.4. bekannte Prozedur Q eingefügt.

5.3. Selbstreproduktionssatz für die Programmiersprache SIMULA

Die in den Kapiteln 3 und 4 vorgestellten Beispielprogramme in SIMULA und PASCAL entsprechen sich weitgehend. Zum selbstreproduzierenden PASCAL-Programm $\pi_6$ aus (3.3.2.) existiert ein nahezu identisches SIMULA-Programm $\pi_4$ in 3.2.7. . Da der Beweis von Satz (5.2.4) in wesentlichen auf der Existenz von $\pi_6$ 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 $\tilde\pi$ eines beliebigen SIMULA-Programms $\pi$ erfolgen. Trotz der Entsprechung von $\pi_4$ und $\pi_6$ muß diese Konstruktion explizit angegeben werden, da SIMULA im Gegensatz zu PASCAL eine blockorientierte Programmiersprache ist. Das aus Teil A resultierende Programm $\tilde\pi$ wird aber weitgehend dem in Teil A von dem Beweis zu (5.2.4) konstruierten Programm entsprechen. Zum Nachweis, daß $\tilde\pi$ selbstreproduzierende Version von $\pi$ 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 $G_{\text{SIM}}$ bezeichnet. Für $G_{\text{SIM}}$ übernehmen wir die Vereinbarung (5.2.2). Außerdem übernehmen wir Vereinbarung (5.2.3) für die Prozedurnamen von $\pi_4$ . Damit präsentiert sich $\pi_4$ , 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 $\pi$ existiert eine selbstreproduzierende Version $\tilde\pi$ .

Beweis

Teil A

Das Programm $\pi_4$ hat laut Grammatik $G_{\text{SIM}}$ den folgenden Aufbau:

   = begin <Vereinbarung> -Folge 
              <Anweisung> -Folge  end

Sei $\pi$ ein beliebiges SIMULA-Programm. Dann hat $\pi$ 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. $\pi_4$ ).

Besteht $\pi$ nur aus

begin <Anweisung> -Folge end,

so nennt man $\pi$ eine Verbundanweisung. Andernfalls ist $\pi$ ein Block. Sowohl Verbundanweisungen als auch Blöcke sind an jeder Stelle von <Anweisung> -Folge $\pi_4$ zulässig, an der eine Anweisung zulässig ist. Dies wird im folgenden ausgenutzt.

Kombination von $\tilde\pi$ aus $\pi_4$ , und $\pi$

Ist <Klassenbezeichnung> $\pi$ nicht leer, so ist zunächst zu testen, ob <Klassenbezeichnung> $\pi$ aus $\{A\}^+$ ist. Ist dies der Fall, so wird <Klassenbezeichnung> $\pi$ umbenannt. Es resultiert das Programm $\pi'$ , das die gleiche Funktion realisiert wie $\pi$ . Andernfalls wird $\pi':=\pi$ gesetzt. Wegen des Konzepts der lokalen Gültigkeit von Bezeichnern ist eine Umbenennung der in - falls vorhanden - <Vereinbarung> -Folge $\pi$ und <Anweisung> -Folge $\pi$ vorkommenden Beseichner auf jeden Fall nicht nötig.

$\begin{array}{ll} \tilde\pi = & \text{\underline{procedure}} A; \dots ;\\ & \text{(zus\ddot{a}tzliche Vereinbarungen)}\\ & { \left. \begin{array}{lcl} \text{\underline{procedure}}& A^2; & \dots;\\ &\vdots& \\ &\vdots& \\ \text{\underline{procedure}}& A^7; & \dots;\\ \end{array} \right\} {\longl \{ \text{mit ge\ddot{a}nderter\\Prozedur A^7 aus \pi_4} } }\\ & \pi';\\ & \text{(zus\ddot{a}tzliche Anweisungen)}\\ & \text{<Anweisung> -Folge \pi_4}\\ & \text{\underline{end}} \end{eqnarray}$

Es brauchen nur noch die Programmteile

    (zusätzliche Vereinbarungen)
und (zusätzliche Anweisungen)

realisiert zu werden.

Sei T gleich $\pi'$ mit angefügtem ; . Also $T=\pi';$ . Der String T wird analog zum String T' aus dem Beweis zu (5.2.4) in eine Folge von $m\ge1$ Teilstrings $t_i$ zerlegt. Für diese Zerlegung von T gilt:

$t_i=\quot\text{ oder }t_i\not\ni\quot\ ,\ \ i\in[m]$
$t_i\not\ni\quot\ \Rightarrow t_{i+1}=\quot\ ,\ \ i\in[m-1]$
$t_1\circ t_2\circ\dots\circ t_m=T$

Sei q die Anzahl der Teilstrings $t_j$ von T, die ungleich " sind. Es gilt: $1\le q \lt m$ .
Für jeden Teilstring $t_j$ ungleich ", mit Ausnahme von $t_m$ , wird eine Prozedur generiert:

procedure ;OUTTEXT("");

wobei $t_i$ der j-te Teilstring von T ungleich " ist.

Die Menge der erzeugten Prozedurnamen ist $AQ=\{A^{7+1},\dots,A^{7+q-1}\}$ . Sei $\calT=\{t_1,\dots,t_m\}$ . Wie im Beweis zu (5.2.4) werden die Funktionen $\tau$ und $\tilde\tau$ 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}$

$t_1$ ist ungleich ", da $\pi$ nicht mit " anfangen kann. Da das letzte Zeichen von T gleich ; ist, ist auch $t_m=t_q$ ungleich ". $t_m$ wird in die Prozedur $A^7$ integriert.

Der Programmteil (zusätzliche Vereinbarungen) besteht aus den q-1 Prozedurvereinbarungen von $A^{7+1}$ bis $A^{7+q-1}$ . Der Programmteil (zusätzliche Anweisungen) besteht aus der Folge von Prozeduraufrufen, die nötig sind, die q-1 zusätzlichen Prozedurvereinbarungen auszugeben. Die Prozedur $A^7$ 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 $\tilde\pi$ in Teil A führt zu einem syntaktisch korrekten SIMULA-Programm. Wegen der sehr engen Entsprechung von den SIMULA-Programm $\pi_4$ und dem PASCAL-Programm $\pi_6$ entspricht $\tilde\pi$ dem im Beweis von (5.2.4) erzeugten PASCAL-Programm weitgehend. Zum Nachweis, daß $\tilde\pi$ wirklich selbstreproduzierende Version von $\pi$ 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 $\pi$ eine selbstreproduzierende Version $\tilde\pi$ angibt.

(5.3.2) Algorithmus:

Eingabe: Das SIMULA-Programm $\pi$ .
1. Schritt: Test, ob <Klassenbezeichnung> $\pi$ - falls überhaupt vorhanden - ein Bezeichner aus $\{A\}^+$ ist. Gegebenenfalls Umbenennung vornehmen.
2. Schritt: Zerlegung von $T:=\pi;$ in Teilstrings $t_1,\dots,t_m$ und Ermittlung der Anzahl q der Teilstrings $t_j$ ungleich ".
Anschließend Formulierung der q-1 Prozeduren $A^{7+1}$ bis $A^{7+q-1}$ und Aufstellung der Wertetabellen von $\tau$ und $\tilde\tau$ .
3. Schritt: Einsetzen der erhaltenen Prozeduren, der Funktionswerte und des Programms $\pi$ in das im Beweis angegebene Programmschema.
Aufwand: Der Aufwand des Algorithmus verhält sich linear zur Länge $l(\pi)$ des Programms $\pi$ .

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

Textkonstanten und
Prozedurkonzept

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.

6. Selbstreproduktion bei loop-Programmen

6.1. Einleitung

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 $\calP$ bezeichnet. Schränkt man die in PL(A) zur Verfügung stehenden Grundanweisungen und Kontrollstrukturen etwa auf
$\begin{array}{ll} \gamma_1,\gamma_2,\gamma_3,\gamma_5 \overline{\ \ \ \ } & \chi_1\ :\ P;Q\\ & \chi_2\ :\ \text{\underline{if} p \underline{then goto} L} \end{array}$
oder auf
$\begin{array}{ll} \gamma_1,\gamma_2,\gamma_3,\gamma_5 \overline{\ \ \ \ } & \chi_1\ :\ P;Q\\ & \chi_2\ :\ \text{\underline{if} p \underline{then} P \underline{else} Q \underline{fi}}\\ & \chi_4\ :\ \text{\underline{while} X=\varepsilon \underline{do} P \underline{od}} \end{array}$
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 $\calP$ 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
$\begin{array}{ll} \gamma_1,\gamma_2,\gamma_3,\gamma_4\overline{\ \ \ \ } & \chi_1\ :\ P;Q\\ & \begin{array}{llllcl} \chi_5\ :\ \text{\underline{loop} X} &\text{\underline{case}}& a_1 & \longr& P_1,\\ & & \vdots& &\vdots\\ & & \vdots& &\vdots\\ & & a_n & \longr& P_n,\\ &\text{\underline{end} ,} \end{array} \end{array}$
also auf reine "loop-Programme", führt zu Programmen, mit denen sich nicht mehr alle Funktionen aus $\calP$ realisieren lassen. Wir werden im folgenden untersuchen, unter welchen Voraussetzungen selbstreproduzierende loop-Programme möglich sind.

6.2. Definition der Programmiersprache LP(A)

(6.2.1) Definition: Sei $A=\{a_1,\dots,a_n\}$ 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 $\gamma_5\ :\ X:=\rho(X),\ X\in VR$ , oder eine der Kontrollstrukturen
$\begin{array}{ll} &\chi_2\ :\ \text{\underline{if} p \underline{then goto} L ,}\\ &\chi_3\ :\ \text{\underline{if} p \underline{then} P \underline{else} Q \underline{fi}}\\ \text{oder} &\chi_4\ :\ \text{\underline{while} X=\varepsilon\ \underline{do} P \underline{od} \end{array}$
enthalten.

(6.2.2) Bezeichnung:

Neben der Hintereinanderausführung von Anweisungen stellt die loop-Schleife $\chi_5$ das einzige Konstruktionselement für Programme aus LP(A) dar. Die Programme aus LP(A) werden daher auch als loop-Programme bezeichnet.
Die Menge aller durch Programme aus LP(A) realisierbaren Wortfunktionen
$f\ :\ (A^*)^r\longr(A^*)^s,\ r,s\ge0$
wird mit $\calZ$ bezeichnet. $\calZ$ 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 $\calZ$ eine echte Teilmenge von $\calP$ 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ß $\calZ$ eine echte Teilmenge von $\calR$ (vgl. (2.4.6)) ist, indem man die Existenz einer total rekursiven Funktion, die nicht primitiv rekursiv ist, nachweist (vgl. [5] Seite 41).

6.3. Eine kontextfreie Grammatik für LP(A)

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 $G'(A)=(V_T',V_N',s_0,P')$

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}$
wobei VR die Menge der zulässigen Variablennamen ist.

Die Menge der nicht terminalen Zeichen ist
$\begin{array}{ll} V_N'=&\{\text{\underline{<program>},\underline{<statement>},\underline{<simple statement>}},\\ &\text{\underline{<identifier>},\underline{<identifier list>}} \} \end{array}$

Das Startsymbol $s_0$ 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.

6.4. Erweiterung der Sprache LP(A)

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 $\calZ$ 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.

Sei A ein endliches Alphabet. In der zu A gehörigen Sprache LP(A) soll es die Möglichkeit geben, Variable mit jedem beliebigen Wert aus $A^*$ und nicht nur mit $\varepsilon$ zu initialisieren. Wir führen daher die Grundanweisung $\gamma_6$ 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}$
Es soll nicht ausgeschlossen werden, daß $'\in A$ sein darf. Damit ist aber auch $a_{i_j}=\ '$ für beliebiges $j\in[k]$ 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 $\gamma_6$ 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 $\gamma_6$ 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}$
Ist $X \in VR$ , so ist folgende Anweisung vom Typ $\gamma_4$ möglich:
$\hspace{100}X:=X$
Auf eine solche Anweisung wird in der Regel ein Semikolon folgen.
$\dots\ \dots\ \dots\ X:=X;\ \dots\ \dots\ \dots$
Da wir nicht ausschließen wollen, daß das Semikolon ein Element aus A ist, könnte der String
$\hspace{100}X:=X;$
auch als Anweisung vom Typ $\gamma_3$ interpretiert werden. Um Doppeldeutigkeiten¹⁾ zu vermeiden, ersetzen wir $\gamma_3$ durch die Grundanweisung $\gamma_3'$ :
$\hspace{50}\gamma_3'\ :\ X:=X|a\hspace{50}\forall X \in VR,\ a\in A$
Die Bedeutung von $\gamma_3'$ ist die gleiche wie die von $\gamma_3$ .

(6.4.2.) Definition: Sei A ein endliches Alphabet. LP(a) ist diejenige Programmiersprache, die durch Erweiterung um die Grundanweisung $\gamma_6$ und durch Ersetzung der Grundanweisung $\gamma_3$ durch $\gamma_3'$ aus der Sprache LP(A) entsteht.

Aus der Grammatik G'(A) für die Sprache LP(A) laßt sich leicht eine kontextfreie Grammatik $\overline{G'(A)}$ für die Sprache $\overline{LP(A)}$ herleiten:

Die Menge der terminalen Zeichen $V_T'$ wird um ' und | erweitert.
Die Produktion
$\begin{array}{ll} \text{<simple statement>}\longr &X:=\ 'a_{i_1}\ \dots\ a_{i_k}\ ';\\ &\text{f\ddot{u}r alle X\in VR,\ a_{i_j}\in A} \end{array}$
wird der Menge P' hinzugefügt.
Die Produktion
$\text{<simple statement>\longr X:=Xa, f\ddot{u}r alle X \in VR, a \in A}$
wird ersetzt durch
$\text{<simple statement>\longr X:=X|a, f\ddot{u}r alle X \in VR, a \in A}$

(6.4.3) Definition: (loop-Hierarchie der $\overline{LP(A)}$ -Programme)

Sei A ein endliches Alphabet.

Es sei $\overline{L_0(A)}$ die Klasse der Programme
$\begin{array}{rcll} \pi & = &\text{\underline{input}}& X_1,\dots,X_r;\\ & & & AW_\pi;\\ & &\text{\underline{output}}&Y_1,\dots,Y_s\ \ \ ,\ r,s\ge0 \end{array}$
aus $\overline{LP(A)}$ , deren Anweisungsteil $AW_\pi$ durch beliebiges Hintereinanderschreiben von Anweisungen vom Typ $\gamma_1,\gamma_2,\gamma_3,\gamma_4$ und $\gamma_6$ ersteht.
Die Klasse $\overline{L_{i+1}(A)$ enthalte alle Programme $\pi$ , deren Anweisungsteile $AW_\pi$ durch Hintereinandersetzen von Anweisungsteilen von Programmen aus $\overline{L_i(A)}$ 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]} }$
wobei $AW_{\pi_1}\ \dots\ AW_{\pi_n}$ Anweisungsteile von Programmen aus $\overline{L_i(A)}$ sind, entstehen ( $i\ge0$ ).

6.5. Selbstreproduzierende Programme in $\overline{LP(A)}$

Sei $\pi_{\text{rep}}$ ein - falls es existiert - selbstreproduzierendes $\overline{LP(A)}$ -Programm. Im Anweisungsteil von $\pi_{\text{rep}}$ muß schrittweise der Text $\pi_{\text{rep}}$ aufgebaut werden. Die einzelnen Buchstaben von $\pi_{\text{rep}}$ 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: $\pi_{\text{rep}}\in A$ . Um dies zu gewährleisten, wird folgende Forderung an das Alphabet A gestellt:

Forderung (1): Für jedes Programm $\pi\in\overline{LP(A)}$ gilt:
$\hspace{100}\pi \in A^*$

Jedes Alphabet, das Forderung (1) erfüllt, muß alle Zeichen enthalten, die zur Konstruktion von $\overline{LP(A)}$ -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 $\overline{LP(A)}$ 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 $\pi_{\text{rep}}\in\overline{LP(A)}$ nur Buchstaben aus A in Frage kommen.

Forderung (2): $\text{VR\subseteq\{a\backslash B\}^*\backslash\{case,loop,end,input,output\}\backslash\{\varepsilon\}$ . Dabei ist $B:=\{\rotate{-90}],:,=,\longr,,,;,\overline\varepsilon,\varepsilon,\ ',|\}$ die Menge der Sonderzeichen.

In einem $\overline{LP(A)$ -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 $\overline{LP(A)}$ schließt Fehlinterpretationen jedoch aus.

(6.5.2) Satz: Sei A endliches Alphabet mit $A_{\text{min}}\subset A$ . Dann existiert in $\overline{L_2(A)}$ ein selbstreproduzierendes Programm, falls $\overline{LP(A)}$ Forderung (2) erfüllt.

Beweis: Betrachte das Programm $\pi^2_{\text{rep}}$

$\text{\underline{input};}\\ \text{a:=\'input;a:=\';;}\\ \text{c:=\':=\'\';;}\\ \text{d:=\'\'\';;}\\ \text{e:=lnloocppnoodpnnooepsnooipunoou\';;}\\ \begin{array}{lllll} \text{i:=\'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,}\\ & & \text{d \longr t:=t|d,}\\ & & \text{e \longr t:=t|e,}\\ & & \text{s \longr loop e}&\text{case} &\text{l \longr t:=t|l,}\\ & & & &\text{n \longr t:=t|n,}\\ & & & &\text{o \longr t:=t|o,}\\ & & & &\text{c \longr t:=t|c,}\\ & & & &\text{p \longr t:=t|p,}\\ & & & &\text{d \longr t:=t|d,}\\ & & & &\text{e \longr t:=t|e,}\\ & & & &\text{s \longr t:=t|s,}\\ & & & &\text{i \longr t:=t|i,}\\ & & & &\text{u \longr t:=t|u,}\\ & & &\text{end,}\\ & & \text{i \longr t:=t|i,}\\ \end{array}$
$\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}$
$\begin{array}{lllll} \text{ } & & \text{d \longr t:=t|d,}\\ & & \text{e \longr t:=t|e,}\\ & & \text{s \longr loop e}&\text{case} &\text{l \longr t:=t|l,}\\ & & & &\text{n \longr t:=t|n,}\\ & & & &\text{o \longr t:=t|o,}\\ & & & &\text{c \longr t:=t|c,}\\ & & & &\text{p \longr t:=t|p,}\\ & & & &\text{d \longr t:=t|d,}\\ & & & &\text{e \longr t:=t|e,}\\ & & & &\text{s \longr t:=t|s,}\\ & & & &\text{i \longr t:=t|i,}\\ & & & &\text{u \longr t:=t|u,}\\ & & &\text{end,}\\ & & \text{i \longr t:=t|i,}\\ & & \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 t:=t|,,}\\ & & & &\text{\longr \longr t:=t|\longr,}\\ & & & &\text{\rotate{-90}] \longr t:=t|\rotate{-90}],}\\ & & &\text{end,}\\ &\text{end},\\ &\text{output t;;}\\ \end{array}$

$\pi^2_{\text{rep}}$ ist offensichtlich ein gültiges $\overline{LP(A)}$ -Programm.

Zu zeigen: $\pi^2_{\text{rep}}$ reproduziert sich selbst.

Da $\pi^2_{\text{rep}}$ keine Eingabe besitzt, ist die Behauptung, daß sich $\pi^2_{\text{rep}}$ selbstreproduziert, gleichwertig mit der Aussage, daß der Inhalt der Variablen t bei Ausführung der letzten Anweisung "output t" gleich $\pi^2_{\text{rep}}$ ist.

Im folgenden bezeichne [x] den Inhalt der Variablen mit dem Namen x. $x\in\{a,c,d,e,i,t\}\subset A_{\text{min}}$ .
Auf Grund der Definition der loop-Schleife ist klar, daß die 4 inneren loop-Schleifen jeweils den Inhalt ihrer Laufvariablen an [t] hängen und [t] somit verlängern. Es sei hier folgende Abkürzung vereinbart:
${([t]:=[t][y]):=}\left\{ \begin{array}{lll} \text{\underline{loop} y}&\text{\underline{case}} & \dots & \longr & \dots\\ & & & \vdots\\ & & & \vdots\\ &\text{\underline{end}}\\ \end{array} \right.\\ y\in\{a,c,d,e,i\}.$
Die Abkürzung [t]:=[t]x hingegen bedeutet das Anhägen des Zeichens $x \in A$ an den Inhalt von [t].

Mit Hilfe der unter II. getroffenen Abkürzungen läßt sich $\pi^2_{\text{rep}}$ 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 $\pi^2_{\text{rep}}$ . Die Kodierung ist durch Hinschreiben der Alternativenliste gegeben. Die äußere loop-Schleife selbst dekodiert [e] und erzeugt sukzessive $\pi^2_{\text{rep}}$ . In $\pi^2_{\text{rep}}$ kommen nur Zeichen aus $A_{\text{min}}$ vor. Daher ist $\pi^2_{\text{rep}}\in\overline{LP(A)}$ für jedes $A\supset A_{\text{min}}$ , falls $\overline{LP(A)}$ Forderung (2) erfüllt.

Da die Schachtelungstiefe der loop-Schleifen in $\pi^2_{\text{rep}}$ 2 ist, folgt der Satz.

Aus dem Programm $\pi^2_{\text{rep}}$ aus dem obigen Beweis läßt sich ein Programm $\pi^1_{\text{rep}}$ gewinnen, daa mit der loop-Schachtelungstiefe 1 auskommt.

Wir konstruieren $\pi^1_{\text{rep}}$ aus $\pi^2_{\text{rep}}$ , 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 $\pi^2_{\text{rep}}$ 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 l> durch}\\ & \fbox { \begin{array}{llll} \text{loop a} & \text{case} & i & \longr t:=t|i,\\ & & n & \longr t:=t|n,\\ & & p & \longr t:=t|p,\\ & & u & \longr t:=t|u,\\ & & t & \longr t:=t|t,\\ & & ; & \longr t:=t|;,\\ & & a & \longr t:=t|a,\\ & & : & \longr t:=t|:,\\ & & = & \longr t:=t|=,\\ & \text{end}\\ \end{array} }\\ \text{<Alternative f\ddot{u}r n> durch}\\ & \fbox { \begin{array}{llll} \text{loop d} & \text{case} & \text{\'} & \longr t:=t|\text{\'},\\ & \text{end}\\ \end{array} }\\ \text{<Alternative f\ddot{u}r o> durch} & \fbox{t:=t|;}\\ \text{<Alternative f\ddot{u}r c> durch} & \fbox{t:=t|c}\\ \text{<Alternative f\ddot{u}r p> durch}\\ & \fbox { \begin{array}{llll} \text{loop c} & \text{case} & : & \longr t:=t|:,\\ & & = & \longr t:=t|=,\\ & & \text{\'} & \longr t:=t|\text{\'},\\ & \text{end}\\ \end{array} }\\ \text{<Alternative f\ddot{u}r d> durch} & \fbox{t:=t|d}\\ \text{<Alternative f\ddot{u}r i> durch} & \fbox{t:=t|i}\\ \end{array}$
$\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}$

Offensichtlich gilt: $\pi^1_{\text{rep}}$ , reproduziert sich selbst. Da $\pi^1_{\text{rep}}\in A^*_{\text{min}}$ , können wir den folgenden Satz formulieren:

(6.5.3) Satz: Sei A endliches Alphabet mit $A_{\text{min}}\subset A$ , Dann existiert in $\overline{L_1(A)}$ ein selbstreproduzierendes Programm, falls $\overline{LP(A)}$ Forderung (2) erfüllt.

Nach der recht einfachen Konstruktion von $\pi^1_{\text{rep}}$ aus $\pi^2_{\text{rep}}$ könnte man versucht sein, aus $\pi^1_{\text{rep}}$ ein selbstreproduzierendes Programm $\pi^0_{\text{rep}}$ gewinnen zu wollen, das ganz ohne loop-Schleifen auskommt. Zu diesem Zweck müßten in $\pi^1_{\text{rep}}$ 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 $\pi^2_{\text{rep}}$ , 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:
$\hspace{100}\text{t:=t|\'}$

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 $\overline{LP(A)}$ -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 $\pi^1_{\text{rep}}$ 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 $\overline{LP_0(A)}$

Beweis: Sei $\overline{LP(A)}$ über dem endlichen Alphabet A vorgelegt. Sei die notwendige Forderung (2) erfüllt.

Annahme: Es existiert selbstreproduzierendes Programm $\pi^0\in\overline{LP_0(A)}$ . Dann hat $\pi^0$ den Aufbau:

$\pi^0=\text{\underline{input}; AW_{\pi^0}; \underline{output} t}$

In $AW_{\pi^0}$ muß der Text $\pi^0$ aufgebaut werden. Da keine loop-Schleifen zur Verfügung stehen, sind nur zwei Möglichkeiten zur Erzeugung des Textes $\pi^0$ in $AW_{\pi^0$ gegeben.

1. Fall: Der Text $\pi^0$ wird, en bloc mit Hilfe einer Grundanweisung vom Typ $\gamma_6$ erzeugt. Dann gilt für $\pi^0$ die Textgleichung
$\pi^0=\text{\underline{input};t:=\'\pi^0\';\underline{output} t}$
Diese Gleichung kann aber von keinem endlichen Text $\pi^0$ erfüllt werden. Widerspruch!

2. Fall: Der Text $\pi_0$ wird in $AW_{\pi^0}$ zeichenweise mit Anweisungen vom Typ $\gamma_3'$ aufgebaut. Da $\pi^0$ ungleich dem leeren Wort seih muß, kommt in $AW_{\pi^0}$ mindestens einmal die Anweisung t:=t|x; mit $x \in A$ vor. Diese Anweisung umfaßt 7 Zeichen. Als String interpretiert ist sie textueller Bestandteil von $\pi^0$ . 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 $\gamma_3'$ notwendig. Diese 6 Anweisungen hinterlassen ihrerseits 36 unbearbeitete Zeichen, u.s.w.

Um also einen Text der Länge $k\ge0$ mit Anweisungen vom Typ $\gamma_3'$ zu erzeugen, braucht man mindestens ein Programm der Länge $k\cdot7$ .

Damit gibt es kein endliches Programm der Länge k, das nur mit Anweisungen vom Typ $\gamma_3'$ einen endlichen Text der Länge k aus dem leeren Wort aufbauen kann, insbesondere nicht seinen eigenen Text. $\pi^0$ 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 $\calP^1_1$ .
Die Klasse aller Wortfunktionen
$\varphi\ :\ (A^*)^r\longr(A^*)^s,\ r,s\ge0\ ,$
die sich mittels $\overline{LP(A)}$ -Programmen berechnen lassen, ist eine Funktionenklasse, die nur aus totalen Funktionen besteht; $\overline{LP(A)}$ -Programme halten immer an. In [5] Seite 47 wird gezeigt, daß es für $\overline{LP(A)}$ -berechenbare Funktionen keine universelle $\overline{LP(A)}$ -berechenbare Funktion geben kann. Trotzdem gibt es in $\overline{LP(A_{\text{min}})}$ 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.

6.6. Selbstreproduktionssatz für $\overline{LP(A)}$ -Programme

In 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 $\overline{LP(A)}$ -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 $\overline{LP(A)}$ -Programme erklärt.

Sei A ein beliebiges endliches Alphabet, sei $\pi\in\overline{LP(A)}$ . Möglicherweise existiert in $\overline{LP(A)}$ keine selbstreproduzierende Version $\tilde\pi$ zu $\pi$ (etwa weil die in $\overline{LP(A)}$ verwendeten Variablennamen nicht aus $A^*$ sind), sondern erst in der Sprache $\overline{LP(B)}$ mit einem entsprechend "großen" Alphabet $B \supset A$ . Nach Definition (5.1.4) wäre ein solches $\tilde\pi\in\overline{LP(B)}$ keine selbstreproduzierende Version von $\pi$ , da es mit einem anderen Datenbereich arbeitet. Definition (5.1.4) ist aber erfüllt, wenn man $\pi$ ebenfalls als Programm aus $\overline{LP(B)}$ auffaßt, was ja wegen $A \subset B$ durchaus zu vertreten ist: Die von $\pi\in\overline{LP(A)}$ realisierte Funktion ist gleich der Restriktion der von $\pi$ als $\overline{LP(B)$ -Programm realisierten Funktion auf $(A^*)^r,\ r\ge0$ (vgl. Definition (5.1.1)).

Dieser Sichtweise entspricht Satz (6.6.1).

(6.6.1) Selbstreproduktionssatz für $\overline{LP(A)}$ -Programme

Seien A ein endliches Alphabet, $\pi\in\overline{LP(A)}$ . Dann gibt es ein endliches Alphabet $B,\ A \subset B$ , so daß gilt:

Es existiert eine selbstreproduzierende Version $\pi\in\overline{LP(B)}$ von $\pi$ (wobei $\pi$ als Element aus $\overline{LP(B)}$ aufzufassen ist).
$\tilde\pi\in \left\{ \text{\overline{LP_2(B)} , falls \pi \in \overline{LP_j(A)} , j=0,1}\\ \text{\overline{LP_i(B)} , falls \pi \in \overline{LP_i(A)} , i \ge 2} \right.$

Beweis: Seien A beliebiges endliches Alphabet, $\pi\in\overline{LP(A)}$ . O.B.d.A. seien alle Variablennamen aus $\pi$ nicht aus {c,d,e,i,t}.

Konstruktion der selbstreproduzierenden Version $\tilde\pi$

$\pi$ hat den folgenden Aufbau

$\begin{array}{lll} \pi=& \text{\underline{input}} & y_1, \dots, y_r;\\ & & AW_\pi;\\ & \text{\underline{output}} & z_1, \dots, z_w,\ \ \ r,w\ge0 \end{array}$

Sei $A_\pi$ die Menge aller Zeichen, aus denen das Programm $\pi$ zusammengesetzt ist. Der String $S\in A^*_\pi$ sei wie folgt definiert:

    S:=input ;;
                         
             (hiermit ist natürlich der Text des
	      Anweisungsteils von  gemeint)

Es gilt: $\pi=S \circ \text{output } z_1,\dots,z_w$ .

S wird in eine Folge von $n\ge1$ Teilstrings $s_i$ zerlegt mit:

$s_i=\text{\'; oder \';}$ ist nicht in $s_i$ enthalten
$s_i$ enthält '; nicht $\Rightarrow s_{i+1}=\text{\'; },i \le n$
$s_1 \circ s_2 \circ \dots \circ s_n=S$

(Zur Erinnerung: '; dient als Endemarkierung von Textkonstanten und darf selbst nicht Teiistring einer Textkonstanten sein.)

Weitere Vorbereitungen:

$\calJ:=\{s_1,\dots,s_n\}$ Menge der Teilstrings.
q sei die Anzahl der Teilstrings von S, die ungleich '; sind. Es gilt $1 \le q \le n$ .
$x_1,\dots,x_{2q}$ seien Zeichen, die weder in {c,d,e,i,t} noch als Variablennamen in $\pi$ vorkommen.
$B:=A \cup A_\pi \cup A_{\text{min}} \cup \{x_1,\dots,x_{2q}\}$
B ist ein endliches Aiphabet und läßt sich als solches in der Form $B:=\{b_1,\dots,b_\alpha\}$ schreiben, wobei $\alpha$ die Kardinalität von B ist.
Definition der Funktionen $\calG$ und $\tilde\calG$ :
$\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}$
Sei v eine zulässige Variable, dann sei die Anweisung
$\begin{array}{lllcl} \text{\underline{loop} v}&\text{\underline{case}} & b_1 \longr t:=t|b_1,\\ & & \dots\ \dots\ \dots\\ & & b_\alpha \longr t:=t|b_\alpha,\\ &\text{\underline{end}} \end{array}$
durch loop v abgekürzt.

Nach diesen Vorbereitungen läßt sich $\tilde\pi\in\overline{LP(B)}$ 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: $\tilde\pi$ ist selbstreproduzierende Version von $\pi$ .

Programm $\tilde\pi$ beginnt mit der Eingabe der Eingabevariablen von $\pi$ und der Abarbeitung des vollständigen Anweisungsteils von $\pi$ . Am Ende von $\tilde\pi$ werden die Ausgabevariablen von $\pi$ ausgegeben. Diese Ausgabevariablen $z_1,\dots,z_w$ werden nicht durch Anweisungen außerhalb des Anweisungsteils von $\pi$ verändert. $\tilde\pi$ gibt zusätzlich die Variable t aus. Zum Nachweis, daß $\tilde\pi$ selbstrenroduzierende Version von $\pi$ ist, genügt es also zu zeigen, daß am Ende der Programmausführung der Inhalt von t gleich $\tilde\pi$ ist.

Die Variablen $x_1,\dots,x_q,c,d,e$ und i enthalten - bis auf einige einzelne Zeichen - den Programmtext $\tilde\pi$ in zerlegter Form. Die Aufgabe der loop-Schleife von $\tilde\pi$ ist es, die in den Variablen gespeicherten Teilstrings zum Text $\tilde\pi$ zusammenzufügen. Die äußere loop-Schleife

loop e case ..... end;

wird durch die Variable e gesteuert, e enthält den Text $\tilde\pi$ in kodierter Form. Die Kodierung ist direkt aus der Alternativenliste ersichtlich. Für jedes Zeichen der Textkonstanten e wird genau ein Teilstring des Programms $\tilde\pi$ 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 $\tilde\pi$ an den Inhalt von t gehängt wird. Dies folgt aus der völligen Analogie zu $\pi^2_{\text{rep}}$ 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 $\tilde\pi$ wird als Inhalt von t ausgegeben. $\tilde\pi$ erfüllt also Definition (5.1.4)(ii) und ist somit selbstreproduzierende Version von $\pi$ .

Die "reproduzierende" loop-Schleife in $\tilde\pi$ hat die loop-Schachtelungstiefe 2 und steht neben dem Anweisungsteil von $\pi$ . Die loop-Schachtelungstiefe von $\tilde\pi$ ist daher mindestens 2, aber beschränkt durch die loop-Schachtelungstiefe von $\pi$ . Damit ist auch die zweite Aussage des Satzes erfüllt.

(6.6.2) Bemerkung:

Aus dem Beweis von Satz (6.6.1) läßt sich direkt ein Algorithmus zur Ermittlung einer selbstreproduzierenden. Version zu einem gegebenen -Programm gewinnen. Dieser Algorithmus ist jedoch stark verbesserungsbedürftig.
Beispiele:
- Die Wahl des Alphabets B läßt sich verfeinern. Man kommt mit "kleinerem" Alphabet B aus, als im Beweis angegeben.
- Die loop-Schleifen vom Typ
```
loop v
```
  enthalten viele unnütze Alternativen, die im Beweis zugunsten einer einheitlichen Schreibweise in Kauf genommen werden.
Die im Beweis von (6.6.1) vorgenommene Konstruktion orientiert sich eng an dem Programm $\pi^2_{\text{rep}}$ aus 6.5. Eine Konstruktion mit Hilfe des $\overline{LP_1(A_{\text{min}})$ -Programms $\pi^1_{\text{rep}}$ würde zu selbstreproduzierenden Versionen $\tilde\pi$ führen mit
$\tilde\pi\in { \left\{ \text{\overline{LP_1(B)} , falls \pi \in \overline{LP_0(A)}}\\ \text{\overline{LP_i(B)} , falls \pi \in \overline{LP_i(A)}, i \ge 1 .} \right. }$
Diese Konstruktion wäre aber noch schwieriger zu überschauen als die Konstruktion mittels $\pi^2_{\text{rep}}$ .

7. Leben bei Programmen?

7.1. Einleitung

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 $\pi$ 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 $\pi' \neq \pi$ reproduziert wird. Falls $\pi'$ ein syntaktisch korrektes Programm ist, kann $\pi'$ durchaus wieder selbstreproduzierend sein und dabei eine andere Funktion realisieren als $\pi$ . 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 moderne Biologie ist sich durchaus nicht einig, wenn es darum geht, die charakteristischen Merkmale des Lebens auf eindeutige Weise zu definieren (vgl. 7.2.).
Biologisches Leben basiert auf einem äußerst vielschichtigen Zusammenspiel von biochemischen Reaktionen. Bestimmten Makromolekülen, namentlich Nukleinsäure- und Aminosäuremoleküle, fallen dabei Schlüsselpositionen zu [13J. Alle irdischen Lebensformen werden von dem Zusammenwirken von Nuklein- und Aminosäuren bestimmt. Die Frage, ob andere Lebensformen als die uns vertrauten denkbar sind, versucht die Biologie zu beantworten, indem sie das Problem untersucht, ob die Funktionen der Nuklein- bzw. Aminosäuren durch andere Makromolekülsorten ersetzt werden können [13]. Diesem Vorgehen läßt sich die Auffassung entnehmen, daß Leben immer chemophysikalischen Ursprungs ist. Leben bei Computerprogrammen wäre in diesem Sinne unmöglich.

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.

7.2. Biologisches Leben

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

Stoffwechsel ( + Regelung )
Zellreproduktion und Mutation

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)

Stoffwechsel

Die "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 A_i treten in das System ein. Innerhalb des Systems werden mittels Binnenreaktionen die Stoffe B_j erzeugt. Die (Abfall-) Produkte C_k 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ß

in den Tochterzellen die gleichen Proteine gebildet werden wie in der (den) Slterzelle(n),
sich diese Bildung in der zeitlich richtigen Reihenfolge vollzieht.

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.

7.3.Selbstreproduzierende Programme und Leben

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:

Lochstreifen
Lochkarten
Formulierung mit "Papier und Beistift"

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 semantisch¹⁾ 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 $\pi$ auf einer Rechenanlage auszuführen, kann natürlich nicht als (Energie-) Stoffwechsel betrachtet werden, da die Zufuhr von Energie

nicht vom Programm $\pi$ aktiv gesteuert wird,
nicht der Erhaltung des Programms $\pi$ , sondern der Interpretation von $\pi$ 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 $\pi$ ₃ aus Abschnitt 3.2.5., Textkonstante der Prozedur AB in $\pi$ ₄ 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

VX Heavens

Selbstreproduktion bei programmen

Selbstreproduktion bei programmen

Inhalt

1. Einleitung

1.1. Motivation

1.2. Definition selbstreproduzierender Programme

2. Existenzselbstreproduzierender Programme

2.1. Einleitung

2.2. Definition einer einfachen Programmiersprache PL(A)

2.3. Eine kontextfreie Grammatik für PL(A)

2.4. PL(A)-berechenbare Funktionen, Church'sche These

2.5. Codierungen, Gödelisierungen von

2.6. Lexikographische Ordnung von

2.7. Reduktion auf jeweils eine Eingabe- und eine Ausgabevariable

2.8. s-m-n-Theorem, Rekursionstheorem

3. Selbstreproduzierende Programme in realen Programmiersprachen - Einige Beispiele

3.1. Einleitung

3.2. Selbstreproduzierende Programme in SIMULA1)

3.2.1. Naiver Ansatz

3.2.2. Textzerlegung und Algorithmus

3.2.3. Ein tabellengesteuertes Programm

3.2.4. Vahl der Iterationsfunktion F

3.2.4.1. Eine Iterationsfunktion mittels Modulo-Bildung

3.2.4.2. Eine Iterationsfunktion basierend auf der Gödelisierung g aus 2.5.

3.2.5. Ein textgesteuertes SIMULA-Programm

3.2.6. Implementierung des Programms

3.2.7. Ein prozedurgesteuertes Programm

3.2.8. Implementierung des Programms

3.3. Selbstreproduzierende Programme in PASCAL1)

3.3.1. Ein textgesteuertes PASCAL-Programm

3.3.2. Implementierung des Programms

3.3.3. Ein prozedurgesteuertes PASCAL-Prograjam

3.3.4. Implementierung des Programms

3.4. Selbstreproduzierende Programme in SIEMENS-Assembler

4. Varianten zur Selbstreproduktion von Programmen

4.1. Motivation

4.2. Unendlich reproduzierende Programme

4.2.1. Implementierung des Programms

4.3. Zyklisch selbstreproduzierende Programme

4.3.1. Implementierung des Programms

4.3.2. Implementierung des Programms

4.4. Unter Wechsel der Programmiersprache sich zyklisch selbstreproduzierende Programme

4.5. k-fach selbstreproduzierende Programme

4.5.1. Implementierung von

4.6. Reproduktionshierarchie bei Programmen

5. Selbstreproduzierende Programme mit Zusatzegeinschaften

5.1. Einleitung

5.2. Selbstreproduktionssatz für die Programmiersprache PASCAL

5.3. Selbstreproduktionssatz für die Programmiersprache SIMULA

6. Selbstreproduktion bei loop-Programmen

6.1. Einleitung

6.2. Definition der Programmiersprache LP(A)

6.3. Eine kontextfreie Grammatik für LP(A)

6.4. Erweiterung der Sprache LP(A)

6.5. Selbstreproduzierende Programme in

6.6. Selbstreproduktionssatz für -Programme

7. Leben bei Programmen?

7.1. Einleitung

7.2. Biologisches Leben

7.3.Selbstreproduzierende Programme und Leben

2.5. Codierungen, Gödelisierungen von $\cal{P}$

2.6. Lexikographische Ordnung von $A^*$

3.2. Selbstreproduzierende Programme in SIMULA¹⁾

3.2.5. Ein textgesteuertes SIMULA-Programm $\pi_3$

3.2.6. Implementierung des Programms $\pi_3$

3.2.7. Ein prozedurgesteuertes Programm $\pi_4$

3.2.8. Implementierung des Programms $\pi_4$

3.3. Selbstreproduzierende Programme in PASCAL¹⁾

3.3.1. Ein textgesteuertes PASCAL-Programm $\pi_5$

3.3.2. Implementierung des Programms $\pi_5$

3.3.3. Ein prozedurgesteuertes PASCAL-Prograjam $\pi_6$

3.3.4. Implementierung des Programms $\pi_6$

4.2.1. Implementierung des Programms $\overset\infty\pi_0$

4.3.1. Implementierung des Programms $\overset{k}\pi_0$

4.3.2. Implementierung des Programms $\pi_0^{\text{zyk}}$

4.5.1. Implementierung von $\pi(k)$

6.5. Selbstreproduzierende Programme in $\overline{LP(A)}$

6.6. Selbstreproduktionssatz für $\overline{LP(A)}$ -Programme