Шешілмеген мәселелер тізімі - List of undecidable problems

Жылы есептеу теориясы, an шешілмейтін мәселе түрі болып табылады есептеу проблемасы иә / жоқ деген жауап қажет, бірақ әрқашан дұрыс жауап беретін кез-келген компьютерлік бағдарлама болуы мүмкін емес; яғни кез-келген ықтимал бағдарлама кейде қате жауап береді немесе ешқандай жауап бермей мәңгі жұмыс істейді. Ресми түрде шешілмейтін проблема - бұл а рекурсивті жиынтық; мақаланы қараңыз Шешімді тіл. Сонда есепсіз көптеген шешілмейтін мәселелер, сондықтан төмендегі тізім міндетті түрде толық емес. Шешімсіз тілдер рекурсивті тіл болып табылмаса да, олар болуы мүмкін ішкі жиындар туралы Тьюринг танылатын тілдер: яғни, мұндай шешілмейтін тілдер рекурсивті түрде санауға болады.

Математикадағы көптеген шешілмейтін мәселелерді қоюға болады сөз проблемалары: таңбалардың екі жолдары (қандай да бір математикалық тұжырымдаманы немесе объектіні кодтау) бір объектіні бейнелейтінін немесе көрсетпейтінін анықтау.

Аксиоматикалық математикадағы шешілмегендік үшін қараңыз ZFC-де шешілмейтін мәлімдемелер тізімі.

Мәселелер логика

Туралы мәселелер дерексіз машиналар

  • The мәселені тоқтату (а. немесе жоқтығын анықтау) Тьюринг машинасы берілген кірісті тоқтатады) және өлім проблемасы (әрбір бастапқы конфигурация үшін тоқтайтындығын анықтау).
  • Тьюринг машинасы а бос күндіз чемпион (яғни күйлер мен символдар саны бірдей тоқтап тұрған Тьюринг машиналарының ішінде ең ұзақ жұмыс істейді).
  • Күріш теоремасы ішінара функциялардың барлық нетривиалды қасиеттері үшін берілген машинаның осы қасиетпен ішінара функцияны есептей ме, шешпейтінін айтады.
  • Тоқтату а Минск машинасы: кірістері жоқ ақырлы күйдегі автомат және екі есептегіш, оны көбейтуге, азайтуға және нөлге тексеруге болады.
  • Нететерминистің әмбебаптығы Түсіру автоматы: барлық сөздердің қабылданатынын анықтау.

Туралы мәселелер матрицалар

  • The матрицалық проблема: анықталған, жиынтығы берілген n × n матрицалар, егер олар қандай-да бір тәртіппен көбейтілуі мүмкін болса, мүмкін қайталану арқылы нөлдік матрица. Бұл алты немесе одан да көп 3 × 3 матрицалар жиынтығы немесе екі 15 × 15 матрицалар жиынтығы үшін шешілмейтін болып саналады.[3]
  • Теріс емес бүтін жазбалары бар жоғарғы үшбұрышты 3 × 3 матрицалардың ақырлы жиынтығы еркін тудыратындығын анықтау жартылай топ.
  • Ақырғы құрылған екі кіші топтың бар-жоғын анықтау Мn(З) жалпы элементі бар.

Мәселелер комбинаторлық топ теориясы

Мәселелер топология

Талдаудағы мәселелер

  • Белгілі бір сыныптардағы функциялар үшін анықтау мәселесі: екі функцияның тең екендігін, нөлдік эквиваленттік есеп деп аталады (қараңыз) Ричардсон теоремасы );[4] функцияның нөлдері; функцияның анықталмаған интегралы класта да бар ма.[5] Әрине, бұл мәселелердің кейбір кіші сыныптары шешімді болып табылады. Мысалы, трансцендентальды элементар функциялар өрісіне жататын кез-келген функцияны элементарлы интеграциялау үшін тиімді шешім процедурасы бар Risch алгоритмі.)
  • «Бастапқы мероморфтық функцияның анықталған контурлық еселік интегралының аналитикалық болатын барлық жерде нақты аналитикалық коллекторда нөлге тең болатындығын шешу мәселесі», нәтижесі MRDP теоремасы шешу Гильберттің оныншы мәселесі.[5]
  • Ан ерітіндісінің анықталу облысын анықтау қарапайым дифференциалдық теңдеу форманың
қайда х Бұл вектор жылы Rn, б(т, х) - векторы көпмүшелер жылы т және х, және (т0, x0) тиесілі Rn + 1.[6]

Басқа проблемалар

  • The Хат алмасу мәселесі.
  • Берілген жиынтығын анықтау мәселесі Ван плиткалары жазықтықты плиткалауға болады.
  • Мәселе а тег жүйесі тоқтайды.
  • Анықтау проблемасы Колмогоровтың күрделілігі жіптің
  • Гильберттің оныншы мәселесі: диофант теңдеуінің (көп айнымалы көпмүшелік теңдеудің) бүтін сандармен шешімі бар-жоғын шешу мәселесі.
  • Егер анықталса контекстсіз грамматика барлық мүмкін жолдарды тудырады, немесе егер ол түсініксіз болса.
  • Екі контекстсіз грамматиканы ескере отырып, олардың бір жолдар жиынтығын құратынын немесе біреуінің екіншісі жасаған жолдардың ішкі жиынын құратынын немесе екеуі де тудыратын жолдардың бар-жоғын анықтау.
  • Рационалды координаталары бар берілген бастапқы нүктенің периодты болатынын немесе оның берілген жиынтықтың тартылу бассейнінде, екі өлшемді сызықтық қайталанатын картада немесе үш өлшемді бөлшек-сызықтық ағында жатқанын анықтау.[7]
  • A немесе жоқ екенін анықтау λ-есептеу формуланың қалыпты формасы бар.
  • Конвейдің өмір ойыны бастапқы өрнек және басқа үлгі берілген-берілмегендігі туралы, соңғысы алғашқыдан пайда бола алады.
  • 110 ереже - «X» қасиетіне қатысты сұрақтардың көпшілігі кейінірек пайда болады.
  • Кванттық механикалық жүйенің а бар-жоғын анықтау мәселесі спектрлік алшақтық.[8]
  • Ойында ойыншының жеңіске жететін стратегиясы бар-жоғын анықтау Сиқыр: жиналыс.[9]
  • Жоспарлау а Марковтың шешім қабылдау процесі ішінара бақыланады.
  • Саяхатты жоспарлау.

Сондай-ақ қараңыз

Ескертулер

  1. ^ Уэллс, Дж.Б. (1993). «Екінші ретті лямбда-калкулуста типтілік пен типті тексеру баламалы және шешілмейді». Техникалық. 93-011. Есептеу. Ғылыми. Бөлім, Бостон Университеті: 176–185. CiteSeerX  10.1.1.31.3590.
  2. ^ Трахтенброт, Б.А. (1950). «Шектелген домендер үшін шешім алгоритмінің мүмкін еместігі». Doklady Akademii Nauk SSSR (N.S.). 70: 569–572. МЫРЗА  0033784.
  3. ^ Кассейн, Джулиен; Халава, Веса; Харджу, Теро; Николас, Франсуа (2014). «Матрицалық өлімге, шешілмеген мәселелерге және тағы басқаларға қатысты шешілмегендіктің қатаң шекаралары». arXiv:1404.0644 [cs.DM ].
  4. ^ Кит О.Геддес, Стивен Р.Чепор, Джордж Лабан, Компьютерлік алгебра алгоритмдері, ISBN  0585332479, 2007, б. 81ff
  5. ^ а б Сталлворт, Даниэль Т. және Фред В.Роуш Анықталған интегралдардың шешілмейтін қасиеті Американдық математикалық қоғамның еңбектері 125 том, 7 сан, 1997 ж., 2147-2148 беттер
  6. ^ Грача, Даниэль С .; Буеску, Хорхе; Кампаньоло, Мануэль Л. (21 наурыз 2008). «Анықтама доменінің шектілігі полиномдық ODE үшін шешілмейді». Теориялық информатикадағы электрондық жазбалар. 202: 49–57. дои:10.1016 / j.entcs.2008.03.007.
  7. ^ Мур, Кристофер (1990), «Динамикалық жүйелердегі болжамсыздық және шешілмегендік» (PDF), Физикалық шолу хаттары, 64 (20): 2354–2357, Бибкод:1990PhRvL..64.2354M, дои:10.1103 / PhysRevLett.64.2354, PMID  10041691.
  8. ^ Кубитт, Тоби С .; Перес-Гарсия, Дэвид; Қасқыр, Майкл М. (2015). «Спектрлік саңылаудың шешілмейтіндігі». Табиғат. 528 (7581): 207–211. arXiv:1502.04135. Бибкод:2015 ж .528..207С. дои:10.1038 / табиғат 16059. PMID  26659181.
  9. ^ Херрик, Остин; Бидерман, Стелла; Черчилль, Алекс (2019-03-24). «Сиқыр: жиналу аяқталды». arXiv:1904.09828v2. Бибкод:2019arXiv190409828C. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)

Библиография

  • Брукшир, Дж. Гленн (1989). Есептеу теориясы: ресми тілдер, автоматтар және күрделілік. Редвуд Сити, Калифорния: Бенджамин / Каммингс Publishing Company, Inc. С қосымшасында алгоритмдердің грамматикада түсініксіз жайттардың бар-жоғын шешудің мүмкін еместігі және бағдарламаның дұрыстығын алгоритм арқылы Halting Problem мысалы ретінде тексерудің мүмкін еместігі келтірілген.
  • Халава, Веса (1997). «Матрица теориясындағы шешілетін және шешілмейтін мәселелер». TUCS техникалық есебі. 127. Турку информатика орталығы. CiteSeerX  10.1.1.31.5792. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)
  • Морет, Б.М. Е .; Х.Д.Шапиро (1991). Алгоритмдер P-ден NP, 1 том - Дизайн және тиімділік. Редвуд Сити, Калифорния: Бенджамин / Каммингс Publishing Company, Inc. «Алгоритмдерді талдаудың математикалық әдістері» атты 2-тарауда экспоненциалды көрсеткіштері бар алгоритмдерге қатысты мәселелердің шешілмейтіндігін талқылайды.
  • Вайнбергер, Шмюэль (2005). Компьютерлер, қаттылық және модульдер. Принстон, NJ: Принстон университетінің баспасы. Топтар үшін проблема сөзінің шешілмейтіндігі және топологиядағы әр түрлі мәселелер талқыланады.

Әрі қарай оқу

Сыртқы сілтемелер