V tomto pdf jsem narazil na problém níže:
Vzhledem k TM M, ať už M při spuštění na prázdnou pásku zapíše symbol, který není prázdný.
Uvedené řešení je následující:
Nechejte stroj psát pouze prázdné symbol. Pak jeho počet konfigurací ve výpočetním výpočtu na w je q × 2, kde q je počet stavů M; faktor 2 je pro volby re. směr pohybu hlav; pro psaný symbol neexistuje žádný faktor, protože ten je vždy prázdný. Takže problém je rozhodnutelný, o kterém rozhoduje následující stroj: vstup (M, w), spuštění M na w pro q × 2 kroky; pokud někdy napíše neprázdný symbol, ukončete odpověď ano; pokud M nikdy nenapíše neprázdný symbol, přestaň bez odpovědi
Pochybnosti:
Q1. Jak jsou jisté všechny konfigurace qx 2 při spuštění qx 2 kroky na w? Některá konfigurace se mohou opakovat v krocích 2.
Q2. Otázka říká „při spuštění na empty tape “, ale odpověď se pokusila simulovat TM na neprázdném řetězci w. Jak to dává smysl?
Odpověď
Q1: Stav se může opakovat. Jde o to, že pokud se stav opakuje a nebyl dokonce napsán žádný neprázdný symbol, pak jste věděli, že Turingův stroj se nikdy nezastaví, protože je nutně zaseknutý cyklicky procházet některými státy, se kterými se dosud setkal. Protože žádný ze stavů cyklu nezpůsobil, že TM zapsala neprázdný symbol, TM nikdy nezapíše neprázdný symbol.
Po $ 2q $ kroky, buď byl napsán neprázdný symbol, a můžete odpovědět „ano“, nebo byly všechny psané symboly prázdné a (alespoň) jeden stát musel být narazen dvakrát nebo vícekrát, což znamená, že můžete odpovědět „ne“.
Q2: Myslím, že $ w $ je někde definován jako prázdný řetězec. Pokud lze TM spustit pomocí libovolného řetězce $ w $ , pak varianta výše uvedeného řešení stále funguje. Předpokládejme, že hlava TM začíná na začátku $ w $ . Počet stavů se zvyšuje o faktor maximálně $ 1+ | w | $ , aby se zohlednily všechny možné stavy pásky (pokud jsou zapsány pouze prázdné symboly , pak páska vždy obsahuje jednu z $ 1+ | w | $ přípon $ w $ ). Pokud může hlava začít kdekoli, bude tento faktor maximálně $ 1+ | w | ^ 2 $ .
Komentáře
- V Q1. Máte na mysli " buď napsaný neprázdný symbol, můžete odpovědět ano … a můžete odpovědět ne "? Protože otázka se ptá ", zda M někdy napíše neprázdný symbol ". V Q2. Nezískal jsem " počet stavů odpovídající počtu podmnožin pozic w, které byly přepsány prázdným symbolem "
- Máte pravdu. Opravil jsem svou odpověď. Také jsem vyjasnil druhou část.