ФОРМАЛІЗАЦІЯ ПОНЯТТЯ В«АЛГОРИТМВ»
1.1. ПОСТАНОВКА ПРОБЛЕМИ
Поняття алгоритму, введене в попередньому параграфі, можна назвати поняттям алгоритму в інтуїтивному сенсі. Воно має нечіткий, неформальний характер, посилається на деякі точно не визначені, але інтуїтивно зрозумілі речі. Наприклад, при визначенні та обговоренні властивостей алгоритму ми виходили з можливостей деякого виконавця алгоритму. Його наявність передбачалося, але нічого певного про нього не було відомо. Говорячи мовою математики, ні аксіоматичного, ні вичерпного конструктивного визначення виконавця ми так і не дали.
Встановлені в попередньому параграфі властивості алгоритмів слід називати емпіричними. Вони виявлені на основі узагальнення властивостей алгоритмів різної природи і мають прикладний характер. Цих властивостей достатньо для практичного програмування, для створення великого кола програм для комп'ютерів, верстатів з ЧПУ, промислових роботів і т.д. Однак, як фундаментальне наукове поняття алгоритм вимагає більш грунтовного вивчення. Воно неможливе без уточнення поняття В«алгоритмВ», більш суворого його опису або, як ще кажуть, без його формалізації.
Відомо кілька підходів до формалізації поняття В«АлгоритмВ»:
• теорія кінцевих і нескінченних автоматів;
• теорія вичіслімих (рекурсивних) функцій;
• О»-числення Черча.
Всі ці виникли історично незалежно один від одного підходи виявилися згодом еквівалентними. Головна мета формалізації поняття алгоритму така: підійти до вирішення проблеми алгоритмічної разрешимости різних математичних задач, тобто відповісти на питання, чи може бути побудований алгоритм, який призводить до вирішення завдання. Ми розглянемо постановку цієї проблеми і деякі результати теорії алгоритмічної можливості розв'язання задач, але спочатку обговоримо формалізацію поняття алгоритму в теорії автоматів на прикладі машин Поста, Тьюринга, а також нормальних алгоритмів Маркова, а потім - основи теорії рекурсивних функцій. Ідеї вЂ‹вЂ‹О»-числень Черча реалізовані в мові програмування LISP (глава 3).
Разом з тим, формально визначений будь-яким з відомих способів алгоритм не може в практичному програмуванні замінити те, що ми називали алгоритмами в попередньому параграфі. Основна причина полягає в тому, що формальне визначення різко звужує коло розглянутих задач, роблячи багато практично важливі задачі недоступними для розгляду.
1.2. МАШИНА ПОСТУ
Абстрактні (тобто існуючі не реально, а лише в уяві) машини Посту і Тьюрінга, призначені для доказів різних тверджень про властивості програм для них, були запропоновані незалежно один від одного (і практично одночасно) в 1936 р. американським математиком Емілем Постом і англійським математиком Алланом Тьюрінгом. Ці машини являють собою універсальних виконавців, які є повністю детермінованими, що дозволяють В«вводитиВ» початкові дані, і після виконання програм В«читатиВ» результат. Машина Поста менш популярна, хоча вона значно простіше машини Тьюринга. З її допомогою можна вести навчання перших навичок складання програм для ЕОМ.
Абстрактна машина Поста являє собою нескінченну стрічку, розділену на однакові клітини, кожна з яких може бути або порожній, або заповненою міткою В«VВ», і головки, яка може переміщатися уздовж стрічки на одну клітку вправо або вліво, наносити в клітку стрічки мітку, якщо цієї мітки там раніше не було, прати мітку, якщо вона була, або перевіряти наявність в клітці мітки. Інформація про заповнених мітками клітинах стрічки характеризує стан стрічки, яке може змінюватися в процесі роботи машини. У кожен момент часу головка (В«-В») знаходиться над однією з клітин стрічки і, як кажуть, оглядає її. Інформація про розташування голівки разом з станом стрічки характеризує стан машини Посту, ріс.1.16.
Ріс.1.16. Абстрактна машина Поста
Команда машини Посту має наступну структуру:
п Km,
де п - порядковий номер команди, K-дія, що виконується голівкою, т - номер наступної команди, що підлягає виконанню.
Існує всього шість команд машини Посту, ріс.1.17:
Рис.1.1. Команди машини Посту.
Ситуації, в яких головка повинна завдавати мітку там, де вона вже є, або, навпаки, прати мітку там, де її немає, є аварійними (неприпустимими).
Програмою для машини Посту будемо називати непорожній список команд, такий що 1) на п-му місці команда з номером n; 2) номер т кожної команди збігається з номером небудь команди списку.
З точки зору властивостей алгоритмів, що вивчаються за допомогою машини Посту, найбільший інтерес представляють причини зупинки машини при виконанні програми:
1) останов по команді В«стопВ»; такий останов називається результативним і вказує на коректність алгоритму (програми);
2) останов при виконанні неприпустимої команди; в цьому випадку останов називається безрезультативно;
3) машина не зупиняється ніколи; в цьому і в попередньому випадку ми маємо справу з некоректним алгоритмом (програмою).
Будемо розуміти під початковим стан головки проти порожній клітини лівіше самої лівої мітки на стрічці. Розглянемо реалізацію деяких типових елементів програм машини Посту.
1. Нехай задано початковий стан головки і потрібно на порожній стрічці написати дві мітки: одну в секцію під головкою, другу праворуч від неї. Це можна зробити по наступній програмі (праворуч від команди показаний результат її виконання):
Рис.1.2. Приклад елементу програми машини Посту.
2. Покажемо, як можна скористатися командою умовного переходу для організації циклічного процесу. Нехай на стрічці є запис з декількох міток поспіль і головка знаходиться над самою крайньою міткою праворуч. Потрібно перевести головку вліво до першої порожній позиції.
Програма буде мати наступний вигляд:
Команда умовного переходу є одним з основних засобів організації циклічних процесів, наприклад, для знаходження першого мітки праворуч (або ліворуч) від головки, розташованої над порожньою кліткою; знаходження зліва (або справа) від головки порожній клітини, якщо вона розташована над міткою і т.д.
3. Зупинимося на представленні чисел на стрічці машини Посту і виконанні операцій над ними.
Число k представляється на стрічці машини Посту йдуть підряд k + 1 мітками (одна мітка означає число В«ОВ»). Між двома числами робиться інтервал як мінімум з однієї порожній секції на стрічці. Наприклад, запис чисел 3 і 5 на стрічці машини Посту буде виглядати так:
Звернемо увагу, що використовувана в машині Посту система запису чисел є непозиційною.
Складемо програму для додавання до довільного числа одиниці. Припустимо, що на стрічці записано тільки одне число і головка знаходиться над однією з клітин, в якій знаходиться мітка, що належить цьому числу:
Для вирішення завдання можна перемістити голівку вліво (або вправо) до першої порожній клітини, а потім нанести мітку.
Програма, що додає до числа мітку зліва, має вигляд:
Програма, що додає до числа мітку праворуч, має вигляд:
(відмінність лише в напрямку руху голівки в першій команді. Перевірте працездатність цих програм на яких приватних прикладах).
Припустимо, що головка розташована на відстані декількох клітин зліва від числа, до якого потрібно додати одиницю. У цьому випадку програма ускладнюється. З'явиться В«блок пошуку числаВ» - дві команди, призводять головку в стан, розглянуте в попередньому прикладі:
Нижче - повні тексти програм, що додають одиницю зліва і праворуч, відповідно:
У першому випадку не потрібно переміщати головку до крайньої лівої мітці числа
4. Наведемо програму для складання...
