Ist die Sprache l= {, m akzeptiert eine endliche Menge an Wörtern} entschieden?

Question

ist $ l={ |L (m) \ ist \ endite \} $ entschieden?M ist ein tm.

Ich denke, es ist relativ einfach zum Beweis mit dem Theorem von Reis.Aber ich interessiere mich für eine Lösung, die den Reisstorem nicht benutzt.

Dies ist mein Versuch: Sei f () eine Funktion, die auf folgende Weise arbeitet:

.
1. run w auf m
2. wenn m akzeptiert, baue ein tm mwhich accepts only the word w and return M
3. Wenn M ablehnt, erstellen Sie einen TM-Mwhich accepts everything. Return M

also, wenn m in $ a_ {tm}={ m \ akzeptiert \ w \} $ wir wissen, dass f () ist in L. Wenn M nicht in einem dann ist, wissen wir, dass f () jedes Wort akzeptiert und daher Unendlichkeitswörter ist.So f () nicht in l.

ist dies eine korrekte Mapping-Reduktion?

Answer 1

Die von Ihnen definierte Funktion ist überhaupt keine Verringerung - es kann nicht einmal aufgehalten werden!

Das Problem läuft $ M $ auf $ W $ : Kannst du sicher sein, dass du sicher bist?="Math-Container"> $ M $ werden in einer unendlichen Schleife auf $ W $ stecken? Sie können nicht.

Sie können eine ordnungsgemäße Reduzierung wie folgt definieren: (bei Eingabe $ $ )

Erstellen Sie das Gerät $ M_ {M, W} $ das tut den folgenden Algorithmus und gibt den folgenden Algorithmus ein: (bei Eingabe $ s $ )

.
1. Emulieren $ M $ auf $ W $ für $ | s | $ Schritte. Wenn $ M $ in dieser Zeit gestoppt, lehnen Sie $ s $ ab. Andernfalls akzeptieren Sie $ s $ .

Ich werde es für Sie verlassen, um zu beweisen, dass dies eine ordnungsgemäße Reduzierung von $ H_ {TM} $ bis $ l ist $ (es ist eine gute Übung!)