Turing-Mächtigkeit Flashcards
Definition Kontextfreie Grammatik (CFG)
Quadrupel (N, Σ, P, S) : N - Menge der Non-Terminal Symbole Σ - Terminal Alphabet P - Menge von Regeln der Form A ϵ N → w ϵ (Σ ∪ N)* S - Startsymbol ϵ N
Definition L(G)
Menge aller Wörter über Σ, die durch wiederholte Anwendung von Regeln in P aus dem Startsymbol hergeleitet werden können.
Die Probleme: Existiert w ϵ Σ*, w ϵ L(G)? / L(G) leer / L(G) endlich sind…
entscheidbar
Die Probleme: Ist G eindeutig? / L(G) = Σ* / L(G) regulär / L(G1) ⊆ L(G2) / L(G1) ∩ L(G2) sind…
unentscheidbar
Hilbertes 10. Problem
Konstruiere eine TM, die die folgende Sprache entscheidet:
Dioph = { Gödelnummer von p | p ist ein Polynom mit ganzzahligen Koeffizienten und mit mindestens einer ganzzahligen Nullstellen }
Die Sprache Dioph ist.. (entscheidbar/semi-entscheidbar/unentscheidbar)
rekursiv-aufzählbar
Algorithmus der Dioph erkennt:
Zähle die l-Tupel aus Z^l in kanonische Reihenfolge auf und werte p für dieses Tupel aus. Akzeptiere sobald eine dieser Auswertungen den Wert 0 gibt.
Satz von Matiyasevich
Das Problem, ob ein ganzzahliges Polynom eine ganzzahlige Nullstelle besitzt, ist unentscheidbar.
Ganzzahlige Polynome sind.. (weniger/genau so/mehr) mächtig als TM.
genau so
Ein Rechnermodell wird als Turing-mächtig bezeichnet, wenn
jede Funktion, die durch eine TM berechnet werden kann, auch durch dieses Modell berechnet werden kann.
Turing-mächtige Rechnermodelle:
RAM, Mini-RAM, höhere Programmiersprachen, μ-rekursive Funktionen, Lamba Kalkulus, Conway’s Game of Life, die Programmiersprache WHILE
Definition Mini-RAM
eingeschränkte Variante der RAM mit nur 8 Befehlen und mit einer endlichen Anzahl von Registern
