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

Чтение книги онлайн.

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

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

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

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

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

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

      Люди відомі своєю нездатністю передбачати власні майбутні дії. Це важлива особливість СКАЧАТЬ