Zufallsbit

Es fällt auf, dass Turingmaschinen, die ein Entscheidungsproblem berechnen am Ende immer entweder eine Null oder eine Eins auf dem Band stehen haben. Man könnte sagen, die Turingmaschine "entscheidet eine Sprache" in dem Sinne, dass sie für jedes Wort, das man auf das Band schreibt, entweder true (Wort gehört zur Sprache) oder false (Gehört nicht zur Sprache) ausgibt. Ein einfaches Beispiel hilft vielleicht.

,,

Das sind alle Zustandsübergänge für . Der erste ist für den Fall, dass ein "a" eingelesen wird. Da passiert nichts weiter, der Kopf bewegt sich nur nach rechts. Wenn ein b gelesen wird, wechselt die TM im den Zustand und schreibt das b zurück aufs Band. Was in passiert, habe ich nicht explizit angegeben, weil es mühselig und langweilig wäre. Was passieren *soll* ist, dass die Turingmaschine das Wort verwirft. Das würde bedeuten, in liefe der Kopf bis ans Ende des Wortes (also bis ein B gelesen wird), läuft dann zurück und löscht dabei jeden Buchstaben. Wenn wieder ein B gelesen wird bedeutet das, dass wir eine Zelle links vom Anfang des Wortes angekommen sind. Wir gehen also noch einen Schritt nach rechts und schreiben eine 0 für false. Ich hoffe mir ist niemand böse, dass ich DAS nicht alles in einer TM codieren wollte. Es sollte aber klar sein, dass es prinzipiell machbar wäre.

Bleibt der letzte Zustandsübergang, nämlich wenn ein B im Zustand gelesen wird. Das würde ja bedeuten, dass wir am Ende des Wortes angekommen sind, ohne jemals auf ein b getroffen zu sein, denn sonst wären wir in gelandet und die TM hätte 0 ausgegeben. Im neuen Zustand würde im Wesentlichen das gleiche passieren wie in , nur dass am Ende eine 1 geschrieben wird.

Die Turingmaschine verwirft also alle Worte, die ein "b" enthalten und akzeptiert alle, die nur aus "a" bestehen. (Bonusfrage: Was ist mit dem leeren Wort? Antwort: Wird auch akzeptiert.) Als Sprache ausgedrückt hieße das übrigens L={ a* }, wobei * den kleenschen Abschluss darstellt, was im Grunde nur "beliebige Anzahl" bedeutet. Und das ist in der Tat eine starke Verbindung zwischen zwei unterschiedlichen Feldern. Eine TM im Entscheidungsmodus und eine Sprache sind ein und dasselbe. Man kann eine Sprache definieren und eine Turingmaschine bauen, die für jedes Wort der Eingabe "1" ausgibt. Umgekehrt gilt das natürlich auch, denn wenn uns jemand eine Turingmaschine gibt, können wir gucken was die für Wörter akzeptiert und uns eine entsprechende Sprache überlegen. Es sind zwei Seiten einer Medaille: Sprachen sind mehr der konstruktive Teil, man will *aktiv* eine Menge von Wörtern generieren und überlegt sich, wie das geht. Die Turingmaschine generiert nichts, sie entscheidet lediglich, ob ein Wort zur Sprache gehört oder nicht.

Wir nähern uns unaufhaltsam dem eigentlichen Thema, denn jetzt kann man sich natürlich überlegen, ob es wirklich für jede Sprache eine entsprechend richtig entscheidende Turingmaschine gibt. Dafür definiere ich das ganze nochmal etwas mathematischer.

Zu einer beliebigen Sprache L gibt es eine so genannte charakteristische Funktion . Das ist jetzt sozusagen das mathematische Äquivalent zu dem oben beschriebenen Sachverhalt. Die Funktion evaluiert zu 1, wenn das Wort in der Sprache ist, sonst zu 0.

Eine Funktion f heißt Turing-berechenbar, falls sie überall definiert ist und falls f von einer TM berechnet werden kann. Dabei muss die TM bei allen Eingaben halten und am Ende wie gefordert 0 oder 1 auf dem Band stehen haben. Eine Sprache L wird Turing-berechenbar genannt, falls die zugehörige Funktion Turing-berechenbar ist. Hier hätten wir also eine formale Verbindung zwischen den drei Betrachtungsweisen. Eine Sprache wird in eine mathematische Funktion umgebastelt, die wiederum von einer Turingmaschine entschieden wird. Übrigens heißt "Turing-berechenbar" auch "rekursiv" und hat nichts mit einem rekursiven Programmaufruf zu tun.

 Rekursiv ist eine Funktion übrigens auch, wenn die entscheidende Turingmaschine nur dann rechnet, wenn die Eingabe aus dem Definitionsbereich ist. Zum Beispiel macht ein Sortieralgorithmus für Ganzzahlen nur für ganzzahlige Eingaben Sinn. Wenn man da einfach ein paar Strings eingeben würde, dürfte die TM formell unendlich weiter rechnen (weil Turingmaschinen keine Exceptions kennen). Trotzdem wäre dieses Verhalten rekursiv. Dann gibt es noch eine letzte wichtige Klasse von Sprachen, die man "rekursiv aufzählbar" nennt. Ich verzichte mal auf eine formale Definition, denn der Unterschied ist auch so leicht zu verstehen. Die TM akzeptiert jedes Wort der Sprache nach wie vor in endlicher Zeit, wenn das Eingabewort aber nicht zur Sprache gehört, rechnet die TM unendlich.

Man, das war lang und langweilig. Damit sind die Vorbereitungen aber endlich abgeschlossen und wir können bald endlich über das Halteproblem sprechen. Bleibt nur noch ein Wort über die Church-Turing-These zu verlieren.

Diese geht nämlich so: "Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen." Was eine Turing-berechenbare Funktion ist, wissen wir ja jetzt. "Intuitiv berechenbare Funktionen" können dagegen nicht so schön definiert werden, man versteht darunter mehr oder weniger alle Funktionen die wir Menschen uns so ausdenken können. Alles was wir Menschen im Prinzip ausrechnen könnten. Sind das nicht *alle* Funktionen, die es gibt? Vermutlich ja, zumindest ist es schwer sich vorzustellen, was es für Funktionen geben könnte, die wir uns nicht ausdenken können. Das liegt aber irgendwie in der Natur der Sache, denn wie sollten wir uns diese Funktionen wohl ausdenken können, wenn es gerade deren Eigenschaft ist, nicht von uns erdacht werden können?

Die These besagt also, dass Computer keine Lücken in ihrer Rechenkraft haben. Alle Dinge die wir entscheiden können, können auch Computer entscheiden. Aber sind alle Computer gleich mächtig? Das sagt uns zumindest die (ebenfalls nicht beweisbare) erweiterte Chruchsche These: "Für je zwei Rechnermodelle R₁ und R₂ gibt es ein Polynom p, so dass t Rechenschritte auf Modell R₁ bei Eingabe der Länge n durch p(t,n) Rechenschritte auf Modell R₂ simuliert werden können." Die Umrechnung von einem auf den anderen Computer soll also maximal in Polynomialzeit machbar sein, was uns Theoretikern zur Zufriedenheit reicht.

Ein spezieller Typ formaler Sprachen sind die so genannten kontextfreien Sprachen. Sie sind auch die praxisrelevantesten und deren Konstruktion sieht irgendwie am natürlichsten aus, deshalb fange ich mit ihnen an.

Um kontextfreie Sprachen zu beschreiben benutzt man oft die Backus-Naur Form. Das ist im Grunde nur eine spezielle Syntax um die Produktionsregeln übersichtlich hinzuschreiben. Es gibt allerdings auch ein paar neue Begriffe. Da sind zum einen die Terminale. Das sind "finale" Buchstaben, wenn ein Terminal in einer Regel generiert wurde, kann es nicht mehr verändert werden. Nichtterminale hingegen sind die "Variablen" aus dem letzten Beitrag. Das sind Hilfssymbole, die wiederum als Ausgangspunkt für weitere Produktionen verwendet werden. Beispiel-Time!

Z ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Der vertikale Strich ist als "oder" zu verstehen. Ein "Z" kann nachher in den Regeln mit einer dieser Terminale ersetzt werden. Dann fehlt da formal noch folgendes:

(G steht für Grammatik, T für Terminale, N für Nichtterminale, S für Startsymbol und P für Produktionsregeln)

T= {Z}

N= {A}

P= { S->ASA, S->, A->Z}

G = {S,P,N,T}

Damit hätten wir eine Grammatik definiert, die eine Sprache generieren kann. Diese Sprache kann ein leeres Wort generieren, denn wir starten bei S und kommen von da aus direkt zum epsilon. Das epsilon ist ein Terminal, von hier aus ginge es also nicht weiter.

Die andere S-Regel generiert ASA. Ein A lässt sich nur ins Terminal aus Z transferieren, also steht da in Wirklichkeit <Zahl>S<Zahl>. Das S in der Mitte wiederum kann man wieder in ein epsilon produzieren (und damit das Wort abbrechen) oder wieder ASA generieren. Die Sprache besteht also aus beliebigen Zahlen, die eine gerade Anazhl von Stellen hat, oder aus dem leeren Wort.

Schön, aber noch nicht perfekt, denn ich könnte damit Zahlen mit führenden Nullen generieren. Wenn ich das nicht wollte, müsste ich ein paar Regeln umschreiben:

Z::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Y::= Z  | "0"

N= {A,B,C}

P= { S->, S-> ACB, A-> Z, B-> Y, C-> BCB C->}

Es wird also etwas komplizierter, aber nicht viel. Wir füren ein paar mehr Regeln und Nichtterminale ein und stellen so sicher, dass gleich nach dem S eine nicht-Null generiert wird. Danach verlassen wir das S und generieren in C weiter. 141592 generiert sich so:

S->ACB->ZCY->ZBCBY->ZYBCBYY->ZYYYYY->ZYYYYY->141592

Das ist also eine kontextreie Sprache, und jetzt kann ich auch erklären, woher das "kontextfrei" kommt. Die Produktionsregeln sind unabhängig davon, welches Terminal vor oder hinter einem Nichtterminal steht. Grundsätzlich kann für ein Nichtterminal jede entsprechende Produktionsregel verwendet werden, ganz unabhängig vom Kontext in dem es steht.

Ich habe noch nicht erklärt, was "entscheidbar" bedeutet, deshalb kann ich im Moment auch noch nicht erklären, welches Automatenmodell kontextfreie Sprachen entschieden kann. Im nächsten Beitrag geht es um deterministische finite Automaten und welche Art Sprache davon entschieden werden können. Das mag etwas seltsam anmuten, aber diese Reihenfolge macht schon Sinn. Sowohl Automaten als auch Sprachen fühlen sich zu Anfang etwas weit hergeholt an. Dennoch besteht ein so starker Zusammenhang zwischen den beiden, dass es meiner Meinung nach Sinn macht, erst einfache Sprachen zu beschreiben, dann einfache Automaten einzuführen und dann den Zusammenhang herzustellen.

Dies ist der Eröffnungsbeitrag zur nächsten Serie in diesem Blog. Es wird um formale Sprachen und dem Zusammenhang zwischen Automatenmodellen und diesen Sprachen gehen. Leider gibt es hier kein "Ziel" in dem Sinne wie es eines bei P vs. NP gab, aber der lose Plan ist, früher oder später in die Entscheidbarkeitstheorie abzuschweifen. Da steht dann das Halteproblem an, was ich jetzt einfach mal als vorläufiges Ziel definiere. Aber keine Angst, diese Serie wird etwas praxisrelevanter sein als die P vs. NP-Serie. Und wie immer versuche ich natürlich, möglichst plastische Beispiele zu benutzen.

Schauen wir uns zu diesem Zweck erstmal natürliche Sprachen an. Nehmen wir den Satz "Ich esse Pizza". Wir erinnern uns an die Regel "Subjekt Prädikat Objekt" aus der Schulzeit. So könnte man diesen Satz formal konstruieren. Das Subjekt wäre "Ich", also substituiere ich "Ich" mit "Subjekt". Dann steht da "Ich Prädikat Objekt". Dann substituiere ich noch Prädikat mit "esse" und Objekt mit "Pizza" und schon steht da "Ich esse Pizza". Natürlich macht unsere menschliche Intuition das ganze automatisch und viel schneller. Aber ich würde einfach mal ohne Beweis behaupten, dass das Gehirn diese Prozedur trotzdem durchläuft, wenn auch fast unmerklich.

Gut, wir haben also gesehen dass natürliche Sprachen nach gewissen Regeln generiert werden, das ganze kann man natürlich auch formalisieren. Es sei aber vorher erwähnt, dass natürliche Sprachen in der Regel weitaus komplizierter als formale Sprachen sind. Es gibt so viele Sonderregeln und Abweichungen, dass die entsprechende formale Sprache riesig groß und kompliziert wäre. Das ändert aber nichts an der Tatsache, dass natürliche Sprachen im Grunde nur ein Spezialfall einer formalen Sprache ist.

Wie definiert man aber eine Sprache formal? Nun, zunächst brauchen wir ein Alphabet. In Deutsch wäre das vielleicht so etwas wie A = {a,b,...,y,z,A,B,...,Y,Z,ä,ü,ö,Ä,Ü,Ö,ß}. Es gehören außerdem Satzzeichen dazu, denn alles was so allgemein in einem Satz vorkommen kann, muss auch im Alphabet auftauchen.

Machen wir es uns aber etwas einfacher, ohne dabei an Bedeutung zu verlieren. Unser Alphabet ist {A,B,C}. Dann ist ein "Wort" eine Aneinanderreihung von validen Buchstaben, zum Beispiel ABBAC. Der nächste Begriff den wir benötigen ist "Sprache". Das ist eine Menge von Wörtern, z.B. {AB, AABB,CCC}. Auch das ist analog zu natürlichen Sprachen. Wir könnten auch im deutschen Alphabet z.B. "hudZ8,," generieren, aber das würde nicht zu unserer Sprache gehören. Genauso könnten wir in der formalen Sprache "ABCCA" generieren, aber das gehört ebenfalls nicht zur Sprache.

Sprachen bezeichnet man in der Regel mit L = {..}, man könnte aber auch unendlich große Sprachen definieren, zum Beispiel als L2={w| w beginnt mit A und endet mit C}. Da steht in Worten: "L2 besteht aus allen Wörtern w, die der Bedingung hinter dem vertikalen Strich genügen". Diese Sprache wäre also {AC, AAC, ABC ACC, AABC,...}

Das letzte was ich noch ansprechen möchte sind die so genannten Produktionsregeln. Diese sind ein bischen abhängig vom Typ der Sprache, allgemein kann man aber sagen, dass wir formale Sprachen immer irgendwie generieren wollen. Bisher haben wir das intuitiv gemacht, aber das funktioniert nur begrenzt oft. Nehmen wir L2 und defineren ein paar Hilfssymbole. Zum Beispiel brauchen wir ein Startsymbol, das nicht zur Sprache gehören darf. In der Regel nennt man das "S". Wenn wir jetzt ein Wort aus der Sprache generieren wollen, fangen wir beim Startsymbol an und schreiben das auf ein Blatt Papier.

Und jetzt kommen die Produktionsregeln ist Spiel. Wir müssen uns ein paar einfach Regeln ausdenken, wie jedes Wort aus L2 zu erzielen ist. Wir wissen schon einmal, dass jedes Wort ein A am Anfang und ein C am Ende haben muss. Was läge also näher als S-> AYC? Wenn man das S auf dem Blatt stehen hat, kann man mit dieser Regel das S in AYC umwandeln. Dabei ist wichtig zu beachten, dass A und C Buchstaben aus dem Alpabet sind und das Y eine Variable. Für diese Variable definieren wir weitere Regeln, denn in der Mitte des Wortes ist es uns egal was da steht. Nehmen wir also Y->AY, Y->BY, Y->CY und . Die ersten drei Regeln generieren einen Buchstaben und packen wieder ein Y mit rein, so dass wir  wieder irgendeinen Buchstaben generieren können. Die letzte Regel ist eine Spezialregel, denn das epsilon steht für das leere Wort, also ein Wort ohne Buchstaben. Wenn man diese Regeln anwendet endet die Generierung, denn das Y fällt dann raus.

Fassen wir also zusammen:

A= {A,B,C}, L2={w| w beginnt mit A und endet mit C}

Produktionsregeln P= { S-> AYC, Y->AY, Y->BY, Y->CY, }

Man kann leicht sehen dass die Produktionregeln die Sprache erzeugen, aber hier noch ein Beispiel: Generieren wir mal ABAC.

S-> AYC ->ABYC -> ABAYC -> ABAC. Man beachte, dass bei der letzten Regel das Epsilon einfach wegfällt. Es ist das leere Wort, das taucht nur symbolisch in den Regeln auf, aber nicht im Wort.

Ein Beispiel habe ich noch, diesmal etwas "praxisnäheres". Das Alphabet A ist A={0,1,} und L3={w| w hat 8 Buchstaben}. Die validen Wörter sind also beliebige Bitstrings mit immer 8 Bits. Das mag nicht spekakulär aussehen, ist aber ganz schön verzwickt. Die Produktionsregeln {S->0S, S->1S, S->} funktionieren offensichtlich nicht, denn sie erzeugen Bitstrings beliebiger Länge. Es stellt sich mit ein wenig Nachdenken heraus, dass die einzig möglichen Produktionsregeln aussehen wie {S->00000000, S->00000001, ... ,S->11111111}. Das ist natürlich sehr unschön, denn das sind natürlich 2⁸ Regeln. Ein Computer allerdings (oder sein theoretischer Gegenpart, die Turingmaschine) kann das ganze in einer simpler Schleife in Millisekunden abarbeiten. Hier ist offensichtlich eine einfach aussehende Sprache strukturell schwieriger als die bisherigen. Und das soll der Cliffhanger für die nächsten Folgen bleiben ;)

Jetzt wo wir also wissen wie man formale Sprachen definiert und generiert, schauen wir uns in einem späteren Posting mal an, was es bedeutet wenn eine Sprache entscheidbar ist und welche Sprachen von Turingmaschinen entscheidbar sind. Später beschäftigen wir uns dann mit anderen Automatenmodellen, Chomsky-Hierachien und vielleicht noch mit Beweismethoden wie dem Pumping-Lemma.