Freitag, 24. Oktober 2008Mal ein bisschen SpieltheorieDieses Blog braucht dringend mehr Input. Das meiste was ich zu erzählen hätte, bräuchte leider eine längere Vorbereitung, scheitert aus Zeitgründen oder interessiert schlicht kein Schwein. Einen kleinen (für mich) interessanten Fakt aus der Spieltheorie habe ich aber doch loszuwerden. Wenn wir von einem nicht kooperativem Zwei-Personen-Spiel mit perfekter Information reden, ist ein Spiel gemeint, wo zwei Spieler jeweils alle Züge des Spielers sehen können. Schach ist zum Beispiel ein Spiel mit perfekter Information, Poker dafür nicht. Bei kooperativen Spielen können sich Spieler untereinander absprechen, um vielleicht einen Vorteil für beide Spieler zu erwirken. Eine weitere Eigenschaft von Zwei-Personen-Spielen ist, dass der Gewinn von Spieler A direkt der Verlust des Spielers B ist. Deshalb spricht man von einer "Auszahlung" am Ende eines Spiel, die positiv oder negativ sein kann. Eine Auszahlung von "10" würde bedeuten, Spieler A gewinnt 10, B verliert dafür 10. Umgekehrt gewinnt B bei Auszahlung "-10" und A verliert. Nehmen wir mal ein Spiel an, das aus Anschaulichkeitsgründen so einfach wie möglich ist. Spieler A wählt einmal, Spieler B wählt danach und dann ist A noch einmal dran. Am Ende wartet irgendein Auszahlungsschema, das nicht besonders viel Sinn macht, aber ich bin ja auch kein Spieleerfinder. Konkret sieht das Spiel so aus, als Baum dargestellt:
Ein Beispiel: Sagen wir A wählt im ersten Zug die 2, B wählt 1 und A wählt noch einmal 1. Damit hätte A "2" gewonnen. Ganz offensichtlich gibt es begrenzt viele Aktionen, die die Spieler überhaupt ausführen können. Jeden "gesamten Spielablauf" aus der Sicht eines einzelnen Spielers bezeichnet man als "Strategie", zum Beispiel könnten wir es (2,2) nennen, wenn A im ersten und dritten Zug die "2" wählt. Zählen wir mal durch, wie viele Strategien A hat: A1: Wähle (1,1) unabhängig von B's Zug Außerdem gibt es natürlich weitere 4 Strategien, wenn A im ersten Zug 2 wählt. B hat weniger Strategien:
Wenn man das alles jetzt "normalisiert" darstellt, schreibt man die Strategien an eine Matrix und schreibt an die Schnittstellen die Auszahlung. Ungefähr so:
Als Beispiel: Sagen wir A wählt Strategie 3, B wählt 4. Damit zieht A "1", B wählt das Gegenteil (wegen seiner Strategie), also 2. Die Strategie für A wiederum sagt, dass A jetzt 2 zieht. Damit ist die Auszahlung -1, was man in der Matrix bei A3xB4 wieder findet. Kleine Bemerkung am Rande: Dass die Matrix in diesem Fall so symmetrisch aussieht hat damit zu tun, dass das Spiel so extrem simpel ist. Schon wenn man für jeden Zug drei Wahlmöglichkeiten zulässt, sieht die Matrix schon deutlich anders aus. Allerdings steigt die Anzahl der Strategien dann auch deutlich und es wird schnell unübersichtlich. Jetzt lassen sich ein paar interessante Beobachtungen anstellen. Zum Beispiel kann B nicht gewinnen, wenn A keinen groben Fehler macht. Egal, was B macht, immer kann A im letzten Zug zumindest ein Unentschieden sichern. Deshalb wäre die rationale Entscheidung für B, die Strategie B2 zu wählen. Denn wenn A 1 wählt, kommt B mit einer "0" raus, wann A am Anfang 2 zeiht, verliert B wenigstens nur mit einer 1. Es ist spät geworden, und der Punkt auf den ich hinaus will, ist nicht mehr wahnsinnig weit entfernt, aber doch weit genug als bis zum Wochenende warten zu müssen. Immer unterschätze ich die Zeit, die ich dafür brauche, Bilder zu malen und Beispiele zu erfinden.
Mal ein bisschen Spieltheorie Geschrieben von Turing
in Informatik um
21:35
Kommentare (0) Trackbacks (0) Donnerstag, 22. November 2007Die Diagonalsprache
Obwohl ich im Moment echt durch den Wind bin, fühle ich irgendwie die Verpflichtung, hier auch mal wieder etwas substantielles zu schreiben, auch wenn es wahrscheinlich weniger umfangreich wird als sonst. Es geht mal wieder um das Halteproblem, heute machen wir einen weiteren (und letzten) Zwischenschritt, um danach endlich das Halteproblem anzugehen. Zunächst brauchen wir dafür die so genannte kanonische Ordnung. Das ist eine spezielle Sortierung von Bitstrings (also eine Ordnung auf {0,1}*). Dabei steht ein Wort w vor einem anderen Wort w', wenn: Anders gesagt wird zuerst nach Länge des Wortes, dann erst nach lexikographisch Ordnung sortiert. Kürzeste Worte kommen also zuerst, inklusive dem leeren Wort: Jetzt überlegen wir uns eine Matrix, wobei die Zeilen mit Turingmaschinen Die Matrix ist natürlich unendlich, denn sowohl die Anzahl der Wörter als auch die Menge der Gödelnummern hört nie auf. Jetzt kommt an eine Schnittstelle von Turingmaschine und Wort jeweils eine 0 oder eine 1, je nachdem ob die Turingmaschine das Wort akzeptiert oder nicht.
In diesem Fall würde die Turingmaschine So weit so gut, aber was soll all der Blödsinn? Stellen wir uns vor, wir hätten eine Sprache, die immer falsch rechnet. Diese wäre mal ganz sicher nicht rekursiv, wir bräuchten uns nicht einmal Gedanken machen, wann sie unendlich läuft oder nicht definiert ist. So eine Sprache ist die so genannte Diagonalsprache: Informell gesagt ist das die Sprache, die alle Wörter enthält, die die zugehörige Turingmaschine nicht akzeptiert. Die zugehörige Turingmaschine ist natürlich die, die in der korrespondierenden Zeile steht. Und damit ist D die Sprache, die alle Nullen auf der Diagonale dieser Matrix enthält. Das führt zu einem ziemlich üblen Widerspruch. Die Annahme ist, dass die Sprache rekursiv ist. Das heißt, dass es eine TM gibt, die auf allen Eingaben hält und genau D akzeptiert. Nennen wir diese TM einfach Das bedeutet, dass das zu 2)
Wie man sieht führen beide Fälle zum Widerspruch, keine Turingmaschine kann damit D akzeptieren und rechnet dabei immer richtig. Die Sprache ist damit definitiv nicht rekursiv. Das kann man benutzen um die nichtrekursivität des Halteproblems zu beweisen, das wird aber erst im nächsten Beitrag passieren.
Die Diagonalsprache Geschrieben von Turing
in Informatik um
20:14
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: diagonalsprache, entscheidbarkeitstheorie, informatik, tm, turing-maschine
Mittwoch, 31. Oktober 2007Turing-berechenbare Funktionen und die Churchsche TheseEs 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 Bleibt der letzte Zustandsübergang, nämlich wenn ein B im Zustand 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 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 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 R1 und R2 gibt es ein Polynom p, so dass t Rechenschritte auf Modell R1 bei Eingabe der Länge n durch p(t,n) Rechenschritte auf Modell R2 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.
Turing-berechenbare Funktionen und ... Geschrieben von Turing
in Informatik um
20:49
Kommentare (0) Trackbacks (0) Mittwoch, 24. Oktober 2007Wolframs 2,3 TM ist universell!Ich glaubs ja kaum. Stephen Wolfram hat 2004 eine Turingmaschine entworfen und 25000$ für einen Beweis ausgelobt, der die Universalität entscheidet. Heute, am gleichen Tag an dem ich zufällig meinen Beitrag über Universelle Turingmaschinen geschrieben habe kommt das rein: Wolfram's 2,3 Turing Machine Is Universal! (Beweis) Damit ist es die kleinste bekannte universelle Turingmaschine. Hier gibts technische Details.
Wolframs 2,3 TM ist universell! Geschrieben von Turing
in Informatik um
18:25
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: entscheidbarkeitstheorie, informatik, tm, turing-maschine, universelle turingmaschinen, utm
Mittwoch, 24. Oktober 2007Universelle TuringmaschinenVielleicht erinnert sich noch jemand, dass ich in grauer Vorzeit mal eine Serie über Automatentheorie gestartet habe, mit dem Ziel, irgendwann zur Entscheidbarkeitstheorie zu gelangen. Der Grund, warum ich das nie weitergeführt habe ist, dass ich Automatentheorie nicht besonders spannend finde. Also überspringe ich den langweiligen Teil, komme direkt wieder zu Turingmaschinen und schreibe vielleicht später einen Beitrag über Automatentheorie mit einem eher zusammenfassenderen Charakter. Entscheidbarkeitstheorie also. Die meisten Probleme sind ja irgendwie durch eine konkrete Fragestellung motiviert. Hier ist diese Frage, welche Funktionen entschieden werden können und welche nicht. Ich werde noch darauf kommen was das im Detail bedeutet. Erstmal führen wir eine neue Art Turingmaschine ein, die wir später brauchen. Eine Turingmaschine, nennen wir sie M, ist ja folgendermaßen definiert: Dabei ist Q die Menge der Zustände und q0 identifiziert den Startzustand. So eine gewöhnliche Turingmaschine hat einen gewaltigen Nachteil. Sie ist mit der formalen Definition bereits vollständig programmiert. Und zwar endgültig. Viel schöner und vertrauter wäre es doch, wenn eine Turingmaschine nur die "Hardware" zur Verfügung stellen würde und wir das Programm auf das Band schreiben könnten, genau wie wir das bei normalen Computern tun. Da schreiben wir das Programm auf die Festplatte (genauer gesagt in den Bootsektor) und von da aus guckt unser Computer nur, welches Programm an der richtigen Stelle der Festplatte zur Ausführung bereit liegt. Man stelle sich vor, wir würden für jeden auszuführenden Algorithmus einen neuen Prozessor kaufen und dem nur die Instanzen füttern. Ein Sortierprozessor zum Beispiel, dem wir nur Ganzzahlen zum Sortieren geben könnten, oder ein "Fülle-den-Cache-mit-Daten-Prozessor". Im echten Leben mutet das absurd an, aber so machen es klassische Turingmaschinen und für die Theorie kann man das auch tun. Aber es geht eben auch anders, und das nennt man eine "universelle Turingmaschine", kurz UTM, noch kürzer U. Diese kann ein beliebiges Programm (bzw. eine andere, normale Turingmaschine M) ausführen. Die Eingabe besteht jetzt nicht mehr aus einem Wort w, sondern aus (<M>w). Dabei ist w nach wie vor das zu bearbeitende Wort, neu ist <M>, die so genannte Gödelnummer der zu simulierenden Turingmaschine M. Man kann jede normale TM in eine lange Zahl codieren, die dann wiederum eindeutig ist. Zu jeder Gödelnummer gehört genau eine Turingmaschine. Diese Nummer wiederum gibt man dann als Eingabe an die UTM, die dann die zur Gödelnummer zugehörige TM simuliert. Diese Codierung funktioniert so:
Keine Erklärung nötig soweit? Doch? Na gut. Zuerst transferieren wir das Bandalphabet (hier oBdA {0,1,B}) in Und das ist ja schließlich unser Ziel gewesen. Nun, die universelle TM hat allerdings auch nur ein {0,1} Alphabet, deshalb notiert man einen einzelnen Zustandsübergang so: Jetzt dienen die Einsen als "Trenner" für eine Anzahl von Nullen, die mit dem ursprünglichen Zustandsübergang korrespondiert. Ein alter Übergang Wo wir uns jetzt diese ganze Arbeit gemacht haben, können wir damit endlich wieder auf die Gödelnummer zurück kommen. Die sieht jetzt nämlich so aus: 111 code(1) 11 code(2) 11 ... 11 code(n-1) 11 code(n) 111 Drei Einsen markieren also Start und Ende der Gödelnummer, zwei Einsen trennen zwei Codierungen für die Übergänge. Das Ziel ist erreicht, die Turingmaschine wird in einer langen, langen Nummer notiert, die offensichtlich auch wieder in die entsprechende Maschine zurück rechnen lässt. Wenn wir jetzt eine solche Gödelnummer, zusammen mit dem zu entscheidenden Wort an die UTM übergeben, kann diese Schritt für Schritt die Gödelnummer lesen, den neuen Zustand (und damit die neue Position in der Gödelnummer) berechnen und am Ende entscheiden, ob das Wort akzeptiert wird oder nicht. Wie das genau funktioniert wollt ihr nicht wissen, die Gödelnummerkonstruktion war ja schon etwas unheimlich. Nur so viel: Man kann Turingmaschinen auch mit mehreren Speicherbändern definieren. Davon nehmen wir uns in diesem Fall drei, schreiben die zu simulierende Gödelnummer auf das erste, das Wort auf das zweite und auf das dritte kommt der aktuelle Zustand der zu simulierenden TM. Dann wird die Programmierung der UTM zwar weniger hässlich, aber nicht viel. Bleibt die Frage nach der Rechenzeit. Wenn man sich die Rechenoperationen der UTM allerdings genau anschaut, wird schnell klar, dass die aufwändigste Operation die Suche nach der neuen Position in der Gödelnummer ist. Die UTM ist damit nur konstant langsamer als die ursprüngliche TM, hier droht also keine exponentielle Gefahr, außer die ursprüngliche TM war eh schon exponentiell langsam. So weit, so gut. Wir haben gesehen, dass man eine TM auch als lange Nummer schreiben kann. Außerdem gibt es offensichtliche eine universelle Turingmaschine, die mit dieser Nummer und dem zu entscheidenden Wort diese TM simulieren kann. Benutzen kann man das für... ääh... eigentlich kann man das nicht benutzen. Man braucht es lediglich später für einen wichtigen Beweis. Ist theoretische Informatik nicht schön? Wer hier aber dringend eine "Auflösung" braucht, der kann sich ja damit behelfen, dass die UTM offenbar eine praxisnähere Version von Turingmaschinen darstellt, denn man kann sie (auf aufwändige Art und weise) programmieren und muss sich nicht für jeden Algorithmus eine neue Turingmaschine kaufen. Gott sei dank. Update: Übrigens..
Universelle Turingmaschinen Geschrieben von Turing
in Informatik um
07:49
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: entscheidbarkeitstheorie, halteproblem, informatik, tm, turing-maschine, universelle turingmaschinen, utm
Montag, 15. Oktober 2007Ach was solls..Ich bin eher der Typ, der einmal liegengelassene Sachen nie, nie, NIE wieder anpackt. Deshalb habe ich den Comic vom letzten Beitrag wenigstens soweit fertig gemalt, dass man wenigstens etwas erkennen kann. Ich kann es wirklich besser, aber irgendwie habe ich den Ehrgeiz gerade nicht. (Creative Commons by-nc)
Ach was solls.. Geschrieben von Turing
in Informatik, Sonstiges um
23:18
Kommentare (0) Trackbacks (0) Donnerstag, 16. August 2007Kontextfreie Sprachen und die BNFEin 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-> 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. 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-> 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->ZYY 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.
Kontextfreie Sprachen und die BNF Geschrieben von Turing
in Informatik um
21:28
Kommentare (0) Trackbacks (0) Mittwoch, 15. August 2007Formale Sprachen und ein paar BegriffsklärungenDies 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 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, 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.
Formale Sprachen und ein paar ... Geschrieben von Turing
in Informatik um
01:08
Kommentare (2) Trackbacks (0) Dienstag, 29. Mai 2007NP VollständigkeitEigentlich hatte ich das P vs. NP Problem bereits abgeschlossen, aber es gibt da so eine Sache, die gehört zum Thema einfach dazu. Außerdem ist es eine großartige Sache um damit auf Cocktailpartys Wissen raushängen zu lassen. Also, wir hatten ja festgestellt, dass Probleme aus NP in polynomieller Zeit auf nichtdeterministischen Turingmaschinen entschieden werden können. Die P vs. NP Frage ist jetzt, ob die Problemklassen P und NP gleich sind oder nicht. Essentiell heißt das, dass wir nicht wissen, ob es für heutzutage praktisch nicht effizient lösbare Probleme wirklich keinen effizienten Algorithmus gibt, oder ob wir ihn nur einfach noch nicht gefunden haben. Nun ist es ziemlich schwierig, untere Schranken zu finden. Ich nehme da immer gerne das Beispiel mit der Orangenkiste. Man stelle sich vor, man will möglichst effizient Orangen in eine Kiste packen. Dabei kommt es natürlich zu Luft zwischen den einzelnen Kugeln. Was ist die optimale Packstrategie? Einfach zufällig reinwerfen, die Orangen wie Blöcke übereinander stapeln oder die Orangen leicht versetzt anordnen, so dass sie gegenseitig die Hohlräume füllen? Intuitiv würden wir natürlich die letztere Möglichkeit wählen, aber können wir denn sicher sein, dass nicht in 2000 Jahren irgendein schlauer Mensch daher kommt und eine revolutionäre Idee hat? Hierzu braucht man untere Schranken, man will mathematisch beweisen, dass es kein besseres Verfahren geben kann. Das ist natürlich eine ganze Ecke schwieriger, denn man muss ja auch alle Fälle ausschließen können, die man noch nicht kennt. Das ist auch im Grunde das Problem bei P vs. NP. Beide Komplexitätsklassen beinhalten eine Menge Probleme, aber wir können nicht erwarten, wirklich alle Probleme bereits identifiziert zu haben. Wie können wir also z.B. P=NP behaupten, wenn wir vielleicht morgen ein Problem entdecken, das in NP aber nicht in P ist? Anders herum: Wir können auch nicht einfach P!=NP sagen wenn wir ein Problem haben, das in NP, aber nicht in P ist. Es könnte ja einen Algorithmus geben, den wir nur noch nicht entdeckt haben. Der Ausweg sind so genannte Reduktionen. Wenn man Problem A auf Problem B reduziert, bedeutet das, dass man die Eingabe für Problem A so umbasteln kann, dass man sie in einen Algorithmus für Problem B füttern kann, der das Problem löst und dabei die Antwort für A liefert. Ein Beispiel hilft wie immer: Problem A ist "Ist die Zahl x gerade?". Problem B ist "Ist x mod 2=1?". Nun, für uns mit unserer menschlichen Intuition sehen die Probleme gleich aus, denn eine gerade Zahl modulo 2 ist eben immer null. Aber unsere Intuition macht nichts anderes als eine Reduktion. Wenn wir Problem A lösen wollen, rechnen wir eigentlich x mod 2 und entscheiden Aufgrund dieser Rechnung (des Problems B!) das Problem A. Und damit (und hier kommt der Knackpunkt), ist das Problem A in der gleichen Zeit entscheidbar wie B. Wenn B einen O(n) Algorithmus hat, dann ist auch A in dieser Zeit entscheidbar. Nicht für alle Probleme allerdings ist das so offensichtlich wie hier, es gibt teilweise die abenteuerlichsten Reduktionen. Wer hätte z.B. gedacht dass Tetris komplexitätstechnisch so schwer ist, wie die optimale Anordnung von Sicherheitskameras zu finden? Zurück zu den unteren Schranken. Sicher wäre es doch äußerst praktisch, wenn man sagen könnte, dass ein Problem das schwerste aus NP ist. Dann könnte wir nämlich sagen, dass wir nur noch einen P-Algorithmus für dieses schwerste Problem finden müssten. Wenn sich dieses allerschwerste Problem nämlich effizient lösen ließe, müssten einfachere Probleme aus NP ja wohl auch effizient lösbar sein. Und interessanterweise hat Stephen A. Cook bewiesen, dass es ein Problem gibt, das das schwerste in NP ist. Das ist natürlich überraschend, denn auch hier muss man ja über potentiell noch nicht entdeckte Probleme argumentieren, trotzdem schafft dieser großartige Beweis genau das. Wie immer reiße ich die Beweisidee nur kurz an, denn die Details dürften nur sehr wenige interessieren. Wer näheres Wissen will schreibt mir eine Mail oder kauft sich ein Buch über theoretische Informatik ;) Das schwerste Problem aus NP heisst "SAT" und hat nichts mit deutschen Fernsehsendern zu tun. Das Kürzel steht viel mehr für "satisfiability". Stellen wir uns eine Klausel aus boolschen Variablen vor. "x1" wäre so eine Klausel mit nur einer Variablen. x1 AND x2 wäre eine andere, auch (x1 AND x3) OR (x5 AND x1 AND NOT(x3)) ist so eine. Die Frage die das SAT-Problem stellt ist: Ist diese Klausel erfüllbar? D.h. gibt es eine Belegung von Variablen, wo die ganze Klausel "true" wird? x1 AND NOT(x1) zum Beispiel ist trivialerweise nicht erfüllbar. Es gibt nur eine Variable, und wenn diese 1 wäre, wäre der NOT(..) Teil nicht mehr erfüllbar und umgekehrt. Dieses Problem ist aus NP, wir kennen keine bessere Idee als "Belegungen ausprobieren". Im schlechtesten Fall müssen wir deshalb alle möglichen Belegungen ausprobieren und das sind exponentiell viele. Deshalb ist es auf TMs nicht effizient lösbar. Warum ist SAT jetzt das schwerste Problem im NP? Ganz einfach, Turingmaschinen lassen sich auf trickreiche Weise in Boolschen Ausdrücken codieren. Dabei stellt man durch allerlei Kniffe sicher, dass eine sehr lange Klausel entsteht, die genau und ausschließlich dann erfüllbar ist, wenn die Turingmaschine terminiert und ein Ergebnis liefert. Dann löst man diese Klausel auf und sieht: Wenn die Klausel erfüllbar ist, dann liefert die codierte TM "true", sonst "false". Und diese Idee ist geradezu genial, denn wer würde schon darauf kommen, ein so umfangreiches Modell wie eine TM in eine lange boolsche Formel umzusetzen um das Ergebnis der SAT Berechnung als Ergebnis der TM zu nehmen? Aber warum ist damit SAT das schwerste Problem aus NP? Nun, man stelle sich ein schwereres Problem als SAT vor, so ein richtig scheiße schweres Problem. Der Michael Moore unter den Problemen. Nun könnte man doch einfach die entsprechende TM in eine Klausel umbasteln (und der Satz von Cook stellt sicher dass das in poynomieller Zeit passiert). Wenn man diese Klausel hat, kann man sie in den SAT Problemlöser füttern, der dann das Ergebnis berechnet. D.h. also, dass jedes noch so schweres NP-Problem nicht schwerer zu lösen sein kann als SAT. Und das ist genial, denn wir haben damit das schwerste Problem aus NP identifiziert. Und die Implikationen sind enorm, denn jetzt können wir die oben angesprochene Reduktion anwenden und wiederum SAT-Eingaben in Eingaben von anderen Problemen umbasteln. Z.B. gibt es ein Problem, das DHC heisst. Wenn wir ein DHC-Probleminstanz so bauen können, dass ein DHC-Algorithmus genau dann "wahr" entscheidet, wenn die Klausel vom SAT "wahr" entscheiden würde, könnten wir auch DHC als "schwerstes" Problem identifizieren. Nun, schwerer als SAT kann es aber auch nicht sein, also müssen beide Probleme gleich schwer sein. Solche Probleme heißen NP-Vollständig. Sie gehören einer Unterklasse von NP an, die die schwersten Probleme aus NP umfasst. Tausende Probleme sind NP Vollständig und wenn man auch nur für ein einiziges von diesen einen P-Algorithmus finden würde, hätte man automatisch P=NP bewiesen. Denn wenn ein schwerstes Problem aus NP effizient lösbar wäre, wären es auch alle einfacheren. Der Fakt allerdings, dass für kein einziges dieser tausenden Probleme ein guter Algorithmus existiert, lässt wenig Hoffnung übrig, dass es einen solchen gibt
NP Vollständigkeit Geschrieben von Turing
in Millenium-Probleme, P vs. NP um
20:27
Kommentare (4) Trackbacks (0) Tags für diesen Artikel: algorithmus, determinismus, informatik, komplexitã¤t, komplexitã¤tsklasse, laufzeit, millenium-probleme, nichtdeterminismus, np, p, p vs. np, tm, turing-maschine
Freitag, 4. Mai 2007O-Notation BeispieleViele meiner Suchanfragen lassen vermuten, dass einige Informatikstudenten im ersten Semester händeringend nach Beispielen suchen, wie man mit der O-Notation umgeht. Ich werde hier ein Beispiel durchrechnen, in der Hoffnung dass es jemandem hilft. Lasst doch ein Kommentar da wenn das der Fall ist ;) Also, neben der informellen Beschreibung der O-Notation gibt es natürlich auch den streng formalen Weg. Zunächst nehme ich mir mal den Bubble-Sort heraus und kopiere den Pseudocode von Wikipedia: Jetzt analysieren wir, wie man diesen Algorithmus bezüglich der O-Notation klassifizieren muss. Zunächst einigen wir uns darauf, dass wir nur Zuweisungen, Additionen und Vertauschungen (was ja auch nur Zuweisungen sind) als Rechenschritt zählen. Alles andere kostet natürlich auch Zeit, macht aber verhältnismäßig wenig aus. Also los: Zeile zwei ist eine Zuweisung, das ist ein Rechenschritt. Alles was zwischen Zeile drei und zwölf steht wird wiederholt, und zwar so lange bis das Array sortiert ist. Wann ist das im schlimmsten Fall passiert? Natürlich wenn das Array umgekehrt sortiert ist. Denn dann muss das vorderste Element nach hinten und umgekehrt. Da Bubble-Sort immer nur direkte Nachbarn vertauscht, muss jedes Element also ganz durchgeschoben werden. Also weiter, das erste Element muss also ganz nach hinten, braucht dafür n Durchläufe der "für"-Schleife. Pro einen solchen Durchlauf brauchen wir einen Vergleich, eine Vertauschung und eine Zuweisung. Wir sind also im Moment bei Da bekommen wir also Da steht also folgendes: Es gibt eine Funktion g, die schneller oder gleich schnell als unsere Funktion f wächst. Dazu multiplizieren wir noch eine Konstante c dran, die wir uns für den Beweis wählen können. Plastischer wirds erst, wenn ich das mal eben für das Beispiel durchführe. Jetzt muss ich nur noch ein c und ein Ich wähle
O-Notation Beispiele Geschrieben von Turing
in Geek-Zeug um
11:04
Kommentare (5) Trackbacks (0) Tags für diesen Artikel: algorithmus, geek-zeug, informatik, komplexität, o-notation, sonstiges mathematisches, wachstum
Sonntag, 8. April 2007Randomisierung und ZPPIm Gegensatz zu den bisher betrachteten deterministischen Algorithmen gibt es die so genannten randomisierten Algorithmen. Dazu wird ein Zufallsgenerator benutzt und der weiter Verlauf des Algorithmus von diesem abhängig gemacht. In der Realität gibt es natürlich Zufallsgeneratoren beliebiger Qualität, aber in der Theorie beschränken wir uns mal wieder auf das kleinste Vorstellbare: Unser Zufallgsgenerator produziert perfekt zufällige Bits. In jedem Rechenschritt genau eins.
Aber vielleicht ist dem ein oder anderen noch nicht einsichtig, warum wir eigentlich randomisierte Algorithmen brauchen, schließlich produzieren sie Fehlerquellen und nehmen uns doch eine große Portion der Sicherheit, dass der Algorithmus das macht was er soll. Am Besten hilft auch hier ein Beispiel. Wenn beim Quicksort-Algorithmus immer deterministisch das letzte Element als Pivot-Element nimmt und die Eingabe vorsortiert ist, ist die Laufzeit O(n2). Und das wo doch gerade Quicksort normalerweise O(n*log(n)) macht. Da der Speziallfall der sortierten Liste nicht gerade selten vorkommt, ist das Verhalten natürlich sehr ungünstig. Und einfach das erste Element als Pivot zu nehmen verschiebt das Problem auch nur. Die Lösung ist, einfach ein zufälliges Element zu wählen. Auch da kann es natürlich ganz blöd laufen und O(n2) brauchen, aber die Wahrscheinlichkeit ist doch sehr gering, denn dazu müsste immer zufällig genau das Element gewählt werden, das im unsortierten Teil am größten ist. Hier trägt randomisierung also dazu bei, dass es in den meisten Fällen eine gute durschnittliche Laufzeit gibt. Ein anderes prominentes Beispiel ist der Primzahltest von Solovay-Strassen. Hier wird am Anfang eine zufällige Zahl gewählt und die zu prüfende Zahl damit "bearbeitet". Die genauen Schritte wären hier jetzt zu schwierig, aber auch hier ist es praktisch unmöglich, eine "fest einprogrammierte" Zahl zu finden die man benutzen kann, denn es würde Primzahlen geben, bei denen der Algorithmus immer "dies ist keine Primzahl" sagen würde. Der Algorithmus würde ohne Randomisierung also nichtmal korrekt funktionieren. Wir sollten uns also darüber einig sein, dass Algorithmen mit einem Zufallselement sinnvoll sind. Wir erweitern unsere Turingmaschine also dahingehend, dass die Zustandsübergangsfunktion nicht nur davon abhängt in welchem Zustand wir sind und welches Zeichen wir lesen, es wird jetzt auch noch in jedem Rechenschritt ein Zufallsbit generiert. Damit verdoppelt sich zwar die Zahl der Übergänge, aber dass Turingmaschinen in der Praxis eh untauglich sind wissen wir ja auch. Jetzt habe ich ja im letzten Beitrag mit den Komplexitätsklassen sozusagen die letzte Abstraktionsstufe erreicht und da passt es natürlich nicht, dass wir wieder in die Tiefen der Turingmaschine gehen. Deshalb gibt es natürlich auch randomisierte Komplexitätsklassen und eine davon besprechen wir jetzt noch kurz, nur um zu sehen wie man Beziehungen zwischen den Klassen herstellt. Wir definieren: Die Komplexitätsklasse ZPP(f(n)) umfasst alle Algorithmen, die auf einer randomisierten TM ausgeführt werden können und wo die Fehlerwahrscheinlichkeit durch f(n) beschränkt ist. Algorithmen in ZPP können entweder das richtige Ergebnis oder "?" ausgeben. Das klingt jetzt vielleicht etwas hölzern, eigentlich geht es nur darum, dass ZPP-Algorithmen vielleicht nicht zu einem Ergebnis kommen und dann "keine Ahnung" ausgeben. Wenn es aber ein Ergebnis gibt, ist es sicher richtig. Die Wahrscheinlichkeit dass ein ? ausgegeben wird, ist dabei durch f(n) angegeben und damit gibt es im Prinzip unendlich viele ZPP-Klassen. Es gibt ZPP(1/4), ZPP(1), ZPP(1/2) usw. Dabei ist ZPP(1/4) natürlich eine Untermenge von ZPP(1/2), denn wir hatten ja gesagt, dass die Fehlerwahrscheinlichkeit durch f(n) beschränkt ist, es geht also darum, dass f(n) ausdrückt was der schlechteste mögliche Fall ist. Denken wir kurz darüber nach, was ist denn ZPP(0)? Ein randomisierter Algorithmus, der nie einen Fehler macht, also immer das richtige Ergebnis liefert. Klingt nach der Definition von P. Damit ist P=ZPP(0) und damit eine Untermenge von ZPP(f(n)). Was ist ZPP(1)? Komplett sinnlos, denn diese Algorithmen geben immer "?" aus. Wenn man jetzt noch weiter nachdenken wollte, könnte man darauf kommen, dass man einen ZPP(1/4)-Algorithmus ja auch einfach zweimal laufen lassen kann, dann wäre die Wahrscheinlichkeit für ein ? nur noch 1/16. Was würde uns denn daran hindern, den Algorithmus einfach so oft auszuführen bis wir kein ? mehr bekommen? Doch nur die exponentielle Grenze, denn irgendwann müssen wir den Algorithmus im Wesentlichen exponentiell oft laufen lassen um ein Ergebnis erwarten zu können. Das ist der Fall wenn f(n) > 1/2, also können wir mit dieser Technik sagen, dass eigentlich alls Algorithmen mit ZPP(1/2) gleich sind. ZPP(1/4), ZPP(1/3) und ZPP(1/2) unterscheiden sich nur dadurch, dass man hier und da eventuell mehrere Durchläufe braucht. Da aber die Laufzeit je Durchlauf polynomiell ist, bleibt die Laufzeit insgesamt auch polynomiell. Nur wenn wir eine exponentielle Anzahl von Durchläufen brauchen, kommen wir insgesamt auf exponentielle Laufzeit (das ist dann bei f(n)>1/2 der Fall). Mit diesem Wissen kürzen wir ZPP(1/2)=ZPP ab und erkennen P als kleine Unterklasse von ZPP. ZPP mit Fehlerwahrscheinlichkeit >1/2 nennt man ZPP*, aber diese Klasse ist relativ uninteressant. Im nächsten Eintrag wird es dann um andere Komplexitätsklassen gehen, die tatsächlich Fehler machen können (im Sinne von: Das Ergebnis kann falsch sein). Und wenn wir diese Klassen kennen und die Verbindung zu Nichtdeterminismus hergestellt haben, können wir die P vs. NP-Frage endlich verstehen.
Noch ein letzter Satz, mit dem man auf Partys wunderbar angeben kann: Diese Technik des "mehrfachen Ausführens" nennt man probability amplification. Wenn man das in einen Satz mit "Komplexitätstheorie", "polynomielle Laufzeit" und "randomisierte Turingmaschine" bringt, kann man sicher sein, dass man von allen anderen Partygästen bis auf weiteres gemieden wird.
Randomisierung und ZPP Geschrieben von Turing
in Millenium-Probleme, P vs. NP um
12:56
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: algorithmus, determinismus, informatik, komplexität, komplexitätsklasse, laufzeit, millenium-probleme, p, p vs. np, randomisierung, tm, turing-maschine, zpp
Freitag, 16. März 2007TuringmaschinenIm letzten Beitrag hatte ich ja erklärt, dass man Algorithmen äußerst weit abstrahiert um sie vergleichen zu können. Das lag daran, dass man bestimmte Faktoren einfach nicht einbeziehen darf, weil sonst nicht mehr Algorithmen verglichen werden würden, sondern CPU-Power oder Betriebssysteme. Wir haben das gemacht, um später überhaupt eine Argumentationsbasis zu haben. Wenn wir sowas sagen wie "Das Problem A lösen wir mit Algorithmus B in O(log(n))", dann geht das nur weil wir uns überhaupt auf die O-Notation und deren Vergleichbarkeit geeinigt haben. Jetzt liegt es natürlich nahe ein möglichst allgemeingültiges Computermodell zu entwickeln, um eben diese Vergleichbarkeit zu erreichen. Das was man üblicherweise benutzt ist die sogenannte Turingmaschine (kurz: TM). Diese wurde 1936 von Alan Turing entwickelt, was insofern bemerkenswert ist, als dass es da noch keine echten Rechner gab. Ich nehme mal die "Auflösung" vorweg: Turingmaschinen bilden genau unsere aktuellen Rechner ab, d.h. man kann Algorithmen mit akzeptablem Aufwand von einem Athlon64 zu einer Turingmaschine übertagen. Was ein akzeptabler Aufwand ist, darüber handelt der nächste Beitrag. Und dass sich keiner wirklich die Mühe macht, TM-Programme zu schreiben, soviel sei auch schon gesagt. Das ist auch nicht nötig. Wichtig ist, dass man damit eine gemeinsame Argumentationsbasis hat. Dann schauen wir uns Turingmaschinen also mal konkret an.
Aber wie berechnet die TM die Ausgabe? Dafür gibt es die Menge der Zustände Vielleicht macht ein Beispiel das etwas klarer. Sagen wir, auf dem Band steht "010011" und wir wollen alle nullen löschen. Wir sind ja im Zustand Das war jetzt kein Entscheidungsproblem, wenn man ein solches hat, wird normalerweise gefordert, dass man die Eingabe komplett löscht und eine 0 oder 1 (wahr oder falsch) an die erste Position schreibt. Im obigen Beispiel kamen wir mit einem Zustand aus, normalerweise hat man mehrere. Man kann sich z.B. leicht vorstellen, dass man zählen will, ob auf dem Band genau so viele einsen wie nullen stehen. Dann würde man z.B. eine null lesen, in Zustand Formal ist eine TM ein Tupel:
Turingmaschinen Geschrieben von Turing
in Millenium-Probleme, P vs. NP um
12:43
Kommentare (0) Trackbacks (0) Tags für diesen Artikel: determinismus, informatik, millenium-probleme, p vs. np, tm, turing-maschine
Dienstag, 13. März 2007Was Quantencomputer können und nicht könnenWährend ich den nächsten Eintrag vorbereite, können die Erfahrenen unter euch ja schonmal bei Scott Aaronson vorbei schauen. Sehr interessanter Post.
Was Quantencomputer können und ... Geschrieben von Turing
in Sonstiges Mathematisches um
11:58
Kommentare (0) Trackbacks (0) |
KategorienFeedsGetaggte Artikelööh.. informatik?
algorithmus china determinismus entscheidbarkeitstheorie fehlerwahrscheinlichkeit fernsehen filme formale sprachen games geek-zeug informatik komplexitã¤t komplexitã¤tsklasse laufzeit linux medien millenium-probleme monty hall nichtdeterminismus nicht eingã¤ngig nintendo ds np o-notation p poker p vs. np randomisierung rffc RP sco sonstiges sonstiges mathematisches spieltheorie statik technische mechanik tm turing turing-maschine universelle turingmaschinen utm videospiele wachstum wahrscheinlichkeit xkcd zpp SonstigesBlogrollSuche |
Powered by s9y - Design by Lordcoffee