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
Kartei Details
| Karten | 99 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 26.02.2017 / 24.07.2020 |
| Weblink |
https://card2brain.ch/box/20170226_ait_chapter_2_peertopeer_systems_2
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170226_ait_chapter_2_peertopeer_systems_2/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Lernkarteien erstellen oder kopieren
Mit einem Upgrade kannst du unlimitiert Lernkarteien erstellen oder kopieren und viele Zusatzfunktionen mehr nutzen.
Melde dich an, um alle Karten zu sehen.
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)
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
-
- 1 / 99
-
