Turing
-
Ähmm, hab ich da irgend was missverstanden oder liegt hier das Halteproblem vor? Falls ja ist die Aufgabe komisch formuliert. Falls nicht hab ich keinen Plan... Könnte mir dann jemand eine Anzatz liefern. Danke
Zeigen Sie, dass es zu jeder Turing-Maschine M eine Turing-Maschine M1 mit
fM1 (w) = ( 1 falls fM(w)defniert ist;
nicht defniert sonst
gibt.
-
<--
-
Erklärt mal bitte ein paar Worte dazu, habe echt keinen Plan zu der Aufgabe und das Skipt gibt auch keinen Aufschluss. Oder seit ihr euch selbt nicht sicher?
-
was soll definiert / nicht definiert bedeuten? dass die turingmaschine ein wort nicht akzeptiert? dann wäre die aufgabe zu zeigen, dass zu jeder turing maschine eine turing maschine existiert, die entscheiden kann, ob eine gegebene turing maschine ein wort akzeptiert oder nicht.
-
Genau so habe ich die Aufgabe auch verstanden. Ahnungslos bin ich aber immer noch. Meine erste Vermutung dass hier das Halteproblem vorliegt schein also falsch zu sein. Ist das so weil das eine Programm entscheidet ob das ander Porgramm einen definierten Eingabewert enthält und nicht ob es terminiert? Gibt es im Internet evtl ein brauchbares Tutorial zu dem Thema? Oder erbarmt sich jemand mir das kurz zu erklären? Das Vorlesungsskript ist für jemand der gerade keine Ahnung hat echt keine Hilfe.
-
ersi schrieb:
Genau so habe ich die Aufgabe auch verstanden. Ahnungslos bin ich aber immer noch. Meine erste Vermutung dass hier das Halteproblem vorliegt schein also falsch zu sein. Ist das so weil das eine Programm entscheidet ob das ander Porgramm einen definierten Eingabewert enthält und nicht ob es terminiert? Gibt es im Internet evtl ein brauchbares Tutorial zu dem Thema? Oder erbarmt sich jemand mir das kurz zu erklären? Das Vorlesungsskript ist für jemand der gerade keine Ahnung hat echt keine Hilfe.
Die Funktion (Semantik der Maschine) ist nicht definiert für Eingaben, für die die Maschine nicht anhält.
Du baust also eine Maschine, die folgendes tut:
1. Führe die ursprünglich gegebene Maschine mit der Eingabe w aus.
2. Gib 1 zurück.
Wenn die erste Maschine nicht anhält, tuts die zweite auch nicht. Ansonsten gibt sie 1 zurück, wie gefordert.
-
Ah danke. Ist ja garnicht so schwer wie ich befürchtet hatte.
Habt mir wirklich geholfen. Eine weitere Frage habe ich noch. Reicht es aus dass letzte Feld mit 1 zu beschreiben, oder müssen zusätzlich noch alle anderen Felder mit "leeres Feld" überschrieben werden?
-
Das gehört zu den Freiheiten, die du bei der Definition "Was ist die Ausgabe der Turingmaschine" hast - für die Praxis ist es irreleavant, ob du am Ende nur die Ausgabe auf dem Band stehen hast oder noch weitere Daten, die sauber von der Ausgabe getrennt werden können.
-
Hab neulich in einem Museum eine Turing Maschine gesehen.
Wer programmiert denn heute noch mit sowas?!
-
zweiti schrieb:
Hab neulich in einem Museum eine Turing Maschine gesehen.
Wer programmiert denn heute noch mit sowas?!theoretische Informatiker
Die Turing-Maschine ist eher ein Gedankenmodell, um an Fragen wie "ist diese Funktion berechenbar?" oder "wie aufwendig ist diese Funktion?" herangehen zu können - sowas wird normalerweise nicht praktisch gebaut, sondern nur auf dem Papier entworfen. Der Vorteil ist, daß eine Turing-Maschine einen relativ einfachen Befehlssatz hat verglichen mit Hochsprachen wie C oder C++ (oder Assambler ;)) - da werden die fertigen "Programme" allerdings auch entsprechend umfangreich.(PS: moderne Rechner liegen aber näher auf der Registermaschine als an der Turingmaschine)