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
Liste sie auf!
[syntax.GOTOProgramme, 3]
1. Variablen
2. Anweisungen
3. Programme
Was ist die Definition?
[variablen.syntax.GOTOProgramme]
VAR := {V0,V1,V2,…}
Liste sie auf?
[anweisungen.syntax.GOTOProgramme, 4]
1. Nullanweisung
2. Nachfolgeranweisung
3. Transferanweisung
4. Sprunganweisung
Was ist die Definition?
[null.anweisungen.syntax.GOTOProgramme]
Vn ← 0 für n in N
Was ist die Definition?
[nachfolger.anweisungen.syntax.GOTOProgramme]
Vn ← Vn+1 für n in N
Was ist die Definition?
[transfer.anweisungen.syntax.GOTOProgramme]
Vn ← Vm für m,n in N
Was ist die Definition?
[sprung.anweisungen.syntax.GOTOProgramme]
IF Vm=Vn GOTO q für m,n,q in N // Ohne IF wenn m=n=0
Was ist die Definition?
[programme.syntax.GOTOProgramme, 2]
1. P := (Z0,…,Zl-1) // Ein Tupel von Anweisungen
2. PROG := {P}
Was ist die Definition?
[parameter.programme.syntax.GOTOProgramme, 2]
1. var(P) // Alle Variablen die in P vorkommen
2. lg(P) // Länge von P als Tupel
Was sind die Eigenschaften?
[registermaschinen.semantik.GOTOProgramme, 3]
1. Sehr einfaches Maschinenmodell
2. Lehnt sich an die von Neumannsche Rechnerarchitektur an
3. Ohne indirekte Adressierung des Speichers
Was sind die Anweisungen?
[registermaschinen.semantik.GOTOProgramme, 3]
1. Zu Beginn steht der Zähler auf der ersten Anweisung // Zeile 0
2. V1,V2,… sind Eingabevariablen
3. V0 ist die Ausgabevariable
Liste sie auf!
[darstellung.registermaschinen.semantik.GOTOProgramme, 2]
1. Anweisungen zeilenweise und nummeriert
2. Flussdiagramm
Liste sie auf!
[semantik.GOTOProgramme, 8]
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
Was ist die Definition?
[belegung.semantik.GOTOProgramme]
BEL := T(VAR,N) // Totale Abbildungen von VAR nach N
Was ist die Definition?
[konfigurationen.semantik.GOTOProgramme]
KONF := N x BEL // Erste Zahl ist die Zeilennummer
Was ist die Definition?
[übergansrelation.semantik.GOTOProgramme, 1+6]
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[Vn→0]) falls Zq=Vn←0
4. (q,b) →P (q+1,b[Vn→ b(Vn)+1]) falls Zq=Vn←Vn+1
5. (q,b) →P (q+1,b[Vn→ b(Vm)]) falls Zq=Vn←Vm
6. (q,b) →P (q+1,b) falls Zq=IF Vm=Vn GOTO q‘ mit b(Vm)!=b(Vn)
7. (q,b) →P (q‘,b) falls Zq=IF Vm=Vn GOTO q‘ mit b(Vm)=b(Vn)
Was ist die Definition?
[berechnungsrelation.semantik.GOTOProgramme, 2]
1. →Pn die n-fache Iteration von →P
2. →P* = Cupn in N →Pn // Die reflexive transitive Hülle
Was ist die Definition?
[konvergenzdivergenz.semantik.GOTOProgramme, 2+1]
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)↓
Was ist die Definition?
[notation.konvergenzdivergenz.semantik.GOTOProgramme]
Ersetze b durch reele Zahlen
Was ist die Definition?
[berechenbarefunktionen.semantik.GOTOProgramme, 3+1]
1. Pn in Pn ist die von P berechnete n-stellige partielle Funktion Pn(x):= y falls P(x)↓y, Ŧ falls P(x)↑
2. phi in Pn ist berechenbar falls P in PROG mit phi=Pn 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
Was ist die Definition?
[entscheidbareprädikate.semantik.GOTOProgramme, 2]
1. Charakteristische Funktion von A \subseteq Nn ist cA in Tn mit cA(x) := 1 falls A(x) sonst 0
2. A ist entscheidbar wenn cA berechenbar ist
Was ist die Definition?
[kodierungen.semantik.GOTOProgramme]
Explizite und effiktive bijektive Abbildung gamma:D→N
Was ist die Definition?
[satz1_8.semantik.GOTOProgramme]
T\B != empty_set
Beschreibe den Beweis!
[satz1_8.semantik.GOTOProgramme, 3]
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
Liste sie auf!
[syntax.GOTOUnterprogramme, 3]
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
Was ist die Definition?
[funktionsaufruf.syntax.GOTOUnterprogramme]
Vi ← phi(Vj1,…,Vjn) // Unterprogramm
Was ist die Definition?
[übergangsrelation.semantik.GOTOUnterprogramme]
(q,b) →P (q+1,b[Vi→k]) falls Zq=Vi←phi(Vj1,…,Vjn) mit phi(b(Vj1),…,b(Vjn))↓k
Was sind die Eigenschaften?
[übergangsrelation.semantik.GOTOUnterprogramme, 2]
1. Auch Übergangsfunktion genannt
2. Nur partiell, da phi divergieren kann
Was ist die Definition?
[satz1_16.semantik.GOTOUnterprogramme]
Falls F \subseteq B, P in PROG(F) dann Pn in B
Beschreibe den Beweis!
[satz1_16.semantik.GOTOUnterprogramme, 3]
1. Induktion über a Funktionsaufrufe in P
2. a=0: trivial
3. a→a+1
Beschreibe den Beweis!
[a→a+1.satz1_16.semantik.GOTOUnterprogramme, 3+1]
1. P=(Y0,…,Yk-1)
2. var(P) \subseteq {V0,…,Vp-1} mit p>n
3. Sei Zr=Vj0←phi(Vj1,…,Vjm) mit phi in F und Q=(Z0,…,Zl-1) mit Qm=phi
4. Konstruiere P‘:=(Y0‘,…,Yk+l+m+2) mit P‘n=Pn
Was ist die Definition?
[P‘.a→a+1.satz1_16.semantik.GOTOUnterprogramme, 6]
1. Yr‘ := GOTO k+1
2. Ys‘ := Ys außer wenn aus dem Programm gesprungen wird, dann wird q>=k durch k+l+m+3 ersetzt // Auch Yk‘
3. Yk+i‘ := Vp+i ← Vji für i in [1,m]
4. Yk+m+1+s‘ verschiebe um k+m+1 sonst um k+m+l+1
5. Yk+m+l+1‘ := Vj0 ← Vp
6. Yk+m+l+2‘ := GOTO r+1 // Zurück zur ehemaligen Ausführung
Was ist die Definition?
[substitution.prfunktionen, 2]
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(x1,…,xn).phi(psi1(x1,…,xn),…,psim(x1,…,xn)) in Cn
Was ist die Definition?
[lemma1_18.substitution.prfunktionen]
T ist abgeschlossen unter Substitution
Was ist die Definition?
[lemma1_19.substitution.prfunktionen]
B ist abgeschlossen unter Substitution
Beschreibe den Beweis!
[lemma1_19.substitution.prfunktionen, 3]
1. Definiere phi in Bm und psi1,…,psim in Bn
2. PROG(phi,psi1,…,psim) mit [i] Vn+i ← psii(V1,…,Vn) und [m+1] V0 ← phi(Vn+1,…,Vn+m)
3. Nach Satz 1.16 ist die Substitution b
Was ist die Definition?
[pr.prfunktionen, 3]
1. Seien phi in Pn und psi in Pn+2
2. Es gibt genau eine Funktion gamma in Pn+1
3. Klasse C \subseteq P ist abgeschlossen unter primitiver Rekursion wenn für jedes paar phi, psi die Funktion gamma existiert
Was ist die Definition?
[gamma.pr.prfunktionen, 2]
1. gamma(x,0)=phi(x)
2. gamma(x,y+1)=psi(x,y,gamma(x,y))
Was ist die Definition?
[lemma1_20.pr.prfunktionen]
T ist abgeschlossen unter pR
Was ist die Definition?
[lemma1_21.pr.prfunktionen]
B ist abgeschlossen unter pR
