>
Теза Черча виявився достатнім, щоб надати необхідну точність формулювань алгоритмічних проблем і в ряді випадків зробити можливим доказ їх нерозв'язності. Причина полягає в тому, що зазвичай у алгоритмічних проблемах математики мова йде не про алгоритми, а про вичіслімості деяких спеціальним чином побудованих функцій. У силу тези Черча питання про вичіслімості функції рівносильний питання про її рекурсивності. Поняття рекурсивної функції суворе. Тому звичайна математична техніка дозволяє іноді безпосередньо довести, що вирішальна завдання функція не може бути рекурсивної. Саме цим шляхом самому Черч вдалося довести нерозв'язність основний алгоритмічної проблеми логіки предикатів - проблеми тотожною істинності формул обчислення першого ступеня.
Точний опис класу частково рекурсивних функцій разом з тезою Черча дає одне з можливих рішень задачі про уточнення поняття алгоритму. Однак це рішення не цілком пряме, так як поняття обчислюваної функції є вторинним по відношенню до поняттю алгоритму. Питається, чи не можна уточнити безпосередньо саме поняття алгоритму і вже потім за його допомогою визначити точно і клас вичіслімих функцій? Такий напрям пошуку призвело до побудови іншого, ніж рекурсивні функції, класу моделей алгоритму. Основна його ідея полягає в тому, що алгоритмічні процеси - це процеси, які може здійснювати певним чином влаштована машина, що моделює тим самим виконання окремих операцій людиною. Функціонування такої машини і є виконання деякого алгоритму. p> Виходячи з властивостей алгоритму, можна сформулювати загальні вимоги до таких машин:
1. характер їх функціонування повинен бути дискретним, тобто складатися з окремих кроків (команд), кожен з яких виконується тільки після завершення попереднього;
2. дії повинні бути детерміновані, тобто кроки виконуються в строгому порядку, а їх результат визначається самим кроком і результатами попередніх кроків;
3. перед початком роботи машині надаються вихідні дані з області визначення алгоритму;
4. за кінцеве число кроків роботи машини повинен бути отриманий результат або інформація про те, що вважати результатом;
5. машина повинна бути універсальною, тобто такий, щоб з її допомогою можна було б виконати будь-який алгоритм. p> Чим простіша структура (Пристрій) описаної машини і чим елементарніше її кроки, тим більше підстав вважати, що її робота і є виконання алгоритму. Щоб відповісти на питання, які кроки роботи машини слід віднести до елементарних, повернемося до того обставині, що нас цікавить перетворення інформації, представленої з допомогою деякого кінцевого алфавіту. Вимога кінцівки алфавіту є очевидним наслідком тієї обставини, що рішення має бути отримано за кінцеве число кроків. Якщо інформація не представлена ​​в дискретної формі, наприклад дійсне число, то його обробка в загальному випадку може містити нескінченне число кроків, наприклад перебування цифр числа ПЂ або витяг квадратного кореня з числа 2. Таким чином, алгоритм виявляється кінцевої послідовністю дій, вироблених над даними, представленими з допомогою кінцевого алфавіту. З урахуванням сказаного стає зрозумілим визначення алгоритму, яке дає В.М. Глушков: В«Алгоритм - це будь-яка кінцева система правил перетворення інформації (даних) над будь-яким кінцевим алфавітом В».
Нехай вихідні дані з області визначення алгоритму представлені за допомогою алфавіту A і утворюють при цьому кінцеву послідовність знаків {a 1 ... a n } - така послідовність називається словом. В результаті виконання алгоритму сформується нове слово {b 1 ... b m }, представлене, в загальному випадку, в іншому алфавіті B. На перший погляд для проведення такого перетворення в якості елементарних виділяються наступні операції (кроки):
1. заміна одного знака вихідного слова a i знаком b j з алфавіту B;
2. видалення знака вихідного слова;
3. додавання до вихідного слову знака з алфавіту B. p> Однак якщо в алфавіти включений знак, що має сенс порожнього знака, додавання якого до слова ліворуч або праворуч не змінює цього слова, по аналогією додавання ліворуч числового нуля до числа, то легко бачити, що: операція (2) є ні що інше, як заміна a i порожнім знаком, а операція (3) є заміна порожнього знака знаком b j . Таким чином, всі можливі алфавітні перетворення зводяться до операції (1) - заміні одного знака іншим. Саме з цієї причини функціонування абстрактної машини зводиться до того, що вона зчитує і розпізнає символи, записані в пам'яті, в якості якої виступає нескінченна стрічка, і, залежно від свого стану, і того, який оглядає символ, вона замінює його іншим символом. Після цього вона переходить в новий стан, читає наступний символ і т.д. до команди про припинення роботи. Оскільки подібні машини є чисто модельним, теоретичним побудовою, вони отримали назву абстрактних м...
