Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
   Turing-mächtige Automaten |
|
MatheStein
Aktiv 
Dabei seit: 03.07.2009
Mitteilungen: 1131
Aus:
 |      Themenstart: 2010-02-22 23:36
|
Hey Leute,
kann mir evtl einer von euch erklären, wie man grob eine TM auf einem Automaten simulieren kann, der genau so definiert ist wie ein normaler endlicher Automat jedoch nicht mit der Einschränkung, dass das die Zustandsmenge endlich ist?
So wie ich das verstanden habe macht diese Freiheit den "endl. Automaten" (der ja eigentlich gar nicht mehr endlich ist) Turing-Mächtig kann mir leider nur absolut nicht vorstellen, wie man den Beweis der simulation angeht.
Eine TM ist ein Automat, mit einem Band, dass beschrieben werden kann etc.
Wie kann man das Beschreiben des Bands einer TM an einer Stelle x auf einem "endl Automaten" mit unendlicher Zustandsmenge simulieren?
Kann mir da evtl. einer einen Denkanstoß geben? :)
Schönen Abend noch an alle
|
 Profil
 Quote
 Link |
wasseralm
Senior 
Dabei seit: 26.10.2003
Mitteilungen: 1838
Aus: Erlangen
 | Beitrag No.1, eingetragen 2010-02-23 01:17
|
Hallo MatheStein,
zu jeder beliebigen Sprache über einem endlichen Alphabet gibt es einen Automaten mit höchstens abzählbar vielen Zuständen (analog zu endlichen Automaten), der genau diese Sprache akzeptiert.
Damit sind solche Automaten viel mächtiger als Turing-Maschinen, die ja nur rekursiv aufzählbare Sprachen akzeptieren können.
Von daher ist mir die Aufgabenstellung recht unklar.
Gruß von Helmut
-----------------
Ich glaube an die Widerspruchsfreiheit der PEANO-Arithmetik (1. Stufe)
|
Profil
Quote
Link |
MatheStein
Aktiv
Dabei seit: 03.07.2009
Mitteilungen: 1131
Aus:
| Beitrag No.2, vom Themenstarter, eingetragen 2010-02-26 07:05
|
Danke für deine Antwort. Formal gesehen war meine Frage folgende:
Sei eine TM gegeben und eine weitere Maschine M=(Q,A,S_0,R,F) mit:
Q: eine (möglicherweise unendliche) Menge von Zuständen
A: Das Eingabealphabet
S_0: eine Menge von Startzuständen
R: Eine Übrgangsrelation R der Form (q,a,q')€R mit q,q'€Q und a€A
F: eine Menge von Startzuständen
M ist also so definiert wie die normalen endlichen Automaten jedoch mit dem kleinen Unterschied, dass die Zustandsmenge Q nicht endlich sein muss.
Unser Prof hat in einem Nebensatz erwähnt, dass allein schon der Verzicht auf die Endlichkeit von Q die Maschine M Turing-Mächtig macht, d.h. man könnte die TM auf M simulieren, ich hab leider nur gar keine beweisidee und genau das war die ursprüngliche Frage :)
Gruß
|
Profil
Quote
Link |
TheBear
Senior 
Dabei seit: 31.01.2006
Mitteilungen: 1219
Aus:
| Beitrag No.3, eingetragen 2010-02-26 14:52
|
Moin MatheStein,
wenn man wirklich die DTM simulieren will, kann man das machen, indem man einfach die Menge der Konfigurationen der DTM (das sind abzählbar unendlich viele) als Zustandsmenge für den Automaten nimmt, und für jede Konfiguration einen epsilon-Übergang zur Nachfolgekonfiguration macht. Dazu kommen noch Übergänge, die am Anfang die Eingabe einlesen und den Automaten in den Zustand entsprechend der Startkonfiguration der DTM bei der Eingabe bringen.
Einfacher wird es, wenn man nicht die DTM simuliert, sondern für eine beliebige Sprache direkt den Automaten baut. Man nehme sich für jedes Wort w aus der Sprache einen endlichen Automaten Aw mit L(Aw) = {w} und bilde den Vereinigungsautomaten aus allen so erhaltenen Automaten. Der hat dann natürlich potentiell unendlich viele Zustände, aber auch offensichtlich nur abzählbar unendlich viele.
Gruß TheBear
|
Profil
Quote
Link |
wasseralm
Senior 
Dabei seit: 26.10.2003
Mitteilungen: 1838
Aus: Erlangen
| Beitrag No.4, eingetragen 2010-02-26 20:22
|
2010-02-26 07:05 - MatheStein in Beitrag No. 2 schreibt:
Danke für deine Antwort. Formal gesehen war meine Frage folgende:
Sei eine TM gegeben und eine weitere Maschine M=(Q,A,S_0,R,F) mit:
Q: eine (möglicherweise unendliche) Menge von Zuständen
A: Das Eingabealphabet
S_0: eine Menge von Startzuständen
R: Eine Übrgangsrelation R der Form (q,a,q')€R mit q,q'€Q und a€A
F: eine Menge von Startzuständen
...
Hallo,
hier noch eine Alternative zu dem Automaten von TheBear:
Für eine Sprache L über dem Alphabet A ist ein deterministischer, vollständiger unendlicher Automat, der genau L akezptiert der folgende:
Q = A* (alle Wörter über A)
S0 = {epsilon} (das leere Wort)
R besteht aus allen (w, a, wa) für a aus A und w aus Q
F = L (Endzustände)
Solche Automaten sind also "allmächtig", nicht nur turingmächtig.
Was ich allerdings nicht weiß ist, auf welche Weise man die Sprachklasse einschränkt, wenn man fordet, dass die Menge der Endzustände endlich ist.
Gruß von Helmut
-----------------
Ich glaube an die Widerspruchsfreiheit der PEANO-Arithmetik (1. Stufe)
|
Profil
Quote
Link |
MatheStein
Aktiv
Dabei seit: 03.07.2009
Mitteilungen: 1131
Aus:
| Beitrag No.5, vom Themenstarter, eingetragen 2010-02-26 21:54
|
Interesannte und auch simple Ideen, danke :)
Habt ihr auch eine Idee wie man eine TM auf einem unendlichen Automaten, wie unten definiert simulieren könnte, ohne den Ansatz über die Sprachklassen zu wählen?
In der Berechenbarkeitstheorie gibts ja auch den Ansatz über Funktionen in der man zB unter anderem eine Registermaschine auf einer TM simuliert und umgekehrt.
Das müsste demnach ja auch mit einer TM und einem unendlichen Automaten gehen, da über die Sprachklassen schon gezeigt wurde, dass eine TM und ein unendlicher Automat gleichmächtig sind.
Gruß und schönes Wochenende an alle ;)
|
Profil
Quote
Link |
TheBear
Senior
Dabei seit: 31.01.2006
Mitteilungen: 1219
Aus:
| Beitrag No.6, eingetragen 2010-02-27 17:11
|
Ahoi,
TM und unendliche Automaten sind nicht gleichmächtig. Ein unendlicher Automat kann also nicht auf einer TM simuliert werden. Eine TM kann aber auf einem unendlichen Automaten simuliert werden, die Konstruktion habe ich oben grob angegeben.
|
Profil
Quote
Link |
MatheStein
Aktiv
Dabei seit: 03.07.2009
Mitteilungen: 1131
Aus:
| Beitrag No.7, vom Themenstarter, eingetragen 2010-02-27 18:02
|
stimmt, hatte die genau Definition einer Konfiguration nicht mehr im Kopf :)
Vielen dank :)
|
Profil
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]