Az alábbi problémával találkoztam ebben a pdf-ben :
Ha egy TM M-et kap, akkor M ír-e valaha nem üres szimbólumot, amikor elindult az üres szalagon.
A megadott megoldás a következő:
A gép csak üresen írjon szimbólum. Ekkor konfigurációinak száma a w számítás során q × 2, ahol q az M állapotainak száma; a 2. tényező a re választásokra vonatkozik. a fejek mozgásának iránya; nincs tényező az írott szimbólumra, mert az mindig üres. Tehát a probléma eldönthető, a következő gép dönti el: bemenet (M, w), futtassa M-et w-n q × 2 lépésenként; ha M valaha nem üres szimbólumot ír, álljon le igen válaszsal; ha M soha nem ír nem üres szimbólumot, álljon meg válasz nélkül
Kételyek:
Q1. Hogyan lehet biztos abban, hogy minden qx 2 konfiguráció megtörténik qx 2 lépés futása közben w? Bizonyos konfigurációk qx 2 lépésekben megismétlődhetnek.
Q2. A kérdés azt mondja, amikor elindult a üres szalag “, de a válasz megpróbálta szimulálni a TM-et nem üres w karakterláncon. Hogyan van értelme?
Válasz
Q1: Egy állapot ismétlődhet. A lényeg az, hogy ha egy állapot megismétlődik, és nem is írtak ki nem üres szimbólumot, akkor tudta, hogy a Turing-gép soha nem fog leállni, mivel szükségszerűen elakadt az eddig tapasztalt állapotok némelyikén keresztül. Mivel a ciklus egyik állapota sem okozta a TM-nek nem üres szimbólum írását, a TM soha nem ír nem üres szimbólumot.
$ 2q után $ lépések szerint vagy egy nem üres szimbólumot írtak, és válaszolhat “igen”, vagy az összes írott szimbólum üres volt, és (legalább) egy állapotot kétszer vagy többször kellett találkozni, ami azt jelenti, hogy válaszolhat “nem”.
Q2: Azt hiszem, hogy $ w $ az üres karakterlánc. Ha a TM valamilyen tetszőleges karakterlánccal $ w $ indítható, akkor a fenti megoldás változata továbbra is működik. Tegyük fel, hogy a TM feje a $ w $ elején kezdődik. Az állapotok száma legfeljebb $ 1+ | w | $ tényezővel növekszik annak érdekében, hogy figyelembe vegyék a szalag összes lehetséges állapotát (ha csak üres szimbólumokat írnak , akkor a szalag mindig tartalmazza az egyik $ 1+ | w | $ utótagot a $ w $ ). Ha a fej bárhonnan elindulhat, akkor ez a tényező legfeljebb $ 1+ | w | ^ 2 $ .
Megjegyzések
- Az első negyedévben. Úgy érted, hogy ", vagy nem üres szimbólumot írtál, és válaszolhatsz igen -re … és válaszolhatsz nemre "? Mivel a kérdés azt kérdezi ", hogy M ír-e valaha nem üres szimbólumot ". A Q2-ben. Nem kapott " az állapotok számában, amely megfelel egy üres szimbólummal felülírt w pozíciók részhalmazainak számának "
- Igazad van. Kijavítottam a válaszomat. Az utóbbi részt is tisztáztam.