Найважливіша машина, яку ніколи не створювали

Обчислення — знайоме поняття, яке більшість із нас розуміє інтуїтивно. Прийміть функцію f(x) = x + 3. Коли x три, f(3) = 3 + 3. Шість. легко. Здається очевидним, що ця функція обчислювана. Але деякі функції не такі прості, і не так легко визначити, чи можна їх обчислити, тобто вони ніколи не дадуть нам остаточної відповіді.

У 1928 році німецькі математики Давид Гільберт і Вільгельм Аккерман запропонували питання під назвою Проблема рішення («проблема прийняття рішення»). Згодом їх запитання призвело б до формального визначення обчислюваності, яке дозволило б математикам відповісти на безліч нових проблем і заклало основу для теоретичної інформатики.

Визначення прийшло від 23-річного аспіранта на ім’я Алан Тьюринг, який у 1936 році написав основоположний документ що не лише формалізувало концепцію обчислення, але й довело фундаментальне питання математики та створило інтелектуальну основу для винаходу електронного комп’ютера. Велике розуміння Тюрінга полягало в тому, щоб дати конкретну відповідь на питання обчислень у формі абстрактної машини, яку пізніше назвав машиною Тюрінга його докторський радник Алонзо Черч. Він абстрактний, оскільки фізично не існує (і не може) існувати як матеріальний пристрій. Натомість це концептуальна модель обчислень: якщо машина може обчислити функцію, то ця функція обчислювана.

Ось як це працює. Машина Тьюрінга може читати та змінювати символи на нескінченно довгій стрічці, як це продиктовано таблицею правил. Стрічка складається з «комірок», кожна з яких може зберігати рівно один символ, і машина зчитує та переписує вміст комірок за допомогою головки стрічки. Кожне правило в таблиці визначає, що має робити машина на основі її поточного стану та символу, який вона читає. Машина може перейти в кінцевий стан («стан прийняття» або «стан відхилення»), після якого вона зупиняється, приймаючи або відхиляючи введення. Або потрапляє в нескінченний цикл і продовжує читати стрічку вічно.

Найкращий спосіб зрозуміти машину Тьюринга — це розглянути простий приклад. Давайте уявімо такий, який розроблений, щоб повідомити нам, чи є даний вхід числом нуль. Ми будемо використовувати вхідне число 0001 із порожніми символами (#), тому «#0001#» є відповідною частиною нашої стрічки.

Машина запускається в початковому стані, який ми назвемо q0. Він зчитує крайню ліву клітинку на нашій стрічці та знаходить порожнє місце. У правилах сказано: «У стані q0, якщо символ #, залиште його без змін, перемістіть одну клітинку вправо та змініть стан машини на q1». Після цього кроку машина перебуває в стані q1, а її головка зчитує другий символ, 0.

Тепер ми шукаємо правило, яке стосується цих умов. Ми знаходимо такий, який говорить: «Залишайтеся в стані q1 і перемістіть голову на одну клітинку вправо». Це залишає нас у тому самому положенні (у стані q1, читання «0»), тому ми продовжуємо рухатися вправо, поки голова нарешті не прочитає інше число, 1.

Коли ми знову звертаємося до таблиці, ми знаходимо нове правило: «Якщо ми зустрічаємо 1, переходимо до q2, що є станом «відхилення». Машина зупиняється, відповідаючи «Ні» на початкове запитання «Чи '0001' дорівнює нулю?»

Якщо замість цього ввести «#0000#», машина зустріне # після всіх цих нулів. Коли ми перевіряємо таблицю, ми знаходимо правило, яке говорить, що це означає, що машина переходить у стан q3, стан «прийняття». Тепер машина відповідає «Так» на запитання «Чи '0000' дорівнює нулю?»

За допомогою своєї абстрактної машини Тьюрінг створив модель обчислень, щоб відповісти на проблему Entscheidungsproblem, яка формально запитує: чи існує набір математичних аксіом механічний процес — набір інструкцій, який сьогодні ми б назвали алгоритмом — який завжди може визначити, чи вірне дане твердження?

Скажімо, ми хочемо знайти алгоритм, який може сказати нам, чи можлива певна шахова позиція. Тут аксіоми — це правила гри в шахи, які керують допустимими ходами. Чи можемо ми слідувати кінцевій покроковій послідовності процедур, щоб досягти цієї позиції? Хоча для аналізу деяких позицій може знадобитися більше часу, ніж наше життя — алгоритм може генерувати всі можливі позиції та порівнювати кожну з них із вхідними — такі алгоритми існують у грі в шахи. У результаті ми говоримо, що шахи «розв’язні».

Однак у 1936 році Черч і Тьюрінг, використовуючи різні методи, незалежно один від одного довели, що не існує загального способу вирішення кожного випадку проблеми Entscheidungs. Наприклад, деякі ігри, як-от «Game of Life» Джона Конвея, нерозв’язні: жоден алгоритм не може визначити, чи з’явиться певний шаблон із початкового шаблону.

Тьюрінг показав, що функція є обчислюваною, якщо існує алгоритм, який може виконати бажане завдання. Водночас він показав, що алгоритм — це процес, який може бути визначений машиною Тьюрінга. Отже, обчислювана функція — це функція, яка має машину Тьюрінга для її обчислення. Це може здатися обхідним способом визначення обчислюваності, але це найкраще, що ми маємо. «Це не те, що у вас є вибір визначити це якось інакше», — сказав Майкл Сіпсер, вчений-теоретик в Массачусетському технологічному інституті. «Я думаю, загальноприйнятим є теза Черча-Тюрінга, що неформальне поняття алгоритму відповідає тому, що може зробити будь-яка «розумна» обчислювальна модель». Інші математики придумали різні моделі обчислень, які виглядають зовсім різними на поверхні, але насправді еквівалентні: вони можуть виконувати будь-які обчислення, які можуть виконувати машини Тьюрінга, і навпаки.

Лише через кілька років після того, як Курт Гедель довів, що математика є неповнийЦією роботою Черч і Тьюрінг показали, що деякі проблеми в математиці неможливо розв’язати — жоден алгоритм, яким би складним він не був, не може сказати нам, чи є відповідь так чи ні. Обидва були нищівними ударами для Гільберта, який сподівався, що математика матиме чіткі, ідеалізовані відповіді. Але, мабуть, це так само добре: якби існувало загальне вирішення проблеми Entscheidungs, це означало б, що всі проблеми в математиці можна було б звести до простих механічних обчислень.

Окрім відповіді на ці фундаментальні запитання, машина Тьюринга також безпосередньо привела до розробки сучасних комп’ютерів через варіант, відомий як універсальна машина Тьюринга. Це особливий вид машини Тьюрінга, яка може імітувати будь-яку іншу машину Тьюрінга на будь-якому вході. Він може зчитувати опис інших машин Тьюрінга (їхні правила та стрічки введення) і симулювати їхню поведінку на власній вхідній стрічці, виробляючи той самий вихід, який створила б змодельована машина, так само, як сучасні комп’ютери можуть читати будь-яку програму та виконувати її. У 1945 році Джон фон Нейман запропонував комп’ютерну архітектуру — так звану архітектуру фон Неймана — яка зробила концепцію універсальної машини Тьюрінга можливою в реальній машині.

Коли Санджив Арора, вчений-теоретик із Прінстонського університету, викладає цю концепцію, він наголошує на ширшій філософській картині. «Є два поняття «універсальний», — сказав він. «Одним із понять універсального є те, що він може запускати будь-яку іншу машину Тьюрінга. Але інше, більш важливе поняття «універсал» полягає в тому, що воно може виконувати будь-які обчислення, які ви придумаєте у Всесвіті». У світі класичної фізики будь-який фізичний процес можна змоделювати або змоделювати за допомогою алгоритмів, які, у свою чергу, можна змоделювати за допомогою машини Тьюрінга.

Іншим помітним і все більш корисним варіантом є імовірнісна машина Тьюринга. На відміну від звичайної машини Тьюринга, яка має чітко визначену реакцію на кожен вхідний сигнал, імовірнісна машина Тьюринга може мати кілька реакцій на основі ймовірностей. Це означає, що він може давати різні результати для того самого введення в різний час. Як не дивно, такого роду імовірнісна стратегія може бути більш ефективним, ніж суто детермінований підхід для певних проблем. Ідеї ​​ймовірнісних машин Тьюрінга виявилися практично корисними в таких сферах, як криптографія, оптимізація та машинне навчання.

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