Сет Ллойд - Програмуючи Всесвіт. Космос – квантовий комп’ютер

Коли комп’ютер обчислює, він просто застосовує логічні елементи до бітів. Комп’ютерні ігри, обробка слів, обробка великих обсягів числових даних та спаму – усе походить із електронної трансформації бітів, одного чи двох за раз.

До цього моменту ми робили акцент на глибинній простоті інформації та обчислення. Біт – це проста річ, комп’ютер – це проста машина. Але це не означає, що комп’ютери не здатні функціонувати у складному режимі. Парадоксальний результат операції комп’ютера – нібито в суті своїй логічної – полягає в тому, що його майбутня поведінка не передбачувана. Єдиний спосіб дізнатися, що робитиме комп’ютер, почавши обчислення, – чекати й дивитися, що відбувається.

У 1930-х роках австрійський логік Курт Ґедель показав, що будь-яка достатньо потужна математична теорія містить формулювання, котрі, якщо вони помилкові, зроблять її суперечливою, але це не може довести її хибність. Усі досить потужні системи логіки містять недоведені формулювання. Обчислювальним аналогом недоведеного формулювання є необчислювана кількість.

Загальновідома проблема, чия відповідь є необчислюваною, – це так звана проблема зупинення. Запрограмуйте комп’ютер. Запустіть його в роботу. Чи комп’ютер коли-небудь зупиниться і дасть результат? Чи він працюватиме вічно? Загальноприйнятої процедури вирахування відповіді на це питання немає. Інакше кажучи, жодна комп’ютерна програма не може прийняти як вхідні дані іншу комп’ютерну програму та визначити зі 100-відсотковою ймовірністю, чи зупиняється перша комп’ютерна програма, чи ні.

Звісно, щодо багатьох програм ви можете сказати, чи зупиниться комп’ютер. Наприклад, програма «print 1 000 000 000»: комп’ютер, якому задано цю програму, друкує «1 000 000 000» і зупиняється. Але, як правило, хоч як довго комп’ютер робить обчислення без зупинки, ви не можете певно сказати, що він ніколи не зупиниться.

Хоча це може звучати затеоретизовано, проблема зупинення має багато практичних наслідків. Візьмімо, наприклад, усунення «баґів» комп’ютера. Більшість комп’ютерних програм містять дефекти, помилки, «баґи», через які комп’ютер поводиться неочікувано, наприклад, ламається. Було б корисно мати «універсальний усувач дефектів» для комп’ютерних програм. Такий усувач брав би як вхідні дані комп’ютерну програму разом з описом того, що програма повинна здійснити, і потім пересвідчувався б, що програма робить належне. Такий усувач неможливий.

Універсальний усувач повинен підтвердити, що його вхідна програма дає правильний результат. Тож перше, що універсальний усувач дефектів має перевірити, – чи ця вхідна програма має взагалі якийсь результат. Але щоб підтвердити, що програма дає результат, універсальний усувач дефектів повинен розв’язати проблему зупинення. Тобто те, чого він зробити не може. Єдиний спосіб визначити, чи програма зупиниться, – це запустити її й побачити, та в цей момент нам уже не потрібен універсальний усувач дефектів. Тож наступного разу, коли «баґ» змушує ваш комп’ютер зависати, ви можете знайти відраду в глибокій математичній істині: системного способу усунути всі дефекти не існує. Або ви можете просто вилаятись і перезавантажити.

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

Люди відомі своєю нездатністю передбачати власні майбутні дії. Це важлива особливість того, що ми називаємо свободою волі. «Свобода волі» означає нашу очевидну свободу вирішувати. Наприклад, коли я сідаю в ресторані й дивлюся в меню, я і тільки я вирішую, що замовлю; і до того, як я вирішу, навіть я не знаю, яким буде мій вибір. Іншими словами, наші власні майбутні вибори є загадкою для нас самих. (Вони можуть, звісно, не бути загадкою для інших. Упродовж років ми з дружиною ходили обідати в ресторан «Джозі» в Санта-Фе. Довго й ретельно досліджуючи меню, я завжди замовляю півтарілки фаршированого перцю релено, з червоним та зеленим перцем чилі й посоле замість рису. У мене було сильне відчуття того, що я практикував свободу волі: доки я не обирав півтарілки чилі релено, я відчував, що можливе будь-що. Проте моя дружина весь час точно знала, що я замовлю!)