Файл: M51_21_-_kopia.pdf

21 

Рис. 2.4. Запис чисел 3 і 5 на стрічці машини Поста. 

Система  запису  чисел,  що  використовується  в  машині  Посту  є 

непозиційною.  

Складемо  програму  для  додавання  до  довільного  числа  одиниці. 

Припустимо, що на стрічці записано тільки одне число і каретка знаходиться 
над однією з клітин, в якій знаходиться мітка, що належить цьому числу:  

Рис. 2.5. Збільшення числа на одиницю. 

Для  рішення  задачі  можна  перемістити  каретку  вліво  (або  вправо)  до 

першої порожньої клітинки, а потім нанести мітку див. рис. 2.5-2.7.  

Програма, що додає до числа мітку справа, має вигляд:  
 

Рис. 2.6. Текст програми, що додає мітку справа. 

 
Програма, що додає  до числа мітку зліва, має вигляд:  

Рис. 2.7. Текст програми, що додає мітку зліва. 

22 

Різниця тільки в напрямку руху каретки в першій команді. 
Машину Посту можна розглядати як спрощену модель ЕОМ. Справді, як 

ЕОМ, так і машина Посту мають: 

• 

неподільні  носії  інформації  (клітини  –  біти),  які  можуть  бути 
заповненими або незаповненими; 

• 

обмежений набір елементарних дій – команд, кожна з яких виконується 
за один такт (крок). 

Обидві  машини  працюють  на  основі  програми.  Проте  в  машині  Посту 

інформація  розташовується  лінійно  і  читається  поспіль,  а  в  ЕОМ  можна 
читати  інформацію  за  адресою;  набір  команд  ЕОМ  значно  ширше  і 
виразніше, ніж команди машини Посту, і т.д. 

Приклад.  
Віднімання натуральних чисел  P — Q. 
Будемо  представляти  натуральне  (ціле  невід’ємне)  число  P  набором  з 

P+1 одиниць і розділять числа нулем. Початкове положення каретки помічено 
символом «v» 
            v 
    00111110111000 
        P           Q 

Додавання двох чисел є тривіальним — достатньо поставити 1 між ними 

і стерти два останніх правих символи у Q.  

Програма  віднімання  складається  з  послідовного  затирання  крайніх 

лівих міток у Q і правих у P: 
 
1. 0           – 

витираємо лівий символ у Q 

2. → 
3. ? 4, 5 
4. Stop      – 

стоп, якщо затерли Q=0 

5. ← 
6. ? 5, 7     – 

цикл пошуку P 

7. 0           – 

витираємо правий символ у P 

8. → 
9. ? 8, 1     – 

шукаємо Q 

23 

Відмітимо,  що  номер  команди  переходу  не  вказується,  якщо  перехід 

відбувається на наступний по порядку рядок (для наочності тексту). В 6-ому 
рядку можливе за циклювання, якщо Q > P (можна добавити перевірку) 

Обґрунтування  цієї  гіпотези  відбувається  сьогодні  не  шляхом  строго 

мате-автоматичного доведення, а на шляху експерименту. Дійсно, всякий раз, 
коли вказується алгоритм, його можна перевести в форму програми машини 
Посту, яка призводить до того ж результату. 

 
 
2.5  

Питання для самоконтролю  

1)  

Поняття загальної та конкретної проблеми по Посту. 

2)  

Простір символів і примітивні операції в машині Поста.  

3)  

Поняття фінітного 1-процесу в машині Поста. 

4)  

Способи завдання проблем і формулювання 1.  

5)  

Гіпотеза Поста. 

24 

3. 

МАШИНА ТЬЮРІНГА ТА ПРОБЛЕМИ, ЯКІ НЕ 

РОЗВ’ЯЗУЮТЬСЯ АЛГОРИТМІЧНО 

 
3.1. Машина Тьюринга 

 
Алан Тьюринг (Turing) в 1936 році опублікував у працях Лондонського 

математичного  товариства  статтю,  яка  нарівні  з  роботами  Посту  і  Черча, 
лежить в основі сучасної теорії алгоритмів. 

Модель  обчислень,  в  якій  кожен  алгоритм  розбивався  на  послідовність 

простих, елементарних кроків і була логічною конструкцією, названої згодом 
машиною «Тьюринга». 

Машина  Тьюринга  –  це  математична  побудова,  математичний  апарат 

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

машиною"  з  тієї  причини,  що  за  описом  його  складових  частин  і 

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

У кожній машині Тьюринга є дві частини: 

1) 

необмежена в обидві сторони стрічка, розділена на клітинки;  

2) 

автомат (каретка для зчитування / запису, керована програмою).  

З кожною

машиною

Тьюринга

пов'язані два

кінцевих

алфавіту:

- 

алфавіт вхідних символів A = {a0, a1, ..., am}   

- 

алфавіт станів Q = {q0, q1, ..., qp}. 

(З різними машинами Тьюринга можуть бути пов'язані різні алфавіти A і 

Q.)  

Стан q0 називається пасивним. Вважається, що якщо машина потрапила 

в цей стан, то вона закінчила свою роботу.  

Стан  q1  називається  початковим.  Перебуваючи  в  цьому  стані,  машина 

починає свою роботу. 

25 

Вхідне  слово  розміщується  на  стрічці  по  одній  літери  в  розташованих 

підряд  клітинках.  Ліворуч  і  праворуч  від  вхідного  слова  знаходяться  тільки 
порожні  клітинки  (в  алфавіт  А  завжди  входить  порожня  буква  а0  –  ознака 
того, що клітинка порожня). 

Автомат  може  рухатися  вздовж  стрічки  вліво  або  вправо,  читати  вміст 

комірок і записувати в клітинку літери. Автомат кожного разу "бачить" тільки 
одну клітинку.  

Залежно від того, яку літеру  він бачить, а також залежно від свого стану 

qj 

автомат може виконувати наступні дії: 

• 

записати нову букву в клітинку, що оглядається; 

• 

виконати  зрушення  по  стрічці  на  одну  клітинку  вправо  /  вліво  або 
залишитися нерухомим; 

• 

перейти в новий стан.  

Тобто  у  машини  Тьюринга  є  три  види  операцій.  Щоразу  для  чергової 

пари  (qj,  ai)  машина  Тьюринга  виконує  команду,  що  складається  з  трьох 
операцій з певними параметрами. 

Програми для машин Тьюринга записуються у вигляді таблиці, де перші 

стовпець і рядок містять літери зовнішнього алфавіту та можливі внутрішні 
стани автомата (внутрішній алфавіт). Вміст таблиці являє собою команди для 
машини  Тьюринга.  Літера,  яку  зчитує  каретка  в  клітинці  (над  якою  вона 
знаходиться  в  даний  момент),  і  внутрішній  стан  каретки  визначають,  яку 
команду  потрібно  виконати.  Команда  визначається  перетином  символів 
зовнішнього і внутрішнього алфавітів в таблиці. 

Щоб  задати  конкретну  машину  Тьюринга,  потрібно  описати  для  неї 

наступні складові: 

• 

Зовнішній  алфавіт.  Кінцева  безліч  (наприклад,  А),  елементи  якої 

називаються  літерами    (символами).  Одна  з  літер  цього  алфавіту 
(

наприклад, а0) повинна являти собою порожній символ. 

• 

Внутрішній  алфавіт.  Кінцева  безліч  станів  каретки  (автомата). 

Один  зі  станів  (наприклад,  q1)  повинний  бути  початковим  (що  запускає 

програму).  Ще  один  зі  станів  (q0)  повинний  бути  кінцевим  (завершальним 

програму) – стан зупинки. 

• 

Таблиця переходів. Опис поведінки автомата (голівки) в залежності 

від стану і символу, що зчитується.