Приклади створення програм для МТ
Міністерство освіти І науки України
національний університет “Львівська політехніка”
Кафедра ЕОМ
Програмування машин Тьюрінга
Методичні вказівки
До лабораторної роботи № 1
з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2012
Методичні вказівки до комплексу лабораторних робіт з дисципліни "Алгоритми та методи обчислень" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2012 – 22 с.
Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
МЕТА РОБОТИ
Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Теорія алгоритмів - одне з основних понять математики та інформатики. Навіть походження
самого терміна «алгоритм» пов'язане з математикою. Відомо, що основна особливість всіх обчислювальних машин полягає в тому, що в основі їх роботи лежить програмний принцип управління. Це означає, що для вирішення як найпростішого, так і найскладнішого завдання користувачеві необхідно використовувати перелік інструкцій або команд, дотримуючись яких крок за кроком комп'ютер видасть необхідний результат. Таким чином, для того, щоб вирішувати завдання на комп'ютері, його необхідно спочатку алгоритмізувати. Саме алгоритмічний принцип і лежить в основі роботи всіх комп'ютерів.
|
|
|
Поняття алгоритму
В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, Розв'язок деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними.
Поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт готування блюда також є алгоритмом, у такому випадку виконавцем є людина. Однак найчастіше як виконавець виступає комп'ютер.
Єдиного «істинного» визначення поняття «алгоритм» немає.
|
|
|
«Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до Розв'язок поставленого завдання.» (А. Колмогоров)
«Алгоритм - це точне розпорядження, яке визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.» (А. Марков)
«Алгоритм - строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцеві команд.» (М. Угринович)
«Алгоритм - це послідовність дій, спрямованих на одержання певного результату за кінцеве число кроків.» (ROXANstudio)
«Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli])
«Алгоритм - однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для Розв'язок нестандартних завдань.»
Машина Тьюрінга
|
|
|
Формальні визначення алгоритму з'явились в тридцятих-сорокових роках 20 століття. Одним із перших було визначення англійського математика Алана Тьюрінга, який у 1936 році описав схему деякої абстрактної машини і запропонував називати алгоритмами те, що вміє робити така машина. При цьому визначенні, якщо щось не може бути зроблено машиною Тьюрінга, це вже не алгоритм. Інакше кажучи, Тьюрінг формалізував правила виконання дій за допомогою опису роботи деякої конструкції. Машина Тьюрінга (МТ) – математичне поняття, введене для формального уточнення інтуїтивного поняття алгоритму.
Метою створення абстрактної уявлюваної машини було отримання можливості доказу існування або неіснування алгоритмів розв'язання різних задач. Керуючись цією метою, Тьюрінг шукав як умога більш просту, «бідну» алгоритмічну схему, аби тільки вона була універсальною.
Машина Тьюрінга - це строга математична побудова, математичний апарат (подібний, наприклад, апарату диференціальних рівнянь), створений для розв'язання певних задач. Цей математичний апарат був названий «машиною» з тієї причини, що по опису його складових частин і функціонуванню він схожий на обчислювальну машину. Принципова відмінність машини Тьюрінга від обчислювальної машини полягає в тому, що її запам'ятовувальний пристрій являє собою нескінченну стрічку, а у реальних обчислювальних машин запам'ятовувальний пристрій може бути як завгодно великим, але обов'язково кінцевим. Машину Тьюрінга не можна реалізувати саме через нескінченність її стрічки. У цьому сенсі вона могутніша будь-якої обчислювальної машини.
|
|
|
Машина Тьюрінга являє собою найпростішу обчислювальну машину з лінійною пам'яттю, яка за допомогою послідовності елементарних дій перетворює вхідні дані. Елементарність дій полягає в тім, що дія міняє лише невеликий об'єм даних у пам'яті (у випадку машини Тьюрінга - лише одну комірку), і кількість можливих дій кінцева. Незважаючи на простоту машини Тьюрінга на ній можна обчислити все, що можна обчислити на будь-якій іншій машині, яка здійснює обчислення за допомогою послідовності елементарних дій. Ця властивість називається повнотою. Машина Тьюрінга може виконувати всі можливі перетворення слів, реалізуючи тим самим всі можливі алгоритми.
Один зі способів доказу того, що алгоритми обчислення, який можна реалізувати на одній машині, можна реалізувати й на інший, - це імітація першої машини на другій. Імітація полягає в наступному. На вхід другої машини подається опис програми (правил роботи) першої машини D і вхідн дані X, які повинні були надійти на вхід першої машини. Потрібно описати таку програму (правила роботи другої машини), яка б у результаті обчислень на виході видавала б те саме, що й повернула б перша машина, якби одержала на вхід дані X. На машині Тьюрінга можна імітувати всіх інших виконавців, які певним чином реализують процес покрокового обчислення, у якому кожний крок обчислення досить елементарний. На машині Тьюрінга можна імітувати машину Поста, нормальні алгоритми Маркова і будь-яку програму для звичайних комп'ютерів, що перетвориє вхідні дані у вихідні по деякому алгоритму. У свою чергу, на різних абстрактних виконавцях можна імітувати Машину Тьюрінга. Виконавці, для яких це можливо, називаються повними по Тьюрінгу.
Багатство можливостей машини Тьюрінга проявляється в тому, що якщо якісь алгоритми А і В реалізуються машинами Тьюрінга, то можна побудувати машини Тьюрінга, що будуть реалізовувати різні композиції алгоритмів А і В. Наприклад, «Виконати А, потім виконати В» або «Виконати А. Якщо в результаті вийшло слово «так», то виконати В. У противному випадку не виконувати В» або «Виконувати по черзі А, В, поки В не дасть відповідь 0». Очевидно, що такі композиції також є алгоритмами, тому їхня реалізація за допомогою машини Тьюрінга підтверджує, що конструкція Тьюрінга є універсальним виконавцем.
Всякий алгоритм може бути реалізований відповідною машиною Тьюрінга. Всі алгоритми, придумані людством протягом сторіч можуть бути реалізовані машиною Тьюрінга. Кожний алгоритм призначений для якогось конкретного виконавця, у кожного виконавця є своя система команд, є своє коло задач. Тьюрінгом же був побудований універсальний виконавець, що може вирішити будь-яку відому задачу. Цей фундаментальний результат був отриманий у той час, коли універсальних обчислювальних машин ще не існувало. Більше того, сам факт побудови уявлюваного універсального виконавця дозволив висловити припущення про доцільність побудови універсальної обчислювальної машини, яка б могла вирішувати будь-які задачі за умови відповідного кодування вхідних даних і розробки відповідної програми дій виконавця.
Структура машини Тьюрінга
Машина Тьюрінга (МТ) складається із двох частин - стрічки та каретки:
| стрічка: |
|
| ||||||||||||||
| каретка: |
Стрічка використовується для зберігання інформації, що складається з символів зовнішнього алфавіту А. Вона нескінченна в обидва боки і розбита на комірки, які ніяк не нумеруються і не іменуються. В кожній комірці може бути записаний один символ або нічого не записано. Вміст комірки може мінятись - в неї можна записати інший символ або стерти символ, який там знаходиться.
Домовимось порожній вміст комірки називати символом «порожньо» і позначати як 
. У зв'язку із цим зображення стрічки, показане на малюнку справа, буде таким самим, як і на малюнку зліва. Для обох цих зображень зовнішній алфавіт визначається як А={a0 , a , b}. Така домовленість зручна тим, що операцію стирання символу в деякій комірці можна розглядати як запис у цю комірку символу , тому замість довгої фрази «записати символ у комірку або стерти символ, що там знаходиться» можна говорити просто «записати символ у комірку».
Каретка - це активна частина МТ. В кожний момент вона розміщується під однією з комірок стрічки і розпізнає її вміст; вміст сусідніх та інших комірок каретка не бачить. Крім того, в кожний момент каретка перебуває в одному із станів, які будемо позначати буквою q з номерами: q0, q1, q2 і т.д., які складають алфавіт внутрішніх станів Q = {q0, q1 , ... , qm},. Перебуваючи в деякому стані, каретка виконує якусь певну операцію (наприклад, переміщується вправо по стрічці, заміняючи всі символи b на a), перебуваючи в іншому стані - іншу операцію.
Такт роботи машини Тьюрінга
МТ працює тактами, які виконуються один за одним. На кожному такті МТ виконує три наступні дії, причому обов'язково в зазначеному порядку:
1) записує деякий символ 
в комірку (зокрема, може бути записаний той самий символ, що й був у ній, тоді вміст цієї комірки не міняється);
2) переміщується на одну комірку вліво (позначається як L, від Left), або на одну комірку вправо (позначається як R, від Right), або залишається нерухливим (не позначається ніяк).
3) переходить в деякий стан qi (зокрема, може залишитись в попередньому стані).
Формально дії одного такту будемо записувати у вигляді:
,
або 
,
або 
.
Наприклад, такт 
означає запис символа 
у комірку, переміщення на одну комірку вліво і перехід у стан 
.
Програма для машини Тьюрінга
Сама по собі МТ нічого не робить. Для того щоб змусити її працювати, треба написати для неї програму. Ця програма записується у вигляді таблиці, в якій рядки відповідають станам, а стовпці відповідають символам. Які саме символи і стани вказувати в таблиці визначає автор програми. В комірках таблиці вказуються ті такти, які повинна виконати каретка, коли вона перебуває у відповідному стані і розпізнає на стрічці відповідний символ. Наприклад, команда 
R в таблиці буде записана наступним чином:
| Q A |
| 
| ... | 
|
|  R
| |||
| ||||
| ... | ||||
|
У цілому таблиця визначає дії МТ при всіх можливих конфигурациях і тим самим повністю задає поведінку МТ. Описати алгоритм у вигляді МТ - значить пред'явити таку таблицю.
На практиці частіше використовують скорочену таблицю. Скорочення полягають в наступному:
а) якщо стан машини після виконання команди не змінюється, то він другий раз вже не записується;
б) якщо команда записує в комірку ту саму букву, що й була записана там, то ця буква другий раз вже не записується.
Якщо заздалегідь відомо, що в процесі виконання програми не може з'явитись деяка конфігурація, тоді, щоб підкреслити це явно, в відповідній комірці таблиці малюється хрестик.
Наприклад:
| Табличне представлення | Скорочена таблиця | ||||||||||||||||||||||||
|
|
Правила виконання програми
До виконання програми потрібно проробити наступні попередні дії.
По-перше, треба записати на стрічку вхідне слово, до якого буде застосована програма. Вхідне слово - це кінцева послідовність символів, записаних у сусідніх комірках стрічки; усередині вхідного слова не повинно бути порожніх комірок, а зліва і справа від нього повинні бути тільки порожні комірки (зазначені в таблиці першим стовпцем). Порожнє вхідне слово означає, що всі комірки стрічки порожні.
По-друге, треба встановити каретку в початковий стан (зазначений в таблиці першим рядком) і розмістити його під першим символом вхідного слова:
| a | b | b |
Якщо вхідне слово порожнє, то каретка може вказувати на будь-яку комірку, тому що всі вони порожні.
Після цих попередніх дій починається виконання програми. У таблиці відшукується комірка на перетині першого рядка (тому що каретка перебуває в початковому стані ) і того стовпця, що відповідає першому символу вхідного слова, і виконується такт, записаний у цій комірці. В результаті каретка опиниться в новій конфігурації. Тепер такі ж дії повторюються, але вже для нової конфігурації: у таблиці відшукується комірка, що відповідає стану і символу цієї конфігурації, і виконується такт із цієї комірки. І так далі.
Коли завершується виконання програми? Будемо позначати стан зупинки через 
. Такт, що містить стан зупинки називається тактом зупинки. Потрапивши в нього, машина припиняє роботу.
Під k-тою конфігурацією будемо розуміти зображення стрічки машини з інформацією, що склалася на ній на початку k-того такту з зазначенням того, яка саме комірка розпізнається в цей такт і в якому стані перебуває машина. Позначати будемо наступним чином: 
. Така конфігурація відповідає такому стану машини:
|
Нехай задана послідовність конфігурацій К0 => К1 => К2 => ... =>Кp , де К0 - початкова конфігурація, Кp - кінцева конфігурація. Така послідовність конфігурацій називається протоколом. Будемо говорити, що вхідне слово 
переробляється машиною в вихідне слово 
, якщо від слова , що знаходиться в початковому положенні, машина після виконання кінцевого числа команд приходить до слова , що знаходиться в кінцевому положенні, тобто в положені зупинки.
В цілому можливі два результати роботи МТ над вхідним словом:
1) Перший результат - «гарний»: це коли в якийсь момент МТ зупиняється (попадає на такт зупинки). В такому випадку говорять, що МТ може бути застосована до заданого вхідного слова. А то слово, що на цей момент отримано на стрічці, вважається вихідним словом, тобто результатом роботи МТ, відповіддю.
В момент останова повинні бути виконані наступні обов'язкові умови:
- всередині вихідного слова не повинно бути порожніх комірок (хоча в процесі виконання програми всередині слова порожні комірки можуть бути, але в кінці їх вже не повинно залишитися);
- каретка зобов'язана зупинитись під одним із символів вихідного слова (під яким саме - не має значення), а якщо слово порожнє - під будь-якою коміркою стрічки.
2) Другий результат - «поганий»: це коли МТ зациклюється, ніколи не потрапляючи на такт зупинки (наприклад, каретка на кожному кроці переміщується вправо і не може зупинитись, тому що стрічка нескінченна). В цьому випадку говорять, що МТ не може бути застосована до заданого вхідного слова.
Відзначимо, що один і той самий алгоритм (програма МТ) може бути застосований до одних вхідних слів (тобто зупинятися) і бути непридатним до інших (тобто зациклюватись). Таким чином, застосовність або незастосовність залежить не тільки від самого алгоритму, але і від вхідного слова.
На яких вхідних словах алгоритм повинен зупинятися? На, так званих, гарних словах, тобто на таких, які відносятся до допустимих вхідних даних задачі, для яких задача є змістовною. Але на стрічці можуть бути записані будь-які вхідні слова, у тому числі й ті, для яких задача не має змісту; на таких словах поводження алгоритму не фіксується, він може зупинитись (при будь-якому результаті), а може і зациклитися.
Приклади створення програм для МТ
Розглянемо приклади створення програм для МТ, щоб продемонструвати деякі типові прийоми програмування на МТ.
Для скорочення формулювання умов задач введемо наступні позначення:
- буквою Р будемо позначати вхідне слово;
- буквою А будемо позначати зовнішній алфавіт, тобто набір тих символів, тільки з яких може складатись Р, однак, в проміжних і вихідних словах можуть з'являтись також і інші символи;
- будемо вважати, що в початковому положені каретка вказує на перший зліва символ слова, що переробляється.
Приклад 1 (переміщення каретки, заміна символів)
Постановка задачі:
Нехай задано А={0,1,2,3,4,5,6,7,8,9} і непусте слово Р. Отже, Р - це послідовність із десяткових цифр, тобто запис невід'ємного цілого числа в десятковій системі числення. Потрібно одержати на стрічці запис числа, яке буде на 1 більше числа Р.
Словесний опис алгоритму:
Для розв'язання цієї задачі потрібно виконати наступні дії:
1. Пересунути каретку під останню цифру числа.
2. Якщо це цифра від 0 до 8, то замінити її на 1 більшою цифрою і зупинитися, наприклад:
3. Якщо ж це цифра 9, тоді замінити її на 0 і перемістити каретку до попередньої цифри, після чого таким же способом збільшити на 1 цю передостанню цифру, наприклад:
4. Особливий випадок: число Р складається тільки з дев'яток (наприклад, 99). Тоді каретка буде пересуватись вліво, замінюючи дев'ятки на нулі, і зрештою опиниться під порожньою коміркою. В цю порожню комірку треба записати 1 і зупинитись (відповіддю буде 100):
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| q1 | 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
| q2 | 
|
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
Пояснення:
q1 - це стан, у якому каретка «біжить» під останню цифру числа. Для цього він весь час рухається вправо, не міняючи цифри і залишаючись в тому ж стані. Але тут є одна особливість: коли каретка опинеться під останньою цифрою, то вона не може знати про це (оскільки вона не бачить, що записано в сусідніх комірках) і може визначити це лише тоді, коли потрапить на наступну порожню комірку. Тому, дійшовши до першої порожньої комірки, каретка має повернутись назад під останню цифру числа і перейти в стан q2 (вправо рухатись вже не треба).
q2 - це стан, у якому каретка додає 1 до тієї цифри, яку вона бачить в цей момент. Спочатку це остання цифра числа. Якщо це цифра з діапазону від 0 до 8, то каретка має замінити її на 1 більшою цифрою, і зупинитись. Але, якщо це цифра 9, то каретка має замінити її на 0 і переміститись вліво, залишаючись в стані q2. Тим самим, він буде додавати 1 до попередньої цифри. Якщо і ця цифра дорівнює 9, то каретка замінить її на 0 і переміститься вліво, залишаючись в стані q2, тому що повинна далі виконувати такі самі дії - збільшувати на 1 видиму цифру. Якщо ж каретка перемістилась вліво, а у видимій комірці немає цифри (а є символ «порожньо»), ті вона має записати в цю комірку 1 і зупинитись.
Відзначимо, що для порожнього вхідного слова задача не визначена, тому на цьому слові МТ може поводитись як завгодно. У цій програмі, наприклад, при порожньому вхідному слові МТ зупиняється і видає відповідь 1.
Вище наведено запис програми в повному, нескороченому виді. Приведемо запис програми в скороченому, більш наочному виді. При цьому справа будемо давати коротке пояснення дій, які реалізуються у відповідних станах каретки:
| Q A |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Пояснення |
| q1 | 
| R | R | R | R | R | R | R | R | R | R | під останню цифру |
| q2 |
|
|
|
|
|
|
|
|
|
| 
| видима цифра + 1 |
Саме так і будемо надалі записувати програми.
Приклад 2 (аналіз символів)
Постановка задачі:
А={a,b,c}. Перенести перший символ непустого слова Р у його кінець. Наприклад:
Словесний опис алгоритму:
Для розв'язання цієї задачі потрібно виконати наступні дії:
1. Запам'ятати перший символ слова P, а потім стерти цей символ.
2. Перемістити каретку вправо під першу порожню комірку за P і записати в неї символ, який був запам'ятований.
Як «бігати» вправо, було розглянуто в попередньому прикладі. Питання, як запам'ятати перший символ, є складнішим. Адже в МТ немає іншого запам'ятовувального пристрою, крім стрічки, а запам'ятовувати символ у якійсь комірці на стрічці безглуздо, оскільки, як тільки каретка зрушиться вліво або вправо від цієї комірки, вона відразу забуде даний символ. Вихід з цієї ситуації може бути такий: треба використовувати різні стани каретки. Якщо перший символ - це символ a, то треба перейти в стан 
, у якому каретка переміщюється вправо і записує в кінці слова символ a. Якщо ж першим був символ b, тоді треба перейти в стан , де робиться все те ж саме, тільки в кінці записується символ b. Якщо ж першим був символ c, тоді треба перейти в стан 
, у якому каретка має дописати за вхідним словом символ c. Отже, те, яким був перший символ, фіксується переведенням каретки в різні стани.
Це типовий прийом запам'ятовування при програмуванні на МТ.
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | Пояснення |
| q1 | R | 
| 
| 
| аналіз 1-го символу, видалення його, розгалуження |
| q2 | R | R | R | 
| запис a справа |
| q3 | R | R | R | 
| запис b справа |
| q4 | R | R | R | 
| запис c справа |
Розглянемо поводження цієї програми на вхідних словах, що містять не більше одного символу. При порожньому вхідному слові, яке є «поганим» для цієї задачі, програма зациклиться - каретка, перебуваючи в стані q1 і потрапляючи весь час на порожні комірки, буде нескінченно переміщатись вправо. Звичайно, в цьому випадку програму можна було б зупинити, але в цьому прикладі спеціально зроблено зациклення, щоб продемонструвати таку можливість.
Якщо ж у вхідному слові тільки один символ, тоді каретка зітре цей символ, переміститься на одну комірку вправо і запише в неї цей символ:
Таким чином, слово з одного символу просто переміститься на одну комірку вправо. Це припустимо. Адже комірки стрічки не нумеруються, тому місце розташування слова на стрічці ніяк не фіксується і переміщення слова вліво або вправо помітити не можна. У зв'язку із цим не обов'язково, щоб вихідне слово перебувало в тому самому місці, де було розташоване вхідне слово, результат може опинитись зліва або справа від цього місця.
Приклад 3 (порівняння символів, стирання слова)
Постановка задачі:
А={a,b,c}. Якщо перший і останній символи непорожнього слова Р однакові, то це слово не міняти, інакше замінити його на порожнє слово.
Словесний опис алгоритму:
Для розв'язання цієї задачі потрібно виконати наступні дії:
1. Запам'ятати перший символ вхідного слова, не стираючи його.
2. Перемістити каретку під останній символ і порівняти його із символом, який запам'ятали.
Якщо вони рівні, то більше нічого не робити.
3. У противному випадку знищити все вхідне слово.
Як запам'ятати символ і як перемістити каретку під останній символ слова, вже відомо з попередніх прикладів. Стирання ж вхідного слова реалізується заміною всіх його символів на символ . При цьому, раз вже каретка опиниться наприкінці слова, будемо переміщувати каретку справа наліво до першої порожньої комірки.
Ці дії описуються наступною програмою для МТ (нагадаємо, що хрестик в комірці таблиці означає неможливість появи відповідної конфігурації при виконанні програми):
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | Пояснення |
| q1 |
|
|
| 
| аналіз 1-го символу, розгалуження |
| q2 | 
| R | R | R | йти до останнього символу при 1-му символі a |
| q3 |
| 
|
| порівняти останній символ з a, якщо не рівні - на q8 | |
| q4 | 
| R | R | R | аналогічно при 1-му символі b |
| q5 |
|
|
| ||
| q6 | 
| R | R | R | аналогічно при 1-му символі c |
| q7 |
|
|
| ||
| q8 |
| 
|
|
| стерти все слово, рухаючись справа наліво |
Приклад 4 (видалення символу зі слова)
Постановка задачі:
А={a,b}. Видалити зі слова Р його другий символ, якщо такий є.
Словесний опис алгоритму:
Для розв'язання цієї задачі потрібно перемістити каретку під комірку із другим символом і потім очистити цю комірку:
Однак, усередині вихідного слова не повинно бути порожніх комірок. Тому після видалення другого символу треба «стиснути» слово, пересунувши перший символ на одну комірку вправо. Для цього каретка повинна повернутись до першого символу, запам'ятати його і стерти, а потім, знову перемістившись вправо, записати його в комірку, де був другий символ. Однак початкове переміщення вправо до іншому символу, щоб його стерти, і наступне повернення до першого символу є зайвими діями: яка різниця - переносити перший символ у порожню комірку, чи в комірку з якимось символом? Тому можна відразу запам'ятати перший символ, стерти його і записати замість другого символу:
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | Пояснення |
| q1 |
| 
|
| аналіз і видалення 1-го символу, розгалуження |
| q2 |
|
|
| заміна 2-го символу на a |
| q3 |
|
|
| заміна 2-го символу на b |
Приклад 5 (стиснення слова)
Постановка задачі:
А={a,b,c}. Видалити зі слова Р перше входження символу a, якщо таке є.
Словесний опис алгоритму:
У попередньому прикладі було перенесено на одну позицію вправо тільки один симвіл. У цьому прикладі потрібно в циклі переносити вправо всі початкові символи b і c вхідного слова, до першого символу a або до порожньої комірки:
Постає питання, як перенести символ x з лівої комірки в чергову комірку, де перебуває деякий символ y, щоб потім цей символ y можна було перенести в праву комірку? Якщо через 
позначити стан, у якому в комірку треба записати символ x, який перебував раніше в комірці зліва, тоді цю дію можна зобразити так:
Для цього потрібно виконати такт 
, у якому об'єднані наступні три дії:
- по-перше, в комірку записується символ x, взятий із комірки зліва;
- по-друге, каретка переміщується вправо (під комірку, в яку потім треба буде записати тільки що замінений символ y);
- по-третє, каретка переходить в стан 
, у якому вона і буде виконувати цей запис.
Повторення таких тактів у циклі і приведе до переміщення вправо на одну позицію початкових символів вхідного слова. Цей цикл повинен закінчитись, коли в черговій комірці виявиться символ a або (y=a або y= ), а на початку циклу можна вважати, що на місце першого символу зліва переноситься символ «порожньо» (x= ).
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | Пояснення |
| q1 |
| 
|
|
|  : стерти 1-й символ і перенести його вправо
|
| q2 |
|
| RR | 
|  : запис b, перенос символу, що був в цій комірці раніше, вправо
|
| q3 |
|
| 
| R |  : запис с, перенос символу, що був в цій комірці раніше, вправо
|
В цій програмі варто звернути увагу на такт , що виконується коли першим символом вхідного слова є a. Треба просто стерти цей символ і зупинитися. Однак у цьому такті зазначене ще й переміщення, оскільки, в момент останова каретка повинна перебувати під вихідним словом (під будь-яким його символом), тому і потрібно перемістити каретку з порожньої комірки на комірку з першим символом вихідного слова.
Приклад 6 (вставка символу в слово)
Постановка задачі:
А={a,b,c}. Якщо Р – непорожнє слово, то за його першим символом вставити символ a.
Словесний опис алгоритму:
Між першим і другим символами слова Р треба звільнити комірку для нового символу a. Для цього треба перенести на одну позицію вліво перший символ (на старому місці його можна поки не видаляти), а потім, повернувшись на старе місце, записати символ a:
Перенос символу на одну позицію вліво аналогічний переносу символу вправо, про що говорилось у двох попередніх прикладах, тому приведемо програму для МТ без додаткових коментарів. Відзначимо лише, що в станах , та каретка може бачити тільки порожню комірку, а в стані 
він обов'язково бачить перший символ вхідного слова, але не порожню комірку.
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | Пояснення |
| q1 |
|
|
| 
| аналіз 1-го символу для переносу його вліво |
| q2 | 
| записати a зліва | |||
| q3 | 
| записати b зліва | |||
| q4 | 
| записати c зліва | |||
| q5 |
|
|
| замінити колишній 1-й символ на a |
Приклад 7 (розсунення слова)
Постановка задачі:
А={a,b,c}. Вставити в слово P символ a за першим входженням символу c, якщо таке є.
Словесний опис алгоритму:
Переглядаємо вхідне слово зліва направо до порожньої комірки або до першого символу c. В першому випадку символ c не входить в слово P, тому нічого не робимо. В іншому випадку треба звільнити місце для символу а, що вставляється. Для цього переміщаємо початок слова P (від знайденого символу c до першого символу) на одну позицію вліво. Крім того, щоб потім не вертатись до позиції, що звільнилась, починаємо це переміщення з запису символу a замість знайденого символу c. Циклічне переміщення вліво реалізується аналогічно циклічному переміщенню вправо із приклада 5.
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | Пояснення |
| q1 | 
| RR | RR | 
| вправо до с, вставка a замість c, переміщення c вліво |
| q2 |
| L | 
|
| переміщення a |
| q3 |
| 
| L | 
| переміщення b |
| q4 |
| 
| 
| L | переміщення c |
Приклад 8 (формування слова на новому місці)
Постановка задачі:
А={a,b,c}. Видалити з P всі входження символу a.
Словесний опис алгоритму:
Попередні приклади показують, що в МТ досить складно реализувати вставки символів в слова та видалення символів зі слів. Тому іноді простіше не розсовувати або стискати вхідне слово, а формувати вихідне слово в іншому, вільному, місці стрічки. Саме так і будемо робити при рішенні цієї задачі.
Потрібно виконати наступні дії:
1. Вихідне слово будемо будувати справа від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, наприклад знаком = (крок 1). Нагадаємо, що на стрічці можуть бути записані не тільки символи з алфавіту вхідного слова, а й, за потребою, інші символи.
2. Після цього повертаємось до початку вхідного слова (крок 2).
3. Далі потрібно перенести в циклі всі символи вхідного слова, крім символу a, вправо за знак = , тобто будемо формувати вихідне слово.
Для цього аналізуємо перший символ вхідного слова. Якщо це символ a, тоді стираємо його і переходимо до наступного символу (крок 3). Якщо ж перший символ - це b або c, тоді стираємо його і «біжимо» вправо до першої порожньої комірки (крок 4), куди й записуємо цей символ (крок 5).
Далі знову повертаємось до того символу, що став першим у вхідному слові, і повторюємо ті ж самі дії, але вже стосовно цього символу (кроки 6-9).
4. Цей цикл завершиться тоді, коли при поверненні до початкового символу виявиться в якості першого символу знак =. Це ознака того, що повністю переглянуто вхідне слово і перенесені всі його символи, відмінні від a, у вихідне слово. Залишилось стерти знак =, переміститись вправо під вихідне слово і зупинитись (крок 10).
Алгоритм у вигляді програми для МТ:
Нагадаємо, що крім символів a, b і c у процесі розв'язання задачі на стрічці з'явився новий знак =, тому в таблиці повинен бути передбачений стовпець для цього знаку.
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | c | = | Пояснення |
| q1 | 
| R | R | R | записати справа знак = | |
| q2 | 
| L | L | L | L | переміститись наліво до 1-го символу слова |
| q3 | 
| 
| 
|
| аналіз і видалення його, розгалуження | |
| q4 | 
| R | R | R | R | запис b справа, повернення наліво |
| q5 | 
| R | R | R | R | запис c справа, повернення наліво |
Приклад 9 (фіксування місця на стрічці)
Постановка задачі:
А={a,b}. Подвоїти слово P, поставивши між ним і його копією знак =.
Наприклад:
Словесний опис алгоритму:
Ця задача вирішується аналогічно попередньої: в кінець вхідного слова записуємо знак = (крок 1), потім повертаємось до початку слова (крок 2) і у циклі всі його символи (у тому числі і символ a) копіюємо в порожні комірки справа:
Однак є й відмінність: символи вхідного слова, які копіюються, не видаляються. Це призводить до наступної проблеми. Записавши справа копію чергового символу, потрібно повернутись до вхідного слова в позицію цього символу і потім переміститись вправо до наступного символу, щоб скопіювати вже його. Але як довідатись, у яку позицію вхідного слова треба повернутись? Наприклад, звідки мі знати, що після копіювання першого символу a треба повернутись саме до першого символу вхідного слова, а не до другого або третього? В попередній задачі завжди потрібно було повертатись до першого з тих символів, що залишились у вхідному слові, а тепер зберігаються всі символи, тому незрозуміло, які символи вже скопійовані, а які ще ні. Відзначимо також, що в МТ комірки стрічки ніяк не нумеруються, немає в МТ і лічильників, які дозволили б визначити, скільки символів вже скопійовано.
В загальному проблему можна сформулювати так: як зафіксувати на стрічці деяку позицію, у якій ми вже були і до якої пізніше повинні повернутись? Зазвичай ця проблема вирішується так. Коли ми опиняємось в цій позиції в перший раз, то заміняємо символ, що в ній знаходиться, на його двійника - на новий допоміжний символ, причому різні символи заміняємо на різні двійники, наприклад a на A і b на B. Після цього виконуються якісь дії в інших місцях стрічки. Щоб потім повернутись до потрібної позиції, треба просто відшукати на стрічці ту комірку, де перебуває символ A або B. Потім в цій комірці можна відновити колишній символ, якщо більше не треба фіксувати цю позицію (саме для відновлення колишнього символу і треба було заміняти різні символи на різні двійники).
Скористаємось цим прийомом, виконавши наступні дії:
1. Записуємо знак = за вхідним словом (крок 1 вище).
2. Повертаємось під перший символ вхідного слова (крок 2 вище).
3. Заміняємо символ a на двійника A (крок 3 нижче), «біжимо» вправо до першої вільної комір-ки і записуємо в неї символ a (крок 4). Після цього повертаємось до комірки із двійником A (крок 5), відновлюємо колишній символ a і переміщаємось вправо до наступного символу (крок 6)
Тепер аналогічним способом копіюємо другий символ (заміняємо його на A, в кінець дописуємо a і т.д.) і всі наступні символи вхідного слова.
4. Коли буде скопійовано останній символ вхідного слова і повернуто до його двійника (після кроку 12), то потім після переміщення на одну позицію вправо потрапимо на знак = (крок 13). Це сигнал про те, що вхідне слово повністю скопійовано, тому роботу МТ треба завершувати.
Алгоритм у вигляді програми для МТ:
У вигляді програми для МТ наведені вище дії описуються такою таблицею:
| Q A | a0 | a | b | = | A | B | Пояснення |
| q1 | =L
| R | R | поставити справа від слова знак = | |||
| q2 |
| L | L | переміститись наліво під 1-й символ | |||
| q3 | 
| 
|
| аналіз і заміна чергового символу | |||
| q4 | 
| R | R | R | запис a справа | ||
| q5 | 
| R | R | R | запис b справа | ||
| q6 | L | L | L | 
| 
| повернення, відновлення, до наступного символу |
Відзначимо, що в цій програмі можна позбутись стану , якщо об'єднати його зі станом , передбачивши в повернення вліво як до порожньої комірки, так і до символів A та B:
| Q A | a0 | a | b | = | A | B | Пояснення |
| . . . | |||||||
| q2 |
| L | L | L |
|
| переміститись наліво до , A або B
|
| . . . |
Емулятор машини Тьюрінга
Емулятор машини Тьюрінга - це навчальна модель універсального виконавця (абстрактної обчислювальної машини).
В пакет включені наступні файли:
turing.exe - основна програма - емулятор машини Тьюрінга
EXAMPLES - підкаталог із прикладами програм для емулятора
Середовище емулятора має такий вигляд:
Машина Тьюрінга - це автомат, який керується таблицею. Зовні таблиця МТ дещо відрізняється від наведених вище таблиць. Рядки в таблиці відповідають символам обраного алфавіту A, а стовпці — станам Q. У кожній комірці таблиці, що відповідає деякому символу ai і деякому стану qj, перебуває запис, що складається із трьох частин:
1. символ з алфавіту A;
2. напрямок переміщення: > (вправо), < (наліво) або . (на місці);
3. новий стан каретки.
На початку роботи машина Тьюрінга перебуває в стані q1. Стан q0 — це кінцевий стан: потрапивши в нього, автомат закінчує роботу.
У верхній частині програми знаходиться поле редактора, у яке можна ввести умову задачі у вільній формі.
Стрічка переміщається вліво і вправо за допомогою кнопок, розташованих зліва і справа від неї. Подвійним кліком по комірці стрічки (або кліком правою клавішою миші) можна змінити вміст комірки стрічки.
За допомогою меню Лента можна запам'ятати стан стрічки у внутрішньому буфері і відновити стрічку з буфера.
В полі Алфавит задаються символи обраного алфавіту. Пробіл додається до введених символів автоматично.
В таблиці в нижній частині вікна набирається програма. В першому стовпці записані символи алфавіту, він заповнюється автоматично. В першому рядку перераховуються всі можливі стани. Додати або видалити стовпці таблиці (стани) можна за допомогою кнопок, розташованих над таблицею.
При введенні команди в комірку таблиці спочатку потрібно ввести новий символ, потім напрямок переходу та номер стану. Якщо символ пропущений, за замовчуванням він не змінюється. Якщо пропущено номер стану, за замовчуванням стан не змінюється.
Праворуч у поле Комментарий можна вводити в довільній формі коментарі до розв'язання. Найчастіше там пояснюють, що означає кожний стан машини Тьюрінга.
Програма може виконуватись безупинно (F9) або по кроках (F8). Команда, яка має виконуватись, підсвічується зеленим кольором. Швидкість виконання регулюється за допомогою меню Скорость.
Задачі для машини Тьюрінга можна зберігати у файлах. Зберігається умова задачі, алфавіт, програма, коментарі і початковий стан стрічки. При завантаженні задачі з файлу і збереженні в файл стан стрічки автоматично записується в буфер.
Дата добавления: 2018-05-13; просмотров: 2337; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!