Оглавление
- 1 Неразрешимая проблема
- 1.1 Неразрешимые задачи в теории вычислимости
- 1.2 Формальное представление задач принятия решения
- 1.3 Связь с теоремой Геделя о неполноте
- 1.4 Примеры неразрешимых проблем
- 1.5 Неразрешимость утверждений
- 1.6 История и развитие
- 1.7 Доказательство невозможности
- 1.8 Непознаваемость
- 1.9 Злая проблема
- 1.10 Записи
- 1.11 Рекомендации
- 1.12 Полный текст статьи:
- 2 Неразрешимая проблема
Неразрешимая проблема
-
Неразрешимые задачи в теории вычислимости
- Неразрешимая задача — это задача принятия решения, для которой невозможно построить алгоритм, всегда приводящий к правильному ответу “да” или “нет”.
- Пример: проблема остановки: не существует алгоритма, определяющего, останавливается ли произвольная программа в конечном итоге.
-
Формальное представление задач принятия решения
- Задача принятия решения — это вопрос, на который для каждого входного сигнала из бесконечного набора входных данных даются ответы “да” или “нет”.
- Формальное представление задачи — это подмножество натуральных чисел.
- Задача называется разрешимой, если формализованное множество является рекурсивным.
-
Связь с теоремой Геделя о неполноте
- Теорема Геделя о неполноте утверждает, что полная и обоснованная аксиоматизация натуральных чисел невозможна.
- Более слабая форма теоремы о неполноте следует из неразрешимости проблемы остановки.
-
Примеры неразрешимых проблем
- Неразрешимые проблемы могут быть связаны с логикой, абстрактными машинами или топологией.
- Примеры: словесная проблема для групп, гипотеза континуума, аксиома выбора, десятая задача Гильберта, проблема остановки, проблема Уайтхеда, принцип Пэриса-Харрингтона, теорема Крускала о дереве, теорема Гудстайна, теорема Чайтина, обобщение задачи Коллатца, обучающая модель EMX.
-
Неразрешимость утверждений
- Неразрешимость утверждения в конкретной дедуктивной системе не решает вопрос о его истинности.
- Неразрешимость подразумевает только то, что рассматриваемая система не доказывает истинность или ложность утверждения.
- Вопрос о существовании абсолютно неразрешимых утверждений остается спорным.
-
История и развитие
- В 1936 году Алан Тьюринг доказал неразрешимость проблемы остановки.
- В 1970 году Юрий Матиясевич показал неразрешимость десятой задачи Гильберта.
- В 1973 году Сахарон Шела доказал неразрешимость проблемы Уайтхеда.
- В 2007 году Курц и Саймон доказали неразрешимость обобщения задачи Коллатца.
- В 2019 году Бен-Дэвид и коллеги показали неразрешимость обучающей модели EMX.
-
Доказательство невозможности
- Утверждается, что невозможно доказать невозможность чего-либо
- Приводятся аргументы в пользу этого утверждения
-
Непознаваемость
- Утверждается, что некоторые вещи невозможно познать
- Приводятся примеры таких вещей
-
Злая проблема
- Упоминается проблема зла
- Обсуждаются её аспекты и последствия
-
Записи
- Приводятся примеры записей
- Обсуждаются их содержание и значение
-
Рекомендации
- Даются рекомендации по теме
- Указываются конкретные шаги для решения проблемы