 Tautologien unentscheidbar für Turing Maschinen |
noAhnung
unregistriert
 |
|
| Tautologien unentscheidbar für Turing Maschinen |
     |
Meine Frage:
Hallihallo,
ich versuche mich gerade an der folgenden Aufgabe:
Sei
![[latex]TM_{TAUT}:= \{<M> | M\,\, ist\,\, eine\,\, TM\,\, mit\,\, L(M) = TAUT\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?TM_{TAUT}:= \{<M> | M\,\, ist\,\, eine\,\, TM\,\, mit\,\, L(M) = TAUT\}) .
Zeigen Sie, dass ![[latex]TM_{TAUT}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?TM_{TAUT}) nicht entscheidbar ist.
Meine Ideen:
Leider haben mir Turing Maschinen schon lange Probleme bereitet und leider macht's mir diese Aufgabe leider nicht besonders leicht. Kann mir hier vielleicht irgendjemand ein bisschen Hilfestellung während der Aufgabe geben?
Soll mein Beweis auf eine Reduktion auf das Halteproblem hinauslaufen oder geht es um etwas ganz anderes?
Würde mich sehr über Hilfe freuen!
|
|
02.06.2016 22:44 |
|
|
Gast777
unregistriert
|
|
TAUT ist semientscheidbar, aber nicht entscheidbar, siehe Satz von Church und Turing (1936). Ein Beweis dafür ist hier skizziert: [www].thi.uni-hannover.de/fileadmin/forschung/arbeiten/lueck-ba.pdf
Ein ausführlicher Beweis soll hier zu finden sein:
Hoffman, Dirk: Grenzen der Mathematik: Eine Reise durch die Kerngebiete der mathematischen Logik, 2011. 2. Auflage (2013). Springer Spektrum
VG,
Steffen
|
|
|
04.06.2016 10:07 |
|
|
noAhnung
unregistriert
|
|
Vielen lieben Dank für den Hinweis! 
|
|
|
05.06.2016 21:22 |
|
|
|
