астосовувати машину Тьюринга для задачі, що не входить в клас розв'язуваних, безглуздо. З іншого боку, в багатьох випадках можливе розширення класу вирішуваних завдань за рахунок створення іншої машини Тьюринга. p> По своєму пристрою машина Тьюринга вкрай примітивна. Вона набагато простіше найперших комп'ютерів. Примітивізм полягає в тому, що у неї гранично простий набір елементарних операцій, вироблених головкою - зчитування і запис, а також у тому, що доступ до комірок пам'яті (секціях стрічки) в ній відбувається не за адресою, як в комп'ютерах, а шляхом послідовного переміщення уздовж стрічки. З цієї причини навіть такі прості дії, як додавання чи порівняння двох символів, машина Тьюринга виробляє за кілька кроків, а звичайні операції додавання і множення вимагають вельми великого числа елементарних дій. Проте машина Тьюринга була придумана не як модель або прототип реальних обчислювальних машин, а для того, щоб показати принципову теоретичну можливість побудови як завгодно складного алгоритму з гранично простих операцій, причому самі операції і перехід від однієї до подальшої машина виконує автоматично.
Машина Тьюринга дає один із шляхів уточнення поняття алгоритму. У зв'язку з цим виникають питання:
- наскільки загальним є поняття машини Тьюринга? p> - чи можна вважати, що спосіб завдання алгоритмів за допомогою машини Тьюринга є універсальним? p> - чи може всякий алгоритм задаватися таким чином? p> На ці питання сучасна теорія алгоритмів пропонує відповідь у вигляді такої гіпотези:
Якщо деяка процедура чітко визначена і за природою своєю механистична, то модно цілком обгрунтовано припустити, що знайдеться машина Тьюринга, здатна її виконати.
Ця гіпотеза отримала назву тези Тьюринга. Як і теза Черча, її не можна довести, так як вона пов'язує Нечитка визначення поняття алгоритму із суворим визначенням машини Тьюринга.
В принципі, ця гіпотеза може бути спростована, якщо вдасться навести приклад алгоритму, який не може бути реалізований за допомогою тьюрінговой функціональної схеми. Проте всі відомі до цих пір алгоритми можуть бути задані за допомогою тьюрінгових функціональних схем.
В
5. Універсальна машина Тьюринга
Машина Тьюринга являє собою цифровий автомат, що оперує словами одиничної довжини (тобто символами) і забезпечений запам'ятовуючим пристроєм у вигляді нескінченної стрічки, на якій записуються символи вхідного слова, проміжні результати, а в підсумку роботи - і вихідне слово.
Зовнішній алфавіт інформаційних слів, з якими оперує машина Тьюринга, може бути довільним, але кінцевим. Крім нього, необхідний внутрішній алфавіт для позначення внутрішніх станів і деяких особливих ситуацій. У результаті робота машини Тьюринга допускає символічний опис у вигляді спеціальної таблиці переходів. У кожному рядку цієї таблиці поточного вхідного символу і поточному стану ставиться у відповідність вихідний символ, новий стан і вказівка, ліворуч або праворуч від поточного потрібно взяти наступний оброблюваний символ. Рядки таблиці називаються командами, а таблиця в цілому - програмою. Робота машини Тьюринга починається з В«установкиВ» на початкове внутрішній стан і перший символ вхідного слова. За ним у програмі знаходиться потрібна команда, а в результаті - вихідний символ, новий стан і місце, звідки потрібно вважати наступний вхідний символ. Так відбувається до тих пір, поки не буде досягнуто особливе, В«кінцевеВ» стан, відповідне вирішення завдання.
Основний результат ідеї Тьюринга полягає не в тому, що для будь-якого алгоритму в інтуїтивному сенсі може бути побудована відповідна машина, хоча цей факт і не викликає сумнівів у результаті численних перевірок. З допомогою результатів роботи Тьюринга можна довести, що машина не може вирішувати завдання, які інтуїтивно нерозв'язні.
Нерозв'язність таких завдань на машині Тьюринга не наслідком її примітивності. Тьюринг, дійсно, шукав якомога простішу схему, дозволяє не тільки формалізувати процес вирішення, але і що володіє применимостью до будь задачах. Припущення Тьюринга про те, що всякий алгоритм може бути реалізований відповідної машиною, було всього лише гіпотезою. Однак весь наступний досвід дозволив звести цю тезу в ранг формального визначення алгоритму. І, мабуть, найбільш вражаючим доказом справедливості ідеї Тьюринга стало встановлення еквівалентності цього визначення іншими формальними визначеннями, даними незалежно Е. Постом і російськими математиками А.А. Марковим і А.Н. Колмогоровим. p> Машина Тьюринга - уявна конструкція. Побудувати її значить вибрати відповідний для даної задачі алфавіт, написати символічну програму і переконатися, чи буде досягнуто в ході її виконання кінцевий стан. Це можна зробити шляхом міркувань, навіть не отримавши кінцевого результату.
Робота машини відбувається в нашій уяві. Отже, машини Тьюринга - зовсім не машини в звичайному сенсі, а скоріше те...
