RT Kapitel 1 Berechenbare Funktionen und Entscheidbare Prädikate
Fragen zur Vorlesung 'Recursion Theory' an der RWTH Aachen Kapitel 1 Berechenbare Funktionen und Entscheidbare Prädikate
Fragen zur Vorlesung 'Recursion Theory' an der RWTH Aachen Kapitel 1 Berechenbare Funktionen und Entscheidbare Prädikate
-
- 1 / 99
-
Lernkarten
Was ist die Definition?
[projektiontupel.prfunktion, 3]
1. Seien für alle n>=1 und i in [n] Projektion piin in T1
2. piin(z):=mye xi<=z \ex x1,…,xi-1,xi+1,…,xn<=z : z=<x1,…,xn>n
3. Dann gilt piin(<x1,…,xn>n)=xi
Was ist die Definition?
[lemma1_39.projektiontupel.prfunktion]
Funktion l(x).<x>n ist pr
Was ist die Definition?
[ackermann, 3]
1. a(0,y) := y+1
2. a(x+1,0) := a(x,1)
3. a(x+1,y+1) := a(x,a(x+1,y))
Was sind die Eigenschaften?
[ackermann, 2]
1. Wohldefiniert und sicherlich „intuitiv b“
2. Es wird gezeigt, dass sie (auch formal) b ist
Was ist die Definition?
[satz1.42.ackermann]
Sie ist nicht pr
Was ist die Idee des Beweises?
[satz1.42.ackermann, 3]
1. a wächst schneller als jede pr Funktion
2. Wir zeigen \fa f in PR1 \ex c in N: f(x) < a(c,x)
3. Daraus folgt lx.a(x,x) not in PR1 und damit a not in PR
Beschreibe den Beweis!
[satz1.42.ackermann, 4]
1. Angenommen a in PR
2. →L1.25 lx.a(x,x) in PR
3. →L1.49 \ex c in N \fa x in N: a(x,x)<a(c,x)
4. Sei x to c+1, das widerspricht L1.46
Was ist die Definition?
[lemma1.43.ackermann]
\fa x,y, in N: y<a(x,y)
Was ist die Definition?
[lemma1.44.ackermann]
\fa x,y, in N: a(x,y)<a(x,y+1)
Beschreibe den Beweis!
[lemma1.44.ackermann, 2]
1. a(0,y)=y+1 < y+2=a(0,y+1)
2. a(x+1,y) <L1.43 a(x,a(x+1,y))=a(x+1,y+1)
Was ist die Definition?
[lemma1.45.ackermann]
\fa x,y in N: a(x,y+1) <= a(x+1,y)
Was ist die Definition?
[lemma1.46.ackermann]
\fa x,y in N: a(x,y)<a(x+1,y)
Beschreibe den Beweis!
[lemma1.46.ackermann]
a(x,y) <L1.44 a(x,y+1) <=L1.45 a(x+1,y)
Was ist die Definition?
[lemma1.47.ackermann]
\fa y in N: [1] a(1,y)=y+2 und [2] a(2,y)=2y+3
Was ist die Definition?
[lemma1.48.ackermann]
\fa k und c1,…,ck in N \ex c in N mit \fa y: Sumi=1k a(ci,y) <= a(c,y)
Was ist die Definition?
[lemma1.49.ackermann]
\fa f in Prn \ex c in N mit f(x)<a(c,x)
Was sind die Eigenschaften?
[lemma1.49.ackermann, 1+2]
1. f ensteht aus g und h durch pR
2. f(x,0)=g(x)
3. f(x,y+1)=h(x,y,f(x,y))
Was ist die Definition?
[behauptung1.ackermann]
\ex c1 mit g(x)+Sumi=1nxi < A(c1,Sumi=1nxi)
Was ist die Definition?
[behauptung2.ackermann]
\ex c2 mit h(x,y,z)+Sumi=1nxi+y<A(c2,Sumi=1nxi+y+z)
