RT Kapitel 1 Berechenbare Funktionen und Entscheidbare Prädikate

Klasse PR \subseteq T ist die kleinste Klasse von Funktionen, die alle Basisfunktionen enthält und abgeschlossen ist unter Substitution und primitiver Rekursion

PR \subseteq TB

1. Für alle sigma:[n]→[n] ist l(x₁,…,x_n).f(x_sigma(1),…,x_sigma(n)) pr

2. Die Funktion l(x₁,…,x_n+1).f(x₁,…,x_n) ist pr

x_sigma(i) = U_sigma(i)ⁿ(x₁,…,x_n)

1. Sei h in T_n+1 definiert als h(x₁,…,x_n,y):=f(x₁,…,x_n)

2. h is die aus f und U_n+2ⁿ⁺² durch pR definierter Funktion

1. Sei phi in B_m+1, psi in B_n und gamma in P_m+n definiert als gamma(x₁,…,x_m,y₁,…,y_n) := phi(x₁,…,x_m,psi(y₁,…,y_n))

2. Dann gilt gamma in B

3. Falls phi,psi in TB, dann auch gamma

4. Falls phi,psi in PR, dann auch gamma

1. Sei eps in P_m+n definiert als eps(x,y):=psi(U_m+1^m+n(x,y),…,U_m+n^m+n(x,y))

2. Dann ist eps(x,y)=psi(y)

3. Dann ist gamma(x,y)=phi(U₁^m+n(x,y),…,U_m^m+n(x,y), eps(x,y))

A \subseteq Nⁿ ist primtiv rekursiv wenn c_A in PR

1. Seien f₁,…,f_k+1 in TB (bzw. PR) und A₁,…,A_k \subseteq Nⁿ paarweise disjunkt und e (bzw. pr)

2. Sei g in T_n definiert durch f_i(x) falls x in A_i und f_k+1(x) sonst

3. Dann ist g in TB (bzw. in PR)

g(x)=c_A1(x)*f₁(x) + … + c_Ak(x)*f_k(x) + (1-Sum_i=1^kc_Ai(x))*f_k+1(x)

Die Klasse der entscheibaren Prädikate und die Klasse der pr Prädikate enthalten TRUE und FALSE und sind abgeschlossen unter Konjunktion, Disjunktion und Negation

1. c_TRUE=1 und c_FALSE=0

2. Für A=¬B gilt c_A(x)=1-c_B(x)

3. Für A(x)↔B(x‘) \land C(x‘‘) gilt nach Lemma 1.25 B‘=l(x).B(x‘) und C‘=l(x).C(x‘‘) mit c_A(x)=c_B‘(x)*c_C‘(x)

4. Für Disjunktion verwenden wir die de Morgansche Regel mit c_{B \lor C}(x) = 1-c_{¬B \land C}(x)

Die Klassen der entscheibaren und primtiv rekursiven Mengent enthalten emptySet, N und sind abgeschlossen unter Durchschnitt, Vereinigung und Komplementboldung in N

1. Summen

2. Produkte

3. Quantoren

4. Minimalisierung

1. Seien phi,psi in T_n+1

2. psi(x,0):=0

3. psi(x,y+1):=psi(x,y)+phi(x,y)

1. Damit ist Sum_z<yphi(x,z)=psi(x,y) // phi ist die Summe aller relevanten psi

2. Falls phi in PR so auch l(x,y).Sum_z<yphi(x,z)

3. Falls phi in TB so auch l(x,y).Sum_z<yphi(x,z)

1. Prod_z<0phi(x,z):=1

2. Prod_z<y+1phi(x,z):=Prod_z<yphi(x,z)*phi(x,y)

1. Falls phi in PR so auch l(x,y).Prod_<yphi(x,z)

2. Falls phi in TB so auch l(x,y).Prod _<yphi(x,z)

1. Seien A,B \subseteq Nⁿ⁺¹ mit B(x,y) ↔ \ex z<y A(x,z)

2. Dann gilt c_B(x,y)=sg(Sum_z<yc_A(x,z))

1. l(x,y).\ex z<y A(x,z) e wenn A e

2. l(x,y).\ex z<y A(x,z) pr wenn A pr

Entsprechend definiert

Die Mengen der e und pr Prädikate sind abgeschlossen unter Disjunktion, Konjunktion, Negation und beschränkter Quantifikation

1. Sei A \subseteq Nⁿ⁺¹

2. mye z<y A(x,z):= min{z<y|A(x,z)} falls \ex z und sonst y

3. Dann gilt mye z<y A(x,z)=Sum_v<yProd_u<=v(1-c_A(x,u))

1. l(x,y).mye z<y A(x,z) in TB wenn A e

2. l(x,y).mye z<y A(x,z) in PR wenn A pr

<x,y>:=1/2(x+y+1)*(x+y) +y

Die Paarfunktion l(x,y).<x,y> ist bijektiv

1. Es gilt <x,y>=Sum_i=0^x+y i+y

2. Falls y>0 gilt <x,y>-<x+1,y-1>=1

3. Außerdem gilt <y+1,0>-<0,y>=1

4. Injektivität

5. Surjektivität

1. Angenommen die Paarfunktion sei nicht injektiv

2. Sei p minimal mit p=<x,y>=<x‘,y‘> mit (x,y)!=(x‘,y‘)

3. ObdA gilt y<y‘ mit x>x‘

4. Falls y>0 so <x+1,y-1>=p-1=<x‘+1,y‘-1> mit p nicht minimal

5. Also y=0 → p = Sum_i=0^xi = Sum_i=0^x‘+y‘i+y‘

6. x‘+y‘<x und y‘=Sum_{i=x‘+y‘+1}^xi // Weil y<y‘

7. Unmöglich weil Sum_{i=x‘+y‘+1}^xi >= y‘+1 > y‘

1. Induktion über p zeigt \fa p in N \ex x,y in N: p=<x,y>

2. p=0: 0=<0,0>

3. p→p+1:

1. Sei p=<x,y>

2. Falls x>0, so p+1=<x-1,y+1>

3. Falls x=0, so p+1=<y+1,0>

1. Seien pi₁, pi₂ in T₁

2. pi₁(z) := mye x<=z \ex y<=z: z=<x,y>

3. pi₂(z) := mye y<=z \ex x<=z: z=<x,y>

4. Wegen Lemma 1.37 gilt für alle x,y in N pi₁(<x,y>)=x und pi₂(<x,y>)=y

Die Paarfunktion und die Projektionen sind pr

1. l(x₁,…,x_n).<x₁,…,x_n>_n in T_n

2. <x>₁:=x

3. <x₁,…,x_n+1>_n+1:=<x₁,<x₂,…,x_n+1>_n>

Funktion l(x).<x>_n ist bijektiv