Алгоритмічно нерозв'язна задача
В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків.
Проблеми, що стосуються абстрактних машин ред.
- проблема зупинки
- проблема самозастосування[ru]
- Busy beaver[en]
- Будь-яка проблема, сформульована в теоремі Райса[ru]
- Визначити, чи досягне коли-небудь задана вихідна конфігурація в грі «Життя» заданої кінцевої конфігурації[1]
Проблеми, що стосуються матриць ред.
- Проблема вмираючої матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає нульову матрицю. Проблема нерозв'язна навіть для n=3 (можливість розв'язання для n = 2 є відкритим питанням[2])
- Проблема одиничної матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає одиничну матрицю. проблема нерозв'язна для цілочисельних матриць починаючи з n=4[3] та розв'язна для n = 2[4] (можливість розв'язання для n = 3 є відкритим питанням). Проблема еквівалентна питанню, чи є матрична півгрупа групою.
- Проблема вільності матричної напівгрупи алгоритмічно нерозв'язна для цілочисельних матриць починаючи з n = 3 і відкрита для n = 2.
Інші проблеми ред.
- Задача розв'язності
- Виводимість формули в арифметиці Пеано
- Проблема збіжності Поста
- Обчислення колмогорівської складності довільного рядка
- Ідеальний архіватор, що створює для будь-якого вхідного файлу програму найменшого можливого розміру, що друкує цей файл[5]
- Ідеальний оптимізувальний за розміром компілятор[6]
- Десята проблема Гільберта
- Визначити, чи можна замостити площину даними набором плиток Ванга
- Визначити, чи можна замостити площину даними набором поліміно.
- Проблема уніфікації другого і вищого порядків
- Проблема виводу типів в моделі Хіндлі — Мілнера з rank-N поліморфізмом
Проблеми, алгоритмічна нерозв'язність яких не доведена ред.
Для деяких задач не вказано алгоритм, що вирішує їх, і за своєю природою вони схожі на відомі алгоритмічно нерозв'язні завдання. Питання щодо алгоритмічної розв'язності таких задач є відкритими питаннями. Ось деякі з таких завдань:
- Аналог десятої проблеми Гільберта для рівнянь ступеня 3
- Аналог десятої проблеми Гільберта для рівнянь в раціональних числах[7]
- Проблема вмираючої матриці для матриць порядку 2
Нерозв'язність ред.
Існують задачі, що неможливо розв'язати, використовуючи комп'ютер.
Якщо проблема має алгоритм, що на будь-якому екземплярі проблеми правильно відповідає «так» або «ні», то така проблема називається розв'язною. У протилежному разі проблема нерозв'язна.
Питання про пошуки алгоритму, що визначав би істинність або хибність будь-якого математичного твердження, було поставлене ще Гільбертом.
У 1931 Курт Гедель довів теорему про неповноту. Він показав, що існує істинна формула першого порядку з цілими змінними, яку не можна ні довести, ні спростувати у вирахуванні предикатів першого порядку над цілими.
Строге доведення базується на теорії частково рекурсивних функцій і рекурсивно-перелічуваних предикатів.
Ідея доведення ред.
Ідея доведення полягає у тому, щоб побудувати приклад формули, яка була б недовідна і разом з тим змістовно істинна. Для побудови такої формули Гедель запропонував спосіб нумерації виразів формальної системи, який дозволив приписати унікальний номер кожному елементарному символу, формулі або доведенню даної формальної системи. Використовуючи геделівську нумерацію, можна побудувати формулу, яка стверджує недовідність формули з номером n, де n — номер самої цієї формули.
Існування алгоритмічно нерозв'язних проблем ред.
Існування алгоритмічно нерозв'язних проблем випливає вже з теореми Геделя про неповноту формальних систем. Справа у тому, що існує тісний зв'язок між алгоритмами і вирахуваннями. Власне кажучи, і алгоритми, і вирахування — це сукупності чітких, однозначно заданих скінченних інструкцій, що описують якісь дії із символічними об'єктами. Однак у випадку алгоритму ці інструкції мають характер розпоряджень, що задають однозначний порядок виконання операцій над символічними об'єктами, тоді як у випадку вирахувань — інструкції не визначать черговості їх виконання.
Приклади алгоритмічної нерозв'язності ред.
Прикладом алгоритмічної нерозв'язності може бути нерозв'язність «проблеми зупинки». «Проблема зупинки» — це проблема пошуку універсальної програми, що дозволяє за записом довільної програми (наприклад, функціональної таблиці машини Тюринга), а також за записом довільних вхідних даних установити, чи зупиниться обчислювальний пристрій, що діє відповідно до даної програми і обробляє вхідні дані, або ж він буде працювати нескінченно довго.
Теорема про «зупинку» ред.
Програма називається застосовною до вхідних даних, якщо вона рано чи пізно зупиниться і видасть деякий результат. У протилежному разі говорять, що програма незастосовна до вхідних даних. Теорема про «зупинку» стверджує, що проблема застосовності довільної програми до довільних вхідних даних алгоритмічно нерозв'язна.
Ця теорема доводиться досить просто. Перший крок полягає у тому, що вводиться поняття самозастосовності програми. Програма називається самозастосовною, якщо вона ефективно переробляє текст, що відповідає її власному запису, у деякий результат за скінченне число кроків. У протилежному разі якщо програма не зупиняється і продовжує працювати нескінченно довго, то вона називається не самозастосовною.
Спочатку доводиться таке твердження: не існує програми, застосовної до всіх несамозастосовних програм і тільки до них. Доведення полягає у вказівці на суперечливість поняття про таку програму. Задамося питанням: чи є дана програм самозастосовною? Якщо вона самозастосовна, то вона несамозастосовна (оскільки застосовна лише до несамозастосовних програм). Якщо ж вона несамозастосовна, то вона самозастосовна (оскільки застосовна до всіх несамозастосовних програм).
Виходячи з цього результату, можна також довести неіснування програми, здатної універсальним способом розпізнавати не самозастосовність довільних програм. Дійсно, якщо така програма існує, то можна побудувати й програму, застосовну до всіх не самозастосовних програм і тільки до них.
Розпізнавання несамозастосовності ред.
Позначимо буквою В програму, здатну розпізнавати несамозастосовність. Тоді наступна програма буде програмою, застосовною до всіх несамозастосовних програм і тільки до них.
- Виконати послідовність команд В, перейти до кроку 2.
- Якщо отримана відповідь «так», то перейти до кроку 3, у протилежному разі перейти до кроку 4.
- Закінчити процес.
- Перейти до кроку 4.
Ця програма зупиняється, якщо розглянута як вхідні дані програма є несамозастосовною, і не зупиняється (зациклюється на кроці 4) у протилежному разі.
Використовуючи даний результат можна також показати, що не існує й програми, що розпізнає універсальним способом самозастосовність (оскільки у протилежному разі можна побудувати алгоритм, що розпізнає несамозастосовність).
І нарешті, можна показати, що алгоритмічно нерозв'язною є проблема розпізнавання застосовності довільної програми до довільних вхідних даних. Припустимо зворотне. Нехай Е — програма, що за заданою довільною програмою і заданим на вході словом розпізнає застосовність даної програми до даного слова. Неважко побудувати програму, що дозволяє установити, чи є задане слово кодом даної програми. Позначимо таку програму буквою Р.
Тоді можна побудувати програму Н.
- Застосувати послідовність команд Р. Перейти до кроку 2.
- Якщо послідовність команд Р дала відповідь «так», перейти до кроку 3, інакше — до кроку 4.
- Виконати послідовність команд Е. Кінець.
- Перейти до кроку 4.
Висновок ред.
Програма Н є програмою, що розпізнає самозастосовність довільних програм. Така програма неможлива, а отже, неможлива і програма Е.
Чому існують нерозв'язні проблеми. Проблема — це питання про приналежність ланцюжка мові. Множина мов над будь-яким алфавітом, де більше одного символу, незліченна. Програми, будучи скінченними ланцюжками у скінченному алфавіті, утворять зліченну множину. Іншими словами, проблем нескінченно більше, ніж програм.
Див. також ред.
Примітки ред.
- ↑ Life Universal Computer. Архів оригіналу за 31 жовтня 2014. Процитовано 30 жовтня 2014.
- ↑ When is a pair of matrices mortal? (PDF). Архів оригіналу (PDF) за 8 грудня 2015. Процитовано 30 жовтня 2014.
- ↑ Paul C. Bell; Igor Potapov (2010). On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups. International Journal of Foundations of Computer Science. World Scientific. 21.6: 963—978. doi:10.1142/S0129054110007660.
{{cite journal}}: Cite має пустий невідомий параметр:|1=(довідка) - ↑ Christian Choffrut; Juhani Karhumäki (2005). Some decision problems on integer matrices. ITA. 39(1): 125—131. doi:10.1051/ita:2005007.
- ↑ Наявність такого архіватора дозволило б обчислити колмогоровську складність довільного рядка, що є алгоритмічно нерозв'язним завданням.
- ↑ Зокрема, він замінював би будь-який алгоритм що не зупиняється на тривіальний порожній цикл, а розпізнавання таких алгоритмів еквівалентно проблемі зупинки і є алгоритмічно нерозв'язним завданням.
- ↑ Успенський В. А., Семенов А. Л. Алгоритмічні проблеми, що можна і не можна вирішити. // Журнал Квант, 1985, № 7, с. 9—15.