Лентаның ұяшықтарының барлық қалыптарының жиынтығы, ЛҚ-ның қалпы және головканың қалпы машинаның конфигурациясы деп аталады.
Конфигурацияны келесі түрде жазуға болды: a1qiaj…ak , бұл k символдан тұратын сөзде j нөмірлі секция шолынуда, және бұл кезде басқарушы құрылғы qi қалыпта тұр дегенді білдіреді. Машина конфигурациясы сыртқы алфавиттің символдарының кез-келген санынан тұратыны және тек бір ғана ішкі алфавит символынан тұратыны түсінікті. Көбінесе конфигурацияны 1 qi 2 түрде жазады, мұндағы 1 – лентадағы головканың сол жағында тұрған сөз, 2 – лентадағы головканың оң жағындағы тұрған сөз, шолынулы таңбаны қоса есептегенде. 1 –дің сол жағында және 2 –нің оң жағында лента бос. 7.1 суретте бейнеленген конфигурацияны келесі түрде жазуға болады: a1 a2 qa3a 4ak, ал 7.2 суреттегі – 1q1111.
Жұмысты бастамас бұрын бос лентаға А алфавитінде жазылған, шекті бастапқы сөзі жазылады; головка сөзінің бірінші символының үстіне орнатылады, ЛҚ q1 қалпына келтіріледі (яғни, бастапқы конфигурация q1 түрде болады). Әрбір конфигурацияда тек қана бір түрлендіру ережесі жүзеге асатындықтан, бастапқы конфигурация машинаның барлық келесі жұмысын, яғни, жұмысты тоқтатқанға дейінгі барлық конфигурациялар тізбегін бірмәнді анықтайды.
Бастапқы конфигурацияға байланысты оқиғаның өрбуінің екі нұсқасы бар:
Тактілердің шекті санынан кейін тоқтау командасы бойынша машина тоқтайды; бұл кезде лентада шығатын ақпаратқа сәйкес соңғы конфигурация қалады;
Тоқтау болмайды. .
Бірінші жағдайда, осы машинаның бастапқы ақпаратқа қолданылатыны туралы айтылады, ал екінші жағдайда – жоқ. Машина нәтиже алуды қамтамасыз ететін барлық кіру конфигурацияларының жиынтығы шешілетін есептер класын құрады. Әрине, Тьюринг машинасын шешілетін классқа кірмейтін есептерге қолдану мәнсіз болады. Екінші жағынан, көптеген жағдайларда шешілетін есептер класын басқа Тьюринг машиналарын құру арқылы кеңейтуге борлады. Сұрақ туындайды: кез-келген есепті шешетін әмбебап машина құруға (тым болмаса теориялық деңгейде) бола ма? Бұл жерде алгоритмдік шешілу мәселесіне келдік, оны кешірек қарастырамыз.
Мысал 7.8
Алдыңғы тақырыпта қарастырылған унарлық санға 1-ді қосу есебін Тьюринг машинасымен шешуді қарастырайық. Сырқы алфавит A={ ,1} жиынымен беріледі, мұндағы 1 толтырылған секцияға, ал - бос белгіге сәйкес келеді, толтырылғандар бірінен кейін бірі қатар тұрады. Ішкі алфавит Q={q,z} жиынымен беріледі, мұндағы q ЛҚ-ның жұмыс қалпына, ал z – тоқстауға сәйкес келеді. Барлық түрлендіру ережесінің жиынтығы (логикалық функция) функционалдық схемамен көрсетіледі:
Осылайша кесте түрінде функционалдық схема құрылады, яғни колонкалар мен жолдарды белгілеген таңбалар ЛҚ-ның кіру параметрлерін бейнелейді, ал кестенің ұяшықтарында олардың қиылысуында шығатын ақпарат тұр. Жекелей алғанда, егер лента головкасы 1 таңбасы тұрған секцияны шолуда болса және машина (q) жұмыс қалпында тұрса, онда оның осы тактідегі жұмыс нәтижесі осы секцияда 1-ді қайталап, бір секция оңға R жылжу болуы керек (бұл кезде алдында айтылғандай лента солға жылжиды) – бұл команда q1R деп жазылады. Егер шолынулы секцияда тұрса, ал ЛҚ-ның қалпы q болса, онда таңбасы 1-ге ауыстырылады, лентаның жылжуы болмайды және машина тоқтайды - z1S. Кірісте z комбинациясы, сол сияқты 1z комбинациясы кезінде машина жұмыс емес қалпында болады – ешқандай өзгеріс, жылжу болмайды – сондықтан мұндай комбинациялар бұдан былай функционалды схемаларда бейнеленбейді.
Айталық, бастапқы конфигурация 1q1111 болсын. Онда машина жұмысы сипатталған логикалық функцияға сәйкес келесі түрде жүргізілдеі:
Такт 1 1 шолынуда, ЛҚ-да в q қалпы. Шығу командасы q1R, бұл головканың лентаға қатысты 1 қадам оңға жалжуына эквивалентті. Сәйкесінше, 11q111 аралық конфигурациясы құрылады.
Такт 2 – аналогиялық түрде 111q11 конфигурациясы жасалынады.
Такт 3 – 1111q1 конфигурациясына өту. .
Такт 4 – 11111q конфигурациясына өту (мұнда жақсы түсіну үшін оң жақтағы анық түрде көрсетілген).
Такт 5 шолынуда, ЛҚ-ның қалпы q. Шығу командасы z1S – орнына ұяшыққа 1 жазылады, жылжу жоқ, жұмыс тоқтатылды. сдвига нет, работа прекращается. Конечная конфигурация 111111z.
Есеп шешілді.
Мысал 7.9
Көпразрядты бүтін сан n–нің ондық санау жүйесіндегі жазылуы бар; n+1 мәнін есептеуді қамтамасыз ететін Тьюринг машинасын құру керек.
Достарыңызбен бөлісу: |
