Egon Borger

1 über dem Inhalt des ersten (oder zweiten)

„ Stoppen " , d.h. cOj = aSa^,sSs^, stop respektive; der Stopbefehl

zweiten ) Register", „Ausführen von Registers*

steht (nur) in den Instruktionen mit der Nummer r -1 und r, und deren instruktionsnummern ф"_1,(^*_1 und q>7.cpt sind gleich resp. r-1 und r; die Nullprobe wird (nur) vor dem Ausführen von Subtraktionsbefehlen durchgeführt, d. h. Vi(0 ^ i ^ r und a>, e {a\ a^} >-<]pf = ф*), und in diesen Fällen wird statt cp^ einfach cp^ geschrieben; für alle 0 g i ^ r gilt 0 ^ (pf, ф* ^ r. Durch die Festlegung der Instruktion mit der Nummer 0 als Anfangszustand, d. h. Maschinenzustand zum Zeitpunkt 0 wird durch das Programm von M in der üblichen Weise für jedes Paar (pq, q^) natürlicher Zahlen eine tionenfolge (CJ^gfj definiert, deren Glieder C^ = {i^lPm^ q^) die tion „Maschinenzustand i^ und Speicherinhalt p^ im ersten, q^ im zweiten Register" von M zum Zeitpunkt m beschreiben; die Abhängigkeit einer solchen Konfigurationenfolge (CJ^^j^ von M und von (pq, qo) dürfte im folgenden wohl stets aus dem Kontext hervorgehen und wird deshalb nicht in die Schreibweise aufgenommen. Konfigurationen werden durchgehend in der Form C^ = (i;p,^) geschrieben, r steht immer für die Nummer der letzten Programmteile von M, n für den Input von M im ersten Register, und für i, i^ und jj^ wird 0 ^ i, i^ ^ r und 0 ^ j, jjn < n (selten ^ и, wie jedoch stets aus dem Kontext deutUch wird) festgesetzt. Natürliche Zahlen 0, |0,110,1110,... (Elemente aus N) werden mit ij, fc, /, m, n, p, q, r, к:,Я,/х, v,^, 1*0, ••• bezeichnet. Frei vorkommende Variablen sind durchgehend universell quantifiziert zu lesen.

Der Satz von der rekursiven Aufzählbarkeit der Mengen der prädikatenlogisch ableitbaren und der endlich erfüllbaren Ausdrücke wird in den folgenden beiden Formen benutzt: 1. es gibt ein effektives Verfahren, das jedem Ausdruck у eine 2-Registermaschine Щ zuordnet, die genau dann bei der Anfangskonfiguration Co = (0; 0,0) nicht im Zustand r stoppt, wenn у erfüllbar ist; 2. es gibt eine Gödeli- sierung - der prädikatenlogischen Ausdrücke und eine 2-Registermaschine Mo der Art, daß Mo für beliebige Ausdrücke у bei der Anfangskonfiguration Q = (0 ; y, 0) mit einer Konfiguration (r; 0,0) stoppt, falls у widerspruchsvoll ist, mit einer figuration (r— 1; 1,0), falls у endHch erfüllbar ist, und daß die folge sonst nicht periodisch wird.

Nach diesen terminologischen Vorbereitungen läßt sich ein eleganter Beweis von Satz 1 wie folgt angeben:

Def : Für bei. M sei уд^ als die Konjunktion der folgenden Ausdrücke definiert:

für œ^ = a^

( 1 )

XqOO

KiXy^K^^\xy

K^yx - ^K^jlx ............a^

Ki\xy - ^K^fxy ............ s^

Kfiy - ^K^rOy ............s'

Kiylx - ^K^fyx ............s^

KtyO^K^ry^ ............^'

пКуХу

( sog . Anfangsaxiom)

( sog . Konfigurationsaxiom)

( sog . Axiom des Nicht-r-Stops).