Тьюринг машинаси учун программа тузишга мисоллар

3-маъруза. Тьюринг машинаси учун программа тузишга мисоллар

Режа:

1. 
   Тьюринг машинасида (ТМ) автоматни силжитиш, белгиларни алмаштириш.
   
2. 
   ТМ да Р сўзнинг биринчи белгисини унинг охирига ўтказиш алгоритми.
   
3. 
   ТМ да кириш сўзидаги иккинчи белгини ўчириш программаси.
   
4. 
   Сўзга белги қўйиш алгоритми.
   

ТМ учун программалар тузишга мисоллар
ТМ да программалар тузишнинг баъзи бир типик усулларини намойиш этиш учун мисоллар кўрамиз. Масалаларни ифодалашни соддалаштириш учун қуйидаги келишувларни киритамиз:
- кириш сўзини Р ҳарфи билан белгилаймиз;
- кириш сўзи алфавитини А деб белгилаймиз, яъни бу шундай белгилар наборики, улардан ва фақат улардан Р тузилиши мумкин (бироқ, таъкидлаб ўтиш керакки, оралиқ ва чиқиш сўзларида бошқа белгилар учраши мумкин).
1-мисол. Автоматни силжитиш, белгиларни алмаштириш.
A={0,1,2,3,4,5,6,7,8,9}. Фараз қилайлик, Р – бўш бўлмаган сўз; демак, Р – бу ўнли рақамлардан ташкил топган кетма-кетлик, яъни манфий бўлмаган бутун сонларнинг ўнли системада ёзилиши. Лентада Р сонидан биттага кўп бўлган сонни ёзиш талаб қилинсин.
Ечиш.
Бу масалани ечиш учун қуйидаги амалларни бажариш тавсия этилади:

1. 
   Автоматни энг охирги рақам остига жойлаштириш керак.
   
2. 
   Агар бу рақам 0 дан 8 гача бўлса, у ҳолда уни 1 га катта бўлган рақам билан алмаштириб тўхташ керак бўлади; масалан:
   

4-расм. ТМ да Р (1957)ни 1 га ошириш программасининг бажарилиши.

3. 
   Агар бу рақам 9 бўлса, у ҳолда уни 0 билан алмаштириш керак ва автоматни олдинги рақамга силжитиш керак, сўнгра худди шу усул билан охиргидан битта олдинги рақамни бирга ошириш керак; масалан:
   

5-расм. ТМ да Р (649)ни 1 га ошириш программасининг бажарилиши.

4. 
   Махсус ҳол: Р да фақат 9 лар бўлсин (масалан, 99). У ҳолда автомат 9 ларни 0 ларга алмаштириб, чапга томон силжийди, ва охирида бўш катак остида тўхтайди. Бу бўш катакка 1 ни ёзиш керак ва тўхташ керак бўлади (жавоби 100 бўлади):
   

6-расм. ТМ да Р (99)ни 1 га ошириш программасининг бажарилиши.

Бу амаллар ТМ учун программа кўринишида қуйидаги кўринишда ёзилади:

-расм. ТМ да Р (1957, 649, 99)ни 1 га ошириш программасининг бажарилиши.