Bei dem $P-NP$-Problem geht es um die Frage wie die beiden Komplexitätsklassen zueinander stehen. Das Skript fasst sich nur sehr kurz, was  dieses Thema angeht, so dass ich beschlossen habe es hier noch einmal im Detail aufzuarbeiten.

Das $P-NP$-Problem gehört zu den Millenium-Problemen, d.h. es winken eine Million USD wenn es gelöst wird. Aber eine Million USD sind im Vergleich zu den Folgen, die z.B. $P=NP$ (beide Komplexitätsklassen sind gleich) auslösen würde keine Erwähnung wert. Es wäre uns auf einen Schlag möglich für jedes Problem in $NP$ einen effizienten Algorithmus anzugeben.

Als Beispiel nehmen wir das Faktorisierungsverfahren, auf dem sehr viele kryptographische Algorithmen (u.a. RSA oder das Verfahren von Diffie-Hellmann zum Schlüsselaustausch) basieren. Diese Algorithmen gehen davon aus, dass das Faktorisierungsproblem nicht effizient zu lösen ist. Es wäre das blanke Chaos, würde sich herausstellen, dass $P=NP$. $P\neq NP$ wäre hingegen nicht so schlimm.

Machen wir uns einmal klar, was $P$ und $NP$ denn nun wirklich sind. Dazu betrachten wir zunächst eine etwas größere Klasse.

Klassifizierung $EXPTIME$

In $EXPTIME$ liegen Probleme, die auf einer deterministischen Turingmaschine in $O(2^n)$, d.h. in exponentieller Zeit, entschieden werden können. Hier ist $n$ die Eingabelänge.

Es ist nicht schwer zu sehen, dass man hier nur für sehr kleine Probleminstanzen effizient nach einer Lösung suchen kann. Für größere Eingabelängen $n$ wird die Suche ungleich schwerer.

Was wäre so ein Problem, dass deterministisch in exponentieller Zeit lösbar wäre? Na klar, das Problem des Handlungsreisenden (auch TSP, travelling salesman, genannt). Der folgende Abschnitt basiert mehrheitlich auf dem Artikel aus der Wikipedia.

Beispiel TSP

Das TSP gehört zur der Klasse der Optimierungsprobleme. Bei diesem Problem geht es darum für eine gegebene Anzahl Städte und einer Entfernung zwischen diesen den kürzesten Weg für einen Rundkurs zu finden.

Diese Problem hat eine Vielzahl an Anwendungsmöglichkeiten (Logistik, Design von Mikrochips, etc.), so dass eine optimale Lösung durchaus wünschenswert erscheint.

Leider haben wir hier, in Abhängigkeit der Anzahl der zu besuchenden Punkte, nur dann eine optimale Lösung wenn wir jeden Punkt prüfen. Das Wachstum ist also exponentiell und zweifellos gehört TSP zur Klasse $EXPTIME$, zumindest bei seinem deterministischen Lösungsansatz.

Auch wenn mittlerweile für mehrere Tausend Punkte optimale Lösungen durch heuristische und exakte Verfahren gefunden wurden, so bleibt das Problem gleich: mit wachsendem $n$ (der Anzahl der Punkte) steigt unser Aufwand immer noch exponentiell.

Graphisch ausgedrückt (geklaut aus der Wikipedia):

Frage: Wie ist der kürzeste Weg von $A$ nach $A$ über alle Punkte?

Während das bei $4$ Punkten noch einfach ist, wird es für $100.000$ Punkte schon deutlich schwerer.

Es sind derzeit nur effiziente, heuristische Algorithmen bekannt, die die Lösung approximieren. Z.B. der Algorithmus von Christofides, der in polynomieller Laufzeit eine Lösung approximieren kann, die maximal $1.5$ Mal so lang ist wie die optimale Lösung.

Für exakte Lösungen gilt: jede Rundreise muss berechnet und die kürzeste ausgewählt werden. Bei $15$ Städten haben wir $43$ Mrd. Möglichkeiten. Hat man einen Rechner, der die Lösung für $30$ Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als $40$ Tage.

Die Folien der RWTH Aachen zeigen eine schöne Tabelle, die ich hier Snapshotten möchte:

Das Beispiel führt vor Augen, dass uns sehr daran gelegen, dass wir Probleme nicht in Exponentialzeit lösen müssen.

Nachdem wir die Optimierungsvariante haben, kommen wir zum Bindeglied des $TSP$ zu der Klasse $NP$: uns geht es zunächst nicht um Optimierung, sondern um eine Entscheidung.

Die Entscheidungsvariante des $TSP$ ist:

Gibt es eine Tour mit Kosten ${}\leq b$?

Und hier beginnt unsere Reise: während wir hier wieder alle Wege durchprobieren und so in der Klasse der Exponentialzeit-Algorithmen landen, können wir uns das Leben deutlich einfacher machen. Aber dazu gleich mehr.

Ich gehe auf das $TSP$ nun nicht weiter ein, da es mir nur um $P-NP$ geht und die Ausführungen bis hierhin für diese Betrachtung ausreichen.

Kleiner Exkurs zum Schluss: Durch die Hierarchiesätze können wir z.B. zeigen, dass $P\subsetneq EXPTIME$ ist. Damit gibt es in $EXPTIME$ Probleme, die nicht in $P$ liegen.

Klassifizierung $P$

Ein Problem in $P$ bedeutet, dass es effizient lösbar ist. Effizient heißt: die deterministische Turingmaschine, die das Problem löst ist nach oben durch ein Polynom $n^k$ beschränkt, wobei $n$ die Länge der Eingabe ist. Wichtig hieran ist: $k$ ist zwar beliebig, aber absolut unabhängig von unserer Eingabe!

Ein Beispiel für ein Problem in der Komplexitätsklasse $P$ ist das $PRIMES$.

Beispiel $PRIMES$

Hier ist die Frage ob eine Zahl $x$ eine Primzahl ist oder nicht.

Die Antwort auf diese Frage ist ziemlich simpel: wir testen einfach aus ob alle Zahlen von $2$ bis $x-1$ unsere Zahl $x$ ohne Rest teilen können. Wenn das nicht der Fall ist, ist die Zahl eine Primzahl.

Mit dem AKS-Algorithmus gibt es sogar einen, der das in Polynomzeit entscheiden kann. Damit gehört $PRIMES$ tatsächlich zur Komplexitätsklasse $P$.

Nach dem der Urvater der AKS-Algorithmen gefunden wurde, wurden weitere ersonnen, die die Laufzeit noch ein Stück nach unten korrigierten. Der schnellste bekannte Algorithmus aus der AKS-Familie terminiert in $O((log\text{ }N)^{6+\varepsilon})$.

Kommen wir nun zur Komplexitätsklasse, die uns so brennend interessiert.

Klassifizierung $NP$

Ist ein Problem in $NP$, so bedeutet es, dass es effizient prüfbar ist. In diesem Fall heißt effizient ebenfalls: die deterministische Turingmaschine, die prüft ob das Zertifikat $z$ zum Problem $X$ (ein Zertifikat ist ein Lösungsvorschlag für ein Problem), ist nach oben durch ein Polynom $n^k$ beschränkt, wobei $n$ die Länge der Eingabe ist.

Gemerkt, was der Unterschied zwischen $NP$ und $P$ ist? Es ist ein Unterschied ob wir ein Problem lösen oder "nur" einen Lösungsvorschlag prüfen.

Was bedeutet es für unser $TSP$?

Beispiel $TSP$-Instanz

Nehmen wir unsere $4$ Punkte aus dem obigen Beispiel und stellen uns die Frage:

Gibt es einen Weg von $A$ nach $A$ mit Länge ${}\leq{100}$?

Das ist ein Entscheidungsproblem. Und hier müssten wir im schlimmsten Fall nun alle Wege durchprobieren bis wir einen Weg finden, der kürzer als/gleich $100$ ist. Was bei vielen Punkten schon eine beträchtliche Zeit in Anspruch nehmen kann, wie wir gesehen haben. Dieses "Durchprobieren" ist genau unser $N$ aus $NP$. Das Orakeln einer Lösung.

Lassen wir das Orakeln weg und geben eine Lösung vor, bleibt nur noch $P$: die Prüfung einer gegebenen Lösung auf ihre Korrektheit. Und das können wir ziemlich zackig bewerkstelligen:

Wir prüfen die Kanten zwischen den Knoten und rechnen sie einfach zusammen:

$A\rightarrow{C}\rightarrow{D}\rightarrow{B}\rightarrow{A}\Rightarrow{{42}\rightarrow{12}\rightarrow{34}\rightarrow{20}=108}$

Nope, das war nichts. Versuchen wir es mit:

$A\rightarrow{D}\rightarrow{C}\rightarrow{B}\rightarrow{A}\Rightarrow{{35}\rightarrow{12}\rightarrow{30}\rightarrow{20}=97}$

Bingo!

Man sieht leicht, dass wir zur Prüfung einer vorgegebenen Lösung auf einer deterministischen Turingmaschine deutlich weniger Zeit benötigen als alle Wege durchzuprobieren.

Und nun holen wir uns unser $N$ aus $NP$, indem wir orakeln. Wir raten einfach alle Kombinationen und prüfen sie polynomiell durch unsere deterministische "Kontrollturingmaschine".

Im Schlimmsten Fall haben wir zwar immer noch einen exponentiellen Aufwand, aber vielleicht raten wir so gut, dass die Kombination $A\rightarrow{D}\rightarrow{C}\rightarrow{B}\rightarrow{A}$ die erste geratene Möglichkeit ist und wir schon nach dem ersten Orakeln eine Lösung gefunden haben.

Und genau das bedeutet $NP$: raten und prüfen. Oder ganz, ganz frei interpretiert: Orakel$N$ und $P$rüfen.

Codieren wir den Graphen als Turingmaschine, so hat z.B. der Zustand $A$ drei mögliche Folgezustände (wir können zu $B$, $C$ oder $D$ reisen). Es existieren also drei mögliche Zustandsübergänge, von denen wir einen wählen können. Genau hier beginnt das Raten/Orakeln, unser $N$ aus $NP$. Anschließend haben wir zwei Möglichkeiten zur Auswahl, usw.

So geht dann unsere $NTM$ für das $TSP$ vor und rät eine Rundreise. Wir brechen ab wenn die Kosten höher sind als $b$ oder wir bei unserem Ausgangsknoten landen ohne alle Knoten besucht zu haben.

Zusammenfassend lässt sich sagen: $NP$ bedeutet orakeln und prüfen. Und das Prüfen geschieht in maximal polynomieller Zeit.

Habt Ihr nun ein Gefühl dafür, was $NP$ bedeutet? Gut.

Nachdem wir nun alle notwendigen Komplexitätsklassen $EXPTIME$, $P$ und $NP$ besprochen haben, sollte euch klar sein wie der Zusammenhang zwischen $P$ und $NP$ ist.

Jetzt können wir auch die Frage stellen, die das $P-NP$-Problem beschreibt:

Gilt $P=NP$ oder $P\neq{NP}$?

In Worten:

Sind die Klassen $P$ und $NP$ gleich oder nicht,

bzw.

kann jede Sprache, die nicht-deterministisch in Polynomzeit entschieden werden kann auch deterministisch in Polynomzeit entschieden werden?

Derzeit gehen alle die meisten von letzterem aus. Die Folgen wären, wie gesagt, übersichtlich wenn das stimmt. Dafür müssten wir nur zeigen, dass es in $NP$ Probleme gibt, die definitiv nicht deterministisch polynomiell lösbar, also nicht in $P$ sind.

Graphisch aufgearbeitet sieht die hier beleuchtete, problematische Beziehung zwischen $P$ und $NP$ so aus:

Entnommen aus den Folien der TUM.

Und welche Möglichkeiten haben wir nun um $P=NP$ oder $P\neq{NP}$ zu beweisen?

1. Konstruktiver Beweis
   Wir finden einen polynomiellen Algorithmus, der ein $NP$-Vollständiges Problem polynomiell löst. Die Vollständigkeit ist wichtig, so dass wir diesen Algorithmus auch auf alle anderen aus $NP$ reduzieren können müssen um die Klasse komplett abzudecken.
   Schaffen wir es also z.B. $TSP$ deterministisch polynomiell zu lösen, haben wir - da $TSP$ eben $NP$-vollständig ist, nichts geringeres als $P=NP$ bewiesen.
2. Nicht-konstruktiver Beweis
   Nicht-konstruktiv bedeutet, dass man keine konkrete Lösung angibt, aber eindeutig auf die Existenz einer Lösung schließen kann.
   Man kann hier auch einen indirekten Beweis führen, indem man annimmt, es gäbe keine Lösung und diesen Satz zu einem Widerspruch führt. Daraus kann man dann schließen, dass es eine Lösung geben muss. Aber welche das ist, wird nicht genannt.

Also an die Arbeit

Ich hoffe, ich konnte euch die Beziehung zwischen $P$ und $NP$ in diesem Beitrag etwas deutlicher machen.

Wie immer: Bei Ungenauigkeiten, ab in die Kommentare.

Update: Schnitzer im Projektionssatz aufgefallen. Fixed.

Als ich die letzten Beiträge zu Kurseinheit 5 von TIA durchgegangen bin, ist mir aufgefallen, dass einige Beweise doch noch nicht so nachvollziehbar sind, wie ich das gerne hätte.

Nach dem Editieren kam ich auf eine Seitenzahl von über 20. Schon wieder. Da blieb mir also nichts anderes übrig, als den Beitrag zu KE6 erneut zu trennen. Schwierigkeiten machten mir aber die Kommentare zu den Lernzielen als alles noch ein einzelner Beitrag war. Diese zu verschieben war ohne manuellen Eingriff in die Datenbank nicht möglich.

Solltet Ihr daher auf Kommentare treffen, die nicht unbedingt zu dem Beitrag hier passen: meine Schuld. Sie gehören dann zu einem der drei anderen.

Dieser Artikel ist brandneu und die anderen Beiträge zu KE6 sind teilweise massiv überarbeitet worden. Eine erneute Lektüre könnte sich also lohnen wenn Ihr bei KE6 der theoretischen Informatik A noch strauchelt und den Sachverhalt gerne mal in anderen Worten gelesen hättet.

Lange Rede, kurzer Sinn: Das sind also die Beiträge zu Kurseinheit 6.

• TIA: Rekursive und rekursiv-aufzählbare Mengen (Lernziele KE6, 1/4)
• TIA: Bild- und Projektionssatz (Lernziele KE6 2/4)
• TIA: Halte- Äquivalenz- und Korrektheitsproblem, Reduzierbarkeit, Satz von Rice (Lernziele KE6, 3/4)
• TIA: Gödel'scher Unvollständigkeitssatz (Lernziele KE6, 4/4)

Dieser dreht sich komplett um den Bild- und Projektionssatz. Ursprünglich war er nicht einmal eine halbe Seite lang. Als ich den Beweis dann Schritt für Schritt nachvollzog, wuchs er auf die aktuelle Größe heran. Tja, und da ist er nun.

Lernziel 5

Charakterisierung der r.a. Mengen durch Bild- und Projektionssatz

Die Charakterisierung ist wie folgt definiert:

1. $A \subseteq \mathbb{N}$ ist r.a. gdw. $A = \emptyset$ oder $A = Bild(g)$ für ein $g \in R^{(1)}$

2. $A \subseteq \mathbb{N}^k$ ist r.a. gdw. es eine rekursive Menge $B \subseteq \mathbb{N}^{k+1}$ gibt mit $A = \{x \in \mathbb{N}^k \mid (\exists t)(x,t) \in B\}$

Nr. 1 bedeutet, dass eine Menge $A$ dann rekursiv ist, wenn sie von einer totalen, rekursiven Funktion $g$ aufgezählt werden kann, d.h. dass $A$ Bild dieser Funktion ist.

Nr. 2 ist der Projektionssatz: eine Menge ist r.a. wenn sie die Projektion einer rekursiven Menge ist. Das Bild im Skript ist relativ eindeutig wenn man weiß, nach was man schauen muss. Ich nehme hierzu ein konkretes Beispiel mit $k=1$ und der Menge $B = \{(1,4),(1,2),(3,3),(3,2),(3,1),(5,1),(6,1)\}$, welche aus $7$ Tupeln besteht.

Wir haben also zwei Achsen, die wir wie in der Definition $t$ und $x$ nennen. So sieht es dann aus:

Das Bild ist angelehnt an das aus dem Skript, nur mit einer Sonne, die ich gleich erkläre. Im Skript steht

"Die Projektion ist der eindimensionale Schatten bei der Beleuchtung von oben".

Wir machen aus unserem $2$-Tupel nun ein $1$-Tupel: Uns interessieren nur die $x$-Werte aus den Tupeln, und so kommen wir auf die 2. x-Achse im Bild für unser $A = \{(1),(3),(5),(6)\}$ . Das ist unsere vorderste Front.

Der Projektionssatz sagt also aus:

War unsere Menge $B$ rekursiv (entscheidbar), so ist unsere Projektion $A$ rekursiv aufzählbar (r.a.). Die Umkehrrichtung gilt auch: Ist unsere Projektion r.a., so ist die Menge $B$ entscheidbar.

Aber beweisen wie diese Aussagen zunächst:

1. Teilbeweis zu Nr. 1: $A\text{ ist r.a.}\Rightarrow{A=\emptyset}$ oder $A=Bild(g)$ mit $g\in R^{(1)}$.

Das ist umgangssprachlich am besten so auszudrücken: eine leere Menge $A=\emptyset$ ist der Definition nach immer rekursiv/entscheidbar. Also Auch immer rekursiv aufzählbar/semi-entscheidbar. Hier gibt es für uns nichts weiter zu beweisen.

Ansonsten gilt: wenn die Menge durch eine totale Funktion aufgezählt werden kann, so ist diese Menge rekursiv-aufzählbar/semi-entscheidbar. Das ist leicht einzusehen: Semi-Entscheidbarkeit einer Menge $A$ bedeutet ja, dass für für jedes Element aus $A$ immer einen positiven (oder negativen, aber nicht beides gleichzeitig) Bescheid bekommen und somit auch $A$ tatsächlich die Bildmenge der Funktion ist, die sie entscheidet: nämlich $g$ ist.

Haben wir z.B. die Gesamtmenge der Instanzen für das Post'sche Korrespondenzproblem und wollen wir daraus die Menge der lösbaren Instanzen konstruieren, so können wir für jedes Element der Gesamtmenge die Funktion $g$ laufen lassen, die es in jedem Fall positiv entscheidet wenn eine Lösung dafür gefunden wurde (dass wir das können, haben wir im letzten Beitrag schon gezeigt) und somit jedes Element aus der Menge $A$, der Menge der gelösten Probleminstanzen, aufzählen.

Genau diese Definition begründet den Namen Art von Mengen: sie werden von $g$ aufgezählt und sind damit rekursiv aufzählbar.

Das war der erste Teil. Kommen wir nun zum Umkehrschluss.

2. Teilbeweis zu Nr. 1: $A\text{ ist r.a.}\Leftarrow{A=\emptyset}$ oder $A=Bild(g)$ mit $g\in R^{(1)}$.

Fall 1: $A=\emptyset$: Wir nehmen an, dass die $A$ leer ist. Nun suchen wir eine Funktion $d$, die für alle Eingabewerte $n$ kein Ergebnis liefert und setzen $A$ als Definitionsmenge dieser Funktion $d$: $A=Def(d)$. Damit haben wir den ersten teil gezeigt.

Fall 2: Nun nehmen wir eine totale Funktion $g$ und setzen $A$ als Bildmenge von $g$: $A=Bild(g)$. Jetzt kommt unser $f$ ins Spiel:

$f(y)=\mu{x}[g(x)=y]$

Was macht $f$? Es gibt uns für einen Eingabewert $y$ das kleinste $x$, wo gilt, dass der Funktionswert von $g$ bei der Eingabe von $x$ genau $y$ ist.

Man mache sich hier klar, dass egal, was $g$ als Eingabewert bekommt, wir immer $div$ zurückbekommen (denn die leere Menge $A$ ist die Bildmenge von $g$).

$f$ kann im Gegenzug alle Werte aus $\mathbb{N}$ bekommen und auf alle abbilden. Diese Funktion ist offensichtlich berechenbar.

Das bedeutet: für ein $y\in{Def(f)}$ gibt es auch ein $x$ mit $g(x)=y$. Da $y\in{Bild(g)}$ ist, gilt: $Def(f)=Bild(g)$ und $Bild(g)$ ist somit rekursiv aufzählbar.

Und das war der zweite Teil.

1. Teilbeweis zu Nr. 2: $A\text{ ist r.a.}\Rightarrow{B}\text{ rekursiv}$

Zeigen wir zunächst den umgekehrten Weg von Punkt 2 mit: $A\text{ ist r.a.}\Rightarrow{B}\text{ rekursiv}$. Dafür gehen wir davon aus, dass eine Menge $A\subseteq\mathbb{N}^k$ rekursiv aufzählbar ist:

• Dann gibt es eine Gödelnummer $i$ für ein $x\in{A}$ mit $\varphi_i(\pi^{(k)}(x))$ existiert.

Es gibt also eine Maschine mit der Nr. $i$, die uns zum Element $x$ eine Ausgabe beschert. Die Cantorsche Tupelfunktion $\pi$ ist hier nur dazu da um eine evtl. Mehrstelligkeit $k$ der Eingabe für die Maschine auf eine Stelle herunterzurechnen.

• Gibt es die Maschine mit der Nr. $i$, so gibt es auch selbstverständlich die dazu gehörige Schrittzahlfunktion $SZ$, die im $\Phi$-Theorem benutzt wird: $\Phi_i(\pi^{(k)}(x))$

Kennen wir alles schon: das ist die Anzahl der Schritte, die $\varphi_i$ bei der Eingabe von $x$ braucht um zum Ende zu gelangen. Da die Menge $A$ rekursiv aufzählbar ist, existiert für jedes $x\in{A}$ diese Rechenzeitfunktion $\Phi_i(x)$.

• Und damit gilt: $(\exists{t})\Phi_i(\pi^{(k)}(x))\leq{t}$

Es gibt also ein kleinstes $t$, d.h. die minimale Anzahl der Schritte, die die Maschine $\varphi_i$ bei der Eingabe von $x$ rechnet um bis zum Ergebnis zu gelangen. Es gibt aber auch noch mehr $t's$. Eben die, die kleiner sind als die maximale Schrittzahl, die die Maschine bei der Eingabe von $x$ rechnet um bis zur HALT-Marke zu gelangen.

• Nun definieren wir die Menge $B=\{(x,t)\mid\Phi_i(\pi^{(k)}(x))\leq{t}\}$

Die Paare sind also die Eingabe $x$ für die Maschine $\varphi_i$ und $t$ die Anzahl der Schritte, die die Maschine bis zum Ergebnis rechnen könnte. Sagen wir z.B. die Maschine rechnet bei der Eingabe von $x$ genau $5$ Schritte bis sie an der $HALT$-Marke ankommt, so kann $t\leq{5}$ sein. In der Menge $B$ würde daher $(x,1)(x,2)(x,3),(x,4),(x,5)$ liegen.

• Nach dem $\Phi$-Theorem ist diese Menge $B$ also entscheidbar.

Das sollte klar sein: das Paar $(x,t)$, also die Eingabe $x$ und die Rechenzeit $t$ ist entscheidbar, da wir für jedes $x$ (wenn es in der Menge $A$ ist) immer einen Ausgabewert haben, ist auch die maximale Schrittzahl immer gegeben. Wir können entscheiden ob die Maschine bei der Eingabe von $x$ nach $t$ Schritten hält oder nicht.

Anders ausgedrückt: Wir können fragen: "Hey, gilt $(x,5)?$ und $\Phi$ prüft ab ob bei der Eingabe von $x$ die Maschine innerhalb von $5$ Schritten zum Ergebnis kommt und kann dann sagen "Ja, das geht!" oder "Nein, ging nicht!". Diese Menge ist also Entscheidbar.

Der eine Weg von Punkt 2 ist damit gezeigt.

2. Teilbeweis zu Nr. 2: ${A}\text{ ist r.a.}\Leftarrow{B}\text{ rekursiv}$

Und nun die andere Richtung: ${A}\text{ ist r.a.}\Leftarrow{B}\text{ rekursiv}$. Sei $B\subseteq\mathbb{N}^{k+1}$ also rekursiv/entscheidbar.

• Setzen wir die Menge $A=\{x\in\mathbb{N}^k\mid{}(\exists{t} (x,t)\in{B}\}$

$B$ ist, wie wir wissen ja entscheidbar. Zu einer Eingabe erhalten wir (wenn sie zu einer r.a. Menge gehört) auch eine maximale Rechenzeit und können so prüfen ob sie $t$ entspricht oder größer/kleiner ist. Hier ist $A$ also die Menge der Eingaben, d.h. die ersten Elemente aus den Tupeln von $B$, die aus Eingabe $x$ und zugehörigem Wert für eine angenommene Rechenzeit $t$ bestehen.

• Nun definieren wir unsere "Projektionsfunktion" durch

$f(x):=\mu{t}[cf_B(x,t)=1]$

Was tut $f$? Zunächst fragen wir uns, was tut $cf_B$? Das ist die (volle) charakteristische Funktion für die Menge $B$. Sie gibt uns eine $1$ zurück wenn die Maschine bei der Eingabe von $x$ nach maximal $t$ Schritten hält.
Und $\mu{t}$? Sie gibt uns das kleinste $t$ zurück, d.h. die minimalste Anzahl an Schritten, die benötigt werden um bei der Eingabe von $x$ von der Maschine eine Ausgabe zu erhalten, denn in unserer menge $B$ liegen ja durchaus mehrere Kombinationen von $(x,t)$ mit den unterschiedlichsten $t's$.

Mit $f(x)$ bekommen wir das also für die Eingabe $x$ kleinste $t$.

Der Definitionsbereich von $f$ sind somit alle Elemente aus $A$ und $A$ damit rekursiv aufzählbar.

Done.

Exkurs: den Unterlagen der Uni Düsseldorf kann man den Projektionssatz auch mit einer anderen Menge $B$ beweisen, z.B. mit $(x,z)$ (wobei $x$ die Eingabe und $z=\pi(y,t)$ das durch die Tupelfunktion $\pi$ auf ein Element $z$ zurückgeführte Paar aus Ausgabe $y$ und Schrittzahl $t$ ist) wenn $T_i(x,t)$ (auch Turingprädikat genannt) erfüllt ist.

Das Turingprädikat ist genau dann erfüllt wenn Maschine $T_i$ bei der Eingabe von $x$ nach $t$ Schritten mit einer Ausgabe $y$ hält.

Im Endeffekt also nur ein kleines Upgrade unserer Menge $B$.

Fassen wir die Ergebnisse zusammen, kommen wir so zu unserer Antwort zum Lernziel.

Antwort zum Lernziel: Der erste Teil des Projektionssatzes ist der Grund für den Begriff  "rekursiv-aufzählbar" für eine Menge $A$. Diese ist genau dann rekursiv-aufzählbar wenn ihre Elemente von einer totalen Funktion $g$ aufgezählt werden können, es gilt damit $A=Bild(g)$ und $A$ ist r.a.

Der zweite Teil ist die Projektion, die aus den Eingabewerten $x$ einer r.a. Menge $A$ besteht. Da diese positiv beschieden sind, gibt es auch die zugehörige Anzahl an Schritten, die die Maschine für den positiven Bescheid brauchte. Setzen wir in den Tupeln $(x,t)$ das Element $t$ auf Werte, die höher sind als die Schrittzahlfunktion der Maschine bei der Eingabe $x$, so haben wir in der Menge $B$ mehrere Tupel der Form $(x,t)$ mit festem $x$ und variablem $t$.

Aus diesen Elementen der Menge $B$ bilden wir die $x$- und $y$-Achse unserer Grafik. Diese Wertekombinationen aus $x$ und $t$ sind entscheidbar (ich kann entscheiden ob ich zu einer positiven Eingabe $x$ mehr als $t$ Schritte brauche oder nicht). Das ist der Weg von einer rekursiv-aufzählbaren Menge $A$ zu einer entscheidbaren $B$.

Auch der Rückweg gilt: aus der Menge $B$ mit den Elementen $(x,t)$ kann ich mir meine Eingabewerte $x$ wieder rausholen, indem ich mich nur für das kleinste $t$ interessiere (die Minimierungsfunktion). Damit "blende" ich alle anderen Kombinationen mit größerem $t$ einfach aus. Das ist die Projektion.

Merksatz: Eine Menge ist rekursiv aufzählbar wenn sie die Projektion einer entscheidbaren Menge ist.

Weiter geht es im nächsten Beitrag zum Halte- Äquivalenz- und Korrektheitsproblem, Reduzierbarkeit und Satz von Rice

Update 3: Korrektur nach Einwand von Phil. Finde ich super, dass Ihr nach fast 3 Jahren immer noch Fehler aufspürt und in den Kommentaren helft, die zu entfernen. Danke!

Update 2: Bitte Kommentar von Steve beachten. Grafik habe ich nun ersetzt (Marke 9 hinzugefügt), aber die Punkte für die "Endlosigkeit" der Bänder in den Beispielen müsst Ihr euch noch dazu denken. Auf die habe ich der Übersichtlichkeit halber (ja, nur der Übersichtlichkeit wegen! Gegen den Einwand, dass meine Schreibfaulheit daran Schuld wäre, wehre ich mich entschieden(!)) in den Beispielen verzichtet

Update: Flussdiagramm Lernziel 2 abgeändert. Danke Basti!

Nun kommen wir zu den Turing- und Bandmaschinen.

Wir nähren uns also der Essenz des ersten Teils der theoretischen Informatik. Die folgenden Beiträge wurden für diese Kurseinheit bereits erstellt und sind in den passenden Lernzielen entsprechend verlinkt.

• Turing-Maschinen, Hilfssymbole und Lernziele KE3

Ich empfehle daher sich einfach mal entlang dieses Beitrags zu hangeln und die Details dann entsprechen der Verlinkung aus dem anderen Beitrag zu holen.

Lernziel 1

Erläuterung der Definition einer Turingmaschine

Das, was im oben verlinkten Beitrag steht, fassen wir hier noch einmal kurz zusammen, da wir dort nur die Einbandmaschine im Detail beschrieben haben.

Die Turingmaschine (Mehrbandmaschine) ist definiert als:

$M=(F,(\Sigma^{*})^k,\Sigma^{*},EC^{(k)},AC)$

• Das $F$ der Turingmaschine ist unser Flussdiagramm
• $(\Sigma^{*})^{k}$ sind unsere beliebig langen $k$ Worte über dem Alphabet $\Sigma$, welche später auf die $k$ Bänder geschrieben werden.
• Die Turingmaschine operiert auf unendlichen Folge von Bändern als Datenspeicher mit dem darauf verwendeten Arbeitsalphabet $\Gamma$.
• Die Turingmaschine hat folgende Eingabecodierung: $EC^{(k)}:(\Sigma^{*})^k\rightarrow D$, definiert als
  $EC^{(k)}(x_1,...,x_k):=((\epsilon,B,\epsilon),(\epsilon,B,x_1),...,(\epsilon,B,x_k),(\epsilon,B,\epsilon))$
  Das bedeutet nichts anderes, als dass wir jedes Eingabewort auf jeweils ein Band schreiben und alle anderen Bänder leer sind.
  Beispiel: $EC^{(3)}(aaa,b,bba):=((\epsilon,B,\epsilon),(\epsilon,B,aaa),(\epsilon,B,b),(\epsilon,B,bba),...,(\epsilon,B,\epsilon))$
  Initial steht also der Lesekopf über dem ersten Blank.
• Die Turingmaschine hat folgende Ausgabecodierung $AC$: das längste Wort auf Band $0$ , welches direkt links vom Lesekopf steht und nur Zeichen aus dem Alphabet $\Sigma$ beinhaltet. Lesen wir die Ausgabe also zurück, so stoppen wir beim $B$; die bis dahin gelesenen Zeichen sind unsere Ausgabe.
• Die Turingmaschine besteht nur aus folgenden Befehlen:
  • $i:L$ Lesekopf auf Band $i$ ein Feld nach links
  • $i:R$ Lesekopf auf Band $i$ ein Feld nach rechts
  • $i:a$ Schreibe auf Band $i$ das Zeichen $a$ unter den Kopf
  • $i:a?$ Teste auf Band $i$, ob das Zeichen $a$ unter dem Kopf steht

Achtung: sollte bei einer Links- oder Rechtsbewegung dann plötzlich ein $\epsilon$ unter dem Lesekopf stehen, wird ein Blank $B$ daraus, da $\epsilon$ nicht zum Alphabet gehört.

Der Einwand vom Phil in den Kommentaren ist berechtigt. $\epsilon$ gehört nicht zum Alphabet und wird nur für die Darstellung als Tripel $(u,v,w)$ benutzt (siehe letzter Kommentar).

Ist doch nicht so schwer, oder. Beispiel?

Beispiel: Turingmaschine $M=(F,(\Sigma^{*})^k,\Sigma^{*},EC^{(k)},AC)$

Alphabet $\Sigma=\{1,0\}$, besteht nur aus $1$ oder $0$

Anzahl der Arbeitsbänder und somit auch unserer Worte: $k=2$

Arbeitsalphbet $\Gamma$, dass aus unserem $\Sigma$ und einem Blank $\{B\}$ besteht.

Die oben definierte Eingabecodierung $EC$

Die oben definierte Ausgabecodierung $AC$

Und unserem Flussdiagramm $F$:

Download: JFLAP-Datei Turing-Maschine 111.

Sieht etwas kompliziert aus, ist es aber nicht. Sicherlich könnte man das alles auch etwas einfacher gestalten.

Was tut die Maschine? Es zählt die Einsen, die auf den Bändern $1$ und $2$ auf gleicher Position stehen und schreibt dann eine $1$ auf Band $0$. Bei jedem Schritt werden die Zeichen auf Band $1$ und $2$ jedoch auch entfernt.

Würden wir die Maschine also mit $0100101$ und $0000100$ starten, so hätten wir am Ende die Ausgabe $1$ auf Ausgabeband $0$. Würden wir als Eingabe aber $0100101$ und $1010010$ wählen, so wäre das Ausgabeband leer.

Formal ausgedrückt bedeutet es

$(1,(\epsilon,B,\epsilon),(B,0100101,B),(B,000100,B))$ $\vdash^*(6,(1,B,\epsilon),(\epsilon,B,\epsilon),(\epsilon,B,\epsilon))$

Ihr kennt die $\vdash^{*}$-Notation ja bereits, aber dennoch zur Auffrischung: es bedeutet, dass ausgehend vom Marker $1$ mit einem leeren Ausgabeband und $0100101$ auf Band $1$, sowie $0000100$ auf Band $2$, wir am Ende in Marker $6$ (unsere $HALT$-Marke) landen und dabei folgende Bandbelegung haben: auf Band $0$ steht eine $1$, Band $1$ und $2$ sind leer.

Und so sieht der 2. Fall ($0100101$ und $1010010$) aus:

$(1,(\epsilon,B,\epsilon),(B,0100101,B),(B,1010010,B))$ $\vdash^*(6,(\epsilon,B,\epsilon),(\epsilon,B,\epsilon),(\epsilon,B,\epsilon))$

Es befand sich keine $1$ auf der gleichen Position auf beiden Bändern, so ist Band $0$ am Ende der Berechnung ebenfalls leer.

Fertig!

Antwort zum Lernziel: das Flussdiagramm einer Turingmaschine besteht aus vier verschiedenen Befehlen (gehe links/rechts, schreibe Zeichen $a$, prüfe ob Zeichen $a$ auf dem Band steht), die auf den Bändern ausgeführt werden können. Die initiale Belegung belegt immer nur Band $1-k$, wobei das Ausgabeband $0$ leer bleibt und erst während der Berechnung beschrieben wird (oder eben nicht).

Die Worte, die auf den Bändern stehen können, sind über dem Alphabet $\Sigma$ gebildet. Zusätzlich zu den Zeichen aus $\Sigma$ wird auch noch das Blank-Zeichen $B$ im Arbeitsalphabet $\Gamma$ auf den Bändern verwendet.

Lernziel 2

Nachweis der Berechenbarkeit einfacher Wortfunktionen

Auch ist in diesem Beitrag bereits beschrieben, wie man das nachweisen kann. Das Verfahren ist ähnlich dem Beispiel für die Einzelschrittfunktion und dem Beweis der Addition mit einer Registermaschine, wo man Behauptungen aufstellt und diese durch vollständige Induktion beweist.

Formal ausgedrückt müssen wir zeigen, dass eine Wortfunktion dann berechenbar ist wenn es eine Turingmaschine gibt, die sie berechnet.

Eine Wortfunktion $f:\subseteq(\Sigma^*)^k\rightarrow\Sigma^*$ heißt berechenbar, gdw. es eine Turingmaschine $M$ gibt mit $f=f_M$.

Beispiel: $f(x)=1^{\#1(x)}$

Wir haben als Ausgabe der Wortfunktion einfach nur die Anzahl der Einsen aus dem Wort $x$.

Um zu beweisen, dass die berechenbar ist, müssen wir also eine Turingmaschine angeben, die den gleichen Ausgabewert hat wie unsere Funktion, so dass am Ende eben gilt: $f=f_M$.

Das ist unser Flussdiagramm für diese äußerst komplizierte Konstruktion:

Und nun stellen wir uns die Frage, was wir beweisen wollen:

Behauptung: Für alle $x\in\Sigma^{*}$ gilt

$(1,(\epsilon,B,\epsilon),(\epsilon,B,x))\vdash^*(6,(1^{\#1(x)},B,\epsilon),(x,B,\epsilon),(\epsilon,B,\epsilon),...)$

Wir landen also beider Eingabe von $x$ nach endlich vielen Schritten in Marker $6$ und haben auf dem Ausgabeband die Anzahl der Einsen von $x$, während auf Band $1$ links vom Kopf unsere Eingabe steht, die wir gelesen haben.

Beweis

$n=lg(x)$, d.h. wir zeigen die Korrektheit über die Länge unserer Eingabe $x$.

$n=0$: dabei ist die Eingabe leer, d.h. $x=\epsilon$ und wir landen direkt in $(6,(\epsilon,B,\epsilon),(\epsilon,B,\epsilon),(\epsilon,B,\epsilon),...)$

$n\rightarrow n+1$: nun nehmen wir an, dass wir für alle Worte der Länge $n$ über $\Sigma$, d.h. für alle $x\in W_n(\Sigma)$ die obige Behauptung gezeigt haben.

Jetzt können wir einen Schritt weiter gehen und $x\in{W_{n+1}}(\Sigma)$ setzen. Dann gibt es ein $x^{'}\in{W_{n}}(\Sigma)$ und ein $a$ aus $\Sigma$ mit $x=x^{'}a$ mit

$(1,(\epsilon,B,\epsilon),(\epsilon,B,x^{'}a))\vdash^*(6,(1^{\#1(x^{'}a)},B,\epsilon),(x^{'}a,B,\epsilon),(\epsilon,B,\epsilon),...)$

wenn $a=1$ und

$(1,(\epsilon,B,\epsilon),(\epsilon,B,x^{'}a))\vdash^*(6,(1^{\#1(x^{'})},B,\epsilon),(x^{'}a,B,\epsilon),(\epsilon,B,\epsilon),...)$

wenn $a=0$.

Damit gilt die Behauptung für alle $x\in{W_{n+1}}(\Sigma)$. Und wir haben $f=f_M$ bewiesen.

Warum ist das so?

Es sieht zwar etwas kompliziert aus, ist es aber nicht wirklich. Schauen wir uns den ersten Fall doch mal genauer an:

Erklärung:

Wir haben ein $x\in{W_{n}}(\Sigma)$, d.h. unser $x$ mit der Länge $n$ endet entweder mit einer $1$ oder einer $0$. Mehr Möglichkeiten haben wir nicht, denn das sind die einzigen Zeichen in unserem Alphabet $\Sigma$.

Nehmen wir unser $x\in{W_{n+1}}(\Sigma)$, d.h. es ist um ein Zeichen länger, ändert sich an der Anzahl der Möglichkeiten etwas? Nein, unser "$+1$" endet immer noch entweder mit einer $1$ oder einer $0$.

Jetzt kommt unsere Fallunterscheidung ins Spiel mit einem Zeichen aus $a\in\Sigma$, dass nur $1$ oder $0$ sein kann. Damit ist in jedem Fall $x=x^{'}a$, denn $lg(x)=n+1$ und $lg(x^{'}a)=n+1$.

Wie sieht denn unsere Ausgabe am Ende aus wenn wir $a=1$ haben? Auf dem Ausgabeband steht dann die Anzahl der Einsen von $x^{'}$ und $a$, also $1^{\#1(x^{'}a)}$. Und bei $a=0$? Genau! Nur die Anzahl der Einsen von $x^{'}$, genau $1^{\#1(x^{'})}$.

Wenn wir es nun genau nehmen, gilt $f=f_M$ noch nicht, denn

$f(10111)=1111$, während

$f_M=(6,(1111,B,\epsilon),(10111,B,\epsilon),(\epsilon,B,\epsilon),...)$

Was tun? Hier hilft unsere Ausgabecodierung $AC$ (Definition siehe oben), denn $AC((6,(1111,B,\epsilon),(10111,B,\epsilon),(\epsilon,B,\epsilon),...))=1111$.

Jetzt erst gilt $f=f_M$!

Antwort zum Lernziel: um eine Wortfunktion als berechenbar nachzuweisen, müssen wir eine Turingmaschine angeben, die sie berechnet. Der formale Nachweis wird mittels vollständiger Induktion erbracht, indem man zeigt, dass für alle Eingaben  das passende Ergebnis am Ende der Berechnung (unser geliebtes Zeichen $\vdash^*$) auf dem Ausgabeband steht.

Lernziel 3

Erläuterung der Definition einer Bandmaschine

Hier hatten wir auch bereits in diesem Beitrag Vorarbeit geleistet. Der Unterschied zu Turingmaschinen mit $k$ Arbeitsbändern ist nicht groß. Wir passen die Ein- und Ausgabecodierung an und ändern die Befehle so ab, dass sie nur auf Band $0$ arbeiten.

Aus der Eingabecodierung für Mehrbandmaschinen mit

• $EC^{(k)}(x_1,...,x_k):=((\epsilon,B,\epsilon),(\epsilon,B,x_1),...,(\epsilon,B,x_k),(\epsilon,B,\epsilon))$

wird ganz einfach

• $EC^{(k)}(x_1,...,x_k):=(\epsilon,B,x_1B...B,x_k)$.

Und nun zu den Befehlen:

• $i:L\rightarrow L$
• $i:R\rightarrow R$
• $i:a\rightarrow a$
• $i:a?\rightarrow a?$

Antwort zum Lernziel: die Befehle einer Turingmaschine (Mehrband) behalten auch bei Bandmachinen (Einband) ihre Gültigkeit. Nur arbeiten diese statt auf $k+1$ (Ausgabeband + $k$ Arbeitsbänder) Bändern nun auf einem einzigen Band $0$.

Ebenso verhält es sich mit der Eingabecodierung, die angepasst werden muss. Für die Ausgabecodierung ändert sich nichts, es bleibt auf Band $0$ als das längste Wort links vom Lesekopf.

Lernziel 4

Erläuterung der Grundidee des Beweises Turing-berechenbar = Band-berechenbar

Das ist Turings ursprüngliche Konstruktion.

Wenn wir doch schon so schön mit Mehrbandmaschinen arbeiten könne, wozu dann Einband? Weil beide Maschinen von der Berechnungsstärke äquivalent sind und letztere weniger kompliziert sind. Persönlich finde ich, dass man mit den Mehrbandmaschinen einfacher hantieren kann, aber sei es drum.

Die Grundidee des Beweises habe ich bereits hier beschrieben, so dass wir uns nur noch um das Lernziel kümmern müssen. Formal ausgedrückt lässt sich festhalten:

Zu jeder Einbandmaschine $M$ gibt es eine Mehrbandmaschine $M^{'}$ mit dem gleichen Bandalphabet wie $M$, so dass gilt: $f_M=f_{M^{'}}$.

Zu jeder Mehrbandmaschine $M^{'}$ gibt es eine Einbandmaschine $M$, so dass gilt: $f_M=f_{M^{'}}$.

Damit haben wir uns auch schon enttarnt: wir können die Mehrbandmaschine durch ein vergrößertes Bandaphabet simulieren. Anders herum bleibt das Bandalphabet natürlich gleich, denn es ist ja bereits groß.

Antwort zum Lernziel: die Simulation der Mehrband- in einer Einbandmaschine erfolgt auf Basis eines vergrößerten Alphabets für die Darstellung der Position der Leseköpfe auf den simulierten Bändern.

Damit erhalten wir "Spuren" auf dem einen Band für die eig. Eingabe und zusätzliche Spuren für die Position der Leseköpfe um die getrennt beweglichen Leseköpfe auf den vormals $k$ Spuren zu simulieren.

Diese neuen Symbole, die wir für die Markierung der Leseköpfe brauchen werden Hilfssymbole genannt und bereichern unser Arbeitsalphabet $\Gamma$ wenn wir sie nicht durch eine Codierung eliminiert haben (siehe nächstes Lernziel).

Lernziel 5

Erläuterung der Grundidee des Beweises, dass man bei Bandmaschinen ohne Hilfssymbole auskommt

Auch hier ist im alten Beitrag die Grundidee bereits beschrieben worden. Ich fasse mich daher sehr schmallippig.

Antwort zum Lernziel: die neuen Hilfssymbole für die simulierte Kopfpositionen der Bänder einer Mehrbandmaschine werden anstatt durch Aufblähen des Arbeitsalphabets mit neuen Zeichen einfach durch eine erweiterte Länge der Wörter über dem alten Arbeitsalphabet $\Gamma$ codiert.

Dadurch ist es möglich, dass das Bandalphabet einer Einbandmaschine bei $\Gamma=\Sigma\cup\{B\}$ bleibt.

Diesen Beitrag habe ich etwas zügig getippt, es könnten sich also ein paar Fehler eingeschlichen haben. Wer etwas sieht: ab damit in die Kommentare. Danke!

In dieser Kurseinheit gibt es zwar nicht viele Lernziele, aber lasst euch nicht täuschen: sie sind wichtig. Die Beiträge zu diesem Thema, die ich auch im passenden Kontext in diesem Beitrag verlinkt habe sind:

• Primitive Rekursion/LOOP Berechenbarkeit
• Mue-Rekursion und WHILE/LOOP-Berechenbarkeit
• Cantorsche Tupelfunktion

Starten wir aber einfach wieder anhand der Lernziele und kämpfen uns da durch.

Lernziel 1

Angabe und Erläuterung der Definition und der Eigenschaften der Cantorschen Tupelfunktion

Zum Glück habe ich bereits hier einen langen Beitrag zum Thema erstellt und wiederhole mich deswegen nicht, sondern springe sofort zur Antwort.

Antwort zum Lernziel: mit der Cantorschen Tupelfunktion ist es uns möglich einem $n$-Tupel mit Elementen aus $\mathbb{N}$ eine einzige, eindeutige Zahl aus $\mathbb{N}$ zuzuordnen (Reduktion). Durch diese bijektive Abbildung von $\mathbb{N}^n\rightarrow\mathbb{N}$ können wir uns auf die Berechnung von einstelligen Funktionen beschränken.

Einen weiteren prominenten Platz hat die Cantorsche Tupelfunktion bei dem Vergleich von Mengen: zwei Mengen sind gleichmächtig wenn man zwischen ihnen eine Bijektion herstellen kann.

Lernziel 2

Erläuterung der Abschlusseigenschaften berechenbarer Zahlenfunktionen

Ich bin mir hier gerade etwas unschlüssig: im Skript ist nicht mehr viel zu dem Thema drin, als der Satz zur Substitution, primitive Rekursion, $\tilde{\mu}$ und der Umkehrfunktion. Vielleicht dann am besten an ein paar Beispielen?

Substitution

Zunächst haben wir zwei ggf. partielle Funktionen $g:\subseteq\mathbb{N}^m\rightarrow\mathbb{N}$ und ggf. partielle Funktionen $h_1$ bis $h_m$ (d.h. so viele Funktionen wie der Definitionsbereich von $g$ Parameter hat), mit $h_1,...,h_m\subseteq\mathbb{N}^k\rightarrow\mathbb{N}$. Alle Funktionen sind berechenbar. Dann ist auch die Substitution $Sub(g,h_1,...,h_m)$ berechenbar.

$Sub(g,h_1,...,h_m)\subseteq\mathbb{N}^k\rightarrow\mathbb{N}$ ist definiert durch $Sub(g,h_1,...,h_m)(x):=g(h_1(x),...,h_m(x))$

Viel Zeug, oder? Keine Sorge, ist ganz easy.

Beispiel

$g(x,y)=x+y$

$h_1(x,y,z)=x+y$

$h_2(x,y,z)=x+z$

Die Substitution sieht nun so aus:

$Sub(g,h_1,h_2)(x,y,z)=g(h_1(x,y,z),h_2(x,y,z))$.

Belegen wir unsere Funktion mit Werten: $x=2,y=3,z=4$

$\begin{array}�Sub(g,h_1,h_2)(2,3,4)&=g(h_1(2,3,4),h_2(2,3,4))\\&=g(5,h_2(2,3,4))\\&=g(5,6)\\&=11\end{array}$

War doch trivial, oder (das wollte ich immer schon mal sagen!)?

Primitive Rekursion

Das ist ein klein wenig ekeliger als die Substitution, aber wir bekommen das gleich noch klein.

Auch hier haben wir zwei Funktionen  $g:\mathbb{N}^k\rightarrow\mathbb{N}$ und  $h:\mathbb{N}^{k+2}\rightarrow\mathbb{N}$, die berechenbar sind (Achtung: sie müssen auch total sein, denn sonst können wir nicht über diese "rekursivieren"). Wenn das der Fall ist, dann ist auch $Prk(g,h)$ berechenbar.

$Prk(g,h)$ ist definiert als:

$f(x,0) = g(x)$

$f(x,y+1)=h(x,y,f(x,y))$

Für alle $x\in\mathbb{N}^k$ und $y\in\mathbb{N}$. Man sieht bereits jetzt, dass wir rekursiv arbeiten. Noch deutlicher wird es an einem Beispiel.

Beispiel

$g(x,z)=x+z$

$h(a,b,x,z)=a+b+x+z$

Nehmen wir einfach mal $y=3$ ($3$-malige Rekursion) und $x=2,z=3,a=4,b=5$.

$\begin{array}�Prk(g,h)(2,3)&=f(2,3,3)\\&=h(2,3,2,f(2,3,2))\\&=h(2,3,2,(h(2,3,1,f(2,3,1))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,f(2,3,0))))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,g(2,3))))))\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,5)))))\\&=h(2,3,2,(h(2,3,1,10)))\\&=h(2,3,2,16)\\&=23\end{array}$

Versuchen wir das mit $y=2$:

$\begin{array}�Prk(g,h)(2,2)&=f(2,3,2)\\&=h(2,3,1,f(2,3,1))\\&=h(2,3,1,(h(2,3,0,f(2,3,0))))\\&=h(2,3,1,(h(2,3,0,5)))\\&=h(2,3,1,10)\\&=16\end{array}$

Viel Text, aber sicherlich gut nachzuvollziehen. Wir loopen und also durch die Funktionen mit einer festen Anzahl an Schleifen! In diesem Beitrag habe ich die primitive Rekursion etwas detaillierter betrachtet.

Und was ist wenn wir keine feste Anzahl an Schleifen haben können? Dann hilft uns unser $\mu$-Operator.

$\tilde{\mu}$

Ist $h$ mit $h:\subseteq\mathbb{N}^{k+1}\rightarrow\mathbb{N}$ berechenbar, so ist es auch $\tilde{\mu}(h)$. Wie ihr seht, auch hier ist $h$ total. Was ist $\tilde{\mu}$?! $\tilde{\mu}:\subseteq\mathbb{N}^{k}\rightarrow\mathbb{N}$. Es ist definiert durch:

$\tilde{\mu}(h)(x)=\mu y[h(x,y)=0]$

What the... Entspannung, Entspannung! Das ist nichts weiter als unsere $\mu$-Rekursion. Ich suche gerade im Skript ob wir das bereits irgendwo auf den vorherigen Seiten hatten... witzig. Hatten wir nicht. Das ist wirklich die erste Erwähnung. Und dann gleich ins kalte Wasser. Nicht schlimm, denn unser $\tilde{\mu}$ ist nichts weiter, als der Operator, der es uns erlaubt auch Dinge zu berechnen, wo wir die genaue Anzahl an Schleifendurchläufen noch nicht wissen.

Und zwar indem wir unserer zu berechnende Funktion so weit umformen, dass wir beim Ende der Berechnung auf eine Nullstelle stoßen. Ich werde das nicht groß ausführen, sondern verweise ganz frech auf meinen alten Beitrag zum Thema.

Umkehrfunktion $f^{-1}$

Das schwerste zum Schluss. Hier gehen wir davon aus, dass $f$ injektiv ist (wichtig!). Wir beschränken uns auch auf einstellige Funktionen. Warum? Na? Na? Genau: aufgrund der Cantorschen Tupelfunktion können wir das. Wenn diese Funktion also berechenbar ist, so ist es auch ihre Umkehrfunktion. Klingt logisch. Ist es auch.

Während für $f$ Totalität und Injektivität gefordert ist, können wir bei $f^{-1}$ bei einer ggf. partiellen Funktion rauskommen. Das liegt daran, dass wir in der Bildmenge von $f$ evtl. Elemente haben, die wir mit unserer Funktion nicht "treffen". Diese landen aber für $f^{-1}$ dennoch in der Definitionmenge, sind aber nicht definiert. Damit ist $f^{-1}$ eben partiell.

Beispiel

$f(x) = x+5$ mit der Umkehrfunktion $f^{-1}(\tilde{x})=\tilde{x}-5$. Setzen wir $x=10$ und $\tilde{x}=f(x)$, so haben wir:

$f(10)=15$

$f^{-1}(15)=10$

Passt.

Damit haben wir die Abschlusseigenschaften für berechenbare Zahlenfunktionen durch.

Antwort zum Lernziel: Funktionen, die sich aus den Funktionen Substitution, primitive Rekursion, $\mu$-Rekursion und der inversen Funktion zusammensetzen sind ebenfalls berechenbar.

Für die Substitution können die Funktionen auch partiell sein, für de primitive und $\mu$-Rekursion sind wir jedoch auf totale Funktionen angewiesen, da wir sonst nicht durch die Schleifendurchläufe kommen. Während wir bei der primitiven Rekursion zwingend die Anzahl der Schleifendurchläufe kennen müssen, ist es uns bei der $\mu$-Rekursion durch das "Nullsetzen" der Funktion nicht wichtig. Es bricht eben ab wenn die Nullstelle gefunden ist. Wie lange es dauert wissen wir nicht.

Ersteres ist das Äquivalent zur $LOOP$-Schleife ("tue etwas genau $x$ Mal"), während die $\mu$-rekursion einer $WHILE$-Schleife ("tue etwas bis...") entspricht.

Für die inverse Funktion benötigen wir neben einer totalen Funktion $f$ jedoch auch die Eigenschaft der Injektivität für $f$, da wir nur auf maximal ein Element aus der Bildmenge abbilden dürfen, da sonst die Umkehrabbildung auf zwei unterschiedliche Elemente abbilden würde.

Lernziel 3

Definition der WHILE-Programme, Erläuterung ihrer Semantik und Angabe des Zusammenhangs zu berechenbaren Funktionen

Letztes Lernziel in dieser Kurseinheit. In diesem Beitrag sind die Details bereits herausgearbeitet, ich kümmere mich daher nur um die Definition und Semantik aus dem Skript. Das Fazit kann man wortwörtlich eig. auch für die Antwort zum Lernziel übernehmen. Also kümmern wir uns um die Syntax und die Semantik.

$R_i+$ und $R_i-$ sind $WHILE$-Programme

Dabei addiert $R_i+$ im $i$-ten Registereine $1$, $R_i-$ subtrahiert eine $1$ im $i$-ten Register.

IF $R_i=0$ THEN $P$ ELSE $Q$

Wir gehen davon aus, dass $P$ und $Q$ selbst $WHILE$-Programme sind.

WHILE $R_i\neq 0$ DO $P$

Kennen wir auch schon. Solange das Register $R_i$ nicht $0$ ist, wird $P$ ausgeführt.

Zusätzlich dazu haben wir noch unser kleines Tau $\tau$. Dadurch weisen wir unseren oben beschriebenen Kommandos tatsächliche Funktionen auf der Datenmenge $D=\mathbb{N}^{\mathbb{N}}$ zu, die wir bereits verbal beschrieben haben (sie ist die uns bekannte Datenmenge der Registermaschinen). Als Beispiel nehmen wir $R_i+$ und $R_i-$:

$\tau(R_i+)(a_0,a_1,...):=(a_0,a_1,...,a_i+1,...,)$

$\tau(R_i-)(a_0,a_1,...):=(a_0,a_1,...,a_i-1,...,)$

Wir können einem kompletten $WHILE$-Programm mittels $\tau$ ebenfalls eine Ausgabe auf der Datenmenge $D$ beschaffen: $\tau(P)$. Und damit haben wir dann die komplette Registerausgabe unserer Maschine, die das Programm $P$ berechnet. Damit schaffen wir es, dass unser Programm auf der Eingabecodierung einer Registermaschine operieren kann und uns auch eine Ausgabecodierung der Registermaschine liefert (siehe vorheriger Beitrag).

Noch eine kleine Definition für die $WHILE$-Berechenbarkeit

Wir nennen eine Funktion $f:\mathbb{N}^k\rightarrow\mathbb{N}$ $WHILE$-berechenbar genau dann wenn gilt: $f=AC(\tau(P)(EC))$

Ähnliches Spiel wie im Beitrag zu KE1. Wir haben unterschiedliche Datenmengen für $\tau$ und für die Flussdiagramme der Registermaschinen. Mit $EC$ und $AC$ wandelt wir diese nur ineinander um.

Das führt uns direkt zum Zusammenhang zu den berechenbaren Funktionen.

Beispiel

Funktion $f(x,y)=x+y$ (operiert auf $\mathbb{N}^2\rightarrow\mathbb{N}$)

Dazu haben wir ein $WHILE$-Programm $P$, welches uns die Funktion $f$ berechnet. Es operiert auf $\mathbb{N}^3\rightarrow\mathbb{N}^3$

R0=R1;

WHILE R2 NOT 0 DO

  R0+;

  R2-;

END;

Wir können auch ein Flussdiagramm $F$ einer Registermaschine $M$ angeben, dass uns die gleiche Funktion raushaut.

Während das Flussdiagramm ebenfalls auf $\mathbb{N}^3\rightarrow\mathbb{N}^3$ operiert, haben wir bei der Registermaschine jedoch $\mathbb{N}^3\rightarrow\mathbb{N}$.

Damit gilt $f=\tau(P)=f_M=f_F$. Oder doch nicht? Spielen wir das doch einfach mal mit $x=2,y=3$ durch:

$f(2,3)=5$

$\tau(P)(0,2,3)=(5,2,0)$

$f_M(0,2,3)=5$

$f_F(0,2,3)=(5,2,0)$

Okay, die Berechnung ist anscheinend in Ordnung. Aber die Ausgabe von z.B. $\tau(P)(0,2,3)=(5,2,0)$ ist sicher nicht gleich $f_M(0,2,3)=5$ (siehe die Definition der Eingabe- und Ausgabecodierung von Registermaschinen im Lernziel 4 von Beitrag zu KE1).

Hier kommen unsere Funktionen $EC$ und $AC$ bei allen drei Berechnungsarten ins Spiel, die unsere Eingabe und unsere Ausgabe entsprechend umformen, so dass sie passen.

Definieren wir also z.B. $AC$ für $\tau(P)$ neu: $AC(x,y,z)=x$, so haben wir

$\begin{array}{}AC(\tau(P)(0,2,3))&=AC(5,2,0)\\&=5\end{array}$

Damit würde $f_M=AC(\tau(P))$ wieder passen.

Das spannende also daran ist, dass es durchaus vorkommen kann, dass unser Flussdiagramm, unsere Registermaschine oder unser $WHILE$-Programm nicht alle auf einer Datenmenge operieren, sondern alle auf unterschiedlichen Mengen (warum auch immer). Um aber zu sagen, dass z.B. $\tau(P)=f_M$ gilt, müssen wir sie evtl. umgestalten. Für $\tau(P)=f_F$ brauchen wir das hingegen - wie wir oben gesehen haben - nicht.

Lange Rede, kurzer Sinn:

Zu jedem $WHILE$-Programm gibt es ein Flussdiagramm einer Registermaschine mit $\tau(P)=f_F$

Zu jedem Flussdiagramm einer Registermaschine gibt es ein $WHILE$-Programm mit $f_F=\tau(P)$ mit einer $WHILE$-Schleife.

Damit gilt: die Funktion $f$ ist $WHILE$-berechenbar genau dann wenn sie Register-berechenbar ist.

Antwort zum Lernziel: die $WHILE$-Programme bestehen aus bedingten Anweisungen ($IF$) und Schleifen ($WHILE$), sowie Anweisungen zum Register hoch- oder runterzählen und Hintereinanderausführungen von Anweisungen.

Der Zusammenhang zu berechenbaren Funktionen kommt daher, dass man zu jedem $WHILE$-Programm eine Registermaschine angeben kann, die die selbe Funktion berechnet und zu jeder Registermaschine ein $WHILE$-Programm existiert.

$WHILE$-Programme sind mächtiger als $LOOP$-Programme: man kann $LOOP$-Schleifen mit $WHILE$-Schleifen nachbilden, aber nicht anders herum, da man die Anzahl der Schleifendurchläufe im Vorfeld nicht bei jeder $WHILE$-Schleife kennt.

Die $LOOP$-Anwendungen sind das Äquivalent zur primitiven Rekursion, während die $WHILE$-Programme erst mit dem $\mu$-Operator (durch "Nullsetzen" der Funktion) nachgebildet werden können.

Update: Einwand von Felix aufgenommen.

Update: Marion hat einen Fehler bei der Berechnung der $ES$ gefunden. Danke!

Update: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz.

Update: Hinweis darauf, dass das erste Register bei der Eingabecodierung $EC$ für eine Maschine belegt werden kann (wir haben keine Einschränkungen), aber nicht durch die Eingabecodierung für eine Registermaschine!

Als ich die ersten Beiträge zur Kurseinheit 1 von Teil A der theoretischen Informatik geschrieben habe, orientierte ich mich an den Themen. Entstanden sind damit die Unterbeiträge:

• Normale und allgemeine Registermaschinen
• Einzelschritt- und Schrittzahlfunktion sowie Ãœbergangsrelationen (Update)
• Beweis der Addition zweier Register mit einer Registermaschine

Irgendwann, gegen Ende der Kurseinheit 5 habe ich gemerkt, dass es vielleicht sinniger ist anhand der Lernziele zu gehen. Das bringt etwas mehr Struktur in die Beiträge und wirft einen roten Faden durch das Skript.

Als ich dann bei Kurseinheit 7 von Teil B angelangt war, hat sich mein Entschluss gefestigt die alten Beiträge ebenfalls zu überarbeiten. Was ich hiermit also tun möchte.

Lernziel 1

Angabe und Erläuterung der Definition des Flussdiagramms

Ich würde vorschlagen, wir definieren wieder und erklären die Definition Zeile für Zeile: das Flussdiagramm ist ein 4-Tupel $F=(Q,D,\sigma,q_o)$

$Q$: Markenmenge

$D$: Datenmenge

$q_0$: Startmarke

$\sigma$: zu jeder Marke gehört entweder eine Zuweisung $(f,p)$ oder eine Verzweigung/Test $(S,p,p^{'})$

Beispiel gefällig?

Beispiel: $F_1=(Q,D,\sigma,q_0)$ mit

$Q=\{1,2,3,4\}$: wir haben nur vier Marken im Flussdiagramm

$D=\mathbb{N}^2$: wir operieren auf max. zweistelligen, natürlichen Zahlen

$q_0=1$: die Anfangsmarke ist $1$

Und nun kommt unsere Funktion, die jeder Marke eine Operation zuweist. Das macht das Flussdiagramm nämlich erst aus.

$\sigma(1)=(y=1,2)$ (Zuweisung)

$\sigma(2)=(y>x,4,3)$ (Verzweigung/Test)

$\sigma(3)=(y=y+1,2)$ (Zuweisung)

$\sigma(4)=HALT$ (Haltemarke)

Und wenn wir $F_1$ auf Papier bringen:

Nicht so schwer, oder? Was tut das Flussdiagramm $F_1$? Nichts besonderes: es zählt nur $y$ hoch bis es größer ist als $x$. Nicht besonders sinnvoll, aber kurz (ich bin faul, sorry) und anschaulich.

Antwort zum Lernziel: Ein Flussdiagramm besteht aus einer Marken- und Datenmenge, einer Startmarke und einer Funktion, die jeder Marke aus der Markenmenge eine Zuweisung oder eine Verzweigung zuordnet.

Lernziel 2

Angabe und Erläuterung der Semantik des Flussdiagramms

Semantik? Bedeutung! Das Flussdiagramm $F$ definiert nämlich nichts anderes als eine Funktion $f_F$, die aus den Parametern (oben waren es $x$ und $y$) in einer Endkonfiguration (so denn es eine gibt) ein Ergebnis generiert. Die Semantik eines Flussdiagramms gliedert sich in folgende Begriffe:

• Konfiguration: z.B. Anfangs- und Endkonfiguration sowie Zwischenkonfigurationen
• Einzelschrittfunktion: Ãœbergang in einem Berechnungsschritt von einer Konfiguration in eine andere
• Schrittzahlfunktion: $div$ wenn es zu einer Eingabe keine Endkonfiguration gibt oder die Anzahl der Schritte, die zu einer Eingabe bis zur Endkonfiguration geführt haben
• Gesamtschrittfunktion: Endkonfiguration zu einer Eingabe. Wenn sie existiert. Ansonsten $div$.
• Semantik: Das Ergebnis

Beispiel: $F_1=(Q,D,\sigma,q_0)$ (von oben)

Sagen wir, wir starten $F_1$ mit $x=2$ und $y=0$.

• Anfangskonfiguration: $(1,(2,0))$ und Endkonfiguration: $(4,(2,3))$ (Zwischenkonfigurationen lasse ich mal weg)
• Einzelschrittfunktion: z.B. $ES(1,(2,0)=(2,(2,1))$. Nach einem Schritt befinden wir uns in Marke $2$ und haben nur $y=1$ gesetzt. Würden wir aber z.B. $ES^6(1,(2,0))$ nehmen, so müssten wir fünf Berechnungsschritte im Flussdiagramm ausführen und wären bei

$\begin{align}ES^6(1,(2,0))&=ES^5(2,(2,1))\\&=ES^4(3,(2,1))\\&=ES^3(2,(2,2))\\&=ES^2(3,(2,2))\\&=ES(2,(2,3))\\&=(4,(2,3))\end{align}$

(Update: Nach Einwand von Felix korrigiert. Danke!)

• Schrittzahlfunktion: $SZ(1,(2,0))=7$. Nach $7$ Schritten kommen wir, ausgehend von der Anfangskonfiguration $(1,(2,0))$ in die Endkonfiguration $(4,(2,3))$.
• Gesamtschrittfunktion: $GS(1,(2,0))=(4,(2,3))$. Die Endkonfiguration zur Anfangskonfiguration $(1,(2,0))$ ist eben $(4,(2,3))$ und damit unsere Gesamtschrittfunktion.
• Semantik: $f_{F_1}(2,0)=(2,3)$. Das Ergebnis der harten Arbeit unseres Flussdiagrsmms.

Auch nicht viel schwerer als Lernziel 1.

In einem alten Beitrag habe ich das bereits für Registermaschinen aufgegriffen.

Antwort zum Lernziel: das Flussdiagramm definiert eine Funktion $f_F$ (die Semantik des Flussdiagramms) auf der Datenmenge des Flussdiagramms, welche von einer Anfangskonfiguration (Startmarke, Eingabe) nach endlich vielen Schritten zu einer Endkonfiguration (Endmarke, Ausgabe) führt. Oder auch nicht.

Die Belegung der Variablen im Flussdiagramm ist das Ergebnis der Berechnung, es gilt dann $f_F(Eingabe)=Ausgabe$. Gibt es zu der Eingabe kein Ergebnis, so ist $f_F(Eingabe)=div$.

Lernziel 3

Angabe und Erläuterung der Definition und Semantik einer Maschine

Kommen wir nun zu den Maschinen. Warum reicht uns das Flussdiagramm von oben nicht? Weil die Datenmenge $D$ des Flussdiagramms meistens nicht mit der Definitions- oder Bildmenge unserer durch das Flussdiagramm darzustellenden Funktion übereinstimmen wird. Wir brauchen hier also zusätzlich noch ein paar andere Dinge: eine Maschine ist ein 5-Tupel mit $M=(F,X,Y,EC,AC)$.

$F$ ist ein Flussdiagramm (siehe oben)

$X$ ist eine Eingabe- und $Y$ eine Ausgabemenge.

$EC:X\rightarrow D$: Eingabecodierung. Es ist nichts weiter als eine Funktion, die aus einem Element aus $X$ eine Eingabecodierung aus $D$ für unser Flussdagramm ausgibt. Under Flussdiagramm nimmt nämlich keine Elemente aus $X$, sondern nur aus $D$ entgegen.

$AC:D\rightarrow Y$: Ausgabecodierung. Ebenfalls nur eine Funktion, die hier jedoch zu einem Element aus $D$, der Datenmenge des Flussdiagramms ein Element aus der Ausgabemenge $Y$ zuweist.

Damit berechnet $M$, unsere Maschine also eine Funktion $f_M=AC(f_F(EC))$

Das letztere erschließt sich wahrscheinlich nicht sofort. Aber wie können das an einem Beispiel etwas anschaulicher gestalten.

Achtung (Update): während wir bei der Eingabecodierung bei einer Maschine es zulassen, dass wir das erste Register belegen, tun wir das keinesfalls bei einer Registermaschine! Das ist bei der Initialbelegung durch die Funktion $EC$ nicht zulässig, denn es fungiert als Ergebnisregister und ist initial immer mit $0$ belegt!

Beispiel: Maschine $M$ mit dem Flussdiagramm von oben, $x=2$ und den zusätzlichen Mengen und Funktionen

$X,Y=\mathbb{N}$: die Mengen unserer Eingabe- und Ausgabecodierungen für unsere Maschine sind nicht mehr Tupel ($\mathbb{N}^2$), wie sie das Flussdiagramm brauchst, sondern bestehen nur noch aus einem einzigen Element.

$EC:X\rightarrow D$ mit $EC(x)=(x,0)$.

$AC:D\rightarrow Y$ mit $AC(x,y)=y$

Wir können unsere Maschine $M$ also einfach nur mit $x$ füttern und erhalten durch die Eingabefunktion $EC$ auch unser $y$ für die Eingabe in unser Flussdiagramm. Ähnliches gilt für die Ausgabecodierung: unser Flussdiagramm gibt uns $(x,y)$ als Ausgabe heraus, was wir mit der Funktion $AC$ in $y$ umwandeln.

Setzen wir also $x=2$ mal ein:

$EC(x)=(2,0)$. Damit füttern wir unser Flussdiagramm und bekommen als Ausgabe des Flussdiagramms $f_F=(2,3)$. Das werfen wir in unsere Ausgabecodierung $AC(2,3)=3$ und haben die Ausgabe unserer Maschine $f_M$.

Der letzte Punkt unserer Maschine mit ausgefülltem $x=2$ bedeutet also:

$\begin{align}f_M&=AC(f_F(EC(2)))\\&=AC(f_F(2,0))\\&=AC(2,3)\\&=3\end{align}$

That's it.

Antwort zum Lernziel: eine Maschine tut für uns also nichts anderes, als es uns zu ermöglichen nicht mehr auf der Datenmenge $D$ des Flussdiagramms operieren zu müssen. Durch die "Eingabecodierungs-Funktion" $EC$ können wir aus einer beliebigen Eingabemenge $X$ in die Datenmenge $D$ des Flussdiagramms abbilden und so unser Flussdiagramm mit einer passenden Eingabe füttern.

Mittels der "Ausgabecodierungs-Funktion" $AC$ gelingt uns auch der Rückweg aus der Ausgabe des Flussdiagramms (die ja ein Element aus $D$ ist) in die Ausgabemenge $Y$.

Damit ist die Semantik einer Maschine die Funktion $f_M\subseteq X\rightarrow{Y}$, die mit Hilfe von $EC$ und $AC$ die Mengen $X$ und $Y$ von, bzw. in die Datenmenge $D$ für das Flussdiagramm überführt. Es gilt somit $f_M=AC(f_F(EC))$ wenn wir von einer Anfangskonfiguration zu einer Endkonfiguration kommen. Ansonsten ist $f_M=div$.

Lernziel 4

Angabe und Erläuterung der Definition einer Registermaschine

Kommen wir nun zu den Registermaschinen. Den eig. Stars dieser Kurseinheit. Ich hatte bereits in diesem Beitrag etwas zum Thema geschrieben. Es macht also keinen Sinn das hier noch einmal zu Wiederholen. Daher: bitte dort nachlesen und wiederkommen

Update: nicht vergessen, die Eingabecodierung für eine Registermaschine belegt nicht das erste Register $R_0$!

$EC^{(k)}(x1,...,x_k):=(0,x_1,...,x_k)$

Ebenso ergeht es uns mit der Ausgabecodierung: uns ist egal, was in den anderen Registern steht, wir finden nur das erste Register spannend:

$AC(a_0,a_1,...):=a_0$

Antwort zum Lernziel: die Registermaschinen bestehen aus Registern mit durch die Eingabecodierung induzierten Registerbelegungen und der "Ausgabecodierungs-Funktion", welche uns das 1. Register (Register $R_0$) der Registermaschine als Ausgaberegister festlegt. Dadurch ist es uns nur möglich die Register $R_1-R_m$ mittels Eingabecodierung zu belegen.

Die Registermaschine verfügt nur über drei Grundoperationen: Addition von $1$, Subtraktion arithmetische Differenz und Test auf $0$.

Lernziel 5

Angabe und Erläuterung der Definition einer verallgemeinerten Registermaschine

Auch die Erläuterungen zur verallgemeinerte Registermaschine sind hier zu finden. Daher kümmern wir uns nur um das Lernziel.

Antwort zum Lernziel: Durch die verallgemeinerte Registermaschine ist es uns möglich weitaus mehr Operationen als die Grundoperationen Addition und Subtraktion von $1$, sowie Test auf $0$ durchzuführen.

Diese Operationen werden jedoch aus den Grundoperationen zusammengesetzt und erlauben es uns Registerinhalte miteinander zu vergleichen oder Registern Werte zuzuweisen, die durch Funktionen berechnet wurden (wobei Registerinhalte der Registermaschine selbst als Parameter dieser Funktion fungieren können).

Lernziel 6

Angabe der Definition einer berechenbaren Zahlenfunktion

Ich gebe mal ganz frech die Definition aus dem Skript wieder:

Eine Funktion $f:\subseteq\mathbb{N}^k\rightarrow\mathbb{N}$ heißt berechenbar wenn es eine $k$-stellige Registermaschine $M$ gibt, die sie berechnet, so dass gilt: $f=f_M$.

Das ist eine der zentralen Definitionen im Teil A der theoretischen Informatik und findet sich auch häufig als Frage in den Protokollen der mündlichen Prüfung wieder: diese Definition sagt uns, dass wir eine Funktion dann berechenbar nennen können, wenn wir eine Registermaschine angeben, die sie berechnet und im Endeffekt auf die Grundoperationen Addition und Subtraktion von $1$ sowie Test auf $0$ zurückführt.

Beispiel: $f(x,y)=x+y$

Wollen wir also nachweisen, dass die Funktion $f$ berechenbar ist, so müssen wir eine Registermaschine inkl. Flussdiagramm angeben, dass uns die gleiche Ausgabe in Register $R_0$ liefert, wie die Funktion $f$.

Für Details und den Beweis, dass die Addition zweier Register ($f(x,y)=x+y$) berechenbar ist, empfehle ich euch hier den alten Beitrag zum Thema.

Antwort zum Lernziel: Wir können eine Funktion mit $k$ Parametern also berechenbar nennen wenn wir sie mit einer $k$-stelligen Registermaschine und der Grundoperationen innerhalb eines Flussdiagramms berechnen können., so dass gilt: $f = f_M$.

Lernziel 7

Zeigen, dass eine Funktion berechenbar ist

Das Thema wurde ebenfalls hier detaillierter besprochen und gezeigt wie man eine Funktion (das angesprochene Beispiel mit der Addition zweier Register) als berechenbar nachweist. Ich begnüge mich also hier mit dem letzten Lernziel dieser Kurseinheit.

Antwort zum Lernziel: Um zu beweisen, dass eine Funktion berechenbar ist, muss man diese am Ende nur mit den Grundoperationen Subtraktion und Addition von $1$ und Test auf $0$ abbilden können.

Hat man z.B. die Addition mittels dieser Grundoperationen nachgebildet und mittels vollständiger Induktion bewiesen, dass sie für alle Werte das gewünschte Ergebnis liefert, so kann man diese komplexe Operation nun in seiner verallgemeinerten Registermaschine für weitere Beweise anderer Funktionen nutzen.

Z.B. kann man ausgehend von den Grundoperationen die Addition zweier Register $x+y$ beweisen und anschließend mit der Addition den Beweis der Multiplikation $x\cdot y$ angehen. Mit der Multiplikation gelingt uns dann das Beweisverfahren für die Exponentialfunktion $x^y$, usw.

Die Lernziele von Kurseinheit 1 haben wir damit durch. Noch 6 und der Kurs ist komplett Bei Fehler wie immer: ASAP in die Kommentare damit falsches Zeug nicht so lange online bleibt!