Unentscheidbarkeit dieser Sprache durch Reduktion zeigen?
Hallo! Ich bräuchte Hilfe bei dieser Aufgabe:
"Sei L = {<M> | M akzeptiert, wenn die Eingabelänge durch 5 teilbar ist}. Zeigen Sie durch Reduktion, dass L unentscheidbar ist."
Ich weiß, dass man jetzt einen Widerspruchsbeweis aufstellen sollte, indem man eine bekanntlich unentscheidbare Sprache U auf L reduziert. Dazu nimmt man an, dass L entscheidbar wäre und dafür somit ein Entscheider existiert. Daraus baut man dann eine Entscheider-TM T für diese unentscheidbare Sprache U, was einen Widerspruch erzeugt.
Welche unentscheidbare Sprache sollte man hier bestenfalls benutzen (vielleicht das Wortproblem ATM) und wie würde dann die TM T im Ansatz funktionieren?
Danke!
(Außerdem verstehe ich nicht ganz, warum L nur <M> als Eingabe hat und nicht <M,w>.)
1 Antwort
Du nimmst eine TM, die L entscheidet.
Du baust eine neue TM M, die eine beliebige TM M' und ein Wort w als Eingabe nimmt.
Du baust eine TM M'', die w'=w+v als Eingabe erhält. v wird vond ieser ignoriert, dann M mit w ausgeführt. v wird so gewählt, dass w' durch 5 teilbar ist.
Du prüfst mittels der TM für L ob M'' für durch 5 teilbare Eingaben, somit auch für w', akzeptiert und gibst das Ergebnis als Ergebnis von M aus.
Und schon hast du eine TM M, die eine beliebige TM und ein beliebiges Eingabewort erhält und entscheidet, ob die übergebene TM für die übergebene Eingabe akzeptierend hält. Somit wurde das Halteproblem gelöst.