Нижче наведено приклади на доповнення статті Машина Тюрінга.

Перший приклад Тюрінга Наведена нижче таблиця є першим прикладом Тюрінга (Turing 1937): «1. Можна побудувати машину для обчислення послідовності 0 1 0 1 0 1…» (0 <пробіл> 1 <пробіл> 0…)

Конфігурація Поведінка m-конфігурація(стан) Символ на стрічці Операції зі стрічкою Кінцева m-конфігурація(стан) b пробіл P0, R c c пробіл R e e пробіл P1, R f f пробіл R b

Щодо того, що насправді робить машина, Тюрінг (1936) стверджує таке: «Цю [прикладну] таблицю (і всі наступні таблиці такого виду) слід розуміти так: для конфігурації, описаної в перших двох стовпцях, операції з третього стовпця виконуються послідовно, після чого машина переходить у m-конфігурацію з останнього стовпця.»

Він робить це абсолютно зрозумілим, коли зводить наведену вище таблицю до єдиної інструкції під назвою «b», але його інструкція складається з 3 рядків. Інструкція «b» має три різні можливості щодо символу {None, 0, 1}. За кожною можливістю слідує послідовність дій, аж доки ми не дійдемо до крайнього правого стовпця, де кінцевою m-конфігурацією є «b»:

Поточна m-конфігурація (інструкція) Символ на стрічці Операції зі стрічкою Кінцева m-конфігурація (інструкція) b P0 b b 0 R, R, P1 b b 1 R, R, P0 b

Як зазначили низка коментаторів, зокрема сам Тюрінг (1937) (наприклад, Пост (1936), Пост (1947), Кліні (1952), Ван (1954)), інструкції Тюрінга не є атомарними — подальші спрощення моделі можливі без зменшення її обчислювальної потужності; докладніше — у статті Машина Поста–Тюрінга.

Як зазначено у статті Машина Тюрінга, Тюрінг запропонував додатково атомізувати свою таблицю, дозволивши лише один друк/стирання з наступним одним рухом стрічки Л/П/Н. Він наводить нам цей приклад перетвореної першої маленької таблиці:

Поточна m-конфігурація (стан Тюрінга) Символ на стрічці Операція друку Рух стрічки Кінцева m-конфігурація (стан Тюрінга) q1 пробіл P0 R q2 q2 пробіл P пробіл, тобто E R q3 q3 пробіл P1 R q4 q4 пробіл P пробіл, тобто E R q1

Твердження Тюрінга все одно передбачає п'ять атомарних операцій. За заданою інструкцією (m-конфігурацією) машина: зчитує символ стрічки під головкою на основі зчитаного символу переходить до відповідної послідовності інструкцій друкує символ Sj, стирає або нічого не робить рухає стрічку ліворуч, праворуч або не рухає взагалі переходить до кінцевої m-конфігурації для цього символу

Оскільки дії машини Тюрінга не є атомарними, симуляція машини повинна розкласти кожен 5-кортеж на послідовність простіших дій. Одна з можливостей — яка використовується в наступних прикладах «поведінки» машини — є такою: (qi) Перевіряє символ стрічки під головкою: якщо символ S0 — перейти до qi.01, якщо символ S1 — перейти до qi.11, якщо символ S2 — перейти до qi.21 тощо.

(qi.01) надрукувати символ Sj0, стерти або нічого не робити, потім перейти до qi.02 (qi.02) рухати стрічку ліворуч, праворуч або не рухати, потім перейти до qm0

(qi.11) надрукувати символ Sj1, стерти або нічого не робити, потім перейти до qi.12 (qi.12) рухати стрічку ліворуч, праворуч або не рухати, потім перейти до qm1

(qi.21) надрукувати символ Sj2, стерти або нічого не робити, потім перейти до qi.22 (qi.22) рухати стрічку ліворуч, праворуч або не рухати, потім перейти до qm2

(і так далі — усі символи мають бути враховані)

Так звані «канонічні» скінченні автомати виконують перевірку символів «паралельно»; докладніше — у статті .

У наступному прикладі роботи машини зазначимо деякі особливості моделей Тюрінга:

Тобто під час друку він пропускає кожну другу клітинку. Клітинки з друком називаються F-клітинками; порожні клітинки між ними можуть використовуватися як «мітки» і називаються «E-клітинками» — як у «призначених для стирання». F-клітинки, у свою чергу, є його «клітинками цифр» і містять лише символи 1 або 0 — символи, які він назвав «цифрами» (як у «двійкові числа»).

У цьому прикладі стрічка спочатку «порожня», і «цифри» потім на неї друкуються. Для стислості тут показано лише стани таблиці:

Крок Ідентифікатор інструкції         Головка                           . . . . . . . . . . . . . . . . . . 1 1 . . . . . . . . . . . . . . . . . . 2 2 . . . . . 0 . . . . . . . . . . . . 3 3 . . . . . . 0 . . . . . . . . . . . 4 4 . . . . . 1 . 0 . . . . . . . . . . 5 1 . . . . . . 1 . 0 . . . . . . . . . 6 2 . . . . . 0 . 1 . 0 . . . . . . . . 7 3 . . . . . . 0 . 1 . 0 . . . . . . . 8 4 . . . . . 1 . 0 . 1 . 0 . . . . . . 9 1 . . . . . . 1 . 0 . 1 . 0 . . . . . 10 2 . . . . . 0 . 1 . 0 . 1 . 0 . . . . 11 3 . . . . . . 0 . 1 . 0 . 1 . 0 . . . 12 4 . . . . . 1 . 0 . 1 . 0 . 1 . 0 . . 13 1 . . . . . . 1 . 0 . 1 . 0 . 1 . 0 . 14 2 . . . . . 0 . 1 . 0 . 1 . 0 . 1 . 0

Той самий «запуск» з усіма проміжними діями друку та рухами показано тут:

Уважний погляд на таблицю виявляє певні проблеми у власному прикладі Тюрінга — не всі символи враховані.

Наприклад, припустимо, що його стрічка спочатку була не порожньою. Що б трапилось? Машина Тюрінга зчитала б інші значення, ніж ті, що передбачалися.

Підпрограма копіювання

Це дуже важлива підпрограма, що використовується в підпрограмі «множення».

Приклад машини Тюрінга обробляє рядок з 0 і 1, де 0 представляється символом пробілу. Її завдання — подвоїти будь-яку послідовність одиниць на стрічці, записавши між ними 0. Наприклад, коли головка зчитує «111», вона запише 0, а потім «111». На виході буде «1110111».

Для виконання свого завдання ця машина Тюрінга потребує лише 5 станів роботи, які називаються {s1, s2, s3, s4, s5}. Кожен стан виконує 4 дії:

Зчитати символ під головкою Записати вихідний символ, визначений станом Рухати стрічку ліворуч або праворуч відповідно до стану Перейти до наступного стану відповідно до поточного стану

Початкова m-конфігурація (поточна інструкція) Символ на стрічці Операція друку Рух стрічки Кінцева m-конфігурація (наступна інструкція) s1 0 N N H s1 1 E R s2 s2 0 E R s3 s2 1 P1 R s2 s3 0 P1 L s4 s3 1 P1 R s3 s4 0 E L s5 s4 1 P1 L s4 s5 0 P1 R s1 s5 1 P1 L s5 H

Операція друку: Pдрукує символ S або Eстирає, або Nічого не робить

«Запуск» машини проходить через 16 машинних конфігурацій (станів Тюрінга): Крок Ідентифікатор інструкції Головка 1 s1 0 0 0 0 1 1 0 0 0 0 0 2 s2 0 0 0 0 0 1 0 0 0 0 0 3 s2 0 0 0 0 0 0 1 0 0 0 0 4 s3 0 0 0 0 0 0 0 1 0 0 0 5 s4 0 0 0 0 1 0 1 0 0 0 0 6 s5 0 0 0 1 0 1 0 0 0 0 0 7 s5 0 0 1 0 1 0 0 0 0 0 0 8 s1 0 0 0 1 0 1 1 0 0 0 0 9 s2 0 0 0 0 1 0 0 1 0 0 0 10 s3 0 0 0 0 0 1 0 0 1 0 0 11 s3 0 0 0 0 0 0 1 0 0 1 0 12 s4 0 0 0 0 1 1 0 0 1 0 0 13 s4 0 0 0 1 1 0 0 1 0 0 0 14 s5 0 0 1 1 0 0 1 0 0 0 0 15 s1 0 0 0 1 1 0 1 1 0 0 0 16 H 0 0 0 1 1 0 1 1 0 0 0

Поведінку цієї машини можна описати як цикл: вона починає в s1, замінює першу 1 на 0, потім використовує s2 для руху праворуч, пропускаючи одиниці та перший зустрінутий 0. s3 потім пропускає наступну послідовність одиниць (спочатку їх немає) і замінює перший знайдений 0 на 1. s4 рухається назад ліворуч, пропускаючи одиниці, доки не знайде 0, і переходить до s5. s5 потім рухається ліворуч, пропускаючи одиниці, доки не знайде 0, який спочатку записав s1.

Він замінює той 0 на 1, рухається на одну позицію праворуч і знову входить у s1 для наступного кола циклу.

Це продовжується, доки s1 не знайде 0 (це 0 посередині двох рядків одиниць), після чого машина зупиняється.

Альтернативний опис

Інший опис розглядає задачу як відстеження кількості одиниць «1». Ми не можемо використати окремий стан для кожного можливого числа (стан для кожного з 0, 1, 2, 3, 4, 5, 6 тощо), бо тоді нам знадобилася б нескінченна кількість станів для представлення всіх натуральних чисел, а скінченний автомат є скінченним — доведеться якось відстежувати це за допомогою стрічки.

Базовий принцип роботи полягає в копіюванні кожної «1» на інший бік, рухаючись туди й назад — машина є достатньо «розумною», щоб пам'ятати, на якій частині шляху вона знаходиться. Детальніше: вона переносить кожну «1» на інший бік, розпізнаючи розділяючий «0» посередині та розпізнаючи «0» з іншого боку, щоб знати, що досягла кінця. Вона повертається тим самим методом, виявляючи середній «0», а потім «0» з вихідного боку. Цей «0» з вихідного боку є ключем до головоломки того, як вона відстежує кількість одиниць.

Хитрість полягає в тому, що перед перенесенням «1» вона позначає цю цифру як «взяту», замінюючи її на «0». Повертаючись, вона заповнює цей «0» назад «1», а потім переходить до наступної, позначаючи її «0» і повторюючи цикл, переносячи ту «1» на інший бік і так далі. З кожним переходом туди й назад мітка «0» рухається на один крок ближче до центру. Ось як вона відстежує кількість перенесених одиниць.

Повертаючись, мітка «0» виглядає для неї як кінець колекції одиниць — будь-які «1», що вже були перенесені, для неї невидимі (вони по інший бік від мітки «0»), і тому складається враження, що вона працює з (N-1) кількістю одиниць — подібно до доведення методом математичної індукції.

Повний «запуск» із результатами проміжних «рухів»:

3-становий Зайнятий бобер

Наведену нижче таблицю інструкцій машини Тюрінга взято з Петерсона: «тристановий зайнятий бобер записує 6 одиниць перед зупинкою». Петерсон рухає головку; у наступній моделі рухається стрічка. 0 — це символ пробілу: стрічка починається з усіма клітинками, що містять 0.

Символ на стрічці Поточний стан A Поточний стан B Поточний стан C Записати символ Рух стрічки Наступний стан Записати символ Рух стрічки Наступний стан Записати символ Рух стрічки Наступний стан 0 1 L B 1 R A 1 R B 1 1 R C 1 L B 1 N ЗУПИНКА

Схема «станів» тристанового зайнятого бобра показує внутрішні послідовності подій, необхідні для фактичного виконання «стану». Як зазначено вище, Тюрінг (1937) цілком ясно дає зрозуміти, що це є правильним тлумаченням 5-кортежів, які описують інструкцію. Докладніше про атомізацію 5-кортежів Тюрінга — у статті Машина Поста–Тюрінга:

Наступна таблиця показує «стиснений» запуск — лише стани Тюрінга:

Крок Ідентифікатор інструкції Головка 1 b 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 B 0 0 0 0 0 0 0 1 0 0 0 0 0 0 3 A 0 0 0 0 0 1 1 0 0 0 0 0 0 0 4 C 0 0 0 0 1 1 0 0 0 0 0 0 0 0 5 B 0 0 0 1 1 1 0 0 0 0 0 0 0 0 6 A 0 0 1 1 1 1 0 0 0 0 0 0 0 0 7 B 0 0 0 1 1 1 1 1 0 0 0 0 0 0 8 B 0 0 0 0 1 1 1 1 1 0 0 0 0 0 9 B 0 0 0 0 0 1 1 1 1 1 0 0 0 0 10 B 0 0 0 0 0 0 1 1 1 1 1 0 0 0 11 B 0 0 0 0 0 0 0 1 1 1 1 1 0 0 12 A 0 0 0 0 0 1 1 1 1 1 1 0 0 0 13 C 0 0 0 0 1 1 1 1 1 1 0 0 0 0 14 З 0 0 0 0 1 1 1 1 1 1 0 0 0 0

Повний «запуск» тристанового зайнятого бобра. Отримані стани Тюрінга (те, що Тюрінг називав «m-конфігураціями» — «машинними конфігураціями») показані виділеними сірим кольором у стовпці A, а також під інструкціями машини (стовпці AF-AU)):

Джерела

Бібліографія