Алгоритмічно нерозв'язна задача
В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків.
Проблеми, що стосуються абстрактних машин
- проблема зупинки
- проблема самозастосування
- Busy beaver
- Будь-яка проблема, сформульована в теоремі Райса
- Визначити, чи досягне коли-небудь задана вихідна конфігурація в грі «Життя» заданої кінцевої конфігурації[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
Примітки
- Life Universal Computer
- When is a pair of matrices mortal?
- 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.