Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Universelle Turingmaschine
Autor
Universität/Hochschule Universelle Turingmaschine
Paritie
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 05.11.2020
Mitteilungen: 1
  Themenstart: 2021-07-13

Hallo, wir haben in der Vorlesung die Universelle Turingmaschine kennen gelernt. Ich frage mich jedoch, wann man diese in der Theorie (für Reduktions-Beweise etc.) wirklich braucht; also was der Unterschied zwischen der Simulation einer TM und der direkten Ausführung ist. Wir haben zum Beispiel das Halteproblem beschrieben als \[ P_{\textrm{Halt}} = \{\textrm{enc}(\mathcal{M})\#\#\textrm{enc}(w) \mid \mathcal{M} \textrm{ hält für Eingabewort } w\} \] Hierbei soll das \( \textrm{enc}(\mathcal{M})\#\#\textrm{enc}(w) \) eine geeignete Kodierung für eine TM mit Eingabewort sein, für die die Simulation durchgeführt wird. könnte man das nicht auch so beschreiben: \[ P_{\textrm{Halt}} = \{w \in \Sigma^* \mid \mathcal{M} \textrm{ hält für Eingabewort } w\} \] Über eine kleine Erklärung wäre ich super dankbar. Liebe Grüße :)


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Zwerg_Allwissend
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 02.12.2013
Mitteilungen: 249
  Beitrag No.1, eingetragen 2021-07-24

Man braucht die UTM beispielsweise, um zu zeigen, daß das Totalitätsproblem oder das Äquivalenzproblem nicht semi-entscheidbar ist. Oder ein einfacheres Beispiel: Zeige, daß das Halteproblem semi-entscheidbar ist. Beweis informell: Sei #TM der Code einer TM und n die Eingabe für TM. Die UTM erhält als Eingabe #TM und n, führt TM mit n aus und schreibt dann 1 aufs Band. Man erhält als Ergebnis 1, falls TM mit Eingabe n hält, andernfalls erhält man kein Ergebnis, da die Ausführung von TM mit n nicht hält. Folglich ist das Halteproblem semi-entscheidbar. PS: Eine UTM ist nichts anderes als ein Interpreter für Turingmaschinen, der Code eine TM entspricht dem Programmtext in konventionellen Programmiersprachen.


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]