KE 1.............................................................................................................................................................................................. 2

1 Einleitung............................................................................................................................................................................. 2

2 Flußdiagramme und Maschinen....................................................................................................................................... 2

3 Berechenbare Zahlenfunktionen...................................................................................................................................... 4

KE 2.............................................................................................................................................................................................. 5

4 Transformationen von Flußdiagrammen......................................................................................................................... 5

5 Berechenbare Zahlenfunktionen II.................................................................................................................................. 5

KE 3.............................................................................................................................................................................................. 6

6 Turingmaschinen und Bandmaschinen........................................................................................................................... 6

KE 4.............................................................................................................................................................................................. 7

7 Berechenbarkeit.................................................................................................................................................................. 7

KE 5.............................................................................................................................................................................................. 9

8 Die Standardnumerierung j von P⁽¹⁾................................................................................................................................ 9

KE 6............................................................................................................................................................................................ 11

9 Rekursive und rekursiv-aufzählbare Mengen.............................................................................................................. 11

KE 7............................................................................................................................................................................................ 12

10 Berechenbarkeit auf anderen Mengen........................................................................................................................ 12

KE 1

1 Einleitung

Def. (rekursiv): Eine Menge A heißt rekursiv, gdw. ihre charakteristische Funktion cf_A berechenbar ist.

Sie ist def. durch cf_A := 1, falls xÎA und 0 sonst.

Def. (r.a.): Eine Menge A heißt rekursiv aufzählbar, gdw. sie leer ist oder eine totale Funktion f existiert mit f(IN)=A.

Weitere Charakterisierung (r.a.): Eine Menge A heißt rekursiv aufzählbar, gdw. eine partielle Funktion f existiert mit Def(f) =A. (Beide Def sind gleichwertig)

Beweis (Charakterisierung r.a.)

2 Flußdiagramme und Maschinen

Def. (Flußdiagramm): F=(Q,D,s,q₀,s,Q_e)

Q Menge der Marken

D Datenmenge

s Funktion, die den Marken Funktionen und Tests und Ausgänge zuordnet

q₀ Anfangsmarke

s Anzahl der Ausgänge

Q_e Menge der Endmarken

Beispiel (Euklidischer Algorithmus):

mit F=(Q,D,s,q₀,s,Q_e) und

Q = {1,2,3,4,5}

D = IN²

s(1)=(id, „x>y“, (2,3))

s(2)=(„x:=x-y“, 1, (1))

s(3)=(id, „x=y“, (5,4))

s(4)=(„x«y“, 1, (2))

s(5)=1

q₀ = 1

s = 1

Q_e = {5}

Def. (Semantik Flußdiagramm): Sei F=(Q,D,s,q₀,s,Q_e).

Menge der Konfigurationen KON:=Q´D.

Einzelschrittfunktion ES:Í KON ® KON.

Schrittzahlfunktion SZ:Í KON ® IN, SZ(q,d)=i, falls nach genau i Schritten eine Endkonfiguration erreicht wird.

Gesamtschrittfunktion GS:Í KON ® KON, liefert die Endkonfiguration oder div.

f_F:Í D ® D mit f_F(q₀,d):=pr₂(GS(q₀,d)).

t_F:Í D ® {1,...,s} mit t_F(q₀,d):=s(pr₁(GS(q₀,d))).

(f_F, t_F) heißt Semantik von F.

Def. (Maschinen): Eine Maschine ist def durch M=(F,X,Y,EC,AC).

F ist ein Flußdiagramm.

X ist eine Eingabemenge.

Y ist eine Ausgabemenge.

EC: X ® D ist die Eingabecodierung.

AC: D ® X ist die Ausgabecodierung.

Die Semantik ist def durch

f_M: X ® Y mit f_M:=AC°f_F°EC und t_M: X ® {1,...,s} mit t_M:=t_F°EC.

3 Berechenbare Zahlenfunktionen

Def. (Registermaschine): Eine Registermaschine ist eine Maschine M=(F,IN^k,IN,EC^(k),AC) mit F=(Q,D,s,q₀,s,Q_e) und

D=IN^IN (Registerbelegungen)

EC^(k):IN^k ® D, EC^(k)(x₁,x₂,...,x_k):=(0,x₁,x₂,...,x_k,0,...)

AC^(k):D ® IN, AC (a₀,a₁,...):= a₀

Als Funktionen und Tests werden nur „R_i:=R_i+1“, „R_i:=R_i1“ und „R_i=0“ verwendet.

Def. (Berechenbare Zahlenfunktionen):

1) Die Funktion f:Í IN^k ® IN heißt berechenbar, gdw es eine k-stellige Registermaschine M gibt mit f=f_M.

2) Der Test t:Í IN^k ® {1,...,s} heißt berechenbar, gdw es eine k-stellige Registermaschine M mit s Ausgängen gibt mit t=t_M.

Def. (verallgemeinerte Registermaschine): Eine verallgemeinerte Registermaschine ist eine Maschine M=(F,IN^k,IN,EC^(k),AC) mit F=(Q,D,s,q₀,s,Q_e) und

D=IN^IN (Registerbelegungen)

EC^(k):IN^k ® D, EC^(k)(x₁,x₂,...,x_k):=(0,x₁,x₂,...,x_k,0,...)

AC^(k):D ® IN, AC (a₀,a₁,...):= a₀

Es wird entweder eine Funktion g auf ein Register und der triviale Test 1 mit einem Ausgang oder die identische Funktion id und ein Test mit zwei Ausgängen verwendet.

Satz: Wenn in einer verallgemeinerten Registermaschine alle Funktionen und Tests berechenbar sind, sind auch f_M und t_M berechenbar.

Übung 1: Beschreibe eine Registermaschine, die von zwei Zahlen das Minimum berechnet.

Übung 2: Beschreibe eine Registermaschine, die von zwei Zahlen das Maximum berechnet.

KE 2

4 Transformationen von Flußdiagrammen

Def. (Einsetzung): Seien F=(Q,D,s,q₀,s,Q_e) und F´=(Q´,D,s´,p´₀,v,Q´_e) Flußdiagramme.

F´ heißt an der Stelle p´₀ in F einsetzbar, gdw QÇQ´= {p´₀ } und f:ÍD ® D, t:ÍD ® {1,...,v} sowie p₁,...,p_v existieren mit s(p´₀)=(f,t,(p₁,...,p_v)).

Sei F´´=(Q´´,D,s´´,q₀,s,Q´´_e) def durch

Q´´:=(QÈQ´)\Q´_e

Q´´_e:= Q_e

s´´(q):= s(q), falls qÎQ\{p´₀}

s´´(q):= (f´,t´,(c(r₁),..., c(r_i))), falls qÎQ´\ Q´_e und s´(q):= (f´,t´,(r₁,..., r_i)).

F´´ heißt dann def durch Einsetzung von F´ in F an der Stelle p´₀.

Übung 3: Gebe ein FD für die Funktion Rest an mit Rest(a,b):=c, falls es ein n gibt mit n*b+c=a. Verfeinere das Flußdiagramm.

Satz (Verfeinerung):

Die Semantik eines Flußdiagramms ändert sich nicht durch Verfeinerung. Dabei muß das verfeinernde FD die gleiche Semantik haben wie der ersetzte Knoten.

Def. (Simulation): d Sim d´ heißt, daß d´d simuliert.

Es gilt f Sim f´, gdw (d Sim d´) Þ (f(d) Sim f(d´) oder f(d)=f(d´)=div).

Es gilt t Sim t´, gdw (d Sim d´) Þ (t(d) = t(d´) oder t(d)=t(d´)=div).

Satz (Simulation): Seien F=(Q,D,s,q₀,s,Q_e) und F´=(Q,D´,s´,q₀,s,Q_e) Flußdiagramme und gelte für jedes qÎQ_e s(q)=s´(q) und für jedes qÎQ\Q_e (s(q)=(f_q,t_q,(p₁,...,p_k)) und s´(q)=(f´_q,t´_q,(p₁,...,p_k)) Þ f_q Sim f´_q und t_q Sim t´_q).

Dann gilt f_F Sim f_F´ und t_F Sim t_F´, also F´ simuliert F.

Satz (Simulation von Maschinen): Seien M=(F,X,Y,EC,AC) mit Datenmenge D und M´=([EA,H,AA],X,Y,EC´,AC´) mit Datenmenge D´ Maschinen mit D Sim D´. Falls

EC(x) Sim EA°EC´(x) für alle xÎX und

f_F Sim f_H und t_F Sim t_H und

AC(d)=AC´°AA(d´) für d Sim d´,

dann folgt f_M Sim f_M´und t_M Sim t_M´.

Übung 4: Simuliere mit einer Registermaschine die Addition und die Multiplikation von komplexen Zahlen. Die Relation Sim ist dabei gegeben durch x+i*y Sim (a,b) gdw. x=a und y=b.

Hinweis: (a+ib)+(x+iy)=((a+x)+i(b+y)) und (a+ib)*(x+iy)=ax+aiy+ibx+iiby=((ax-by)+i(ay+bx)).

5 Berechenbare Zahlenfunktionen II

Beweis des Satzes über verallgemeinerte Registermaschinen

Def. (Cantorsche Paarungsfunktion): p:IN²®IN wird def durch p(x,y)= = ½(x+y)(x+y+1)+y.

Def. (Cantorsche Tupelfunktionen): p⁽¹⁾(x)=x. p⁽ⁿ⁺¹⁾(x₁,...,x_n+1)= p(p⁽ⁿ⁾(x₁,...,x_n),x_n+1).

Def:

P^(k):= Menge der partiell rekursiven Funktionen f:ÍIN^k®IN.

R^(k):= Menge der totalen rekursiven Funktionen f:IN^k®IN.

P:= Menge aller partiell rekursiven Funktionen.

R:= Menge aller totalen rekursiven Funktionen.

Def (primitive Rekursion):

f:IN^k+1®IN sei def durch f(x,0)=g(x) und f(x,y+1)=h(x,y,f(x,y)) mit g:IN^k®IN und h:IN^k+2®IN. f=Prk(g,h) ist dann eindeutig def und entsteht durch primitive Rekursion.

Def (m-Rekursion):

Def mx[Q(x)]:=min M, falls M:={kÎIN | Q(k)}¹Æ, div sonst.

Es sei h:IN^k+1®IN.Dann sei m~(h):ÍIN^k®IN def durch m~(h)(x)= m y[h(x,y)=0]. m~(h) entsteht durch m-Rekursion.

Lemma:

Sei L eine k-stellige Registermaschine. Dann ist h:IN^k+1®IN mit

h(x,t)=1+f_L(x), falls SZ_L(EC(x))=t, 0 sonst, berechenbar.

Beweisidee: Neues Register als Schrittzähler einbauen.

Anwendung:

Beweis der Äquivalenz der beiden Def der rekursiven Aufzählbarkeit.

Def (WHILE-Programme): Rek Def durch

R_i+ und R_i- sind WHILE-Programme

Mit P und Q sind auch (P;Q), (R_i | P | Q) und (R_i : P)

Def (Semantik der WHILE-Programme):

t(R_i+)(a₀,a₁,...):=( a₀,a₁,..., a_i-1,a_i+1, a_i+1,...)

t(R_i-)(a₀,a₁,...):=( a₀,a₁,..., a_i-1,a_i1, a_i+1,...)

t(P;Q):= t(Q)°t(P)

t(R_i | P | Q)(d):= t(P), falls d(i)=0, sonst t(Q)

t(R_i : P)(d):= t(P)^t(d), falls die Schleife t-mal durchlaufen wird, sonst div.

Satz:

Die Menge der WHILE-berechenbaren und der Register-berechenbaren Funktionen ist identisch.

Beweisidee:

KE 3

6 Turingmaschinen und Bandmaschinen

Def (Turingmaschine)

Def (berechenbare Wortfunktion): Eine Funktion f:Í(S*)^k®S* heißt berechenbar, wenn sie durch eine Turingmaschine berechnet wird.

Satz: Zu einer Register-berechenbaren Funktion f gibt es eine Turing-berechenbare Funktion f´ mit f´(0^x1,...,0^xk)=0^f(x1,...,xk).

Beweisidee:

Das Register i wird auf dem i-ten Band simuliert.

Def (Bandmaschine):

Ist im wesentlichen eine Turingmaschine, die mit einem einzigen Band arbeitet.

Satz (Turing-bb=Band-bb):

1) Zu jeder Bandmaschine gibt es eine Turingmaschine, die dieselbe Funktion berechnet.

2) Zu jeder Turingmaschine gibt es eine Bandmaschine, die dieselbe Funktion berechnet.

Beweisidee:

1) Simuliere das Band der Bandmaschine auf dem Band 0 der Turingmaschine und nehme eine Eingabeanpassung vor.

2) Simuliere alle Bänder der Turingmaschine auf dem einzigen Band der Bandmaschine. Vergrößere dazu das Bandalphabet so, daß jedes Zeichen jeweils die untereinanderstehenden Zeichen der m gebrauchten Bänder codiert und sogar, auf welchen Zeichen der Schreib-Lese-Kopf steht.

Satz (Hilfssymbole):

Zu jeder Bandmaschine gibt es eine äquivalente, die als Hilfssymbol nur B verwendet.

Beweisidee:

Kodiere die m Zeichen außer B durch Kombinationen gleicher Länge aus Symbolen von S mit élog(m)ù Zeichen. Ersetze alle Befehle auf einzelnen Zeichen durch Programme, die jeweils auf élog(m)ù Zeichen arbeiten.

KE 4

7 Berechenbarkeit

Def (Numerierung):

Eine Numerierung einer Menge M ist eine möglicherweise partielle surjektive Funktion n:ÍIN®M.

Jedes Element von M bekommt dadurch mindestens eine (evtl. auch mehrere) Nummern.

Def (Standardnumerierung von S*):

Sei S ein Alphabet mit n:=card(S) und a_i das i-te Zeichen für 1£i£n. Sei s:S*®IN def durch

s(e):=0 und s(a_ika_ik-1...a_i0):=i_kn^k+i_k-1n^k-1+...+i₁n+i₀.

Dann heißt n: IN ® S* mit n:=s^-1 eine Standardnumerierung von S*.

Satz:

Sei S ein Alphabet und n: IN ® S* eine Standardnumerierung von S* und n´(i₁,...,i_k):=(n(i₁),..., n(i_k)). Für g:Í(S*)^k® S* gilt dann: g berechenbar Û n^-1gn´:ÍIN^k® IN berechenbar.

Für f: ÍIN^k® IN gilt analog: f berechenbar Û nfn´^-1: Í(S*)^k® S* berechenbar.

Def (primitiv-rek Funktionen):

Werden aus den Grundfunktionen Gr:={0,Z,S}È{pr_i^(k) | 1£i£k} mit den Operatoren Sub und Prk in endlich vielen Schritten def, Bez PRK.

Satz:

A_n: IN® IN werden def durch

A₀(x):= 1, falls x=0, 2, falls x=1 und x+2 sonst.

A_n+1(x):=A_n^x(1).

Dann sind alle A_n primitiv-rek.

Satz (Ackermann-Funktion):

Die Ackermann-Funktionen A: IN²® IN und A_d: IN® IN mit A(n,x):=A_n(x) und A_d(x):= A_x(x) sind berechenbar, aber nicht primitiv-rek.

Def (LOOP-Berechenbarkeit):

LOOP-Programme sind wie WHILE-Programme aufgebaut, nur steht die Anzahl der Schleifendurchläufe zu Anfang der Schleife fest.

Satz:

Die Menge der LOOP-berechenbaren Funktionen ist gleich der Menge der primitiv-rek Funktionen.

Weitere Def der Berechenbarkeit:

Markov-Algorithmen, l-definierbare Funktionen, durch Gleichungssysteme definierbare Funktionen, m-rek Funktionen.

Def (m-rek Funktionen):

Werden aus den Grundfunktionen Gr:={0,Z,S}È{pr_i^(k) | 1£i£k} mit den Operatoren Sub, Prk und m~ in endlich vielen Schritten def.

Satz:

Die m-rek Funktionen sind genau die berechenbaren Zahlenfunktionen.

Beispiel:

Die Addition add ist primitiv-rekursiv.

Beispiel:

Die Fakultät fak ist primitiv-rekursiv.

Beispiel:

Die Fibonacci-Funktion ist primitiv-rekursiv. Sie wird def durch fib(0)=1, fib(1)=1 und fib(n+2)=fib(n)+fib(n+1).

Bemerkungen:

Ackermann fand heraus, daß nicht alle m-rek Funktionen primitiv-rek sind: er fand die sogenannte Ackermann-Funktion. Die m-rek Funktionen entsprechen den While-berechenbaren Funktionen. Die primitiv-rek Funktionen entsprechen den Funktionen, die mit For-Schleifen berechnet werden können, wobei der Endwert der Schleife in der Schleife nicht geändert werden darf.

CHURCHSCHE THESE:

Die Register-berechenbaren Funktionen sind genau die maschinell (im intuitiven Sinne) berechenbaren Zahlenfunktionen.

Beweis:

Þ: trivial.

Ü: prinzipiell nicht beweisbar.

Konstruktion einer nicht berechenbaren Zahlenfunktion (DIAGONAL-BEWEIS):

Sei y(i) die vom i-ten WHILE-Programm definierte Zahlenfunktion.

Sei f def durch f(i):=1, falls y(i)(i)=0, sonst 0.

Dann gilt f¹y(i) für alle i, denn für jedes i gilt f(i) ¹y(i)(i).

Die Funktion f ist so definiert, daß sie sich in der Diagonalen der Tabelle von jeder Funktion y(i) unterscheidet, und zwar an der Stelle i, also mit dem Argument i.

	0	1	2	3	4	5	6	...
y(0)	y(0)(0)
y(1)		y(1)(1)
y(2)			y(2)(2)
y(3)				y(3)(3)
y(4)					y(4)(4)
y(5)						y(5)(5)
y(6)							y(6)(6)
...								...

KE 5

8 Die Standardnumerierung j von P⁽¹⁾

Def (Standardnumerierung j):

1) Es sei a:{1,...,8}®W definiert durch (a₁,...,a₈):=(1,B,(,),:,,,R,L) und n_W die aus a abgeleitete Standardnumerierung von W*.

2) n_P:IN®BP sei die Numerierung der Bandprogramme.

3) x:BM®P⁽¹⁾ sei def. durch x(M):=i^-1f_Mi mit i(i):=1ⁱ.

4) Dann ist j:IN®P⁽¹⁾ def. durch j_i:= j(i):=x°n_M°n_P(i) die Standardnumerierung von P⁽¹⁾.

Def (Standardkomplexität F):

Es ist F:IN®IN def. durch F_i(x):= F(i)(x):=SZ_i(q_0i,(e,B,1^xB)) die Standardkomplexität zu j, wobei q_0i die Anfangsmarke und SZ_i die Schrittzahlfunktion der Bandmaschine n_M°n_P(i) ist.

Lemma:

h:IN³®IN, def. durch h(i,n,t):= 1+j_i(n), falls F_i(n)£t, 0 sonst, ist berechenbar.

Beweisidee:

Auf Band 1 wird das i-te Bandprogramm geschrieben, auf Band 2 das Argument n, auf Band 3 der Zähler t und auf Band 4 die Anfangsmarke. Dann simuliert das Programm das Programm auf Band 1, dekrementiert bei jedem Schritt den Zähler t und endet, wenn das Bandprogramm auf Band 1 beendet wird oder der Zähler t 0 wird.

Satz (utm-Theorem):

Die universelle Funktion u_j:ÍIN²®IN, def. durch u_j(i,x):= j_i(x), ist berechenbar.

Das utm-Theorem besagt, daß man statt unterschiedlicher Turingmaschinen eine einzige verwenden kann, die man programmieren kann.

Beweisidee:

Satz (smn-Theorem, Übersetzungslemma):

Sei fÎP⁽²⁾ berechenbar. Dann gibt es eine total-rek. Funktion rÎR⁽¹⁾ mit

("i,jÎIN) f(i,j)=j_r(i)(j).

Man kann zu einer Turingmaschine mit zwei Argumenten eine neue schreiben, bei der das erste Argument nach der Eingabe auf das Band geschrieben wird.

Beweisidee:

Konstruiere eine Turingmaschine, die das erste Argument nach Start vor die Eingabe schreibt und dann weitermacht wie die ursprüngliche Maschine.

Satz (F-Theorem):

1) ("iÎIN) F_iÎP⁽¹⁾.

2) ("iÎIN) Def(F_i)= Def(j_i).

3) g:IN³®IN, def durch g(i,x,t):=1, falls F_i(x)£t, 0 sonst, ist berechenbar.

Beweisidee:

1) mit Rückgriff auf h.

2) trivial

3) mit Rückgriff auf h.

Satz (Rekursionssatz):

Zu jeder Funktion fÎR⁽¹⁾ gibt es eine Zahl n mit j_n=j_f(n).

Beweisidee:

Zu v(z,x):=u_j( u_j(z,z),x) gibt es ein gÎR⁽¹⁾ mit j_g(z)(x)= j_jz(z)(x).

Zu w(i,x):=u_j( i,g(x)) gibt es ein qÎR⁽¹⁾ mit j_q(i)(x)= j_ig(x).

Mit h:=g°q gilt dann j_jih(i)(x)= j_jigq(i)(x) = j_jq(i)q(i)(x) = j_gq(i)(x) = j_h(i)(x).

Wenn f=j_i wähle n:=h(i).

Satz (Selbstreproduktion):

Es gibt eine Zahl n, so daß j_n(x)=n für alle xÎIN.

Beweisidee:

Def f durch f(i,x):=i. Dann gibt es ein rÎR⁽¹⁾ mit j_r(i)(x)=f(i,x)=i. Nach dem Rekursionssatz gibt es eine Zahl n mit j_n=j_r(n). Es folgt j_n(x)=j_r(n) (x)=n für alle x.

Satz (Äquivalenzsatz von Rogers):

Es sei y:IN®P⁽¹⁾ eine Numerierung von P⁽¹⁾. Dann sind folgende Eigenschaften äquivalent:

1) Es gibt „Übersetzer“ g,hÎR⁽¹⁾ mit j=y°g und y=j°h.

2) y erfüllt das utm-Theorem und das smn-Theorem.

Beweisidee:

Satz (smn-Theorem Û effektive Komposition):

Es sei y:IN®P⁽¹⁾ eine Numerierung von P⁽¹⁾, die das utm-Theorem erfüült Dann sind folgende Eigenschaften äquivalent:

1) y erfüllt das smn-Theorem.

2) Es gibt rÎR⁽²⁾ mit y_r(i,j)= y_i ° y_j.

ohne Beweis

Satz:

Es gibt keine totale surjektive Funktion y:IN®R⁽¹⁾ mit berechenbarer universeller Funktion.

Beweisidee:

Durch Diagonalisierung.

Frage:

Warum gilt dieser Satz nicht für j?

Satz:

Die berechenbare Funktion f:IN®IN mit f<i,x>:=u_j(i,x) hat keine Fortsetzung in R⁽¹⁾.

Beweisidee:

Würde dem Satz davor widersprechen.

Satz (Halteproblem):

Es gibt keine Funktion hÎR⁽²⁾ mit h(i,x)=1, falls j_i(x) ex., 0 sonst.

Beweisidee:

Würde dem Satz davor widersprechen.

KE 6

9 Rekursive und rekursiv-aufzählbare Mengen

Def (rekursive Menge):

Eine Menge AÍIN^k heißt rekursiv oder entscheidbar, gdw. die charakteristische Funktion cf_A berechenbar ist. Sie ist def. durch cf_A:IN^k®IN mit cf_A(x):=1, falls xÎA, 0 sonst

Satz:

A ist rek. gdw. es eine totale berechenbare Funktion fÎR^(k) gibt mit A=f^-1{0}.

Satz:

Sei A unendlich. A ist rek. gdw. es eine wachsende (monotone) berechenbare Funktion fÎR⁽¹⁾ gibt mit A=Bild(f).

Beweisidee:

Satz (Abschlußeigenschaften rekursiver Mengen):

1) Mit A₁ und A₂ sind auch IN^k\A₁, A₁ÈA₂ und A₁ÇA₂ rekursiv.

2) Sei A rekursiv und fÎR^(k). Dann ist f^-1(A) rekursiv.

3) A rekursiv Û p^(k)(A) rekursiv.

Def (rekursiv-aufzählbare Menge):

Eine Menge AÍIN^k heißt rekursiv-aufzählbar (r.a.), gdw. es eine partielle berechenbare Funktion f gibtmit A=Def(A).

Satz (Abschlußeigenschaften rekursiv-aufzählbarer Mengen):

1) Mit A₁ und A₂ sind auch A₁ÈA₂ und A₁ÇA₂ rekursiv.

2) Sei A r.a. und fÎP^(k). Dann ist f^-1(A) r.a.

3) A r.a. Û p^(k)(A) r.a.

Satz (Charakterisierung durch Bild, Projektionssatz):

1) A ist r.a. gdw. A=Æ oder A=Bild(g) für ein gÎR⁽¹⁾.

2) A ist r.a. gdw. A={x | ($t) (x,t)ÎB} für eine rek. Menge B.

3) A r.a. Û p^(k)(A) r.a.

Satz:

A ist rek. gdw. A und IN^k\A r.a. sind.

Satz (Selbstanwendbarkeitsproblem):

K_j:={i | j_i(i) existiert} ist r.a., aber nicht rek.

Beweisidee:

Satz (Halteproblem):

K_j⁰:={(i,x) | j_i(x) existiert} ist r.a., aber nicht rek.

Beweisidee:

Def. (Reduzierbarkeit):

A£B :Û es gibt ein fÎR⁽¹⁾ mit A=f^-1(B).

Dies läßt sich auch ausdrücken durch die Bedingung xÎA Û f(x)ÎB für alle x.

Satz von Rice:

Falls FÎP⁽¹⁾ und F¹Æ und F¹P⁽¹⁾, dann ist die Menge j^–1(F)={i | j_iÎF} nicht rek.

Das heißt, daß nur die Nummernmengen der trivialen Teilmengen aller ber. Funktionen rek. sind.

Satz (Korrektheitsproblem, Äquivalenzproblem):

Sei d def. durch d(i)=div für alle i.

1) Für jedes fÎP⁽¹⁾\{d} sind die Mengen M_f:={i | j_i =f} und IN\M_f={i | j_i ¹f} nicht r.a.

2) Die Mengen {(i,j) | j_i=j_j} und {(i,j) | j_i¹j_j} sind nicht r.a.

Satz (Postsches Korrespondenzproblem):

Satz:

1) Es gibt für jedes Beweissystem X Sätze der Form „1ⁿÏK_j“, die wahr, aber nicht beweisbar sind.

2) Man kann sogar mit einer berechenbaren Funktion zu einem beliebigen Beweissystem X die Nummer eines Satzes „1ⁿÏK_j“ berechnen, der wahr, aber nicht beweisbar ist.