Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу
жүктеу/скачать 0.88 Mb.
|
| Мысал 1. Тьюринг машинасы көмегімен унарлы санға 1-ді қосу керек.
Сыртқы алфавит A={ ,1} жиынымен берілуі мүмкін, мұндағы 1 толтырылған ұяшыққа, ал - бос таңбаға сәйкес келеді, толтырылғандар бірінің артынан бірі орналасады. Ішкі алфавит Q={q,z} жиынымен беріледі, мұндағы q логическалық құрылғының жұмыс күйіне, ал z – тоқтатуға сәйкес келеді. Барлық түрлендірулер ережесінің жиынтығы (логикалық функция) төмендегі функционалдық схема түрінде көрсетілуі мүмкін:
Баған және жолдарын білдіретін таңбалар логикалық құрылғының ішкі параметрлерін анықтайтындай, ал олардың қиылысуындағы ұяшықта сыртқы команда тұратын функционалдық схема кесте түрінде құрылады. Дербес жағдайда, егер машинаның бастиегі лентаның 1 таңбасы бар ұяшықты бақыласа және машина (q) жұмыс күйінде болса, онда оның берілген тактідегі жұмыс нәтижесі берілген ұяшықта бірді қайталау және бір ұяшыққа оңға өту болып табылады– бұл команда былай жазыладыq1R. Егер бақыланатын ұяшықта болса, ал логикалық құрылғының (ЛҚ) күйі q болса, онда 1-ге ауыстырылады, лентаның ығысуы болмайды және машина тоқтайды - z1S. Алғашқы конфигурация 1q1111 түрінде болсын. Сонда сипатталған логикалық функция бойынша машинаның жұмыс төмендегідей болады: Такт 1. 1 бақыланады, ЛҚ-ныңкүйіq. Сыртқы команда q1R, ол лентаға қатысты бастиекті 1 қадамға оңға орын ауыстыруға эквивалентті. Сонымен, 11q111 аралық конфигурациясы пайда болады. Такт 2.Дәл сол сияқты 111q11 конфигурациясына өту жүзеге асады. Такт 3. 1111q1конфигурациясына өту. Такт 4. 11111q конфигурациясына өту. Такт 5. бақыланады, ЛҚ-ныңкүйіq. Сыртқы команда z1S – орнына ұяшыққа 1 жазылады, ығысу жоқ, жұмыс тоқтатылады. Соңғы 111111z. Мысал2.nкөпразрядты санының ондық санау жүйесінде жазылуы берілген. n+1 мәнін есептеуді орындайтын Тьюрингмашинасын құрыңдар. А={0,1,…,9,0, }сыртқы алфавитін қолданамыз, ондағы символыбос таңбаға сәйкес келеді. Ішкі алфавиталдыңғы мысалдағы сияқтыекі күйде – жұмысшы (q) және тоқтату (z) (Q={q, z}) болады. Берілген n саны, сондай-ақ нәтиже – n+1 – ондық жүйеде жазылады, цифрлар бірден көрші ұяшықтарға бос орынсыз орналасады. Функционалдық схеманы кесте түрінде көрсетейік:
Алғашқыконфигурация 21q9 түрінде болсын. Такт 1.q9 q0L, яғни 9 0-ге ауысадыжәне бастиек ондық разрядқа ығысады – аралық конфигурация 2q10. Такт 2.q1 z2S, яғни 1 2-ге ауысадыжәне соңғы конфигурациясы 2z20 болатын тоқтату болады, яғни 219+1 қосынды нәтижесі алынады. Алғашқы конфигурация 99q9 түрінде болсын.. Такт 1.q9 q0L, яғни 9q90 аралық конфигурациясы құрылады. Такт 2.q9 q0L, q900конфигурациясы құрылады. Такт 3.q9 q0L, q 000 құрылады. Такт 4.q z1S – z1000 құрыладыжәне жұмыс тоқтайды. жүктеу/скачать 0.88 Mb. Достарыңызбен бөлісу:
|