Как доказать отсутствие алгоритма для решения задачи?

Как доказать отсутствие алгоритма для решения какой-либо задачи? Что можно почитать об этом? Заранее спасибо.
  • Вопрос задан
  • 965 просмотров
Решения вопроса 1
arusef
@arusef
Novice .NET dev
В общем случае, задачи такого рода сводятся к, наоборот, доказательству существования алгоритма.
Есть несколько универсальных базовых методов доказательств: от противного, индукция, инвариант, и т.д.

Для решения такой задачи, вам нужно выделить несколько основных тезисов, касающихся вашей проблемы:
1. Исходные данные
2. Варианты возможных действий с ними
3. То, как изменяются данные в процессе
4. Что должно получиться на выходе
Основываясь на этом можно применить вышеуказанные методы, например, предположить, что такой алгоритм существует, или, например, составить шаги индукции и определить, для всех ли случаев выполняются условия. В таком контексте, ваши исходные условия - это аксиомы, они нерушимы и не требуют доказательств. На основе аксиом можно строить некоторые леммы - такие себе "частичные доказательства" - какие-то более сложные положения, которые выводятся из аксиом, и помогают позже в конечном доказательстве. Следует также помнить, что условие доказательства можно искусственно усилить, для того, чтобы легче было доказать всю вашу теорему.
Больше об этом можно послушать в лекциях от MIT.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 4
Найти условие, которое соответствует решению, но не соответствует исходным данным. Или наоборот и справа налево
Ответ написан
@fireSparrow
Имхо, универсального доказательства здесь не может быть.
Только для каких-то конкретных категорий задач, для каждой - своим способом.
Ответ написан
Комментировать
@evgeniy_lm
Ни как.
Задача либо имеет некорректное условие, либо имеет решение.
То что некто не имеет необходимых навыков для решения задачи в данном случае значения не имеет
Ответ написан
Комментировать
@SeptiM
Вы возможно ищете проблему останова? Обычно ее сводят к нужной задаче, тем самым показывая алгоритмическую неразрешимость.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы