Алгоритмічно нерозв'язна задача

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після кінцевого числа кроків.

Проблеми, що стосуються абстрактних машин[ред. | ред. код]

Проблеми, що стосуються матриць[ред. | ред. код]

  • Проблема вмираючої матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає нульову матрицю. Проблема нерозв'язна навіть для n=3 (можливість розв'язання для n = 2 є відкритим питанням[2])
  • Проблема одиничної матриці: для даної кінцевої множини квадратних матриць n×n визначити, чи існує добуток всіх або деяких з цих матриць (можливо, з повтореннями) в якому-небудь порядку, що дає одиничну матрицю. проблема нерозв'язна для цілочисельних матриць починаючи з n=4[3] та розв'язна для n = 2[4] (можливість розв'язання для n = 3 є відкритим питанням). Проблема еквівалентна питанню, чи є матрична півгрупа групою.
  • Проблема вільності матричної напівгрупи алгоритмічно нерозв'язна для цілочисельних матриць починаючи з n = 3 і відкрита для n = 2.

Інші проблеми[ред. | ред. код]

Проблеми, алгоритмічна нерозв'язність яких не доведена[ред. | ред. код]

Для деяких задач не вказано алгоритм, що вирішує їх, і за своєю природою вони схожі на відомі алгоритмічно нерозв'язні завдання. Питання щодо алгоритмічної розв'язності таких задач є відкритими питаннями. Ось деякі з таких завдань:

  • Аналог десятої проблеми Гільберта для рівнянь ступеня 3
  • Аналог десятої проблеми Гільберта для рівнянь в раціональних числах[7]
  • Проблема вмираючої матриці для матриць порядку 2

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Life Universal Computer
  2. When is a pair of matrices mortal?
  3. 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. 
  4. Christian Choffrut; Juhani Karhumäki (2005). Some decision problems on integer matrices.. ITA. 39(1): 125–131. doi:10.1051/ita:2005007. 
  5. Наявність такого архіватора дозволило б обчислити колмогоровську складність довільного рядка, що є алгоритмічно нерозв'язним завданням.
  6. Зокрема, він замінював би будь-який алгоритм що не зупиняється на тривіальний порожній цикл, а розпізнавання таких алгоритмів еквівалентно проблемі зупинки і є алгоритмічно нерозв'язним завданням.
  7. Успенський В. А., Семенов А. Л. Алгоритмічні проблеми, що можна і не можна вирішити. // Журнал Квант, 1985, № 7, с. 9—15.