Программа тузишга мисоллар Режа: Тьюринг машинасида (ТМ) автоматни силжитиш, белгиларни алмаштириш

5-мисол. Сўзни сиқиш.
A={a, b, с} . P сўзидан биричи учраган а белгисини ўчиринг, агар шундай белги бўлса.
Ечилиши. Олдинги мисолда биз ўнг томонга битта белгини ўтказишни кўрдик. Бу мисолда биз циклда барча бошланғич b ва с белгиларни то биринчи а белгигача ёки бўш катакгача ўнгга ўтказамиз:

16-расм. ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси.
Энг асосий моменти бу ерда х белгисини қандай қилиб чап катакдан у белгиси жойлашган ўнг катакка ўтказиш масаласидир. Шу билан бирга у белгисини кейинги ўнг катакка ўтказиш мумкин бўлсин. Агар q_x билан кўриниб турган катакка х белгисини ёзиш керак бўлган ҳолатни белгиласак, қайсики олдин у чапда турган бўлса, у ҳолда бу ҳолатни қуйидагича ифодалаш мумкин:

17-расм. ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси.
Бунинг учун ўзида қуйидаги учта амални бирлаштирган х,R,q_y тактини бажариш таклиф этилади: биринчидан, кўринадиган катакка чап катакдан олинган х белгиси ёзилади; иккинчидан, автомат ўнгга томон ҳозиргина алмаштириладиган у остига ўтади; автомат бу ёзувни амалга ошириш учун q_y ҳолатга ўтади. Мана шунақа тактларни циклда такрорлаш кириш сўзининг бошланғич белгиларини битта позицияга суришга олиб келади. Бу цикл навбатдаги катакда а ёки Λ белгиси учраши биланоқ тугалланиши (y=a ёки y= Λ) керак. Цикл бошида эса чапдан биринчи белги ўрнига “бўш” (x= Λ) белгиси ўтказилади деб ҳисоблаш керак. Натижада ТМ учун қуйидаги программа ҳосил бўлади:



18-расм. ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси.
Бу программада, кириш сўзининг биринчи белгиси а бўлганда конфигурацияда бажариладиган Λ,R,! тактга эътибор беринг. Тушунарлики, шунчаки бу белгини ўчириб тўхташ керак. Шу билан бирга яна ўнгга силжиш ҳам айтилган. Нега? Эслатиб ўтамизки, тўхташ пайтида автомат чиқиш сўзининг остида жойлашиши керак (унинг ихтиёрий белиси остида), шунинг учун биз автоматни бўш катакдан чиқиш сўзининг биринчи белгиси остига силжитамиз, қайсики кириш сўзида у иккинчи белги бўлсин.