Неразрешимая проблема

• Теорема Геделя о неполноте

  • Теорема утверждает, что в любой формальной системе, достаточно мощной для арифметики, существуют утверждения, которые нельзя ни доказать, ни опровергнуть. 
  • Утверждения, которые нельзя ни доказать, ни опровергнуть, называются “неразрешимыми”. 
  • Неразрешимые утверждения могут быть связаны с парадоксами, такими как парадокс лжеца. 

• Проблема остановки

  • Проблема заключается в определении, остановится ли машина Тьюринга на заданном входе. 
  • Алан Тьюринг доказал, что эта проблема неразрешима для машин Тьюринга. 

• Связь с теоремой Геделя

  • Неразрешимость проблемы остановки является следствием теоремы Геделя о неполноте. 
  • Более слабая форма теоремы Геделя утверждает, что полная аксиоматизация натуральных чисел невозможна. 

• Примеры неразрешимых проблем

  • Множество неразрешимых проблем включает логику, абстрактные машины и топологию. 
  • Примеры неразрешимых утверждений включают проблему определения эквивалентности слов в группах и проблему определения всех решений диофантова уравнения. 

• Неразрешимость в теории вычислимости

  • Проблема принятия решения, связанная с ответом “да” или “нет” на бесконечное множество вопросов, также является неразрешимой. 
  • Неразрешимость в этом смысле подразумевает отсутствие вычислимой функции, которая могла бы дать правильный ответ на все вопросы. 

• Спорные вопросы о “абсолютно неразрешимых” утверждениях

  • Существуют философские споры о том, существуют ли утверждения, истинность которых не может быть определена. 
  • Примеры “абсолютно неразрешимых” утверждений включают гипотезу континуума и аксиому выбора. 

• Неразрешимость в информатике

  • Теорема Крускала о дереве и принцип Пэриса-Харрингтона являются примерами неразрешимых утверждений в информатике. 
  • Теорема Гудстайна связана с теорией натуральных чисел Рамсея и также является неразрешимой. 

• Неразрешимость в алгоритмической теории информации

  • Грегори Чайтин доказал, что в любой теории, способной представлять арифметические данные, существует верхняя граница сложности чисел. 
  • Проблема Коллатца и семейство функций EMX, обучаемость которым неразрешима в стандартной теории множеств, являются примерами неразрешимости в этой области.