Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

: Menge der Wörter der Länge k über dem Alphabet



: Kleenescher Abschluss. Alle Wörter über , die wir z.B. in kanonischer Reihenfolge der Länge nach aufzählen können: ,0,1,00,01,...

Eine Sprache ist eine Menge von Wörter über .

Eingabe: eine binär kodierte Zahl
Ausgabe: ein binär kodierter Primfaktor von p

Relation mit



=> es gibt mehrer mögliche Ausgaben, deshalb als Relation modelliert

Eingabe: zwei binär kodierte Zahlen
Ausgabe: die binär kodierte Zahl

=>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:

Eingabe ist dann kodiert als:

und Ausgabe

=>Problem mit "Ja-Nein-Frage"



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.

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

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 erreicht ist.

"Schnappschuss" der Rechnung zu einem bestimmten Zeitpunkt

Konfiguration: ist ein String mit und
auf dem Band steht eingerahmt von Blanks und der Zustand ist q und der Kopf steht unter dem ersten Zeichen von
Bsp.: 0001011 Kopf steht auf rot
direkte Nachfolgekonfiguration: ist d.Nkonf. von , falls in einem Rechenschritt aus entsteht:
Nachfolgekonfiguration: von , falls in endlich vielen Rechenschritten aus entsteht.


Die Rechnung terminiert, wenn Stoppzustand erreicht ist. Dann gibt es keine Nachfolgekonfiguration.

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.

..ist die Zahl der besuchten Speicherzellen. Dieser kann auch unbeschränkt sein.

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

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.

allgemein:

Entscheidungsprobleme:

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 .

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:


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!)

Variablen: pro Variable eine Spur reservieren.

Unterprogramme: eine Spur als Prozedurstack reservieren.

Verfügt über k-Bänder mit jeweils unabhängigem Kopf.

Band 1: Eingabe/Ausgabe Band
Bänder 2-k: initial mit B* beschrieben



Funktionsweise, Laufzeit und Platzbedarf analog zur allgm. 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

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.

- Modelle sind gleich mächtig: können also gleiche Funktionen berechnen
- bzgl. logarithmischem Kostenmaß sind Laufzeiten der Modelle ähnlich
- gegenseitige Simulation mit polynomiellem Zeitverlust

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

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
und Menge der Sprachen ist überabzählbar => es gibt mehr Sprachen als TMn

Das i-te Wort bzgl. der kanonischen Reihenfolge () ist genau dann in D, wenn die i-te TM () dieses Wort nicht akzeptiert
Matrixanschauung:



Diagonalsprache lässt sich auf der Diagonalen der Matrix ablesen:

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

2.Fall: liegt nicht in D
- dann verwirft die Eingabe , weil die Sprache entscheidet
- Wegen der Definition von D muss aber in D liegen

Widerspruchsbeweis:
- nehme an es ex. TM , die entscheidet
=> hält auf Eingabe w, gdw.

- Konstruiere TM M, die als Unterprogramm aufruft:

M startet auf der vorliegenden Eingabe

M negiert Ausgabe von
=> M entscheidet offensichtlich L.
Widerspruch zur Unentscheidbarkeit von  L.

=> Komplement der Diagonalsprache ist unentscheidbar

Entscheiden, ob ein Programm auf einer bestimmten Eingabe terminiert.

ist nicht rekursiv, aber rekursiv aufz.
(Eine TM , die erkennt, aktzeptiert als Eingabe nur TMs, die auf Epsilon halten, TMs die dies nicht tun, halten also nie auf Eingabe Epsilon und damit muss darauf auch nicht halten.)

=> ist nicht rekursiv aufz. (andernfalls wäre rekursiv)

Eine Sprache L wird von einer TM M entscheiden, wenn M auf jeder Eingabe hält und genau die Wörter aus L akzeptiert.

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.

Eine Sprache L heißt semi-entscheidbar, wenn es eine TM gibt, die L erkennt.

Bsp: Halteproblem (S.34)

- 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.

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

zwei TMn, die bzw. entscheiden (erkennen).

Konstruieren eine TM M, die entscheidet (erkennt)

- simuliere das Verhalten von auf w, dann das Verhalten von auf w
- Falls und akzeptieren, so auch M

=> M akzeptiert offensichtlich die Eingaben von , da sowohl als auch auf jeder Eingabe halten. Also entscheidet (erkennt) M die Sprache .

und TMn, die bzw. entscheiden.

Konstruiere eine TM M, die entscheidet:

- Simuliere das Verhalten von auf w, danach das von auf w
- Falls oder akzeptieren, so auch M.

=> M akzeptiert offensichtlich alle Eingaben aus , da sowohl als auch auf jeder Eingabe halten. Also entscheidet M ##L_1 \cup L_2#.

Tm, die L entscheidet. Man erhält TM , die entscheidet, indem man das Akzeptanzverhalten von invertiert.

Beispiel: Halteproblem
H ist rekursiv aufzählbar, wäre auch rekursiv aufzählbar, dann wäre H rekursiv

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

Nein!
Beweis:
L rekursiv aufzählbar => rekursiv aufzählbar => L rekursiv => alle rekursiv aufzählbaren Sprachen sind rekursiv (Widerspruch!)

Es seien und Sprachen über . Dann heißt auf reduzierbar (), wenn es eine berechenbare Funktion gibt, sodass für alle gilt:

                   

=> ist also unter dem Gesichtspunkt der Berechenbarkeit nicht schwerer als

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)

und nicht rekursiv aufzählbar.

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

Modifikation: Startdomino bestimmten, mit dem die korrespondierende Folge beginnen muss.

Instanz des MPKP: besteht aus einer geordneten Menge
         
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

.

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.

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.

6.)Abschlussdomino:

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-Programme:
WHILE-Konstrukt	P WHILE-Programm: WHILE DO P END

WHILE Porgramme berechnen k-stellige Funktionen der Form

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

RAM-Befehle in der Form implementieren.
1.) LOAD i:
2.) CLOAD i: Weise x0 den Wert Null zu und addiere danach i mal eine 1.
3.) STORE i:
4.) CADD i:
5.) CSUB i:

6.) GOTO i:
7.) END: Befehlszähler auf Null setzen

Befehlszähler b     Hilfsvariable help

(b:=b+1)
        (help := c(0))
WHILE   DO (while help != 0 do)
   (b:=j)

   (help :=0)
END