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
-
Flashcards
Beschreibe den Beweis!
[lemma1_21.pr.prfunktionen, 2]
1. gamma lässt sich in einem Flussdiagramm von PROG(phi,psi) zeigen
2. Nach Satz 1.16 ist die primitive Rekursion b
Liste sie auf!
[basisfunktionen.prfunktionen, 3]
1. Nullfunktion
2. Nachfolgerfunktion
3. Projektion
Was ist die Definition?
[null.basisfunktionen.prfunktionen]
0 in T0
Was ist die Definition?
[nachfolger.basisfunktionen.prfunktionen]
S:= lx.x+1 in T1
Was ist die Definition?
[projektion.basisfunktionen.prfunktionen]
Uin in Tn definiert durch Uin(x1,…,xn) := xi
Was ist die Definition?
[lemma1_22.basisfunktionen.prfunktionen]
Alle Basisfunktionen sind b
Was ist die Definition?
[prfunktionen.prfunktionen]
Klasse PR \subseteq T ist die kleinste Klasse von Funktionen, die alle Basisfunktionen enthält und abgeschlossen ist unter Substitution und primitiver Rekursion
Was ist die Definition?
[satz1_24.prfunktionen.prfunktionen]
PR \subseteq TB
Was ist die Definition für f in PRn?
[lemma1_25.prfunktionen.prfunktionen, 2]
1. Für alle sigma:[n]→[n] ist l(x1,…,xn).f(xsigma(1),…,xsigma(n)) pr
2. Die Funktion l(x1,…,xn+1).f(x1,…,xn) ist pr
Beschreibe den Beweis!
[1.lemma1_25.prfunktionen.prfunktionen]
xsigma(i) = Usigma(i)n(x1,…,xn)
Beschreibe den Beweis!
[2.lemma1_25.prfunktionen.prfunktionen, 2]
1. Sei h in Tn+1 definiert als h(x1,…,xn,y):=f(x1,…,xn)
2. h is die aus f und Un+2n+2 durch pR definierter Funktion
Was ist die Definition?
[lemma1_27.prfunktionen.prfunktionen, 4]
1. Sei phi in Bm+1, psi in Bn und gamma in Pm+n definiert als gamma(x1,…,xm,y1,…,yn) := phi(x1,…,xm,psi(y1,…,yn))
2. Dann gilt gamma in B
3. Falls phi,psi in TB, dann auch gamma
4. Falls phi,psi in PR, dann auch gamma
Beschreibe den Beweis!
[lemma1_27.prfunktionen.prfunktionen, 3]
1. Sei eps in Pm+n definiert als eps(x,y):=psi(Um+1m+n(x,y),…,Um+nm+n(x,y))
2. Dann ist eps(x,y)=psi(y)
3. Dann ist gamma(x,y)=phi(U1m+n(x,y),…,Umm+n(x,y), eps(x,y))
Was ist die Definition?
[prprädikate.prfunktionen]
A \subseteq Nn ist primtiv rekursiv wenn cA in PR
Was ist die Definition durch Fallunterscheidung?
[lemma1_32.prfunktionen, 3]
1. Seien f1,…,fk+1 in TB (bzw. PR) und A1,…,Ak \subseteq Nn paarweise disjunkt und e (bzw. pr)
2. Sei g in Tn definiert durch fi(x) falls x in Ai und fk+1(x) sonst
3. Dann ist g in TB (bzw. in PR)
Beschreibe den Beweis!
[lemma1_32.prfunktionen]
g(x)=cA1(x)*f1(x) + … + cAk(x)*fk(x) + (1-Sumi=1kcAi(x))*fk+1(x)
Was ist die Definition Quantorenfreie Logik?
[lemma1_33.prfunktionen]
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
Beschreibe den Beweis!
[lemma1_33.prfunktionen, 4]
1. cTRUE=1 und cFALSE=0
2. Für A=¬B gilt cA(x)=1-cB(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 cA(x)=cB‘(x)*cC‘(x)
4. Für Disjunktion verwenden wir die de Morgansche Regel mit cB \lor C(x) = 1-c¬B \land C(x)
Was ist die Definition Mengenalgebra?
[korollar1_34.prfunktionen]
Die Klassen der entscheibaren und primtiv rekursiven Mengent enthalten emptySet, N und sind abgeschlossen unter Durchschnitt, Vereinigung und Komplementboldung in N
Liste sie auf!
[beschränkt.prfunktionen, 4]
1. Summen
2. Produkte
3. Quantoren
4. Minimalisierung
Was ist die Definition?
[summen.beschränkt.prfunktionen, 3]
1. Seien phi,psi in Tn+1
2. psi(x,0):=0
3. psi(x,y+1):=psi(x,y)+phi(x,y)
Was folgt?
[summen.beschränkt.prfunktionen, 3]
1. Damit ist Sumz<yphi(x,z)=psi(x,y) // phi ist die Summe aller relevanten psi
2. Falls phi in PR so auch l(x,y).Sumz<yphi(x,z)
3. Falls phi in TB so auch l(x,y).Sumz<yphi(x,z)
Was ist die Definition?
[produkte.beschränkt.prfunktionen, 2]
1. Prodz<0phi(x,z):=1
2. Prodz<y+1phi(x,z):=Prodz<yphi(x,z)*phi(x,y)
Was folgt?
[produkte.beschränkt.prfunktionen, 2]
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)
Was ist die Definition?
[existenz.quantoren.beschränkt.prfunktionen, 2]
1. Seien A,B \subseteq Nn+1 mit B(x,y) ↔ \ex z<y A(x,z)
2. Dann gilt cB(x,y)=sg(Sumz<ycA(x,z))
Was ist folgt?
[existenz.quantoren.beschränkt.prfunktionen, 2]
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
Was ist die Definition?
[global.quantoren.beschränkt.prfunktionen]
Entsprechend definiert
Was ist die Definition?
[lemma1_35.beschränkt.prfunktionen, 2]
Die Mengen der e und pr Prädikate sind abgeschlossen unter Disjunktion, Konjunktion, Negation und beschränkter Quantifikation
Was ist die Definition?
[minimalisierung.beschränkt.prfunktionen, 3]
1. Sei A \subseteq Nn+1
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)=Sumv<yProdu<=v(1-cA(x,u))
Was folgt?
[minimalisierung.beschränkt.prfunktionen, 2]
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
Was ist die Definition der Paarfunktion?
[kodierungpaaren.prfunktion]
<x,y>:=1/2(x+y+1)*(x+y) +y
Was ist die Definition?
[lemma1_37.kodierungpaaren.prfunktion]
Die Paarfunktion l(x,y).<x,y> ist bijektiv
Beschreibe den Beweis!
[lemma1_37.kodierungpaaren.prfunktion, 3+2]
1. Es gilt <x,y>=Sumi=0x+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
Beschreibe den Beweis!
[injektivität.lemma1_37.kodierungpaaren.prfunktion, 7]
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 = Sumi=0xi = Sumi=0x‘+y‘i+y‘
6. x‘+y‘<x und y‘=Sumi=x‘+y‘+1xi // Weil y<y‘
7. Unmöglich weil Sumi=x‘+y‘+1xi >= y‘+1 > y‘
Beschreibe den Beweis!
[surjektivität.lemma1_37.kodierungpaaren.prfunktion, 3]
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:
Beschreibe den Beweis!
[p→ p+1.surjektivität.lemma1_37.kodierungpaaren.prfunktion, 3]
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>
Was ist die Definition?
[projektiongpaaren.prfunktion, 4]
1. Seien pi1, pi2 in T1
2. pi1(z) := mye x<=z \ex y<=z: z=<x,y>
3. pi2(z) := mye y<=z \ex x<=z: z=<x,y>
4. Wegen Lemma 1.37 gilt für alle x,y in N pi1(<x,y>)=x und pi2(<x,y>)=y
Was ist die Definition?
[lemma1_38.projektiongpaaren.prfunktion]
Die Paarfunktion und die Projektionen sind pr
Was ist die Definition?
[kodierungtupel.prfunktion, 3]
1. l(x1,…,xn).<x1,…,xn>n in Tn
2. <x>1:=x
3. <x1,…,xn+1>n+1:=<x1,<x2,…,xn+1>n>
Was ist die Definition?
[lemma1_39.kodierungtupel.prfunktion]
Funktion l(x).<x>n ist bijektiv
