У теоретичній інформатиці гра зайнятого бобра має на меті знайти таку завершувану програму заданого розміру, яка (залежно від визначення) або генерує якнайбільший вивід, або виконується якнайдовше. Оскільки програму, яка нескінченно зациклюється, генеруючи нескінченний вивід або виконуючись нескінченно довго, легко побудувати, такі програми виключаються з гри. Замість традиційних мов програмування у грі використовуються n-станові машини Тюрінга, — одна з перших математичних моделей обчислення.
Машини Тюрінга складаються з нескінченної стрічки та скінченної множини станів, що слугують «вихідним кодом» програми. Найбільший вивід визначається як запис найбільшої кількості одиниць на стрічці — це також називають найвищим результатом; найдовший час роботи — це найбільша кількість кроків до зупинки. Гра n-станового зайнятого бобра полягає у пошуку машини Тюрінга з n станами, яка зупиняється і при цьому працює найдовше або отримує найвищий результат. Такі машини вважаються такими, що починають роботу на порожній стрічці, а стрічка містить лише нулі та одиниці (двійкова машина Тюрінга). Мета гри — запрограмувати набір переходів між станами, що забезпечує найвищий результат або найдовший час роботи, при цьому гарантуючи, що машина зрештою зупиниться.
Визначення часу роботи або результату n-го зайнятого бобра є необчислюваним. Зокрема, обидві функції Σ(n) і S(n) зрештою стають більшими за будь-яку обчислювану функцію. Це має наслідки для теорії обчислюваності, задачі зупинки та теорії складності. Концепцію зайнятого бобра вперше запровадив у своїй статті 1962 року «On Non-Computable Functions».
Один із найважливіших аспектів гри зайнятого бобра полягає в тому, що якби можна було обчислити функції Σ(n) і S(n) для всіх n, це дозволило б розв'язати всі математичні гіпотези, які можна закодувати у вигляді «чи зупиняється ⟨ця машина Тюрінга⟩?». Наприклад, існує 27-станова машина Тюрінга, яка перевіряє гіпотезу Гольдбаха для кожного числа і зупиняється на контрприкладі; якщо ця машина не зупинилась після S(27) кроків, вона виконуватиметься вічно, що розв'яже гіпотезу. Багато інших задач, зокрема Гіпотеза Рімана (744 стани) та несуперечність теорії множин ZF (745 станів), можна виразити в аналогічній формі, де потрібно перевірити щонайбільше зліченно нескінченну кількість випадків.
Технічне визначення Гра n-станового зайнятого бобра (або гра BB-n), введена у статті Тібора Радо 1962 року, розглядає клас машин Тюрінга, кожна з яких повинна відповідати таким вимогам до конструкції:
«Запуск» машини полягає в тому, що вона починає в початковому стані, з поточною коміркою на будь-якій комірці порожньої (усі 0) стрічки, і потім ітеративно застосовує функцію переходів, доки не буде досягнуто стан Зупинки (якщо взагалі досягається). Тоді і тільки тоді, коли машина зрештою зупиняється, кількість одиниць, що залишилися на стрічці, називається результатом машини. n-й зайнятий бобер, BB-n або просто «зайнятий бобер» — це машина Тюрінга, яка виграє гру n-станового зайнятого бобра. Залежно від визначення, вона або досягає найвищого результату (позначається Σ(n)), або виконується найдовше (S(n)), серед усіх інших можливих n-станових машин.
Приклад
Правила для однієї 1-станової машини Тюрінга можуть бути такими: У стані 1, якщо поточний символ — 0: записати 1, рухатись праворуч, перейти до стану 1 У стані 1, якщо поточний символ — 1: записати 0, рухатись праворуч, перейти до ЗУПИНКИ
Ця машина Тюрінга рухалась би праворуч, змінюючи значення всіх бітів, що зустрічаються. Оскільки початкова стрічка складається лише з нулів, вона утворювала б нескінченний рядок одиниць. Така машина не може бути претендентом на зайнятого бобра, оскільки виконується вічно на порожній стрічці.
Функції У своїй оригінальній статті 1962 року Радо визначив дві функції, пов'язані з грою зайнятого бобра: функцію результату Σ(n) і функцію зсувів S(n). Обидві приймають кількість станів машини Тюрінга і видають максимально досяжний результат машини з цією кількістю станів за певним критерієм. Функція результату Σ(n) дає максимальну кількість одиниць, яку може вивести -станова машина Тюрінга перед зупинкою, тоді як функція зсувів S(n) дає максимальну кількість зсувів (або еквівалентно кроків, оскільки кожен крок включає зсув), яку може здійснити -станова машина Тюрінга перед зупинкою. Він довів, що обидві ці функції є необчислюваними, оскільки кожна з них зростає швидше за будь-яку обчислювану функцію. Функцію BB(n) визначають як будь-яку з цих функцій, тому ця нотація у статті не використовується.
Також можна визначити низку інших необчислюваних функцій, що вимірюють продуктивність машин Тюрінга іншими способами, ніж час або максимальна кількість одиниць. Наприклад: Функція визначається як максимальна кількість суміжних одиниць, яку зупиняється машина Тюрінга може записати на порожній стрічці. Іншими словами, це найбільше унарне число, яке може вивести машина Тюрінга з n станами. Функція визначається як максимальна кількість комірок стрічки, яку зупиняється машина Тюрінга може прочитати (тобто відвідати) перед зупинкою. Це включає початкову комірку, але не комірку, до якої машина потрапляє лише після переходу до стану зупинки (якщо цей перехід позначено напрямком руху), оскільки та комірка не впливає на поведінку машини. Це максимальна просторова складність n-станової машини Тюрінга. Ці чотири функції пов'язані нерівністю . Більше функцій можна також визначити, застосовуючи гру до інших обчислювальних машин, зокрема 3-символьних машин Тюрінга, недетермінованих машин Тюрінга, лямбда-числення або навіть довільних мов програмування.
Функція результату Σ
Функція результату кількісно визначає максимальний результат, досяжний зайнятим бобром за заданим критерієм. Це необчислювана функція, оскільки вона зростає асимптотично швидше за будь-яку обчислювану функцію.
Функція результату визначається так, що — це максимально досяжний результат (максимальна кількість одиниць на стрічці після зупинки) серед усіх зупиняємих двосимвольних -станових машин Тюрінга зазначеного вище типу, запущених на порожній стрічці.
Очевидно, що є коректно визначеною функцією: для кожного n існує щонайбільше скінченна кількість n-станових машин Тюрінга вказаного вище типу з точністю до ізоморфізму, а отже, щонайбільше скінченна кількість можливих часів роботи.с. 880
За визначенням на основі результату, будь-яка n-станова двосимвольна машина Тюрінга M, для якої (тобто яка досягає максимального результату), називається зайнятим бобром. Для кожного n існує щонайменше 4(n − 1)! n-станових зайнятих бобрів. (Маючи будь-якого n-станового зайнятого бобра, іншого отримують простою зміною напрямку зсуву в переході до зупинки, третього — інвертуванням усіх напрямків зсувів, а четвертого — інвертуванням напрямку зупинки у повністю переставленого бобра. Крім того, перестановка всіх станів, крім Початкового і Зупинки, дає машину з таким самим результатом. Теоретично може існувати більше одного типу переходів до стану зупинки, але на практиці це марно, оскільки існує лише одна послідовність переходів між станами, що дає потрібний результат.)
Необчислюваність У статті 1962 року Радо довів, що якщо — будь-яка обчислювана функція, то Σ(n) > f(n) для всіх достатньо великих n, і тому Σ не є обчислюваною функцією.
Крім того, це означає, що загальним алгоритмом є алгоритмічно нерозв'язною задача, чи є довільна машина Тюрінга зайнятим бобром. (Такий алгоритм не може існувати, оскільки його існування дозволило б обчислити Σ, що є доведеною неможливістю. Зокрема, такий алгоритм міг би використовуватися для побудови іншого алгоритму, який обчислював би Σ таким чином: для будь-якого заданого n кожну зі скінченно багатьох n-станових двосимвольних машин Тюрінга перевіряли б, поки не знаходили б n-станового зайнятого бобра; після чого цю машину моделювали б для визначення її результату, що за визначенням і є Σ(n).)
Хоча Σ(n) є необчислюваною функцією, для деяких малих n можна отримати її значення та довести їх коректність. Нескладно показати, що Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, а з наростаючими труднощами можна показати, що Σ(3) = 6, Σ(4) = 13 і Σ(5) = 4098 . Значення Σ(n) для жодного n > 5 досі не визначено точно, хоча нижні оцінки встановлено (див. розділ Відомі значення нижче).
Складність і недоведуваність Σ
Варіант колмогоровської складності визначається так:Boolos, Burgess & Jeffrey, 2007. «Computability and Logic» Складність числа n — це найменша кількість станів, потрібна машині класу BB, щоб зупинитися з єдиним блоком з n послідовних одиниць на спочатку порожній стрічці. Відповідний варіант теореми Чайтіна про неповноту стверджує, що в контексті заданої аксіоматичної системи для натуральних чисел існує число k таке, що жодне конкретне число не може бути доведено таким, що його складність перевищує k, і тому не може бути доведена жодна конкретна верхня оцінка для Σ(k) (останнє пояснюється тим, що «складність n більша за k» було б доведено, якби було доведено ). Як зазначено у вказаному джерелі, для будь-якої аксіоматичної системи «звичайної математики» найменше значення k, для якого це є істинним, значно менше за 10⇈10; отже, в контексті звичайної математики ні значення, ні жодна верхня оцінка Σ(10⇈10) не може бути доведена. (Перша теорема Геделя про неповноту ілюструється цим результатом: в аксіоматичній системі звичайної математики існує істинне, але недоведуване твердження вигляду , і існує нескінченно багато істинних, але недоведуваних тверджень вигляду .)
Функція максимальних зсувів S На додаток до функції Σ, Радо ввів іншу граничну функцію для машин Тюрінга — функцію максимальних зсувів S, що визначається так:
= кількість зсувів, що здійснює M до зупинки, для будь-якої , } = найбільша кількість зсувів будь-якої зупиняємої n-станової двосимвольної машини Тюрінга.
Оскільки звичайні машини Тюрінга зобов'язані здійснювати зсув у кожному переході або «кроці» (включаючи будь-який перехід до стану Зупинки), функція максимальних зсувів є водночас функцією максимальних кроків.
Радо показав, що S є необчислюваною з тієї ж причини, що й Σ — вона зростає швидше за будь-яку обчислювану функцію. Він довів це, просто зазначивши, що для кожного n виконується S(n) ≥ Σ(n). Кожен зсув може записати 0 або 1 на стрічку, тоді як Σ рахує підмножину зсувів, що записали 1, а саме ті, які не були перезаписані до моменту зупинки машини Тюрінга; отже, S зростає щонайменше так само швидко, як Σ, яка вже була доведена такою, що зростає швидше за будь-яку обчислювану функцію.
Наступний зв'язок між Σ і S використали Лін і Радо (Computer Studies of Turing Machine Problems, 1965) для доведення того, що Σ(3) = 6 і S(3) = 21: для заданого n, якщо відомо S(n), то всі n-станові машини Тюрінга можна (в принципі) запустити на S(n) кроків, після чого будь-яка машина, що ще не зупинилася, не зупиниться ніколи. Після цього, спостерігаючи, які машини зупинилися з найбільшою кількістю одиниць на стрічці (тобто зайняті бобри), зі стрічок отримують значення Σ(n). Підхід Ліна і Радо для n = 3 полягав у висуненні гіпотези, що S(3) = 21 (після невдалої гіпотези 18), а потім у моделюванні всіх принципово різних 3-станових машин (82 944 машини, що дорівнює 21034) на 21 крок. Вони знайшли 26 073 машини, що зупинилися, включаючи одну, що зупинилася лише після 21 кроку. Аналізуючи поведінку машин, що не зупинились протягом 21 кроку, вони змогли показати, що жодна з цих машин ніколи не зупиниться, більшість з них слідуючи певному шаблону. Це довело гіпотезу, що S(3) = 21, а також визначило, що Σ(3) = 6, чого досягли кілька машин, усі зупиняючись після 11–14 кроків.