Комп'ютери проникли в більшість сфер життя людини і продовжують розвиватися. Автопілот, банківська сфера, машинний переказ, медицина, фінансові ринки, польоти в космос - все це можливо завдяки одній простій ідеї.
У цій статті я пропоную заглянути за межі можливостей комп'ютерів і розглянути чого ж вони не можуть. І чому. Алан Тьюрінг ще в 30-ті роки позначив неможливі для комп'ютера завдання.
Машина Тьюрінга
Якщо бути гранично точним, то та сама публікація Тьюрінга, яка поклала початок комп'ютерним наукам [1], була саме про обчислювальні функції, що підкреслює існування кордону, яку не може переступити машина Тьюрінга.
Машина Тьюрінга (МТ) - це абстрактна обчислювальна машина, тісно пов'язана з поняттям алгоритму [10]. Це найпростіший комп'ютер.
Також варто пам'ятати, що будь-яка функція, яка може бути обчислена фізичним пристроєм, може бути обчислена машиною Тьюрінга [2]. Це веде до того, що всі висновки стосуються абстрактної машини Тьюрінга, повністю застосовні до будь-яких комп'ютерів на будь-якій архітектурі.
Невичисленні функції і проблема зупинки
Проблему зупинки [3] можна сформулювати як: не існує загального алгоритму, який би міг визначити, чи зупиниться програма, за її описом і вхідними даними.
Тобто. функція визначення зупинки незвичайна. Докази можна знайти у Вікіпедії.
На практиці це виглядає так - сам комп'ютер ніколи не зможе визначити точно, зависне його чергова програма в нескінченному потоці інструкцій чи ні. Адже написані людиною програми ой як недосконалі.
Одна відома спроба вирішити цю задачу виникла в надрах Майкрософт під назвою Microsoft Terminator [4]. У Microsoft хотіли зменшити кількість забаганних драйверів до заліза шляхом побудови автоматичної системи перевірки їх на коректність. Вони намагалися побудувати інструмент доказу коректності математичної моделі програми. Про позитивні результати мені не відомо, але, думаю, частково підвищити стабільність драйверів їм вдалося.
Busy Beaver Game
Це завдання в 1962 році позначив угорський математик Tiber Rado, в статті «» On non-computable functions «» [5]. За допомогою аналогії з бобром, він пояснював машину Тьюрінга, але назва закріпилася. Ще в цій статті було згадано найбільше число, відоме на той час.
Якщо обмежити машину Тьюрінга (MT) N станами, то можна створити кінцеве число машин.
При зростанні кількості статків N, кількість можливих машин Тьюринга зростає швидше ніж експоненціально: (4(n+1))^2n.
Серед решти МТ будуть два типи - ті, що зупиняються і ні.
Rado задався одним питанням у двох формулюваннях:
- Яку максимальну кількість операцій може здійснити МТ з N станами до свого завершення. Це і називають числом Busy Beaver, позначається як BB (n) або S (n).
- Яку максимально кількість одиниць може надрукувати МТ з N на порожній стрічці до завершення. Позначено як (n).
Очевидно, що це число існує. І вважаючи його, можна було б перевірити, чи завершується виконання МТ за це число кроків. Якщо ні - очевидно, що вона буде працювати вічно, так як максимальний поріг пройдено.
The Busy Beaver Game пропонує знайти програму для машини Тьюрінга з N станами, яка працює максимально довго і потім завершується.
Як вхідні дані, стрічка машини Тьюрінга заповнена нулями.
Необхідно скласти програму, яка заповнить її максимальним числом одиниць і завершиться, перейшовши в стан HALT.
Ось так виглядають правила для машини Тьюрінга з двома станами (N = 2). Цей же приклад є рішенням Busy Beaver для N = 2.
Виконання програми відбувається приблизно так:
- Вся стрічка заповнена нулями як вхідні дані.
- Початковий стан - A.
- Зчитуємо поточний біт - якщо це 1, то виконуємо код A1, інакше - A0.
- Інструкції 1RB означають - записати на літню 1, перейти вправо, перейти в стан B.
- Робота програми триває поки не настане перехід на стан HALT (H)
Малюнок 1. Візуалізація покрокової роботи MT при N = 2. Перший стовпчик - це номер кроку. Другий стовпчик показує як змінюються стану МТ у міру виконання. Третя колонка - стану стрічки, де видно черговість появи одиниць на ній. Четверта - траєкторія переміщення індексу по стрічці.
N=3
Малюнок 2. Розв "язання Busy Beaver для завдання N = 3
Малюнок 3. Візуалізація покрокової роботи MT при N = 3.
N=4
Малюнок 4. Розв "язання Busy Beaver для завдання N = 4
Малюнок 5. Візуалізація покрокової роботи MT при N = 4. Ось така ялинка, з Наступаючим!
Для відображення такого графа N = 5 нам би знадобилося 47,176,870 кроків мінімум.
При N = 6, максимальне знайдене на сьогодні число Бобра S (6) = 7.4 ^ 10 ^ 36534.
Для N = 7 існує лише попередня оцінка S (7) >. (7) > 10. 10. 10. 10. 18705352 [6]
На сьогоднішній день є думка, що люди можуть знайти S (6) і надати докази що воно максимальне. S (7) є абсолютно недоступним [8].
Існують різні варіації: на стрічку можна записувати 3,4,5,6 символів, замість {0,1}. При цьому числа тільки зростають.
Як вирішують цю задачу?
Загальний підхід до вирішення виглядає як поділ всіх можливих машин Тьюрінга на наступні класи:
- Tree-normalized: ці машини виключені з простору пошуку, тому що доведено, що вони еквівалентні іншим МТ або їх поведінка очевидно [8]
- Candidate-halter: Машини, які гарантовано залишаються - це кандидати на звання чемпіонів Busy Beaver Game.
- Non-candidate-halter: зупиняючи, але не задовольняють певним вимогам.
- Non-halter: безліч дрібних класів для кожного з яких проявляє специфічну поведінку пов'язану з не зупинкою.
- Holdouts: все що залишилося, при тому не ясно зупиняються чи ні ці машини. Коли цей клас виявиться порожнім, можна вважати завдання Busy Beaver вирішеним.
За допомогою нормалізації по дереву (tree normalization) можна значно скоротити кількість МТ.
- Прикладом методу tree normalization може служити видалення половини МТ, де перший крок робиться ліворуч. Тому що існує аналогічна дзеркальна машина, яка починає рух праворуч [8]. *
Надтьюрингові обчислення
Якби вдалося побудувати машину для розрахунку BB (n), це була б вже надтьюрингова машина.
Надтьюрингові обчислення - це такі обчислення, які не можуть бути виконані на машині Тьюрінга [9]. Але чи можна побудувати фізичний надтьюринговий комп "ютер [7]?
Важливе питання для створення Сильного Штучного Інтелекту - чи оперує розум людини тільки тьюринговими обчисленнями?
Ув'язнення
Навіщо намагатися вирішити невирішувану задачу? Може тому, що прикордонні випадки в математиці відкривають всю повноту вихідної теорії.
The Busy Beaver Game тісно пов'язана з теорією обчислення, проблемою зупинки і теорією складності.
Ще це завдання змусило мене задуматися - що ж такого може вирахувати машина Тьюринга протягом трохи менше ніж нескінченність?
Мій блог на Medium
Посилання
[1] On Computable Numbers
[2] Теза Черча-Тьюрінга
[3] Проблема зупинки
[4] Microsoft Terminator
[5] On non-computable functions
[6] Good bound for S(7)
[7] Hypercomputation: Hype or Computation?
[8] The complex behavior of simple machines. Rona Machilin
[9] Надтьюрингові обчислення
Машина Тьюрінга
[11] Python and C++ sources by by Peteris Krumins
