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
Fichier Détails
| Cartes-fiches | 99 |
|---|---|
| Langue | Deutsch |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 26.02.2017 / 24.07.2020 |
| Lien de web |
https://card2brain.ch/box/20170226_ait_chapter_2_peertopeer_systems_2
|
| Intégrer |
<iframe src="https://card2brain.ch/box/20170226_ait_chapter_2_peertopeer_systems_2/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Créer ou copier des fichiers d'apprentissage
Avec un upgrade tu peux créer ou copier des fichiers d'apprentissage sans limite et utiliser de nombreuses fonctions supplémentaires.
Connecte-toi pour voir toutes les cartes.
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
-
