я конструювання машин Тьюринга. Покажемо це на прикладі.
Приклад 6.1. сконструюємо машини Тьюринга, правильно обчислюють функції-проектори (,, ...,)=(1? m? n).
Розглянемо спочатку конкретний випадок n=3, m=2, тобто функцію (,,) =. Ми повинні переробити слово 0 в слово 0. Будемо застосовувати до початкової конфігурації послідовно сконструйовані раніше машини Тьюринга, В,, О:
0
: 0;
У: 0;
: 0;
Про: 0;
: 0;
Про: 0;
: 0.
Таким чином, функція (,,)=обчислюється наступній композицією машин: У Про Про=В.
Тепер ми можемо уявити собі алгоритм побудови композиції машин, В,, О для обчислення будь-якої функції виду (,, ...,) =. За допомогою правого зсуву, застосувавши його m - 1 раз, потрібно спочатку досягти масиву:
: 0 ... 0 ... 0.
Потім, рухаючись вліво, транспонувати (за допомогою В) масив з кожним сусіднім зліва масивом, поки масив не вийде на перше місце:
: 0 ... 0 ... 0.
Тепер потрібно дійти до крайнього правого масиву з допомогою (n - 1) - кратного застосування правого зсуву:
: 0 ... 0 ... 0.
Нарешті, потрібно прати послідовно справа наліво все масиви одиниць, крім першого:
: 0 ... 0 ... 0.
Отже, цю функцію (правильно) обчислює наступна машина Тьюринга:
.
1.7 Теза Тьюринга (основна гіпотеза теорії алгоритмів)
Нагадаємо, одна з властивостей алгоритму полягає в тому, що він являє собою єдиний спосіб, що дозволяє для кожного завдання з якогось нескінченного безлічі завдань за кінцеве число кроків знайти її рішення.
На поняття алгоритму можна подивитися і з дещо іншої точки зору. Кожну задачу з нескінченного безлічі завдань можна виразити (закодувати) деяким словом деякого алфавіту, а рішення задачі - якимось іншим словом того ж алфавіту. У результаті одержимо функцію, задану на деякій підмножині множини всіх слів обраного алфавіту і приймаючу значення в множині всіх слів того ж алфавіту. Вирішити якусь завдання - значить знайти значення цієї функції на слові, що кодує дану задачу. А мати алгоритм для вирішення всіх задач даного класу - значить мати єдиний спосіб, що дозволяє в кінцеве число кроків «вираховувати» значення побудованої функції для будь-яких значень аргументу з її області визначення. Таким чином, алгоритмічна проблема - по суті, проблема про обчисленні значень функції, заданої в деякому алфавіті.
Залишається уточнити, що означає вміти обчислювати значення функції. Це означає обчислювати значення функції за допомогою підходящої машини Тьюринга. Для яких же функцій можливе їх тьюрінгово обчислення? Численні дослідження вчених, великий досвід показали, що такий клас функцій надзвичайно широкий. Кожна функція, для обчислення значень якій існує який-небудь алгоритм, виявлялася обчислюваною допомогою деякої машини Тьюринга. Це дало привід Тьюрингу висловити таку гіпотезу, званої основний гіпотезою теорії алгоритмів, або тезою Тьюринга:
Для знаходження значень функції, заданої в деякому алфавіті, тоді і тільки тоді існує який-небудь алгоритм, коли функція є обчислюваною по Тьюрингу, тобто коли вона може обчислюватися на підходящої машині Тьюринга.
Це означає, що строго математичне поняття обчислюваною (по Тьюрингу) функції є по суті ідеальною моделлю взятого з досвіду поняття алгоритму. Дана теза є не що інше, як аксіома, постулат, що висувається нами, про взаємозв'язки нашого досвіду з тією математичною теорією, яку ми під цей досвід хочемо підвести. Звичайно ж дана теза в принципі не може бути доведений методами математики, тому що він не має внутріматематіческіе характеру (одна сторона в тезі - поняття алгоритму - не є точним математичним поняттям). Він висунутий виходячи з досвіду, і саме досвід підтверджує його спроможність. Точно так само, наприклад, не можуть бути доведені і математичні закони механіки; вони відкриті Ньютоном і багаторазово підтверджені досвідом.
Втім, не виключається принципова можливість того, що теза Тьюринга буде спростований. Для цього повинна бути вказана функція, яка вичіслімого за допомогою якого-небудь алгоритму, але невичісліма ні на якій машині Тьюринга. Але така можливість є малоймовірною (у цьому одне із значень гіпотези): всякий алгоритм, який буде відкритий, може бути реалізований на машині ...
