«Информатиканың теориялық негіздері» Қазақстан республикасы білім және ғылым министрлігі

Конфигурацияны келесі түрде жазуға болды: a₁q_ia_j…a_k , бұл k символдан тұратын сөзде j нөмірлі секция шолынуда, және бұл кезде басқарушы құрылғы q_i қалыпта тұр дегенді білдіреді. Машина конфигурациясы сыртқы алфавиттің символдарының кез-келген санынан тұратыны және тек бір ғана ішкі алфавит символынан тұратыны түсінікті. Көбінесе конфигурацияны ₁ q_i түрде жазады, мұндағы ₁ – лентадағы головканың сол жағында тұрған сөз, ₂ – лентадағы головканың оң жағындағы тұрған сөз, шолынулы таңбаны қоса есептегенде. ₁ –дің сол жағында және ₂ –нің оң жағында лента бос. 7.1 суретте бейнеленген конфигурацияны келесі түрде жазуға болады: a₁ a₂qa₃a ₄a_k, ал 7.2 суреттегі – 1q1111.

Жұмысты бастамас бұрын бос лентаға А алфавитінде жазылған, шекті бастапқы сөзі жазылады; головка сөзінің бірінші символының үстіне орнатылады, ЛҚ q₁ қалпына келтіріледі (яғни, бастапқы конфигурация q₁ түрде болады). Әрбір конфигурацияда тек қана бір түрлендіру ережесі жүзеге асатындықтан, бастапқы конфигурация машинаның барлық келесі жұмысын, яғни, жұмысты тоқтатқанға дейінгі барлық конфигурациялар тізбегін бірмәнді анықтайды.
Бастапқы конфигурацияға байланысты оқиғаның өрбуінің екі нұсқасы бар:

• Тактілердің шекті санынан кейін тоқтау командасы бойынша машина тоқтайды; бұл кезде лентада шығатын ақпаратқа сәйкес соңғы конфигурация қалады;

  
  

• Тоқтау болмайды. .

  
  

Бірінші жағдайда, осы машинаның бастапқы ақпаратқа қолданылатыны туралы айтылады, ал екінші жағдайда – жоқ. Машина нәтиже алуды қамтамасыз ететін барлық кіру конфигурацияларының жиынтығы шешілетін есептер класын құрады. Әрине, Тьюринг машинасын шешілетін классқа кірмейтін есептерге қолдану мәнсіз болады. Екінші жағынан, көптеген жағдайларда шешілетін есептер класын басқа Тьюринг машиналарын құру арқылы кеңейтуге борлады. Сұрақ туындайды: кез-келген есепті шешетін әмбебап машина құруға (тым болмаса теориялық деңгейде) бола ма? Бұл жерде алгоритмдік шешілу мәселесіне келдік, оны кешірек қарастырамыз.

Алдыңғы тақырыпта қарастырылған унарлық санға 1-ді қосу есебін Тьюринг машинасымен шешуді қарастырайық. Сырқы алфавит A={,1} жиынымен беріледі, мұндағы 1 толтырылған секцияға, ал - бос белгіге сәйкес келеді, толтырылғандар бірінен кейін бірі қатар тұрады. Ішкі алфавит Q={q,z} жиынымен беріледі, мұндағы q ЛҚ-ның жұмыс қалпына, ал z – тоқстауға сәйкес келеді. Барлық түрлендіру ережесінің жиынтығы (логикалық функция) функционалдық схемамен көрсетіледі:

Осылайша кесте түрінде функционалдық схема құрылады, яғни колонкалар мен жолдарды белгілеген таңбалар ЛҚ-ның кіру параметрлерін бейнелейді, ал кестенің ұяшықтарында олардың қиылысуында шығатын ақпарат тұр. Жекелей алғанда, егер лента головкасы 1 таңбасы тұрған секцияны шолуда болса және машина (q) жұмыс қалпында тұрса, онда оның осы тактідегі жұмыс нәтижесі осы секцияда 1-ді қайталап, бір секция оңға R жылжу болуы керек (бұл кезде алдында айтылғандай лента солға жылжиды) – бұл команда q1R деп жазылады. Егер шолынулы секцияда тұрса, ал ЛҚ-ның қалпы q болса, онда таңбасы 1-ге ауыстырылады, лентаның жылжуы болмайды және машина тоқтайды - z1S. Кірісте z комбинациясы, сол сияқты 1z комбинациясы кезінде машина жұмыс емес қалпында болады – ешқандай өзгеріс, жылжу болмайды – сондықтан мұндай комбинациялар бұдан былай функционалды схемаларда бейнеленбейді.