В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків.
Проблеми, що стосуються абстрактних машин Редагувати
- проблема зупинки
- проблема самозастосування[ru]
- Busy beaver[en]
- Будь-яка проблема, сформульована в теоремі Райса[ru]
- Визначити, чи досягне коли-небудь задана вихідна конфігурація в грі «Життя» заданої кінцевої конфігурації
Проблеми, що стосуються матриць Редагувати
- Проблема вмираючої матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає нульову матрицю. Проблема нерозв'язна навіть для n=3 (можливість розв'язання для n = 2 є відкритим питанням)
- Проблема одиничної матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає одиничну матрицю. проблема нерозв'язна для цілочисельних матриць починаючи з n=4 та розв'язна для n = 2 (можливість розв'язання для n = 3 є відкритим питанням). Проблема еквівалентна питанню, чи є матрична півгрупа групою.
- Проблема вільності матричної напівгрупи алгоритмічно нерозв'язна для цілочисельних матриць починаючи з n = 3 і відкрита для n = 2.
Інші проблеми Редагувати
- Задача розв'язності
- Виводимість формули в арифметиці Пеано
- Проблема збіжності Поста
- Обчислення колмогорівської складності довільного рядка
- Ідеальний архіватор, що створює для будь-якого вхідного файлу програму найменшого можливого розміру, що друкує цей файл
- Ідеальний оптимізувальний за розміром компілятор
- Десята проблема Гільберта
- Визначити, чи можна замостити площину даними набором плиток Ванга
- Визначити, чи можна замостити площину даними набором поліміно.
- Проблема уніфікації другого і вищого порядків
- Проблема виводу типів в моделі Хіндлі — Мілнера з rank-N поліморфізмом
Проблеми, алгоритмічна нерозв'язність яких не доведена Редагувати
Для деяких задач не вказано алгоритм, що вирішує їх, і за своєю природою вони схожі на відомі алгоритмічно нерозв'язні завдання. Питання щодо алгоритмічної розв'язності таких задач є відкритими питаннями. Ось деякі з таких завдань:
- Аналог десятої проблеми Гільберта для рівнянь ступеня 3
- Аналог десятої проблеми Гільберта для рівнянь в раціональних числах
- Проблема вмираючої матриці для матриць порядку 2
Див. також Редагувати
Примітки Редагувати
- . Архів оригіналу за 31 жовтня 2014. Процитовано 30 жовтня 2014.
- . Архів оригіналу за 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.
- 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.