Необчислювана функція (також нерекурсивна функція) — це функція, для якої не існує алгоритму, що обчислює її значення для довільного вхідного аргументу за скінченну кількість кроків. Іншими словами, жодна машина Тюрінга не може правильно обчислити цю функцію для всіх можливих вхідних даних.
Поняття необчислюваності є центральним у теорії обчислюваності та має глибокі наслідки для математики й інформатики.
Необчислювані функції та нерозв'язні задачі
Кожна обчислювана функція має скінченну процедуру, що дає явні й однозначні інструкції щодо її обчислення. Крім того, ця процедура має бути закодована у скінченному алфавіті, що використовується обчислювальною моделлю, тому існує лише зліченна кількість обчислюваних функцій. Наприклад, функції можуть бути закодовані рядком бітів (алфавіт }).
Дійсних чисел незліченно багато, тому більшість дійсних чисел не є обчислюваними. Множина фінітарних функцій на натуральних числах також є незліченною, тому більшість із них не є обчислюваними. Конкретні приклади таких функцій: зайнятий бобер, колмогоровська складність або будь-яка функція, що виводить цифри необчислюваного числа.
Аналогічно, більшість підмножин натуральних чисел не є обчислюваними. Задача зупинки була першою такою множиною, яку було побудовано. Проблема Entscheidungsproblem, запропонована Давидом Гільбертом, запитувала, чи існує ефективна процедура для визначення істинності довільних математичних тверджень (закодованих як натуральні числа). Тюрінг і Черч незалежно показали в 1930-х роках, що ця множина натуральних чисел не є обчислюваною. Відповідно до тези Черча–Тюрінга, не існує ефективної процедури (алгоритму), яка могла б виконати ці обчислення.
Формальне визначення
Функція називається обчислюваною (або рекурсивною), якщо існує машина Тюрінга M така, що для кожного машина M на вході n зупиняється і повертає значення .
Функція називається необчислюваною, якщо вона не є обчислюваною, тобто жодна машина Тюрінга не може обчислити її значення для всіх можливих входів.
Це визначення не залежить від конкретної моделі обчислень завдяки тезі Черча–Тюрінга: усі розумні моделі обчислень (машини Тюрінга, лямбда-числення, рекурсивні функції тощо) обчислюють один і той самий клас функцій.
Чому більшість функцій є необчислюваними
Аргумент підрахунку кількостей показує, що необчислюваних функцій незрівнянно більше, ніж обчислюваних:
Кількість машин Тюрінга є зліченною — кожну машину можна закодувати скінченним рядком символів. Отже, кількість обчислюваних функцій також зліченна. Водночас кількість усіх функцій є незліченною (за теоремою Кантора).
Таким чином, «майже всі» функції є необчислюваними — обчислювані функції утворюють нескінченно малу частку серед усіх функцій.
Приклади необчислюваних функцій
Задача \ проблема зупинки
Найвідомішим прикладом є проблема зупинки: функція
є необчислюваною. Це було доведено Аланом Тюрінгом у 1936 році за допомогою діагонального аргументу.
Функція зайнятого бобра
Функція Σ(n) — максимальна кількість одиниць, яку може записати на стрічку n-станова машина Тюрінга перед зупинкою, — є необчислюваною. Більше того, вона зростає швидше за будь-яку обчислювану функцію. Відомо лише кілька значень:
n 1 2 3 4 5 6 Σ(n) 1 4 6 13 4098 > 2↑↑↑5
Колмогоровська складність
Колмогоровська складність рядка s — це довжина найкоротшої програми, що виводить s. Ця функція є необчислюваною: не існує алгоритму, який для довільного рядка визначав би його колмогоровську складність точно.
Десята задача Гільберта
Функція, що визначає, чи має довільне діофантове рівняння розв'язок у цілих числах, є необчислюваною. Це було доведено Юрієм Матіясевичем у 1970 році (з використанням результатів Джулії Робінсон).
Наслідки для математики
Існування необчислюваних функцій має глибокі наслідки:
Неповнота: За теоремами Геделя про неповноту, у будь-якій достатньо потужній формальній системі існують істинні твердження, які неможливо довести в цій системі. Це тісно пов'язано з необчислюваністю. Межі автоматизації: Не існує універсального алгоритму для перевірки правильності довільних математичних доведень, вирішення довільних рівнянь тощо. Зв'язок з інформаційною теорією: Колмогоровська складність пов'язує необчислюваність з поняттям інформаційного змісту.
Часткова обчислюваність
Деякі функції є частково обчислюваними (або частково рекурсивними): існує машина Тюрінга, яка для тих входів, де функція визначена, повертає правильне значення, але може не зупинитися для інших входів.
Наприклад: Задача зупинки є напіврозв'язною (обчислювано перелічуваною): можна перелічити всі машини, що зупиняються, але не можна ефективно визначити, яка з них не зупиниться ніколи. Теорема Райса стверджує, що будь-яка нетривіальна властивість обчислюваної функції є нерозв'язною.
Методи доведення необчислюваності
Основні методи доведення необчислюваності:
Діагоналізація Метод, вперше застосований Кантором і використаний Тюрінгом для доведення необчислюваності задачі зупинки. Припускається існування алгоритму і будується вхід, на якому він суперечить сам собі.
Зведення Якщо відомо, що задача A є нерозв'язною, і можна звести A до задачі B (тобто розв'язок B дозволив би розв'язати A), то B також є нерозв'язною. Цей метод використовується для доведення необчислюваності більшості конкретних задач.
Теорема Райса Будь-яка нетривіальна семантична властивість обчислюваних функцій є нерозв'язною. Наприклад, нерозв'язно визначити, чи виводить програма парне число, чи зупиняється на всіх входах тощо.
Зв'язок з теорією складності
Необчислюваність є «суворішим» поняттям, ніж обчислювальна складність. Теорія складності вивчає функції, що є обчислюваними, але потребують великих ресурсів (часу або пам'яті). Необчислювані функції лежать поза межами будь-якого класу складності.
Див. також Обчислювана функція Задача зупинки Теорія обчислюваності Зайнятий бобер Колмогоровська складність Теорема Райса Ступінь Тюрінга Теореми Геделя про неповноту
Джерела