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

Тушунтиришлар
q1 ҳолатда автомат соннинг охирги рақами остига “югуради”. Бунинг учун у ҳамма вақт кўриниб турган рақамларни ўзгартирмаган ва ўша ҳолатда қолган ҳолда ўнгга томонга силжийди. Аммо бу ерда битта махсуслик бор: қачонки автомат охирги рақам остида ётганда, у ҳали ўзи бу ҳақида билмайди (ахир у кўрмайдику, қўшни катакларда нималар ёзилганлигини) ва буни фақатгина бўш катак пайдо бўлгандагина билади. Шунинг учун, автомат биринчи бўш катакка бориши биланоқ, орқага –охирги рақамнинг остига қайтади ва q2 ҳолатга ўтади (ўнгга ҳаракатланиш керак эмас). q2 шундай ҳолатки, бунда автомат айни вақтда кўриб турган рақамига 1 қўшиб қўяди. Дастлаб бу рақам соннинг охирги рақами бўлсин; агар у 0-8 оралиғидаги рақам бўлса, у ҳолда автомат уни ўзидан биттага катта рақам билан алмаштиради ва тўхтайди. Агар бу рақам 9 бўлса, у ҳолда автомат уни 0 билан алмаштиради ва олдинги q2 ҳолатда турганича чапга томон силжийди. Шу билан бирга у энди 1 ни олдинги рақамга қўшиб қўяди. Агар бу рақам ҳам 9 га тенг бўлса, у ҳолда уни 0 билан алмаштиради ва яна олдинги q2 ҳолатда турганича чапга томон силжийди. Агар автомат чапга силжиганда кўринадиган катакда рақам бўлмаса ( аммо “бўшлик” бор), у ҳолда бу катакка 1 ни ёзади ва тўхтайди. Айтиб ўтиш жоизки, бўш кириш сўзи учун бу масала аниқланмаган. Шунинг учун бундай бўш кириш сўзига ТМ ўзини хоҳлаганча тутиши мумкин. Бизнинг программада, масалан, бўш кириш сўзида ТМ тўхтайди ва 1 жавобини беради. Юқорида биз программани тўлиқ кўринишда, қисқартирилмаган ҳолда келтирдик. Энди программанинг ёзилишини қисқартирилган кўринишда, анча кўринарли ҳолда келтирамиз. Шу билан бирга жадвалнинг ўнг томонида амалнинг қисқача тушунтириш матни келтирилади, қайсики, автоматнинг мос ҳолатида жорий қилинади:

8-расм. ТМ да Р (1957, 649, 99)ни 1 га ошириш программасининг бажарилиши.
Бундан кейин айнан мана шундай қилиб программа ёзилади.
2-мисол. Белгилар таҳлили.
A={a,b,c}. Бўш бўлмаган Р сўзнинг биринчи белгисини унинг охирига ўтказинг. Масалан:

9-расм. ТМ да Р сўзнинг биринчи белгисини унинг охирига ўтказиш.
Ечилиши.
Бу масалани ечиш учун қуйидаги амалларни бажариш тавсия этилади:

1. 
   Р сўзининг биринчи белгисини эслаб қолиш ва сўнгра уни ўчириш.
   
2. 
   Автоматни Р нинг охиридаги биринчи бўш катак остига олиб бориш ва у ерга хотирага олинган белгини қўйиш.
   

Ўнгга қандай “чопиш” кераклигини биз олдинги мисолдан биламиз. Аммо биринчи белгини қандай эслаб қолиш керак? Ахир ТМда лентадан бошқа эслаб қоладиган қурилма йўқку, белгини лентадаги бирор катакда сақлаб қўйиш эса маъносиздир. Автомат бу катакдан чапга ёки ўнгга силжиши биланоқ белгини эсдан чиқаради. Нима қилиш керак?
Ҳал қилиш йўли қуйидагича: автоматнинг ҳар хил ҳолатларидан фойдаланиш керак. Агар биринчи белги а бўлса, унда q2 ҳолатга ўтиш керак, қайсики бунда автомат ўнгга силжийди ва охирига а ни ёзади. Агар биринчи белги b бўлса, унда q3 ҳолатга ўтиш керак, бажариладиган иш олдингидек бўлиб, фақат охирида b ёзилади. Агар биринчи белги с бўлса, унда q4 ҳолатга ўтиш керак, бажариладиган иш олдингидек бўлиб, фақат охирида с ёзилади. Шундай қилиб, масаланинг ечими, биринчи белги қандай бўлишидан қатъий назар, автоматни ҳар хил ҳолатларга ўтказиш йўли билан ҳал қилинди. Бу ТМ да программалашнинг типик усули бўлиб ҳисобланади.
Айтилганлар бўйича программа кўриниши қуйидагича бўлади:


10-расм. ТМ да программанинг бажарилиши.
Бу программанинг ўзгаришини битта белгили кириш сўзларидаги ўзгаришини кўрайлик. Бўш сўзда, қайсики бу масала учун “ёмон” дейилар эди, программа циклга тушиб қолади, q1 ҳолатда турган автомат, ҳар доим бўш катакка тушиб, чексиз марта ўнгга томон силжийди. (Албатта, бу ҳолда программани тўхтатса бўлар эди, аммо биз бундай имкониятни кўрсатиш учун уни атайин циклга тушадиган қилиб қўйдик.)
Агар кириш сўзида битта белги бўлса, унда автомат бу белгини ўчиради, ўнгга томон бир хона силжийди ва унга мана шу белгини ёзади.


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