Funktion Turingmaschine |
| 18.09.2014, 15:19 | Auf diesen Beitrag antworten » | ||||||||
| tungusk@ | Funktion Turingmaschine Hallo, ich würde mich gern ein wenig in manche Teilgebiete der Theoretischen Informatik einlesen, scheiter jetzt aber schon im 2ten Anlauf an der Definition einer Turingmaschine. Habe mir das Buch "Theoretische Informatik" von Norbert Blum geholt, und sag mal was genau ich an der Definition einer k-Band TM nicht verstehe: Eine deterministische k-Band Turingmaschine M ist ein 5-Tupel M = (Q , E , d , q(0) , F), dabei soll sein: Q eine endliche Menge von Zuständen, E endliches Bandalphabet, disjunt zu Q, mit 0,1,#,_,$ unter anderen in E enthalten, d eine Funktion die Elemente von Qx(E^k) in Elemente in Q x (E^k) x {-1 , 0 , 1}^k abbildet. Dabei sollen die "x" das kartesische Produkt von Mengen sein, und eine Menge hoch k (^k) das k-fache kart. Produkt mit sich selbst, also die Menge der k-Tuel aus dieser Menge. q(0) der Startzustand F = {q(e) : d(q(e),a) für kein a element E^k definiert ist} die Menge der Endzustände Soweit so gut. Die Menge E ist der Zeichenvorrat der in die Bandquadrate eingeschrieben werden kann. Die Funktion d stelle ich mir so vor sie nimmt ein Tupel, das einen von endlichen vielen Zuständen enthält, und ein Element aus E^k, also ein k-tupel von Zeichen, die wohl in die k-Bänder irgendwo eingeschrieben sind, und bringt si auf ein 3 tupel, bestehend aus einem Zustand aus Q, k neuen Zeichen die über die vorherigen geschrieben werden sollen, und k Anweisungen jeweils der Form -1, 0, 1 die links bleiben und rechts bedeuten sollen, dem Kopf also sagen dass er, etwa für k = 3 bei dem tripel (-1,1,1) sagen, dass der Kopf in der ersten Zeile eins nach links soll, in der zweiten und dritten jeweils eins nach rechts. Soweit so gut hoffe ich mal. Aber was sollen diese Zustände darstellen? Also was ist einer dieser Zustände? Am besten glaube ich würde ich das in einer formalen Darstellung verstehen. Wenn ich da was weiss, weiss ich denk ich auch was Start und Endzustände darstellen sollen(Irgendwo hab ich eine Ahnung aber auf den Punkt bringen kann ich die nicht) Danke schonmal fpr eure Hilfe! |
||||||||
|
|
|||||||||
| 20.09.2014, 14:34 | Auf diesen Beitrag antworten » | ||||||||
| ed209 | RE: Funktion Turingmaschine Zuerst einmal denke ich, dass du es im Prinzip schon richtig vestanden hast wie die Bänder mithilfe der Tupel repräsentiert werden. Glücklicherweise gibt es weitverreitete Darstellungsmöglichkeiten für Zustände und Übergänge, die sogenannte Zustandsübergangsdiagramme. Hier ein Beispiel aus Wikipedia, aber dabei handelt es sich nicht um eine Turingmaschine sondern um einen endlichen Automaten. Wenn Du nicht weisst was ein endlicher Automat ist, lohnt es sich mal bei Wikipedia nachzuschauen. Ein endlicher Automat benutzt dieselben konzepte wie eine Turingmaschine ist aber wesentlich einfacher. http://upload.wikimedia.org/wikipedia/co.../DFAexample.svg Zustände werden durch Kreise symbolisiert und Übergänge sind Pfeile von einem Zustand zum anderen. An den Übergängen ist notiert, bei welcher Eingabe sich der Zuständ ändert. (Bei einer k-Band Turingmaschine wären das k-Tupel anstelle von einzelnen Werten). Der Startzustand ist angedeuteted durch den Pfeil aus dem Nichts (hier: S0) und Endzustände haben einen doppelten Kreis (hier: ebenfalls S0). Ich hoffe das hilft dir weiter. Gruss, ED |
||||||||
| 21.09.2014, 13:15 | Auf diesen Beitrag antworten » | ||||||||
| tungusk@ | In dem Buch steht weiter: d(q,a(1),...,a(n)) = (q´,c(1),...c(n),s(1),...,s(n)) wird folgendermaßen interpretiert: Liest die TM im Zustand q auf dem k-ten Band, a(k), so wird dieses mit c(k) überschrieben, und es wird die links-rechts Bewegung s(k) durchgeführt, und geht in den Zustand q´ über. Woher weiss ich, was die Funktion d für gewisse Werte ausgibt, also das Bandquadrat mit Eintrag x, mit y überschreibt und dann nach L/R geht? Ich nehme an, dass das ganze über den Zustand q spezifiziert ist; nur was ist q? Ich bin Mathematiker, ich habe keine Probleme mit den sehr formalen Definitionen über Mengen und Tupel, nur weiss ich nicht wie diese Zustände als mathematische Objekte definiert sind. Gibt ein Zustand etwa eine der endlich vielen Möglichkeiten an, wie die Bänder beschrieben sind? Sprich ist ein Zustand q ein Tupel etwa von der Form, wenn bei dem k-ten Band n(k) Bandquadrate beschrieben sind, (a(1),...,a(n(k)),b(1),...b(n(k)),......r(1),...,r(n(k))), das heißt einfach von links oben auf dem obersten Band alle Eingaben gelistet, und dann nach der letzten Listung im ersten Band, also a(n(k)), mit der ersten im nächsten anfängt, hier dann b(1)? Danke dir echt für die Hilfe, wenn ich diese verdammten Dinger mal endlich verstanden hab, kann ich da mal ein wenig weitermachen. |
||||||||
| 21.09.2014, 13:43 | Auf diesen Beitrag antworten » | ||||||||
| Karlito | Hallo tungusk@,
Die Funktion d verwendet ja den Bandwert und den aktuellen Zustand. Somit ist natürlich nicht nur der Zustand relevant, sondern auch der aktuelle Wert auf dem Band (k-Tupel im Falle einer k-Band-TM). Stell dir eine einfache Machine vor, welche zwei Zustände hat: "An" und "Aus". Die Reaktion auf Eingaben in den beiden Zuständen ist verschieden. Ist sie aus, so reagiert sie im Zustand "Aus" nur auf die Eingabe "Anschalten" und nicht auf "Ausschalten". Dabei geht sie bei Anschalten in den Zustand "An" über und bei Ausschalten bleibt sie in dem Zustand "Aus". Analog für den Zustand "An" Welche Zustände es gibt und welche Übergänge definiert sind ist Sache des "Programmierers", denn die Menge der partiellen Übergangsfunktionen stellt das Programm der Turingmaschine dar. Du siehst gleichzeitig das Problem. Jede so definierte Turingmaschine kann nur ein Programm verarbeiten, nämlch das, was durch die Menge der partiellen Übergangsfunktionen definiert ist. Das lässt sich dadurch lösen, indem man eine TM erstellt, welche Programme vom Band liest und dieses abarbeitet. Edit: Ein Zustand die Beschreibung, wie die TM aktuell auf Eingaben (was auf dem Band steht) reagiert. Ich hoffe das hat dir beim Verständnis geholfen. Gruß, Karlito |
||||||||
| Anzeige | |||||||||
|
|
|||||||||
| 07.10.2014, 08:36 | Auf diesen Beitrag antworten » | ||||||||
| Tuling | Hallo, ich hatte kürzlich ebensolche Frage zum Thema gestellt und möchte Euer Gespräch dankbar aufgreifen, um es endlich auch zu kapieren: 'matheboard.de/thread.php?threadid=546333'. Ihr seid ja jetzt noch sehr allgemein gewesen! Aus dem Gesagten schließe ich, daß die Notation d, d' auf eine Rekursion weist. Der Automat (Algorithmus) wird also immer durch eine Rekursion beschrieben? (In der Mathematik wird ein d' als der Nachfolger "d von n+1" bezeichnet. Informatiker und Mathematiker sprechen eben zwei verschiedene Sprachen. Bitte setzt jetzt mal konkret für mein genanntes Beispiel ein und beweist für die dann erhaltenen Konkrete Rekursionsgleichung/ Algorithmus die Verdoppelung. Vielen Dank! |
||||||||
| 09.10.2014, 00:44 | Auf diesen Beitrag antworten » | ||||||||
| ed209 | Bei Automaten/Turingmaschinen spricht man eigentlich nicht von Rekursionen. Man hat ja auch keine Funktionen in dem Sinne. |
||||||||
| 10.10.2014, 09:52 | Auf diesen Beitrag antworten » | ||||||||
| Tuling | Mag sein, aber irgendwelche mathematischen Objekte müssen doch vorliegen, ansonsten wäre eine Beweisführung nicht durchführbar. Mein nur privater Ansatz bisher war, jedem Rechenschritt (Bewegung Kopf), einen Zustand (die LR-Kopf-Lage) zuzuordnen (Funktion). Dann jedem Zustand ein Zeichen (Funktion). Problem hierbei wäre jetzt das Neubeschreiben im gleichen Zustand (löschen u. neues Zeichen Eintragen), denn einem Zustand würden jetzt zwei o. mehr Zeichen zugeordnet werden (keine Funktion). Dies könnte mit dem Begriff d. Relation gefasst werden, was aber zu schweren Problemen führen würde (Determiniertheit usw.). Vorschlag: Ändern wir meine ursprüngliche Frage ab und gebt mir doch nur den konkreten Formalismus (Gleichung/ Gleichungen) für gen Problem. Ich beweise dann, daß die Verdoppelung Lösung des Gleichungssystems ist. OK? (Oder, notfalls gebe ich meine Gedanken und wir versuchen die Lösung gemeinsam zu erarbeiten). |
||||||||
| 11.10.2014, 11:43 | Auf diesen Beitrag antworten » | ||||||||
| Karlito | Hallo Tuling, coole Sache, dass Du versuchst es auf diese Weise zu durchdringen. Ich glaube ein Problem deinerseits ist wie bei dem Themenersteller, dass Du den Begriff des Zustands nicht richtig verstehst oder dass Du einen globaleren Begriff des Zustands zu verwenden versuchst. Dazu zwei "Begriffsdefinitionen". Der Zustand aus der Menge der Zustände einer Turingmaschine (TM) ist ein Zustand, in dem die TM auf eine Art und Weise auf Eingaben reagiert. In einem anderen Zustand reagiert die TM also anders auf Eingaben. Eine Eingabe ist dabei ein Zeichen auf dem Band unter dem Schreib-/Lesekopf. Der "Zustand", in dem Sich eine TM befindet, dh. Bandinhalt + aktueller Zustand aus der Menge der Zustände, wird Konfigution genannt. In Beweise über TM habe ich mich bisher noch nicht eingearbeitet. Ein Ansatz wäre aber vielleicht eine Kombination aus Induktion und Ableitbarkeit. Also:
Ich will dir natürlich nicht erklären wie Induktion funktioniert, sondern nur meinen Ansatz mitteilen, dass es zwei Abstraktionsstufen geben könnte. D.h. die Ableitbarkeit und danach die Induktion mit Hilfe der Ableitbarkeit. Auch wenn meine Antwortfrequenz eher gering ist, bin ich auf weitere Gedanken und Fragen gespannt. Gruß, Karlito |
||||||||
| 13.10.2014, 15:13 | Auf diesen Beitrag antworten » | ||||||||
| Tuling | Hallo Karlito, genau, mit "Ableitung" zielst Du wohl auf den Ableitungsoperator ab und der muß konkretisiert werden, z. Bsp. mittels Induktionbew.; Dein Punkt(2) wäre die Ind.voraussetzung, auch gen. Ind.behauptung. Dazu braucht es aber mind. ein math. Objekt (d. formalisierte Automat) über den natürlichen Zahlen?! Danke für die Definition Zustand, hatte diese nirgends gefunden. Ich bin über den Beweis 10. Hilbert-Problem darauf gestoßen, Entscheidbarkeit usw. Außerdem dürfte jeden die Begriffsdefinition 'Algorithmus' interessieren. Die Frage (*) ist zudem, wie eine Verbindung zwischen den dann formalisierten Begriffen 'Turing-Alg.' und 'math. Alg.' geschaffen werden kann. Habe allerdings am Wochenende eine Quelle ("Schnorr, Rekursive Fkt.") gefunden: Church'sche These, partielle Funktionen.. . Weiterzureden, ohne mir das vorher geanu anzusehen, wäre nicht konstruktiv. Ist aber hartes Brot, ohjeh, das wird dauern. Allenfalls könnten wir die Unterscheidung (*) diskutieren. Da hätte ich Fragen. Will den Thread aber nicht in Konfusion stürzen. |
||||||||
| 13.10.2014, 17:09 | Auf diesen Beitrag antworten » | ||||||||
| Karlito | Hallo Tuling,
Jein. Schau dir mal das Konzept der strukturellen Induktion an.
Ja, das war bei mir zum Teil Inhalt des Grundstudiums. Viele Informatiker haken das ab und vergessen es.
Mach ruhig... Gruß, Karlito |
||||||||
|
|
