Sei
. Wofür steht
? Was ist eine Sprache über dem Alphabet
?
![](/pool/data/tex/a3acfcce12167fd1946d19ee1add570d.gif)
![](/pool/data/tex/5f1f202fa36d69fca7cc260e1befa0de.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/031010e9f2111e92d564b794ab7b96be.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/0fddcf8bfa0f88ab10d3195a363a42a1.gif)
![](/pool/data/tex/3a1ef81ee3e8f4b386f457813ae8eaa9.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
Eine Sprache ist eine Menge von Wörter über
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
Primfaktorbestimmung: Modellierung als Relation
Eingabe: eine binär kodierte Zahl ![](/pool/data/tex/25e3bf0a980a68e0a6438ca6458cf807.gif)
Ausgabe: ein binär kodierter Primfaktor von p
Relation
mit
![](/pool/data/tex/bbf415619a4a486300892f61d0420a25.gif)
=> es gibt mehrer mögliche Ausgaben, deshalb als Relation modelliert
![](/pool/data/tex/25e3bf0a980a68e0a6438ca6458cf807.gif)
Ausgabe: ein binär kodierter Primfaktor von p
Relation
![](/pool/data/tex/71eabea827ef823bc2645f881b2f6899.gif)
![](/pool/data/tex/bbf415619a4a486300892f61d0420a25.gif)
=> es gibt mehrer mögliche Ausgaben, deshalb als Relation modelliert
Multiplikation: Modellierung als Funktion
Eingabe: zwei binär kodierte Zahlen ![](/pool/data/tex/ef5a3bc537dcbf7a6220b29a94774d71.gif)
Ausgabe: die binär kodierte Zahl![](/pool/data/tex/5a2bcad812d995fdce0392566327fc82.gif)
=>es gibt nur eine eindeutige Ausgabe, deshalb Modellierung als Funktion:
Die zur Eingabe
gesuchte Ausgabe ist in diesem Fall
.
Führe dazu zum Alphabet ein Trennsymbol # ein:![](/pool/data/tex/8a6326094ff5a895986cb120ed1a1a0d.gif)
Eingabe ist dann kodiert als:![](/pool/data/tex/df98619702afe7c35079b5f48be47768.gif)
und Ausgabe![](/pool/data/tex/54bb62a1c9cb5664be95ec50a83a77e1.gif)
![](/pool/data/tex/ef5a3bc537dcbf7a6220b29a94774d71.gif)
Ausgabe: die binär kodierte Zahl
![](/pool/data/tex/5a2bcad812d995fdce0392566327fc82.gif)
=>es gibt nur eine eindeutige Ausgabe, deshalb Modellierung als Funktion:
![](/pool/data/tex/d749746452a0bf06a90f83f3cfc739f4.gif)
![](/pool/data/tex/0c45e03bcc795af48f72c87b6a40ee3b.gif)
![](/pool/data/tex/538656a3e1175f81e1d7fd321234b01b.gif)
Führe dazu zum Alphabet ein Trennsymbol # ein:
![](/pool/data/tex/8a6326094ff5a895986cb120ed1a1a0d.gif)
Eingabe ist dann kodiert als:
![](/pool/data/tex/df98619702afe7c35079b5f48be47768.gif)
und Ausgabe
![](/pool/data/tex/54bb62a1c9cb5664be95ec50a83a77e1.gif)
Entscheidungsproblem
=>Problem mit "Ja-Nein-Frage"
![](/pool/data/tex/bd7e461a3bb6113d3a6170bffbfcae09.gif)
Ja Antworten sind 1 und Nein Antworten sind 0.
ist Menge der Eingaben mit Ja-Antwort und ist Teilmende der Wörter über
. Diese Teilmenge ist eine Sprache.
![](/pool/data/tex/bd7e461a3bb6113d3a6170bffbfcae09.gif)
Ja Antworten sind 1 und Nein Antworten sind 0.
![](/pool/data/tex/2361308a55e1e51767c00f30e5eff522.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
Graphzusammenhang: Modellierung eines Entscheidungsproblems
Eingabe: die Kodierung eines Graphen G =(V,E)
Ausgabe: 1, falls G zusammenhängend. 0, sonst
Kodierung: Als Adjazenzmatrix unter der Annahme, dass diese einen Graph bereits korrekte Kodierung eines Graphen ist
G: Menge aller Graphen
: Menge aller zusammenhängender Graphen
![](/pool/data/tex/4175b403cfe699549280939340ed69c1.gif)
Ausgabe: 1, falls G zusammenhängend. 0, sonst
Kodierung: Als Adjazenzmatrix unter der Annahme, dass diese einen Graph bereits korrekte Kodierung eines Graphen ist
G: Menge aller Graphen
![](/pool/data/tex/cfad124bda4ba030cb6b6453288f9e91.gif)
![](/pool/data/tex/4175b403cfe699549280939340ed69c1.gif)
Definition des Turingmachinenmodells
=> man geht von unbeschränkter Rechenzeit und Speicher aus
ist definiert durch das 7-Tupel![](/pool/data/tex/b0349503cd01097777f5594ac970572c.gif)
Am Anfang der Rechnung befindet sich die TM im Anfangszustand, auf dem Band steht von links nach rechts die Eingabe in benachbarten Zellen, alle anderen Zellen links und rechts der Eingabe enthalten Leerzeichen, und der Kopf steht unter dem ersten Zeichen der Eingabe.
ist definiert durch das 7-Tupel
![](/pool/data/tex/b0349503cd01097777f5594ac970572c.gif)
![]() | endliche Zustandsmenge |
![]() | endliches Eingabealphabet |
![]() | endliches Bandalphabet |
![]() | Blanksymbol |
![]() | Anfangszustand |
![]() | Stoppzustand |
![]() | Zustandsübergangsfunktion |
Rechenschritt
![](/pool/data/tex/a6a3dd02dc17e3c127a811a7be5aca8d.gif)
Wenn der aktuelle Zustand der TM q ist und der Kopf auf einer Zelle mit Inhalt a steht, dann schreibt die TM den Buchstaben a', wechselt in den Zustand q' und geht eine Position d=(L,R,N) weiter.
Es wird solange ein Rechenschritt nach dem anderen ausgeführt bis der Stoppzustand
![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
Konfiguration (direkte) Nachfolgekonfiguration
"Schnappschuss" der Rechnung zu einem bestimmten Zeitpunkt
Konfiguration: ist ein String
mit
und ![](/pool/data/tex/922f1619403522e7398c20cd37d32c66.gif)
auf dem Band steht
eingerahmt von Blanks und der Zustand ist q und der Kopf steht unter dem ersten Zeichen von ![](/pool/data/tex/b0603860fcffe94e5b8eec59ed813421.gif)
Bsp.: 000
1011 Kopf steht auf rot
direkte Nachfolgekonfiguration:
ist d.Nkonf. von
, falls
in einem Rechenschritt aus
entsteht: ![](/pool/data/tex/788c7c4f71ad57fd4b2ccca697558964.gif)
Nachfolgekonfiguration:
von
, falls
in endlich vielen Rechenschritten aus
entsteht.
![](/pool/data/tex/4a03166d751743dcd558ccf1b503cbb4.gif)
Die Rechnung terminiert, wenn Stoppzustand erreicht ist. Dann gibt es keine Nachfolgekonfiguration.
Konfiguration: ist ein String
![](/pool/data/tex/d25187a741809c52aa384463aea554dd.gif)
![](/pool/data/tex/6bce8dea34dca6de99f898552ac31489.gif)
![](/pool/data/tex/922f1619403522e7398c20cd37d32c66.gif)
auf dem Band steht
![](/pool/data/tex/f38e6ffe43515f07a92c862469cbb2ef.gif)
![](/pool/data/tex/b0603860fcffe94e5b8eec59ed813421.gif)
Bsp.: 000
![](/pool/data/tex/fa043c065dd111d926a3d140b618b05e.gif)
direkte Nachfolgekonfiguration:
![](/pool/data/tex/f16069491f5e68a71ab4d4807d3e0290.gif)
![](/pool/data/tex/d25187a741809c52aa384463aea554dd.gif)
![](/pool/data/tex/f16069491f5e68a71ab4d4807d3e0290.gif)
![](/pool/data/tex/d25187a741809c52aa384463aea554dd.gif)
![](/pool/data/tex/788c7c4f71ad57fd4b2ccca697558964.gif)
Nachfolgekonfiguration:
![](/pool/data/tex/cc4ceb8291073647ad7430f04bd1576a.gif)
![](/pool/data/tex/d25187a741809c52aa384463aea554dd.gif)
![](/pool/data/tex/cc4ceb8291073647ad7430f04bd1576a.gif)
![](/pool/data/tex/d25187a741809c52aa384463aea554dd.gif)
![](/pool/data/tex/4a03166d751743dcd558ccf1b503cbb4.gif)
Die Rechnung terminiert, wenn Stoppzustand erreicht ist. Dann gibt es keine Nachfolgekonfiguration.
Lauftzeit einer TM
Die Laufzeit einer TM ist die Zahl der Rechenschritte, die bis zur Terminierung ausgeführt werden. (Die Rechnung terminiert, sobald der Stoppzustand erreicht wird).
Falls die Rechnung nicht terminiert ist die Laufzeit unbeschränkt.
Falls die Rechnung nicht terminiert ist die Laufzeit unbeschränkt.
Platzbedarf einer TM
..ist die Zahl der besuchten Speicherzellen. Dieser kann auch unbeschränkt sein.
Wann heißt eine Funktion TM-berechenbar?
Eine TM M, die für alle Eingaben terminiert, berechnet eine totale Funktion
.
Da TMs im Allgemeinen nicht immer terminieren berechnen sie also eine Funktion![](/pool/data/tex/ce8e7ba4bfa2eba6ec782d7b76c26145.gif)
Eine Eingabe
wird auf
abgebildet, wenn M auf der Eingabe x nicht terminiert. Sonst steht der Kopf im Stoppzustand auf einem Zeichen aus
. Wenn das Ergebnis
ist steht der Kopf auf B.
Eine Funktion
heißt TM-berechenbar, wenn es eine TM M mit
gibt.
![](/pool/data/tex/735082882f3a4914de56ea98144794fe.gif)
Da TMs im Allgemeinen nicht immer terminieren berechnen sie also eine Funktion
![](/pool/data/tex/ce8e7ba4bfa2eba6ec782d7b76c26145.gif)
Eine Eingabe
![](/pool/data/tex/0c45e03bcc795af48f72c87b6a40ee3b.gif)
![](/pool/data/tex/b70979a357cfbe7c61e4c686ea2beb93.gif)
![](/pool/data/tex/07710b5c43702a8bb7b9104eacc6ba71.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
Eine Funktion
![](/pool/data/tex/eb8cac6adb2a63c39d9378a0e1808fd4.gif)
![](/pool/data/tex/dce20eab99b6cea2bef9695b84f2fb2b.gif)
Welche Funktionen berechnet eine TMn M allgemein und für Entscheidungsprobleme?
allgemein: ![](/pool/data/tex/5bdddc15126f50f4862813869f07fa6c.gif)
Entscheidungsprobleme:![](/pool/data/tex/4db0ebf2e74188acb71126fff36de0de.gif)
![](/pool/data/tex/5bdddc15126f50f4862813869f07fa6c.gif)
Entscheidungsprobleme:
![](/pool/data/tex/4db0ebf2e74188acb71126fff36de0de.gif)
TM-entscheidbar für Entscheidungsprobleme (Sprachen)
Eine Sprache
heißt TM-entscheibar bzw. rekursiv, wenn es eine TM gibt, die auf allen Eingaben stoppt und die Eingabe aktzeptiert, wenn
, und die Eingabe verwirft, wenn
.
![](/pool/data/tex/3b0615c5a8ff0a3e8ac34d072df9ea13.gif)
![](/pool/data/tex/4631ed4fd2fe4dbf2f7bb7ec1ed77cc1.gif)
![](/pool/data/tex/31809ee2d31edf685942a8bc28570f39.gif)
Mehrspur-TM
Bei iner k-spurigen TM, handelt es sich um eine TM, bei der das Band in k Spuren eingeteilt ist.
In jeder Bandzelle stehen k-Zeichen, die der Kopf gleichzeitig lesen kann.
Das Bandalphabet wird also um einen k-dimensionalen Vektor erweitert:
![](/pool/data/tex/d7bb9fc7483f3f1b411aa2063f5cb2dd.gif)
Beispiel: Addition binärer Zahlen: Spur 1 und 2 enthalten zwei binär kodierte Zahlen, das Ergebnis wird auf Spur 3 geschrieben. Überträge werden während der Rechnung im Zustandsraum gespeichert. (3 Phasen!)
In jeder Bandzelle stehen k-Zeichen, die der Kopf gleichzeitig lesen kann.
Das Bandalphabet wird also um einen k-dimensionalen Vektor erweitert:
![](/pool/data/tex/d7bb9fc7483f3f1b411aa2063f5cb2dd.gif)
Beispiel: Addition binärer Zahlen: Spur 1 und 2 enthalten zwei binär kodierte Zahlen, das Ergebnis wird auf Spur 3 geschrieben. Überträge werden während der Rechnung im Zustandsraum gespeichert. (3 Phasen!)
Programmkonstrukte aus höheren Programmiersprachen
Variablen: pro Variable eine Spur reservieren.
Unterprogramme: eine Spur als Prozedurstack reservieren.
Unterprogramme: eine Spur als Prozedurstack reservieren.
k-Band TM
Verfügt über k-Bänder mit jeweils unabhängigem Kopf.
Band 1: Eingabe/Ausgabe Band
Bänder 2-k: initial mit B* beschrieben
![](/pool/data/tex/b20298833e7e9a0154c3c47cba7ac696.gif)
Funktionsweise, Laufzeit und Platzbedarf analog zur allgm. TM
Band 1: Eingabe/Ausgabe Band
Bänder 2-k: initial mit B* beschrieben
![](/pool/data/tex/b20298833e7e9a0154c3c47cba7ac696.gif)
Funktionsweise, Laufzeit und Platzbedarf analog zur allgm. TM
Simulation einer k-Band TM M als 1-Band TM M'
Eine k-Band TM M mit Rechenzeit t(n) und Platz s(n), kann von einer 1-Band TM M' mit Zeitbedarf
und Platzbedarf O(s(n)) simuliert werden.
M' verwendet 2k Spuren:
- ungerade Spuren 1,3,...2k-1 enthalten den Inhalt der Bänder 1...k von M
- gerade Spuren 2,4,...,2k enthalten die Kopfpostitionen von M (mit # markiert)
Die Initialisierung der Spuren ist in konstanter Zeit möglich
Jeder Rechenschritt wird wie folgt simuliert:
- M' geht vom linkesten # bis zum rechtesten # (M' kennt Zustand von M)
- k Zeichen an mit # markierten Positionen werden im Zustandsraum gespeichert (möglich, da nur konstant viele Markierungen)
- M' wertet Übergangsfunktion von M aus (kennt nun neuen Zustand und Bandbewegungen)
- M' läuft zum linkesten # zurück und verändert Bandinschriften und verschiebt # nach links oder rechts.
Laufzeit: Nach t Schritten können die äußeren Markierungen höchstens 2t Positionen auseinander liegen (pro Schritt nur um eine Position verschoben) => Abstand zwischen Zeichen durch O(t(n)) beschränkt => Laufzeit pro Schritt durch O(t(n)) beschränkt => Simulation von t(n) Schritten durch
beschränkt
Platzbedarf:linear (zu jeder von M' besuchten Zelle gehört mind. eine Zelle, die M besucht?)
![](/pool/data/tex/ea9ffe13f7ee63b180ea3abe7f0e3e95.gif)
M' verwendet 2k Spuren:
- ungerade Spuren 1,3,...2k-1 enthalten den Inhalt der Bänder 1...k von M
- gerade Spuren 2,4,...,2k enthalten die Kopfpostitionen von M (mit # markiert)
Die Initialisierung der Spuren ist in konstanter Zeit möglich
Jeder Rechenschritt wird wie folgt simuliert:
- M' geht vom linkesten # bis zum rechtesten # (M' kennt Zustand von M)
- k Zeichen an mit # markierten Positionen werden im Zustandsraum gespeichert (möglich, da nur konstant viele Markierungen)
- M' wertet Übergangsfunktion von M aus (kennt nun neuen Zustand und Bandbewegungen)
- M' läuft zum linkesten # zurück und verändert Bandinschriften und verschiebt # nach links oder rechts.
Laufzeit: Nach t Schritten können die äußeren Markierungen höchstens 2t Positionen auseinander liegen (pro Schritt nur um eine Position verschoben) => Abstand zwischen Zeichen durch O(t(n)) beschränkt => Laufzeit pro Schritt durch O(t(n)) beschränkt => Simulation von t(n) Schritten durch
![](/pool/data/tex/77b9e0d4966a750929583355abb99f6f.gif)
Platzbedarf:linear (zu jeder von M' besuchten Zelle gehört mind. eine Zelle, die M besucht?)
universelle TM
simuliert beliebige andere TM M auf beliebiger Eingabe w:
- simuliert das Verhalten von M auf w
- übernimmt das Aktzeptanzverhalten von M
- bei inkorrekter Eingabe (also kein Gödelnummer) Fehlermeldung
- erhält als Eingabe String der Form
, wobei
die simulierte TM M kodiert (Gödelnummer)
- ist im Gegensatz zur normalen TM (special purpose Rechner) general purpose Rechner
- simuliert das Verhalten von M auf w
- übernimmt das Aktzeptanzverhalten von M
- bei inkorrekter Eingabe (also kein Gödelnummer) Fehlermeldung
- erhält als Eingabe String der Form
![](/pool/data/tex/953d15a1d27092a7fefa549c4ef95db8.gif)
![](/pool/data/tex/c5845729ba3350bd6d74f559c91d9079.gif)
- ist im Gegensatz zur normalen TM (special purpose Rechner) general purpose Rechner
Gödelnummerierung
- ist injektive Abbildung von der Menge aller TMn in die Menge ![](/pool/data/tex/331255180869cc1b71aab4137ad6ff55.gif)
- Präfixfreiheit: keine Gödelnummer darf Anfangsteilwort einer anderen Gödelnummer sein (111 am Ende und nirgends sonst in der Kodierung)
Kodierung:
![](/pool/data/tex/331255180869cc1b71aab4137ad6ff55.gif)
- Präfixfreiheit: keine Gödelnummer darf Anfangsteilwort einer anderen Gödelnummer sein (111 am Ende und nirgends sonst in der Kodierung)
Kodierung:
![]() | Menge der Zustände |
![]() | Anfangszustand (statt ![]() |
![]() | Stoppzustand |
![]() ![]() | Bandalphabet durchnummeriert |
![]() | mögliche Kopfbewegungen durchnummeriert |
![]() ![]() | Übergangsfunktion als Binärstring kodiert |
<M>= code(1)11code(2)11...11code(s)111 | Kodierung des t-ten Übergangs ist code(t) |
Implementierung der universellen TM als 3-Band-TM
- Band 1: simuliert das Band der TM M
- Band 2: enthält die Gödelnummer von M
- Band 3: enthält den jeweils aktuellen Zustand von M
Initialisierung:
1.) Überprüfung ob Eingabe mit korrekter Göldenummer beginnt (sonst Fehlermeldung)
2.) kopiert <M> auf Band 2
3.) kopiert Binärkodierung des Anfangszustand auf Band 3
4.) kopiert w auf Band 1
5.) Kopf steht auf erstem Zeichen von w
Simulation eines Schritts:
-aktualisiert Inschrift auf Band 1
-bewegt Kopf auf Band 1
-verändert den auf Band 3 abgespeicherten Zustand
Laufzeit:
für Initialisierung O(1) bei konstant angesehener Kodierungslänge
-Laufzeit eines Schritts ist kosntant
=> U simuliert M mit konstantem Zeitverlust
=> wenn wir als 1-Band simulieren quadratischer Zeitverlust
=> konstanter Zeitverlust: wenn GN auf Spur 2 und Zustand auf Spur 3 mit dem Kopf der TM M mitführen(?)
- Band 2: enthält die Gödelnummer von M
- Band 3: enthält den jeweils aktuellen Zustand von M
Initialisierung:
1.) Überprüfung ob Eingabe mit korrekter Göldenummer beginnt (sonst Fehlermeldung)
2.) kopiert <M> auf Band 2
3.) kopiert Binärkodierung des Anfangszustand auf Band 3
4.) kopiert w auf Band 1
5.) Kopf steht auf erstem Zeichen von w
Simulation eines Schritts:
-aktualisiert Inschrift auf Band 1
-bewegt Kopf auf Band 1
-verändert den auf Band 3 abgespeicherten Zustand
Laufzeit:
für Initialisierung O(1) bei konstant angesehener Kodierungslänge
-Laufzeit eines Schritts ist kosntant
=> U simuliert M mit konstantem Zeitverlust
=> wenn wir als 1-Band simulieren quadratischer Zeitverlust
=> konstanter Zeitverlust: wenn GN auf Spur 2 und Zustand auf Spur 3 mit dem Kopf der TM M mitführen(?)
Registermaschine (RAM)
- Speicher ist unbeschränkt und besteht aus Registern ![](/pool/data/tex/a3ca86a73cf6bb746232dd6e97b69417.gif)
- c(0) ist Akkumulator:
=> Rechenbefehle benutzen ihn als implizites Argument
=> Ergebnis der Rechenoperationen wird dort gespeichert
- Register enthalten beliebig große ganze Zahlen
- Befehlszähler b steht initial auf 1
Eine RAM arbeitet wie ein Programm mit durchnummerierten Befehlen:
- in jedem Schritt wird der Befehl in Programmzeile b abgearbeitet
- goto i: Befehlszähler wird auf i gesetzt
- END stoppt Rechnung
- sonst wird Befehlszähler um eins erhöht
- Eingabe steht am Anfang der Rechnung in den Registern![](/pool/data/tex/a1e0ecc7cb7914db9c90aeff8e708159.gif)
- Ausgabe befindet sich nach dem Stoppen in Registern![](/pool/data/tex/4252f4f2c742680a935593ad2fb8e45e.gif)
k und l liegen zum Anfang der Rechnung fest.
RAM berechnet Funktion
![](/pool/data/tex/a3ca86a73cf6bb746232dd6e97b69417.gif)
- c(0) ist Akkumulator:
=> Rechenbefehle benutzen ihn als implizites Argument
=> Ergebnis der Rechenoperationen wird dort gespeichert
- Register enthalten beliebig große ganze Zahlen
- Befehlszähler b steht initial auf 1
Eine RAM arbeitet wie ein Programm mit durchnummerierten Befehlen:
- in jedem Schritt wird der Befehl in Programmzeile b abgearbeitet
- goto i: Befehlszähler wird auf i gesetzt
- END stoppt Rechnung
- sonst wird Befehlszähler um eins erhöht
- Eingabe steht am Anfang der Rechnung in den Registern
![](/pool/data/tex/a1e0ecc7cb7914db9c90aeff8e708159.gif)
- Ausgabe befindet sich nach dem Stoppen in Registern
![](/pool/data/tex/4252f4f2c742680a935593ad2fb8e45e.gif)
k und l liegen zum Anfang der Rechnung fest.
RAM berechnet Funktion
![](/pool/data/tex/cb66a3e1f730728542774cbd1f078c66.gif)
Kostenmaße der RAM
Uniformes Kostenmaß: Jeder Schritt zählt eine Zeiteinheit
Logarithmisches Kostenmaß: Die Laufzeitkosten eines Schritts sind proportional zur binären Länge der Zahlen in den angesprochenen Registern.
Terminiert die Rechnung nicht, ist die Laufzeit unbeschränkt.
Logarithmisches Kostenmaß: Die Laufzeitkosten eines Schritts sind proportional zur binären Länge der Zahlen in den angesprochenen Registern.
Terminiert die Rechnung nicht, ist die Laufzeit unbeschränkt.
Syntax der RAM (wichtigste, evtl. ergänzen)
Syntax | Zustandsänderung |
LOAD i | c(0) := c(i) |
CLOAD i | c(0) := i |
STRORE i | c(i) := c(0) |
ADD i | c(0) := c(0) + c(i) |
CADD i | c(0) := c(0) + i |
SUB i | c(0) := c(0) - c(i) |
CSUB i | c(0) := c(0) - c(i) |
MULT i | c(0) := c(0) * i |
CMULT i | c(0) := c(0) * c(i) |
DIV i | c(0) := Lc(0) / c(i) ┘ |
CDIV i | Lc(0) / i ┘ |
GOTO j | b:=j |
IF c(0) = < <= x GOTO j | b:= j, falls c(0) =<<=x; b+1, sonst |
Vergleich TM - RAM
- Modelle sind gleich mächtig: können also gleiche Funktionen berechnen
- bzgl. logarithmischem Kostenmaß sind Laufzeiten der Modelle ähnlich
- gegenseitige Simulation mit polynomiellem Zeitverlust
- bzgl. logarithmischem Kostenmaß sind Laufzeiten der Modelle ähnlich
- gegenseitige Simulation mit polynomiellem Zeitverlust
Simulation RAM durch TM
Simulation der RAM als 2-Band-TM
- ein Band für den Speicher der RAM
- das andere ist Arbeitsband für die TM in den Unterprgrammen
- pro Programmzeile der RAM (p-Stück) ein TM-Unterprogramm
=>
ist Unterprogramm für Programmzeile i
-
ist Unterprogramm zur Initialisierung der TM
-
ist Unterprogramm zur Ergebnisaufbereitung
- den Befehlszähler b kann die TM im Zustandsraum abspeichern, da es nur konstant viele Zeilen gibt
- Inhalt der Registern ist allerdings unbeschränkt
=> mit Speicher, Befehlszähler und Unterprogrammen ist die RAM vollständig erfasst.
Rechenschritte:
Rufe durch Befehlszähler b beschriebenes Unterprogramm
auf
1.)
kopiert die in Programmzeile b angesprochenen Register auf Band 1
2.) führt notwendige Operationen auf Registerinhalten aus
3.) kopiert das Ergebnis des in Programmzeile b angegebenen Registers zurück auf Band 2
4.) aktualisiert Programmzähler
Laufzeit: Länge des Speicherinhalts auf Band 2 ist durch O(n+t(n)) beschränkt, weil die RAM für jedes neue Bit, das sie erzeugt, mindestens eine Zeiteinheit benötigt. Initialisierung benötigt O(n). Laufzeit der Unterprogramme ist polynomiell in Länge der Bandinschrift auf Band 2 beschränkt, also in n+t(n). Gesatmlaufzeit ist also polynomiell in n+t(n) beschränkt.
- ein Band für den Speicher der RAM
- das andere ist Arbeitsband für die TM in den Unterprgrammen
- pro Programmzeile der RAM (p-Stück) ein TM-Unterprogramm
=>
![](/pool/data/tex/164f4ec8743ae6c1ba707c618b76ff61.gif)
-
![](/pool/data/tex/c799681b2a0fb7c2094ebe82855ed99c.gif)
-
![](/pool/data/tex/0fe4d61cec0378a29e4a911a252b078f.gif)
- den Befehlszähler b kann die TM im Zustandsraum abspeichern, da es nur konstant viele Zeilen gibt
- Inhalt der Registern ist allerdings unbeschränkt
=> mit Speicher, Befehlszähler und Unterprogrammen ist die RAM vollständig erfasst.
Rechenschritte:
Rufe durch Befehlszähler b beschriebenes Unterprogramm
![](/pool/data/tex/06154eca89935c16391249e30b659550.gif)
1.)
![](/pool/data/tex/06154eca89935c16391249e30b659550.gif)
2.) führt notwendige Operationen auf Registerinhalten aus
3.) kopiert das Ergebnis des in Programmzeile b angegebenen Registers zurück auf Band 2
4.) aktualisiert Programmzähler
Laufzeit: Länge des Speicherinhalts auf Band 2 ist durch O(n+t(n)) beschränkt, weil die RAM für jedes neue Bit, das sie erzeugt, mindestens eine Zeiteinheit benötigt. Initialisierung benötigt O(n). Laufzeit der Unterprogramme ist polynomiell in Länge der Bandinschrift auf Band 2 beschränkt, also in n+t(n). Gesatmlaufzeit ist also polynomiell in n+t(n) beschränkt.
Simulation TM durch RAM
Simulation einer 1-Band-TM als RAM:
- Register 1 speichert den Index der Kopfposition
- Register 2 speichert aktuellen Zustand
- Register 3,4,... speichern Inhalte der Bandpositionen 0,1,2,... falls diese zur Eingabe der TM gehören oder vorher vom Kopf besucht wurden
Rechenschritte:
1.) Überprüfung, ob TM im aktuellen Schritt terminiert (falls ja, endet RAM mit entsprechender Ausgabe)
2.) erste Stufe: |Q| viele IF-Abfragen: aktuellen Zustand bestimmen
zweite Stufe: |
| viele IF-Abfragen: gelesenes Zeichen bestimmen
=> je nach Ausgang der IF-Anfragen wird der Zustand in Register 2 und die Kopfposition in Register 1 und das Zeichen an Bandposition c(1) geändert
Laufzeit:
uniformes Kostenmaß: O(n+t(n))
logarithmisches Kostenmaß: Zustände in Zeichen haben konstante Kodierungslänge. Bandpos, die angesprochen werden sind durch n+t(n) beschränkt. Kodierungslänge der Position ist also O(log(n+t(n)). Insgesamt also: O((t(n) + n)log(t(n) + n)
- Register 1 speichert den Index der Kopfposition
- Register 2 speichert aktuellen Zustand
- Register 3,4,... speichern Inhalte der Bandpositionen 0,1,2,... falls diese zur Eingabe der TM gehören oder vorher vom Kopf besucht wurden
Rechenschritte:
1.) Überprüfung, ob TM im aktuellen Schritt terminiert (falls ja, endet RAM mit entsprechender Ausgabe)
2.) erste Stufe: |Q| viele IF-Abfragen: aktuellen Zustand bestimmen
zweite Stufe: |
![](/pool/data/tex/07710b5c43702a8bb7b9104eacc6ba71.gif)
=> je nach Ausgang der IF-Anfragen wird der Zustand in Register 2 und die Kopfposition in Register 1 und das Zeichen an Bandposition c(1) geändert
Laufzeit:
uniformes Kostenmaß: O(n+t(n))
logarithmisches Kostenmaß: Zustände in Zeichen haben konstante Kodierungslänge. Bandpos, die angesprochen werden sind durch n+t(n) beschränkt. Kodierungslänge der Position ist also O(log(n+t(n)). Insgesamt also: O((t(n) + n)log(t(n) + n)
Church-Turing-These
Die Klasse der rekursiven Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.
Erklärung: Klasse der intuitiv berechenbaren Funktionen entspricht der Menge aller Funktionen, die von realistischem Rechnermodell berechnet werden können
Erklärung: Klasse der intuitiv berechenbaren Funktionen entspricht der Menge aller Funktionen, die von realistischem Rechnermodell berechnet werden können
Abzählbare Mengen
Eine Menge M heißt abzählbar, wenn es eine surjektive Funktion
gibt. Nicht abzählbare Mengen heißen überabzählbar.
Bsp.:
- alle endlichen Mengen sind abzählbar
- Potenzmenge der natürlichen Zahlen ist überabzählbar
- Menge der Sprachen über dem Alphabt {0,1} ist überabzählbar
=> Menge der TMn ist abzählbar (weil durch GN kodierbar und Menge der GN Teilmenge von![](/pool/data/tex/634dd9c94924cd72cba63b1e25778ae6.gif)
und Menge der Sprachen ist überabzählbar => es gibt mehr Sprachen als TMn
![](/pool/data/tex/0db8160074b439c183ce967179932d5a.gif)
Bsp.:
- alle endlichen Mengen sind abzählbar
- Potenzmenge der natürlichen Zahlen ist überabzählbar
- Menge der Sprachen über dem Alphabt {0,1} ist überabzählbar
=> Menge der TMn ist abzählbar (weil durch GN kodierbar und Menge der GN Teilmenge von
![](/pool/data/tex/634dd9c94924cd72cba63b1e25778ae6.gif)
und Menge der Sprachen ist überabzählbar => es gibt mehr Sprachen als TMn
Diagonalsprache D
![](/pool/data/tex/73501c6b745ee591313d0194aecd85b1.gif)
Das i-te Wort bzgl. der kanonischen Reihenfolge (
![](/pool/data/tex/aa38f107289d4d73d516190581397349.gif)
![](/pool/data/tex/cf02c22fc164faf4976cae168d7d73bd.gif)
Matrixanschauung:
![](/pool/data/tex/7d942f6350f0ef901f8a5512bc75e8a5.gif)
Diagonalsprache lässt sich auf der Diagonalen der Matrix ablesen:
![](/pool/data/tex/882cd84105e54f619dd1a1faff1ecd84.gif)
Beweis: D ist nicht rekursiv
Widerspruchsbeweis:
- nehme an D sei rekursiv
- dann gibt es TM
, die D entscheidet
- wende
auf
an
1.Fall:
liegt in D
- dann aktzeptiert
die Eingabe
, weil
die Sprache entscheidet
- Wegen der Definition von D kann
aber nicht in D liegen ![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
2.Fall:
liegt nicht in D
- dann verwirft
die Eingabe
, weil
die Sprache entscheidet
- Wegen der Definition von D muss
aber in D liegen ![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
- nehme an D sei rekursiv
- dann gibt es TM
![](/pool/data/tex/f7a82463d2e917011368c7637c6fcbf8.gif)
- wende
![](/pool/data/tex/80a0b425e1414bd57767d67567c48c0c.gif)
![](/pool/data/tex/a66b1344e22223f77cb2b496a51cc162.gif)
1.Fall:
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
- dann aktzeptiert
![](/pool/data/tex/f7a82463d2e917011368c7637c6fcbf8.gif)
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
![](/pool/data/tex/f7a82463d2e917011368c7637c6fcbf8.gif)
- Wegen der Definition von D kann
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
2.Fall:
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
- dann verwirft
![](/pool/data/tex/f7a82463d2e917011368c7637c6fcbf8.gif)
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
![](/pool/data/tex/f7a82463d2e917011368c7637c6fcbf8.gif)
- Wegen der Definition von D muss
![](/pool/data/tex/e8100be07fa5419af6c6738b934dfca0.gif)
![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
Beweis: L unentscheidbar =>
unentscheidbar
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
Widerspruchsbeweis:
- nehme an es ex. TM
, die
entscheidet
=>
hält auf Eingabe w, gdw. ![](/pool/data/tex/ec4c53c2962ca2134ef4d04c51729dde.gif)
- Konstruiere TM M, die
als Unterprogramm aufruft:
M startet
auf der vorliegenden Eingabe
M negiert Ausgabe von![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
=> M entscheidet offensichtlich L.
Widerspruch zur Unentscheidbarkeit von L.
=> Komplement der Diagonalsprache ist unentscheidbar
- nehme an es ex. TM
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
=>
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
![](/pool/data/tex/ec4c53c2962ca2134ef4d04c51729dde.gif)
- Konstruiere TM M, die
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
M startet
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
M negiert Ausgabe von
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
=> M entscheidet offensichtlich L.
Widerspruch zur Unentscheidbarkeit von L.
=> Komplement der Diagonalsprache ist unentscheidbar
Beweis: Das Halteproblem ist nicht rekursiv
Zum Zweck des Widerspruchs nehmen wir an, dass H entscheidbar ist. Dann gib es eine TM
, die H entscheidet.
Konstruieren nun eine TM
, die
als Unterprgramm aufruft und
entscheidet.
(
ist unentscheidbar, als kann es
nicht geben)
arbeitet wie folgt:
1.) Auf Eingabe w, berechne i, so dass gilt![](/pool/data/tex/59169ca7de1a5091f590565cdc435cd5.gif)
2.) Berechne nun Gödelnummer der i-ten TM:![](/pool/data/tex/74e385b0dda8d1cf593406575a1ce68e.gif)
3.) Starte
als Unterprogramm auf Eingabe ![](/pool/data/tex/718f3f234f7a752d07cbea8514d561b5.gif)
4.) Falls
akzeptiert, simuliere
auf w und übernehme deren Akzeptanzverhalten
5.) Falls
verwirft, so verwirf
Korrektheit:
1.Fall:
=>
akzeptiert
, da
auf w hält=>
akzeptiert w
2.Fall:
=>
akzeptiert, falls
w verwirft oder
verwirft, falls
nicht hält (also weder verwirft noch akzeptiert)=>in beiden Fällen:
verwirft w.
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
Konstruieren nun eine TM
![](/pool/data/tex/720def1cc6b26a55cd016afe8573c31f.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/b7bc25228c03b496dc5904e7d6e6da0e.gif)
(
![](/pool/data/tex/b7bc25228c03b496dc5904e7d6e6da0e.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/720def1cc6b26a55cd016afe8573c31f.gif)
1.) Auf Eingabe w, berechne i, so dass gilt
![](/pool/data/tex/59169ca7de1a5091f590565cdc435cd5.gif)
2.) Berechne nun Gödelnummer der i-ten TM:
![](/pool/data/tex/74e385b0dda8d1cf593406575a1ce68e.gif)
3.) Starte
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/718f3f234f7a752d07cbea8514d561b5.gif)
4.) Falls
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/cf02c22fc164faf4976cae168d7d73bd.gif)
5.) Falls
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
Korrektheit:
1.Fall:
![](/pool/data/tex/163ef88043ab03ef38b0e16bb06e5adc.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/d50b5cfff726ad39561678a408ad4d7e.gif)
![](/pool/data/tex/cf02c22fc164faf4976cae168d7d73bd.gif)
![](/pool/data/tex/720def1cc6b26a55cd016afe8573c31f.gif)
2.Fall:
![](/pool/data/tex/14cdf70207d56a1bc0d8e5653f681877.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/cf02c22fc164faf4976cae168d7d73bd.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/cf02c22fc164faf4976cae168d7d73bd.gif)
![](/pool/data/tex/720def1cc6b26a55cd016afe8573c31f.gif)
spezielles Halteproblem
![](/pool/data/tex/435bd57e8f746c6ef66a0287ed42365d.gif)
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
(Eine TM
![](/pool/data/tex/95c22c3b4fcf946a58e106d7c0320d7a.gif)
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
![](/pool/data/tex/95c22c3b4fcf946a58e106d7c0320d7a.gif)
=>
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
Beweis: spezielles Halteproblem ist nicht rekursiv
Zum Zwecke des Widerspruchs nehmen wir an, dass
entscheidbar ist. Es gibt also eine TM
, die
entscheidet.
Konstruieren nun eine TM
, die
als Unterprogramm aufruft und das Halteproblem entscheidet. (Da H nicht entscheidbar ist, kann
also nicht ex.)
Die TM
arbeiten wie folgt:
1.) Falls die Eingabe keine korrekte GN ist, verwirft
die Eingabe
2.) sonst, auf alle Eingaben der Form
berechnet
die GN einer TM
mit folgenden Eigenschaften:
- falls die TM
auf leere Eingabe startet, schreibe w aufs Band und simuliere M auf w.
- auf anderen Eingaben, verhält sie sich beliebig
3.)
schreibt GN
aufs Band und startet
auf dieser Eingabe und übernimmt deren Akzeptanzverhalten.
Korrektheit:
1.Fall:
=> M hält auf w =>
hält auf
, da sonst M auf w nicht simuliert worden wäre =>
akzeptiert
=>
akzeptiert ![](/pool/data/tex/953d15a1d27092a7fefa549c4ef95db8.gif)
2. Fall:
=> M hält nicht auf w =>
hält nicht auf
=>
verwirft
=>
verwirft ![](/pool/data/tex/2bd61abf21b861974c3783fa0b5e4434.gif)
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
![](/pool/data/tex/e0b63c7f2515ff6e6d89aa05379e21fa.gif)
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
Konstruieren nun eine TM
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/e0b63c7f2515ff6e6d89aa05379e21fa.gif)
![](/pool/data/tex/e0b63c7f2515ff6e6d89aa05379e21fa.gif)
Die TM
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
1.) Falls die Eingabe keine korrekte GN ist, verwirft
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
2.) sonst, auf alle Eingaben der Form
![](/pool/data/tex/953d15a1d27092a7fefa549c4ef95db8.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/8c6277fc2f63675a458ed974facfc4c3.gif)
- falls die TM
![](/pool/data/tex/8c6277fc2f63675a458ed974facfc4c3.gif)
- auf anderen Eingaben, verhält sie sich beliebig
3.)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/db8ac5cf841da4d382092d2236100efb.gif)
![](/pool/data/tex/e0b63c7f2515ff6e6d89aa05379e21fa.gif)
Korrektheit:
1.Fall:
![](/pool/data/tex/a38859673a80567d0f8a3c85f5d8e793.gif)
![](/pool/data/tex/8c6277fc2f63675a458ed974facfc4c3.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/db8ac5cf841da4d382092d2236100efb.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/953d15a1d27092a7fefa549c4ef95db8.gif)
2. Fall:
![](/pool/data/tex/534e47633b2c8844459805ecc8a44732.gif)
![](/pool/data/tex/8c6277fc2f63675a458ed974facfc4c3.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/db8ac5cf841da4d382092d2236100efb.gif)
![](/pool/data/tex/5a2c7edee9bbb7cf05995dece263f511.gif)
![](/pool/data/tex/2bd61abf21b861974c3783fa0b5e4434.gif)
Satz von Rice
![](/pool/data/tex/e54eb748ae8103ed8635e3660b45aafe.gif)
R bezeichnet also die Menge der TM-berechenbaren Funktionen.
Sei S eine Teilmenge von R mit
![](/pool/data/tex/b313b188eae11236a7e932abf33c19c1.gif)
![](/pool/data/tex/f9b236dafea9971bf242740094685e9c.gif)
Nicht-triviale Eigenschaften der von einer TM berechneten Funktion sind nicht entscheidbar.
Konsequenzen für die Praxis: Es kann keinen Compiler geben, der entscheidet, ob ein gegebenes TM oder RAM_Programm auf allen Eingaben terminiert, weil der Compiler dazu entscheiden müsste, ob das Programm eine Funktion der Form
![](/pool/data/tex/6978a783e1fe5ffa1db48fdc468a2b69.gif)
Beweis: Satz von Rice
Unterprogrammtechnik:
Sei
eine TM, die L(S) entscheidet. Konstruiere eine TM
, die
entscheidet und
als Unterprogramm aufruft. (Widerspruch zu
unentscheidbar)
Sei u die überall undefinierte Funktion.
1. Fall:![](/pool/data/tex/7286764fdc0cfa7b480d144b9cde9d31.gif)
Sei
eine Funktion aus S. (Ex. aufgrund Vors.
). Die TM
arbeitet so:
1.) Eingabe keine korrekte GN <M>: verwirft die Eingabe
2.) Konstruiere aus der GN <M> eine TM M* mit folgendem Verhalten:
(a) Ignoriere die Eingabe x. Simuliere M auf Eingabe
auf einer dafür reservierten Spur (von M*).
(b) Berechne f(x), simuliere M auf Eingabe x.
=> M* berechnet also nur f(x), wenn M in Schritt (a) auf
gehalten hat.
3.)
startet
auf <M*> und akzeptert, wenn
akzeptiert.
Sei
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/872b6693f2a0af3d7774a5acf17b1191.gif)
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
![](/pool/data/tex/872b6693f2a0af3d7774a5acf17b1191.gif)
Sei u die überall undefinierte Funktion.
1. Fall:
![](/pool/data/tex/7286764fdc0cfa7b480d144b9cde9d31.gif)
Sei
![](/pool/data/tex/74bf8effea9f6dcb100dfbb90cf62d73.gif)
![](/pool/data/tex/e333b19476833d15fb4ae9345db1031d.gif)
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
1.) Eingabe keine korrekte GN <M>: verwirft die Eingabe
2.) Konstruiere aus der GN <M> eine TM M* mit folgendem Verhalten:
(a) Ignoriere die Eingabe x. Simuliere M auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
(b) Berechne f(x), simuliere M auf Eingabe x.
=> M* berechnet also nur f(x), wenn M in Schritt (a) auf
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
3.)
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
Beweis: Satz von Rice Korrektheit
Korrektheit:
Falls Eingabe keine Korrekt GN ist, verwirft
korrekterweise die Eingabe. Bei Eingaben der Form
gilt:
:
=> M hält auf![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* berechnet f
=> <M*>
L(S)
=>
akzeptiert <M*>
=>
akzeptiert w
:
=> M hält nicht auf![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* berechnet u
=>![](/pool/data/tex/b9ccbd6af3605c182af3b993cb589e44.gif)
=>
verwirft <M*>
=>
verwirft w.
2.Fall:
wähle f aus ![](/pool/data/tex/0bb67f918892344c6181b7df775aae83.gif)
Falls Eingabe keine Korrekt GN ist, verwirft
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/7fd9342f0faee771901663ee780cf364.gif)
![](/pool/data/tex/115ce914682fde2f54bb8782d210057a.gif)
=> M hält auf
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* berechnet f
=> <M*>
![](/pool/data/tex/986c22f151c46acac223b858e3fcf6fd.gif)
=>
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
=>
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
![](/pool/data/tex/33ee2da7661c31d919bd95ec35ae51dc.gif)
=> M hält nicht auf
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* berechnet u
=>
![](/pool/data/tex/b9ccbd6af3605c182af3b993cb589e44.gif)
=>
![](/pool/data/tex/9eeed44af1c33d4ade892d04053d1307.gif)
=>
![](/pool/data/tex/0f7d2b93bb965623bf6b4f870de622cd.gif)
2.Fall:
![](/pool/data/tex/3643d6055b31486321d3d8ee2f42753b.gif)
![](/pool/data/tex/0bb67f918892344c6181b7df775aae83.gif)
Definition: entscheidbar
Eine Sprache L wird von einer TM M entscheiden, wenn M auf jeder Eingabe hält und genau die Wörter aus L akzeptiert.
Definition: erkennen
Eine Sprache
wird von einer TM M erkannt, wenn M jedes Wort aus L akzeptiert und keins akzeptiert, dass nicht in L enthalten ist. Auf letzteren muss sie aber auch nicht halten.
![](/pool/data/tex/3b0615c5a8ff0a3e8ac34d072df9ea13.gif)
Definition: semi-entscheidbar
Eine Sprache L heißt semi-entscheidbar, wenn es eine TM gibt, die L erkennt.
Bsp: Halteproblem (S.34)
Bsp: Halteproblem (S.34)
Aufzähler
- Variante einer TM mit angeschlossenem Drucker (zusätzliches Ausgabeband, auf dem sich der Kopf nur nach rechts bewegt)
- ennummeriert alle Wörter aus L auf dem Drucker
1.) gedruckt werden nur Wörter aus L
2.) jedes Wort aus L wird irgendwann ausgegeben
=> Wiederholen der Wörter ist nicht explizit verboten
=> eine Sprache heißt rekursiv aufzählbar, wenn es einen Aufzähler L gibt.
- ennummeriert alle Wörter aus L auf dem Drucker
1.) gedruckt werden nur Wörter aus L
2.) jedes Wort aus L wird irgendwann ausgegeben
=> Wiederholen der Wörter ist nicht explizit verboten
=> eine Sprache heißt rekursiv aufzählbar, wenn es einen Aufzähler L gibt.
semi-entscheidbar/rekursiv aufzählbar
Eine Sprache L ist genau dann semi-entscheidbar, wenn L rekursiv aufzählbar ist
Beweis:
"<=": Konstruiere aus einem Auzähler für L eine TM M, die L erkennt
- zusätzliche Spur, die Rolle des Drucker übernimmt
- wenn neues Wort enummeriert wurde, vergleicht es M mit w
- falls
wird w irgendwann enummeriert und von M akzeptiert
- falls
wird w nicht akzeptiert, aber M hält auch nicht
"=>": Konstruiere aus eine TM M, die L erkennt einen Aufzähler
- führe i Schritte von M auf Wörtern
aus (kanonische Reihenfolge)
- wird ein Wort akzeptiert, drucke es aus
- falls
wird L nach endlich vielen Schritten gedruckt
- falls
wird w nie gedruckt
Beweis:
"<=": Konstruiere aus einem Auzähler für L eine TM M, die L erkennt
- zusätzliche Spur, die Rolle des Drucker übernimmt
- wenn neues Wort enummeriert wurde, vergleicht es M mit w
- falls
![](/pool/data/tex/bf1ddf671a756c653093e7ec9682c3f8.gif)
- falls
![](/pool/data/tex/cd976d0cd23a4b744b11353602cac33c.gif)
"=>": Konstruiere aus eine TM M, die L erkennt einen Aufzähler
- führe i Schritte von M auf Wörtern
![](/pool/data/tex/aa38f107289d4d73d516190581397349.gif)
- wird ein Wort akzeptiert, drucke es aus
- falls
![](/pool/data/tex/bf1ddf671a756c653093e7ec9682c3f8.gif)
- falls
![](/pool/data/tex/cd976d0cd23a4b744b11353602cac33c.gif)
Beweis: Wenn Sprachen
und
rekursiv (aufzählbar), dann auch
rekursiv (aufzählbar)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
![](/pool/data/tex/f0bfe2140faacda364f8c59f20b8ce82.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
Konstruieren eine TM M, die
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
- simuliere das Verhalten von
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- Falls
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
=> M akzeptiert offensichtlich die Eingaben von
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
Beweis: Wenn Sprachen
und
rekursiv, dann auch ihre Vereinigung
rekursiv
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/c5aa73771bff78b8ae2e10a05cb09058.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
Konstruiere eine TM M, die
![](/pool/data/tex/c5aa73771bff78b8ae2e10a05cb09058.gif)
- Simuliere das Verhalten von
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- Falls
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
=> M akzeptiert offensichtlich alle Eingaben aus
![](/pool/data/tex/c5aa73771bff78b8ae2e10a05cb09058.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
Beweis: Sprachen
und
rekursiv aufzählbar, so auch
rekursiv aufzählbar
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/c5aa73771bff78b8ae2e10a05cb09058.gif)
Beweis anders, als bei anderen Sätzen, da
Eingabe evtl. akzeptiert, M dies aber nie feststellen kann, da
evtl. nicht terminiert (
und
erkennen
und
nur)
=> verwende parallele Simulation der beiden TMn (statt einer sequentiellen)
- M verwendet zwei Bänder: auf einem wird
auf dem anderen
simuliert
- M merkt sich in ihrem Zustand, den momentanen Zustand von
und ![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- pro Rechenschritt wird abwechselnd eine Rechenschritt von
oder
simuliert (ein bit gibt an, welche TM im aktuellen Rechenschritt simuliert wird)
=> sichergestellt, dass M akzeptiert, falls
oder
akzeptieren
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
=> verwende parallele Simulation der beiden TMn (statt einer sequentiellen)
- M verwendet zwei Bänder: auf einem wird
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- M merkt sich in ihrem Zustand, den momentanen Zustand von
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- pro Rechenschritt wird abwechselnd eine Rechenschritt von
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
=> sichergestellt, dass M akzeptiert, falls
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
Beweis: Sprache L rekursiv, dann auch
rekursiv
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
![](/pool/data/tex/90a34c5feb01ce266340f81f2b97bf6b.gif)
![](/pool/data/tex/2865368a8dc74b8d449af384064cbf67.gif)
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
![](/pool/data/tex/90a34c5feb01ce266340f81f2b97bf6b.gif)
Beweis: Sind
und
rekursiv aufzählbar, so ist L rekursiv.
![](/pool/data/tex/3b0615c5a8ff0a3e8ac34d072df9ea13.gif)
![](/pool/data/tex/2697c0826768f9add114a38c52c744ef.gif)
Beispiel: Halteproblem
H ist rekursiv aufzählbar, wäre
auch rekursiv aufzählbar, dann wäre H rekursiv ![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
Maschinen, die L bzw.
erkennen.
TM M' entscheidet L durch parallele Simulation von
und
auf Eingabe w:
- M' akzeptiert w, sobald M akzeptiert
- M' verwirft w, sobald
akzeptiert
=> Terminierung: Da entweder
oder
sicher
Folge aus dem Lemma: L ist nicht rekursiv gdw. mind. eine der beiden Sprache L oder
nicht rekursiv aufzählbar ist
H ist rekursiv aufzählbar, wäre
![](/pool/data/tex/ece9f36c842bc066ce0144fd813b20c0.gif)
![](/pool/data/tex/564dde0e742a16c58c014be95a39953d.gif)
![](/pool/data/tex/bf713c3e9f3767ea321f74109b4cc475.gif)
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
TM M' entscheidet L durch parallele Simulation von
![](/pool/data/tex/69691c7bdcc3ce6d5d8a1361f22d04ac.gif)
![](/pool/data/tex/d7eca9c3834831765cc278bb764642f2.gif)
- M' akzeptiert w, sobald M akzeptiert
- M' verwirft w, sobald
![](/pool/data/tex/d7eca9c3834831765cc278bb764642f2.gif)
=> Terminierung: Da entweder
![](/pool/data/tex/4631ed4fd2fe4dbf2f7bb7ec1ed77cc1.gif)
![](/pool/data/tex/31809ee2d31edf685942a8bc28570f39.gif)
Folge aus dem Lemma: L ist nicht rekursiv gdw. mind. eine der beiden Sprache L oder
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
Sind rekursiv aufzählbare Sprachen abgeschlossen gegen ihr Komplement?
Nein!
Beweis:
L rekursiv aufzählbar =>
rekursiv aufzählbar => L rekursiv => alle rekursiv aufzählbaren Sprachen sind rekursiv (Widerspruch!)
Beweis:
L rekursiv aufzählbar =>
![](/pool/data/tex/a2c84776e80204766a4997afe85dbfee.gif)
reduzierbar
Es seien
und
Sprachen über
. Dann heißt
auf
reduzierbar (
), wenn es eine berechenbare Funktion
gibt, sodass für alle
gilt:
![](/pool/data/tex/3b31c108ed4b92f74123af169a0e643d.gif)
=>
ist also unter dem Gesichtspunkt der Berechenbarkeit nicht schwerer als ![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/01d66126947a770d765b444db9095131.gif)
![](/pool/data/tex/936d761554105f0e2c87754a9646232a.gif)
![](/pool/data/tex/0c45e03bcc795af48f72c87b6a40ee3b.gif)
![](/pool/data/tex/3b31c108ed4b92f74123af169a0e643d.gif)
=>
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
Lemma Reduktion
Falls
und
rekursiv (rekursiv aufzählbar) ist, so ist auch
rekursiv (rekursiv aufzählbar).
Beweis:
![](https://cobocards.s3.amazonaws.com/card/480_300/6/6445230.jpg)
akz.
akz. ![](/pool/data/tex/2af1409a3aac6d19a16a088f08030781.gif)
Falls
rekursiv ist, ist die Terminierung von
auf jeder Eingabe gesichert. Falls
rek. aufz. ist, ist die Terminierung von
auf Eingaben aus
gesichert.
![](/pool/data/tex/01d66126947a770d765b444db9095131.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
Beweis:
![](https://cobocards.s3.amazonaws.com/card/480_300/6/6445230.jpg)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/a3b66b1daaa3c50bbc2e1e8f58c9da7d.gif)
![](/pool/data/tex/2af1409a3aac6d19a16a088f08030781.gif)
Falls
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
Unterschied Unterprogrammtechnik und Reduktion
Reduktion ist eine spezielle Variante der Unterprogrammtechnik, bei der nach dem Unterprogrammaufruf keine Manipulation der Ausgabe mehr möglich ist.
Insbesondere ist es nicht möglich nach dem Unterprogrammaufruf das Akzeptanzverhalten zu invertieren (macht bei Aufruf einer rek. aufz. Sprache als Unterprogramm auch wenig Sinn, da es auf Wörter, die nicht zur Sprache gehören, möglicherweise nicht terminiert)
Insbesondere ist es nicht möglich nach dem Unterprogrammaufruf das Akzeptanzverhalten zu invertieren (macht bei Aufruf einer rek. aufz. Sprache als Unterprogramm auch wenig Sinn, da es auf Wörter, die nicht zur Sprache gehören, möglicherweise nicht terminiert)
Was ist eine Reduktion?
Eine Reduktion ist eine Technik zum Nachweis, ob eine Sprache rekursiv bzw. rekursiv aufz. oder nicht rekursiv bzw. nicht rek. aufzb. ist.
Diese bildet die Eingabe eines Problems auf die Eingabe eines anderen Problems ab. Sie wird deshalb auch Eingabe-Eingabe-Reduktion bzw. Many-One-Reduktion genannt
Diese bildet die Eingabe eines Problems auf die Eingabe eines anderen Problems ab. Sie wird deshalb auch Eingabe-Eingabe-Reduktion bzw. Many-One-Reduktion genannt
Beweis:
ist nicht rekursiv aufzählbar
![](/pool/data/tex/20e91f25445ec781e4ad2fbcb15614ab.gif)
Reduziere eine nicht rek. aufz. Sprache auf
:
nicht rek. aufz. =>
bzw. äquivalent ![](/pool/data/tex/89bdabd6386a8c3132b4e3331c20d9fb.gif)
Konstruiere eine berechenbare Funktion f, die alle Ja/Nein-Instanzen von
auf alle Ja/Nein-Instanzen von
abbildet.
w Eingabe für![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
1.) Wenn w keine gültige GN, dann f(w)=w
2.) Wenn w=<M> GN einer TM, dann sei f(w) GN einer TM M* mit folgender Eigenschaft: M* ignoriert die Eingabe und simuliert M auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
f ist offensichtlich berechenbar. Falls w keine GN ist, so gilt
und
Für w=<M> ist f(w)=<M*>:
|
=> M hält auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf jeder Eingabe
=> f(w)=<M*>
=> M hält nicht auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf keiner Eingabe
=> f(w)=<M*>![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)
![](/pool/data/tex/005e291af01e1f8456a32add6b9bc29b.gif)
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
![](/pool/data/tex/122b424e984e3cc587dd2f74a91fcb8c.gif)
![](/pool/data/tex/89bdabd6386a8c3132b4e3331c20d9fb.gif)
Konstruiere eine berechenbare Funktion f, die alle Ja/Nein-Instanzen von
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
![](/pool/data/tex/361c74716a074bcec144a5b2332ce324.gif)
w Eingabe für
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
1.) Wenn w keine gültige GN, dann f(w)=w
2.) Wenn w=<M> GN einer TM, dann sei f(w) GN einer TM M* mit folgender Eigenschaft: M* ignoriert die Eingabe und simuliert M auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
f ist offensichtlich berechenbar. Falls w keine GN ist, so gilt
![](/pool/data/tex/59e01cdab501e9b98c28013b91095210.gif)
![](/pool/data/tex/8d0d7a1744a558dbf58bf0ba1bf34966.gif)
Für w=<M> ist f(w)=<M*>:
![](/pool/data/tex/d828fde91ed58532ec5452bad83f65c4.gif)
=> M hält auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf jeder Eingabe
=> f(w)=<M*>
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
![](/pool/data/tex/59e01cdab501e9b98c28013b91095210.gif)
=> M hält nicht auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf keiner Eingabe
=> f(w)=<M*>
![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)
Beweis:
ist nicht rekursiv aufzählbar
![](/pool/data/tex/361c74716a074bcec144a5b2332ce324.gif)
![](/pool/data/tex/c7a945044f1c34ba619f7f3a677f8ddd.gif)
w Eingabe für
![](/pool/data/tex/4a53bd52e0a7ead577de5ce5e13d1f71.gif)
1.) Wenn w keine gültige GN ist, liegt w in
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
2.) Wenn w=<M>, so ist f(w)=<M'>. M' verhält sich auf Eingabe x wie folgt:
Falls |x|=i, simuliert M' die ersten i Schritte von M auf
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
f ist offensichtlich berechenbar.Falls w=<M> gilt:
![](/pool/data/tex/04283e113ea841f20c919fb328305d85.gif)
=> M hält nicht auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/ce63ea2c7462bda2d44e505c77f6ebf6.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/f20daf383541d27af9906a2160f757ff.gif)
=> f(w)=<M'>
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
![](/pool/data/tex/321b3029af48fc526efcf50eb591266e.gif)
=> M hält auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/1d98d5ab33d4e5b332fba49d7976a055.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/1d98d5ab33d4e5b332fba49d7976a055.gif)
=> f(w)=<M'>
![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)
Hilberts zehntes Problem
Beschreibe einen Algorithmus, der entscheidet, ob ein gegebenes Polynom mit ganzzahligen Koeffizienten eine ganzzahlige Nullstelle hat
N = {p / p ist ein Polynom mit einer ganzzahligen Nullstelle}
ist rekursiv aufzählbar:
Polynom p mit l Variablen (Wertbereich ist also abzählbar unendliche Menge aller l-Tupel mit Werten in Z:
)
Zähle nun nacheinander alle l-Tupel auf und werte p für dieses Tupel aus
Akzeptiere falls Auswertung Null ergibt
=> N wird erkannt
ist nicht rekursiv:
Falls es obere Schranke für Absolutwerte der Nullstellen gebe, müsste man nur endlich viele l-Tupel aufzählen und N wäre rekursiv Dies gilt allerdings nur für Polynome mit einer Variablen:
Für
mit ganzzahligen Koeffizienten gitl:
. Es gibt also keine Nullstelle mit Absolutwert größer als |a0|.
N = {p / p ist ein Polynom mit einer ganzzahligen Nullstelle}
ist rekursiv aufzählbar:
Polynom p mit l Variablen (Wertbereich ist also abzählbar unendliche Menge aller l-Tupel mit Werten in Z:
![](/pool/data/tex/78fbba7140209d7510f32ded22dd0cd2.gif)
Zähle nun nacheinander alle l-Tupel auf und werte p für dieses Tupel aus
Akzeptiere falls Auswertung Null ergibt
=> N wird erkannt
ist nicht rekursiv:
Falls es obere Schranke für Absolutwerte der Nullstellen gebe, müsste man nur endlich viele l-Tupel aufzählen und N wäre rekursiv Dies gilt allerdings nur für Polynome mit einer Variablen:
Für
![](/pool/data/tex/2e63bc72e16e91e167e60f00e6257812.gif)
![](/pool/data/tex/acff9d5ed7265b6b47d1cd7666a6436b.gif)
Postsches Korrespondenzproblem
korrespondierende Folge: Folge von Dominos aus einer Menge K von Dominos, sodass oben und unten dasselbe Wort steht. (Folge soll aus mind. einem Domino bestehen und Dominos dürfen sich wiederholen)
Instanz des PKP: besteht aus einer Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
und
nichtleere Wörter über einem endlichen Alphabet
sind.
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
gibt, also eine Folge, sodass gilt
.
=>PKP nicht rekursiv, aber rekursiv aufzählbar.
=>
ist nicht rekursiv aufzählbar
(Reduziere dazu MPKP auf PKP und H auf MKPK daraus folgt dass man H auf PKP reduzieren kann)
Instanz des PKP: besteht aus einer Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
![](/pool/data/tex/8d62e469fb30ed435a668eb5c035b1f6.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
![](/pool/data/tex/b4aba7a2c394906d729efedb68c297ea.gif)
![](/pool/data/tex/92c1fa9d21dad8c54563288784c4f009.gif)
=>PKP nicht rekursiv, aber rekursiv aufzählbar.
=>
![](/pool/data/tex/c0049e6f44e2055f5fe0b0177ec95eb7.gif)
(Reduziere dazu MPKP auf PKP und H auf MKPK daraus folgt dass man H auf PKP reduzieren kann)
Modifiziertes PKP
Modifikation: Startdomino
bestimmten, mit dem die korrespondierende Folge beginnen muss.
Instanz des MPKP: besteht aus einer geordneten Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
und
nichtleere Wörter über einem endlichen Alphabet
sind.
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
gibt, also eine Folge, sodass gilt
.
![](/pool/data/tex/19000b04273f664d7ea9c7a324d92ffc.gif)
Instanz des MPKP: besteht aus einer geordneten Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
![](/pool/data/tex/8d62e469fb30ed435a668eb5c035b1f6.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
![](/pool/data/tex/696c40b52e4e7fcfc792ed1c0b7b7aa5.gif)
![](/pool/data/tex/fdeb7bc5ec23e6bf37044c650f3e08b5.gif)
Beweis: MPKP
PKP
![](/pool/data/tex/de44c582df9d8d29dbbd70aca311c641.gif)
Definiere Funktion die Eingaben des MPKP auf Eingaben des PKP abbildet:
auf ![](/pool/data/tex/209d710b52d15ab97186ac98b743e904.gif)
Führe Sonderzeichen #, $ ein, die nicht im Alphabet von MPKP enthalten sind
Füge nach jedem
ein # ein
Füge vor jedem
ein # ein
Füge Startdomino
ein
Füge Schlussstein
ein
=> k Steine für MPKP, f(k) hat zwei Steine mehr
=> jede f(k) muss mit $ | #$ aufhören: egal was man legt, man muss oben mit # aufhören und unten mit nicht-# aufhören
=> jede Lösung muss mit Startdomino beginnen: einzige Möglichkeit oben mit # anzufangen
![](/pool/data/tex/5f3b26ff9a2ce16ef997e2ba478802dd.gif)
![](/pool/data/tex/209d710b52d15ab97186ac98b743e904.gif)
Führe Sonderzeichen #, $ ein, die nicht im Alphabet von MPKP enthalten sind
Füge nach jedem
![](/pool/data/tex/ef7232e9c1cdce5cf0d2c6150800b904.gif)
Füge vor jedem
![](/pool/data/tex/84100015f8e2af3094c042d96cbccacd.gif)
Füge Startdomino
![](/pool/data/tex/d02aaac6800029e51109230915c0202a.gif)
Füge Schlussstein
![](/pool/data/tex/fe8fd32f1dcd99390c23148f94499efd.gif)
=> k Steine für MPKP, f(k) hat zwei Steine mehr
=> jede f(k) muss mit $ | #$ aufhören: egal was man legt, man muss oben mit # aufhören und unten mit nicht-# aufhören
=> jede Lösung muss mit Startdomino beginnen: einzige Möglichkeit oben mit # anzufangen
Beweis: MPKP
PKP II ![](/pool/data/tex/7853dec865a6833f9e26e4a84ad1a9fa.gif)
![](/pool/data/tex/de44c582df9d8d29dbbd70aca311c641.gif)
![](/pool/data/tex/7853dec865a6833f9e26e4a84ad1a9fa.gif)
Sei
eine MPKP-Lösung also
für gewählte Symbole aus
. Dann ist
eine PKP-Lösung für f(K), denn
.
Gibt es eine Lösung für K bzgl. MPKP so gibt es auch eine Lösung für f(K) bzgl. PKP.
![](/pool/data/tex/1e98a8f753b04389068c580cd1caad8c.gif)
![](/pool/data/tex/a97c9ce160112e2ebd01a5d7cae48adc.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
![](/pool/data/tex/a3a1b9b62def6c2384c0915404d0912c.gif)
![](/pool/data/tex/3a8197600263e297f5be5a953d031734.gif)
Gibt es eine Lösung für K bzgl. MPKP so gibt es auch eine Lösung für f(K) bzgl. PKP.
Beweis: MPKP
PKP II ![](/pool/data/tex/b9862aa05204a9716dab5425eee141bb.gif)
![](/pool/data/tex/de44c582df9d8d29dbbd70aca311c641.gif)
![](/pool/data/tex/b9862aa05204a9716dab5425eee141bb.gif)
Sei
eine PKP Lösung minimaler Länge für f(K).
1.) Die Lösung beginnt und endet mit Anfangsstein
bzw. Schlussstein
weil nur diese mit demselben Zeichen beginnen/enden
2.) Der Anfangsstein kann nicht in der Mitte vorkommen, da sonst im oberen Wort zwei # aufeinanderfolgen würden, was im unteren unmöglich ist.
3.) Der Schlussstein ist der letzte Stein, da sonst $ vorher auftreten würde und wir die korrespondierende Folge nach dem ersten Vorkommen des $-Zeichen abschneiden könnten und damit eine kürzere gefunden hätten.
Die PKP-Lösung von f(K) hat also die Struktur:
![](/pool/data/tex/bad70747214329bffb311a912fbed02c.gif)
Daraus ergibt sich folgende MPKP-Lösung für K:
![](/pool/data/tex/0eac6172042a48d548a4a997ff5da777.gif)
Es gilt also:![](/pool/data/tex/b9862aa05204a9716dab5425eee141bb.gif)
![](/pool/data/tex/3460245c3b284c93f7d6adc40d109d1a.gif)
1.) Die Lösung beginnt und endet mit Anfangsstein
![](/pool/data/tex/18399a42fd1f5e322917428bdad85bb2.gif)
![](/pool/data/tex/6e339b11d7a533351b5260a70a3e14aa.gif)
2.) Der Anfangsstein kann nicht in der Mitte vorkommen, da sonst im oberen Wort zwei # aufeinanderfolgen würden, was im unteren unmöglich ist.
3.) Der Schlussstein ist der letzte Stein, da sonst $ vorher auftreten würde und wir die korrespondierende Folge nach dem ersten Vorkommen des $-Zeichen abschneiden könnten und damit eine kürzere gefunden hätten.
Die PKP-Lösung von f(K) hat also die Struktur:
![](/pool/data/tex/bad70747214329bffb311a912fbed02c.gif)
Daraus ergibt sich folgende MPKP-Lösung für K:
![](/pool/data/tex/0eac6172042a48d548a4a997ff5da777.gif)
Es gilt also:
![](/pool/data/tex/b9862aa05204a9716dab5425eee141bb.gif)
Beweis: H
MPKP
![](/pool/data/tex/de44c582df9d8d29dbbd70aca311c641.gif)
Gegeben sei die Eingabe (<M>,w) für H. Konstruiere berechnbare Funktion f als Menge M von Dominos M=f(<M>,w). Bilde ungültige Eingaben für H auf ungültige Eingaben für MPKP ab.
Simuliere dazu eine TM als Dominos.
Simuliere dazu eine TM als Dominos.
Simulation einer TM durch Dominos
Gegeben sei die Eingabe (<M>,w) für H. Konstruiere berechnbare Funktion f als Menge M von Dominos M=f(<M>,w). Bilde ungültige Eingaben für H auf ungültige Eingaben für MPKP ab.
1.) Startdomino: Startkonfiguration![](/pool/data/tex/a83ee70bf76f7fdd507618b6abf3d000.gif)
2.) Kopierdominos:
für alle ![](/pool/data/tex/b6e088b4910f747ab77100cfbe57ce5e.gif)
3.) Überführungssteine:![](/pool/data/tex/b682d29243ed2eba8462a5af10bd1b80.gif)
falls ![](/pool/data/tex/58e555ee26d29bde3afe470fd685450d.gif)
falls ![](/pool/data/tex/f385097bb69b5b78376666cc42a92e60.gif)
falls ![](/pool/data/tex/fc605fc034632edd37ac4d11ba9f3c7c.gif)
1.) Startdomino: Startkonfiguration
![](/pool/data/tex/a83ee70bf76f7fdd507618b6abf3d000.gif)
2.) Kopierdominos:
![](/pool/data/tex/2d0850b990ab9485c0c886b61d48f5aa.gif)
![](/pool/data/tex/b6e088b4910f747ab77100cfbe57ce5e.gif)
3.) Überführungssteine:
![](/pool/data/tex/b682d29243ed2eba8462a5af10bd1b80.gif)
![](/pool/data/tex/710d475432dbfed1324cdf1b1a7a2841.gif)
![](/pool/data/tex/58e555ee26d29bde3afe470fd685450d.gif)
![](/pool/data/tex/b5d7a26b0b5bc9657fb4a602e8d7ef77.gif)
![](/pool/data/tex/f385097bb69b5b78376666cc42a92e60.gif)
![](/pool/data/tex/d4b4d9513e0d502b6d7942a0dd9d8560.gif)
![](/pool/data/tex/fc605fc034632edd37ac4d11ba9f3c7c.gif)
Simulation durch Dominos Teil 2
4.) Überführungsdominos, die implizite Blanks berücksichtigen: ![](/pool/data/tex/5e01417a796e8ca16b2226e2ea510f27.gif)
falls ![](/pool/data/tex/fc605fc034632edd37ac4d11ba9f3c7c.gif)
falls ![](/pool/data/tex/2aaee9ee9a3871568e2b8586377535df.gif)
falls ![](/pool/data/tex/e461465eb75565716eca761a1cd4c40a.gif)
falls ![](/pool/data/tex/470d31f7a4aa0a769608f501eb3e1445.gif)
falls ![](/pool/data/tex/470d31f7a4aa0a769608f501eb3e1445.gif)
5.) Löschdominos:![](/pool/data/tex/00e325c965240da6f541e847d709bf81.gif)
und ![](/pool/data/tex/2594f25bf8c6037168ee8718b9ecdca9.gif)
![](/pool/data/tex/5e01417a796e8ca16b2226e2ea510f27.gif)
![](/pool/data/tex/347fad58f615ab43a7c68e31f2074811.gif)
![](/pool/data/tex/fc605fc034632edd37ac4d11ba9f3c7c.gif)
![](/pool/data/tex/ee8d89fa0c81e4ea866ff338a25fb506.gif)
![](/pool/data/tex/2aaee9ee9a3871568e2b8586377535df.gif)
![](/pool/data/tex/c0a067a19414f5b625f27db7d90fe1a3.gif)
![](/pool/data/tex/e461465eb75565716eca761a1cd4c40a.gif)
![](/pool/data/tex/64c1341e208e5171278384d8eade7e20.gif)
![](/pool/data/tex/470d31f7a4aa0a769608f501eb3e1445.gif)
![](/pool/data/tex/9d231e501c97e3db0e01d66a2f8e9670.gif)
![](/pool/data/tex/470d31f7a4aa0a769608f501eb3e1445.gif)
5.) Löschdominos:
![](/pool/data/tex/00e325c965240da6f541e847d709bf81.gif)
![](/pool/data/tex/e1240279d4dd2b927bb989f0d3314011.gif)
![](/pool/data/tex/2594f25bf8c6037168ee8718b9ecdca9.gif)
Korrektheit
durch Dominos Teil 1
![](/pool/data/tex/0dcbc3a9325d287f9dc54af8a8170b0d.gif)
1.) M hält auf w => ![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
mit
Start- und
Endkonfiguration im Zustand ![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
Man kann nun nach und nach Kopier- und Überführungsdominos legen, sodass der untere String die vollständige Konfigurationsfolge von M enthält
und der obere String ein Präfix des unteren ist ![](/pool/data/tex/bfe64bd7239fbe28b03e073bc5fff42e.gif)
Durch Hinzufügen der Löschdominos kann Rückstand des unteren ausgeglichen werden. Danach sind sie identisch bis auf
.
Durch hinzufügen des Abschlussdominos sind sie identisch:![](/pool/data/tex/8dc7dac91600f70763b604313439e497.gif)
Wenn M auf w hält gilt also![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Dann entspricht die Rechnung von M einer endlichen Konfigurationsfolge:
![](/pool/data/tex/16b35eb1777ad72cd54a657ff0157567.gif)
![](/pool/data/tex/3a3a31c01221cd0fa25152cb1c38f56c.gif)
![](/pool/data/tex/2d748fa42abdf5d8d84eb3beac40535c.gif)
![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
Man kann nun nach und nach Kopier- und Überführungsdominos legen, sodass der untere String die vollständige Konfigurationsfolge von M enthält
![](/pool/data/tex/6fc675aee097a488b776f610f893123a.gif)
![](/pool/data/tex/bfe64bd7239fbe28b03e073bc5fff42e.gif)
Durch Hinzufügen der Löschdominos kann Rückstand des unteren ausgeglichen werden. Danach sind sie identisch bis auf
![](/pool/data/tex/1da69fc07e76cc7ba73cad951a2ca649.gif)
Durch hinzufügen des Abschlussdominos sind sie identisch:
![](/pool/data/tex/8dc7dac91600f70763b604313439e497.gif)
Wenn M auf w hält gilt also
![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Korrektheit
durch Dominos Teil 2
![](/pool/data/tex/0dcbc3a9325d287f9dc54af8a8170b0d.gif)
M hält nicht auf w => ![](/pool/data/tex/15be2f22504eb7d8d0f4ff0163c41eac.gif)
Nehme zum Widerspruch an, dass M nicht auf w hält, aber
.
Nehme also an, dass eine korrespondierende Folge existiert.
1.) Mit Kopier- und Übergangsdominos entsteht bei Einhaltung der Übereinstimmung des oberen und unteren Strings die Konfigurationsfolge von M auf w. (Der obere String folgt dabei dem unteren String)
2.) Irgendwann muss auch der Abschluss- oder ein Löschdomino vorkommen. Diese enthalten jedoch im oberen Wort den Zustand
. Das Hinzufügen dieses Dominos verletzt die Übereinstimmung der beiden Strings, da im unteren String nie der Stoppzustand erreicht wird, da die Rechnung nicht terminiert. (Widerspruch zur Annahme, dass eine korrespondierende Folge existiert.)
![](/pool/data/tex/15be2f22504eb7d8d0f4ff0163c41eac.gif)
Nehme zum Widerspruch an, dass M nicht auf w hält, aber
![](/pool/data/tex/4178344d8d4c1a49a905c06467e4a223.gif)
Nehme also an, dass eine korrespondierende Folge existiert.
1.) Mit Kopier- und Übergangsdominos entsteht bei Einhaltung der Übereinstimmung des oberen und unteren Strings die Konfigurationsfolge von M auf w. (Der obere String folgt dabei dem unteren String)
2.) Irgendwann muss auch der Abschluss- oder ein Löschdomino vorkommen. Diese enthalten jedoch im oberen Wort den Zustand
![](/pool/data/tex/30edc55565b06d9a34b636a00ff32208.gif)
WHILE-Syntax
Turing-mächtige Programmiersprache
konstante Anzahl von Variablen | ![]() |
drei Konstanten | -1 0 1 |
vier Symbole | ; := + ![]() |
drei Schlüssel Wörter | WHILE DO END |
Zuweisung | Für jedes ![]() ![]() |
Hintereinanderausführung | ![]() ![]() |
WHILE-Konstrukt | P WHILE-Programm: WHILE ![]() |
WHILE-Semantik
WHILE Porgramme berechnen k-stellige Funktionen der Form ![](/pool/data/tex/0deb8561c2b4d3793cd12b8c0b177e00.gif)
Eingabe ist in Variablen
enthalten
alle anderen Variablen werden mit 0 initialisiert
Resultat ist die Zahl, die sich am Ende der Rechnung in der Variablen
ergibt
![](/pool/data/tex/0deb8561c2b4d3793cd12b8c0b177e00.gif)
Eingabe ist in Variablen
![](/pool/data/tex/98ba3b143f705a17c9d6f60a987d2a6b.gif)
alle anderen Variablen werden mit 0 initialisiert
Resultat ist die Zahl, die sich am Ende der Rechnung in der Variablen
![](/pool/data/tex/3e0d691f3a530e6c7e079636f20c111b.gif)
Beweis: WHILE ist Turing-mächtig
Jede TM kann durch RAM mit konstant vielen Registern mit eingeschränktem Befehlssatz simuliert werden(LOAD,CLOAD,STORE,CADD,CSUB,GOTO, if c(0)!=0 GOTO, END)
Sei
ein RAM-Programm, dass aus l Zeilen und k Registern für natürliche Zahlen besteht
1.) Jede Zeile des RAM-Programms wird in eine WHILE Programm transformiert (Zeile i ist im WHILE Programm
)
dazu: Inhalt von Register c(i) in Variable![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
- bei k Registern also![](/pool/data/tex/4075e73f1c052bc71e0e66d56b0651f0.gif)
- Befehlszähler in Variable
realisiert
-
Variable mit initialem Wert 0
2.) Füge WHILE-Programme Pi' zu einem großen Programm P zusammen:
![](/pool/data/tex/b3f709e49994e0106e7594ef20abd05d.gif)
WHILE
DO
![](/pool/data/tex/02cc322877a219cd94ceed0a57489e3c.gif)
END Semantik: Falls
führe
aus.
Das WHILE-Programm berechnet also dieselbe Funktion wie![](/pool/data/tex/d744af1210420bc542a6a63b938a5601.gif)
Sei
![](/pool/data/tex/d744af1210420bc542a6a63b938a5601.gif)
1.) Jede Zeile des RAM-Programms wird in eine WHILE Programm transformiert (Zeile i ist im WHILE Programm
![](/pool/data/tex/08b0104e514f16d489cc743b6f66d906.gif)
dazu: Inhalt von Register c(i) in Variable
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
- bei k Registern also
![](/pool/data/tex/4075e73f1c052bc71e0e66d56b0651f0.gif)
- Befehlszähler in Variable
![](/pool/data/tex/bad8e9c82dfa1fb4a31da372281affa9.gif)
-
![](/pool/data/tex/05d3e17d000e32a4bbd754019fdf0c09.gif)
2.) Füge WHILE-Programme Pi' zu einem großen Programm P zusammen:
![](/pool/data/tex/b3f709e49994e0106e7594ef20abd05d.gif)
WHILE
![](/pool/data/tex/6040d99e8c38c7846a2c9c3d15dbf805.gif)
![](/pool/data/tex/02cc322877a219cd94ceed0a57489e3c.gif)
END Semantik: Falls
![](/pool/data/tex/30ac266d032d55112eaf4c93e000b77f.gif)
![](/pool/data/tex/08b0104e514f16d489cc743b6f66d906.gif)
Das WHILE-Programm berechnet also dieselbe Funktion wie
![](/pool/data/tex/d744af1210420bc542a6a63b938a5601.gif)
Beweis: WHILE ist Turing-mächtig RAM-Befehle als WHILE
RAM-Befehle in der Form
implementieren.
1.) LOAD i:![](/pool/data/tex/0ae02d56d630b767d11e57a7eab94a48.gif)
2.) CLOAD i: Weise x0 den Wert Null zu und addiere danach i mal eine 1.![](/pool/data/tex/efbb0a49991eccccf7fd7de882191d8a.gif)
3.) STORE i:![](/pool/data/tex/79dff1958c65d6b6d2757a43d265c9b9.gif)
4.) CADD i:![](/pool/data/tex/7347d350a8319157727c66e4435cc330.gif)
5.) CSUB i:
6.) GOTO i:![](/pool/data/tex/49a9f2e23ab03e53b41a0c7dcb535f8d.gif)
7.) END: Befehlszähler auf Null setzen![](/pool/data/tex/3c64b4f767016443a6cf5d62016ea339.gif)
![](/pool/data/tex/8cca0d0ab2b559b49bf68e699cf034a8.gif)
1.) LOAD i:
![](/pool/data/tex/0ae02d56d630b767d11e57a7eab94a48.gif)
2.) CLOAD i: Weise x0 den Wert Null zu und addiere danach i mal eine 1.
![](/pool/data/tex/efbb0a49991eccccf7fd7de882191d8a.gif)
3.) STORE i:
![](/pool/data/tex/79dff1958c65d6b6d2757a43d265c9b9.gif)
4.) CADD i:
![](/pool/data/tex/7347d350a8319157727c66e4435cc330.gif)
5.) CSUB i:
6.) GOTO i:
![](/pool/data/tex/49a9f2e23ab03e53b41a0c7dcb535f8d.gif)
7.) END: Befehlszähler auf Null setzen
![](/pool/data/tex/3c64b4f767016443a6cf5d62016ea339.gif)
RAM-Befehle als WHILE-Programm: IF c(0) != 0 GOTO j
![](/pool/data/tex/bad8e9c82dfa1fb4a31da372281affa9.gif)
![](/pool/data/tex/0954a08a2c8cf0f4e7bd803270720932.gif)
![](/pool/data/tex/297820831b9f687823628a91a487c6f1.gif)
![](/pool/data/tex/a15b936fb1161f77c0dd6cc4d7feaa0f.gif)
WHILE
![](/pool/data/tex/1d3191f50738594dbd99857f23b36168.gif)
![](/pool/data/tex/5c61715f1a70a7b0094de5d2865bf623.gif)
![](/pool/data/tex/2b616b5d8a6f152c97bdcfb86d9b98bd.gif)
END
LOOP-Programme
ersetze WHILE durch LOOP-Schleife:
LOOP
DO P END (
darf nicht in P vorkommen!)
=> P wird sooft ausgeführt, wie
es vorgibt
=> jedes LOOP-Konstrukt kann durch ein WHILE-Konstrukt ersetzt werden, aber nicht umgekehrt
=> LOOP-Programme terminieren immer, da man bei Eintritt in LOOP-Schleife weiß, wie oft diese ausgeführt wird (mit WHILE kann man dagegen Endlosschleifen konstruieren) => nicht alle Funktionen, die auf TM berechenbar sind, sind es auch LOOP-berechenbar
=> LOOP ist nicht TM-mächtig (Möglichkeit der Nicht-Terminierung ausgeschlossen)
Beweis: (berechenbare totale) Funktion gefunden, die von einer TM berechnet werden kann nicht aber durch ein LOOP-Programm:
Ackermann-Funktion
![](/pool/data/tex/d97e695550873bb99afb851ace51dd8f.gif)
A(0,n) = n+1 für n >=0
A(m+1,0) = A(m,1) für m>=0
A(m+1,n+1) = A(m,A(m+1,n)) für m,n >=0
LOOP
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
=> P wird sooft ausgeführt, wie
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
=> jedes LOOP-Konstrukt kann durch ein WHILE-Konstrukt ersetzt werden, aber nicht umgekehrt
=> LOOP-Programme terminieren immer, da man bei Eintritt in LOOP-Schleife weiß, wie oft diese ausgeführt wird (mit WHILE kann man dagegen Endlosschleifen konstruieren) => nicht alle Funktionen, die auf TM berechenbar sind, sind es auch LOOP-berechenbar
=> LOOP ist nicht TM-mächtig (Möglichkeit der Nicht-Terminierung ausgeschlossen)
Beweis: (berechenbare totale) Funktion gefunden, die von einer TM berechnet werden kann nicht aber durch ein LOOP-Programm:
Ackermann-Funktion
![](/pool/data/tex/d97e695550873bb99afb851ace51dd8f.gif)
A(0,n) = n+1 für n >=0
A(m+1,0) = A(m,1) für m>=0
A(m+1,n+1) = A(m,A(m+1,n)) für m,n >=0
![](/pool/img/avatar_40_40.gif)
Kartensatzinfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010
Schlagwörter Karten:
Alle Karten (76)
keine Schlagwörter