Löysin alla olevan ongelman tässä pdf-muodossa :
Kun otetaan huomioon TM M, kirjoittaako M koskaan tyhjän symbolin aloitettaessa tyhjälle nauhalle.
Annettu ratkaisu on seuraava:
Anna kone kirjoittaa vain tyhjäksi symboli. Sitten sen konfiguraatioiden määrä laskennassa w: llä on q × 2, missä q on M: n tilojen lukumäärä; tekijä 2 on valinnoille re. pään liikkeen suunta; kirjoitetulle symbolille ei ole tekijää, koska se on aina tyhjä. Joten ongelma on ratkaistavissa, päättää seuraava kone: tulo (M, w), ajaa M w: llä q × 2 askelta; jos se M kirjoittaa koskaan ei-tyhjän symbolin, lopeta kyllä-vastauksella; jos M ei koskaan kirjoita ei-tyhjää symbolia, lopeta ilman vastausta
Epäilyt:
Q1. Kuinka varma, että kaikki qx 2 -määritykset tapahtuvat samalla kun suoritat qx 2 askelta w: llä? Joitakin määrityksiä voidaan toistaa qx 2 -vaiheissa.
Q2. Kysymys sanotaan ”kun se aloitettiin tyhjä nauha ”, mutta vastaus yritti simuloida TM: tä muulla kuin tyhjällä merkkijonolla w. Kuinka sillä on järkeä?
Vastaa
Q1: Tila voidaan toistaa. Asia on, että jos tila toistuu eikä mitään tyhjää symbolia ole edes kirjoitettu, niin tiesit, että Turingin kone ei koskaan pysähdy, koska se on välttämättä jumissa pyöräilemällä joissakin toistaiseksi havaituissa tiloissa. Koska yksikään syklin tiloista ei aiheuttanut TM: n kirjoittavan ei-tyhjää symbolia, TM ei koskaan kirjoita ei-tyhjää symbolia.
$ 2q jälkeen $ vaiheet, joko ei-tyhjä symboli on kirjoitettu ja voit vastata ”kyllä”, tai kaikki kirjoitetut symbolit olivat tyhjiä ja (ainakin) yksi tila on täytynyt kohdata vähintään kaksi kertaa, mikä tarkoittaa, että voit vastata ”ei”.
Q2: Oletan, että $ w $ määritetään jonnekin tyhjäksi merkkijonoksi. Jos TM voidaan aloittaa jollakin mielivaltaisella merkkijonolla $ w $ , niin muunnelma yllä olevasta ratkaisusta toimii edelleen. Oletetaan, että TM: n pää alkaa $ w $ alusta. Tilojen määrä kasvaa kertoimella enintään $ 1+ | w | $ , jotta voidaan ottaa huomioon kaikki mahdolliset nauhan tilat (jos vain tyhjiä symboleja kirjoitetaan , sitten nauha sisältää aina yhden $ 1+ | w | $ loppuliitteistä $ w $ ). Jos pää voi alkaa mistä tahansa, tämä tekijä on enintään $ 1+ | w | ^ 2 $ .
Kommentit
- Q1. Tarkoitatko ", onko joko tyhjä symboli kirjoitettu, ja voit vastata kyllä … ja voit vastata ei "? Koska kysymys kysyy " kirjoittaako M koskaan mikään tyhjä symboli ". Q2: ssa. En saanut " tilojen lukumäärään, joka vastaa w-sijaintien osajoukkojen määrää, jotka on korvattu tyhjällä symbolilla "
- Olet oikeassa. Korjasin vastaukseni. Selvensin myös jälkimmäistä osaa.