RT Kapitel 1 Berechenbare Funktionen und Entscheidbare Prädikate

IF V_m=V_n GOTO q für m,n,q in N // Ohne IF wenn m=n=0

1. P := (Z₀,…,Z_l-1) // Ein Tupel von Anweisungen

2. PROG := {P}

1. var(P) // Alle Variablen die in P vorkommen

2. lg(P) // Länge von P als Tupel

1. Sehr einfaches Maschinenmodell

2. Lehnt sich an die von Neumannsche Rechnerarchitektur an

3. Ohne indirekte Adressierung des Speichers

1. Zu Beginn steht der Zähler auf der ersten Anweisung // Zeile 0

2. V₁,V₂,… sind Eingabevariablen

3. V₀ ist die Ausgabevariable

1. Anweisungen zeilenweise und nummeriert

2. Flussdiagramm

1. Belegung beta

2. Konfigurationen (q,beta)

3. Übergansrelation/-funktion

4. Berechnungsrelation

5. Konvergez und Divergenz

6. Berechenbare Funktionen (Definition 1.2, 1.13)

7. Entscheibare Prädikate/Relationen/Mengen (Definition 1.9)

8. Kodierungen

BEL := T(VAR,N) // Totale Abbildungen von VAR nach N

KONF := N x BEL // Erste Zahl ist die Zeilennummer

1. →_P \subseteq KONF x KONF

2. (q,b) →_P (q,b) falls q nicht in [0,l-1]

3. (q,b) →_P (q+1,b[V_n→0]) falls Z_q=V_n←0

4. (q,b) →_P (q+1,b[V_n→ b(V_n)+1]) falls Z_q=V_n←V_n+1

5. (q,b) →_P (q+1,b[V_n→ b(V_m)]) falls Z_q=V_n←V_m

6. (q,b) →_P (q+1,b) falls Z_q=IF V_m=V_n GOTO q‘ mit b(V_m)!=b(V_n)

7. (q,b) →_P (q‘,b) falls Z_q=IF V_m=V_n GOTO q‘ mit b(V_m)=b(V_n)

1. →_Pⁿ die n-fache Iteration von →_P

2. →_P^* = Cup_{n in N} →_Pⁿ // Die reflexive transitive Hülle

1. P(b)↓ ↔ \ex q>=lg(P), b‘ in BEL: (0,b)→_P^*(q,b‘) // P hält bei b

2. P(b)↑ ↔ !P(b)↓

3. P(b)↓b‘ \ex q>=lg(P): (0,b)→_P^*(q,b‘) // P definiert eine partielle Funktion von BEL nach BEL mit Definitionsbereich aller b in BEL mit P(b)↓

Ersetze b durch reele Zahlen

1. Pⁿ in P_n ist die von P berechnete n-stellige partielle Funktion Pⁿ(x):= y falls P(x)↓y, Ŧ falls P(x)↑

2. phi in P_n ist berechenbar falls P in PROG mit phi=Pⁿ existiert

3. B := {phi in P| phi ist berechenbar} und TB := T cut B = {phi in T| phi ist berechenbar}

4. f in P(D,D) ist berechenbar bezüglich gamma wenn g°f°g^-1 in P

1. Charakteristische Funktion von A \subseteq Nⁿ ist c_A in T_n mit c_A(x) := 1 falls A(x) sonst 0

2. A ist entscheidbar wenn c_A berechenbar ist

Explizite und effiktive bijektive Abbildung gamma:D→N

T\B != empty_set

1. T ist überabzählbar

2. PROG \subseteq {( ) , V _{0 1} ← 0 + 1 = I F G O T}* ist abzählbar

3. Mit PROG ist auch B abzählbar

1. F \subseteq P

2. GOTO-Programm über F ermöglicht Funktionsaufrufe

3. PROG(F) bezeichnet alle GOTO-Programme über F // Wenn endlich, kann F ersetzt werden

V_i ← phi(V_j1,…,V_jn) // Unterprogramm

(q,b) →_P (q+1,b[V_i→k]) falls Z_q=V_i←phi(V_j1,…,V_jn) mit phi(b(V_j1),…,b(V_jn))↓k

1. Auch Übergangsfunktion genannt

2. Nur partiell, da phi divergieren kann

Falls F \subseteq B, P in PROG(F) dann Pⁿ in B

1. Induktion über a Funktionsaufrufe in P

2. a=0: trivial

3. a→a+1

1. P=(Y₀,…,Y_k-1)

2. var(P) \subseteq {V₀,…,V_p-1} mit p>n

3. Sei Z_r=V_j0←phi(V_j1,…,V_jm) mit phi in F und Q=(Z₀,…,Z_l-1) mit Q^m=phi

4. Konstruiere P‘:=(Y₀‘,…,Y_k+l+m+2) mit P‘ⁿ=Pⁿ

1. Y_r‘ := GOTO k+1

2. Y_s‘ := Y_s außer wenn aus dem Programm gesprungen wird, dann wird q>=k durch k+l+m+3 ersetzt // Auch Y_k‘

3. Y_k+i‘ := V_p+i ← V_ji für i in [1,m]

4. Y_k+m+1+s‘ verschiebe um k+m+1 sonst um k+m+l+1

5. Y_k+m+l+1‘ := V_j0 ← V_p

6. Y_k+m+l+2‘ := GOTO r+1 // Zurück zur ehemaligen Ausführung

1. Klasse C \subseteq P ist abgeschlossen unter Substitution wenn n Parameter mittels m Funktionen psi als m Parameter an phi übergeben werden

2. l(x₁,…,x_n).phi(psi₁(x1,…,x_n),…,psi_m(x1,…,x_n)) in C_n

T ist abgeschlossen unter Substitution

B ist abgeschlossen unter Substitution

1. Definiere phi in B_m und psi₁,…,psi_m in B_n

2. PROG(phi,psi₁,…,psi_m) mit [i] V_n+i ← psi_i(V₁,…,V_n) und [m+1] V₀ ← phi(V_n+1,…,V_n+m)

3. Nach Satz 1.16 ist die Substitution b

1. Seien phi in P_n und psi in P_n+2

2. Es gibt genau eine Funktion gamma in P_n+1

3. Klasse C \subseteq P ist abgeschlossen unter primitiver Rekursion wenn für jedes paar phi, psi die Funktion gamma existiert

1. gamma(x,0)=phi(x)

2. gamma(x,y+1)=psi(x,y,gamma(x,y))

T ist abgeschlossen unter pR

B ist abgeschlossen unter pR