Здравствуйте, Codealot, Вы писали:
C>Есть ли хоть один класс задач кроме автореферентных, для которых доказано, что для них нельзя получить результат?
Вообще задачу остановки надо решать несколько иначе. Противоречие основано на том что множество содержи себя внутри себя.
Достаточно потребовать не точного решения да/нет, а определить вероятность остановки.... PROFIT
Здравствуйте, Codealot, Вы писали:
C>Это само собой. Но мне все же интересно, есть ли вообще какие-то виды таких задач, которые не сводятся к самопротиворечивости?
Нет. Все подобные задачи сводятся к противоречию. Вы вольны использовать любое если у вас такие есть в наличии.
Здравствуйте, Codealot, Вы писали:
C>Есть ли хоть один класс задач кроме автореферентных, для которых доказано, что для них нельзя получить результат?
Если ты про математику в целом, то теорема Геделя не накладывает ограничений на автореферентность.
Доказано, например, что гипотеза континуума, независима от ZFC (и это не смотря на всепобеждающую аксиому выбора), т.е. не может быть ни доказана, ни опровергнута в рамках ZFC.
Здравствуйте, Codealot, Вы писали:
C> Есть ли хоть один класс задач кроме автореферентных, для которых доказано, что для них нельзя получить результат?
Да полно, например, неразрешимость Диофантовых Уравнений.
А они эквивалентны алгоритмам.
Или я вопрос не понял.
Здравствуйте, Codealot, Вы писали:
C>Есть ли хоть один класс задач кроме автореферентных, для которых доказано, что для них нельзя получить результат?
Ну, например, невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная. Это автореферентная задача?
Здравствуйте, Pzz, Вы писали:
Pzz>Ну, например, невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная.
Перебором всех возможных генераторов меньших, чем данная последовательность.
Здравствуйте, Pzz, Вы писали:
Pzz>Ну, например, невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная.
Здравствуйте, Codealot, Вы писали:
Pzz>>Ну, например, невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная.
C>а при чем здесь остановка?
Вопрос был, как я его понял, о существовании других алгоритмически неразрешимых задач, кроме проблемы остановки и "похожих" на него.
Здравствуйте, graniar, Вы писали:
Pzz>>Ну, например, невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная.
G>Перебором всех возможных генераторов меньших, чем данная последовательность.
А ты сейчас не предложил ли алгоритм для вычисления Колмогоровской сложности последовательности, которая доказанно алгоритмически неразрешима?
Здравствуйте, Pzz, Вы писали:
Pzz>А ты сейчас не предложил ли алгоритм для вычисления Колмогоровской сложности последовательности, которая доказанно алгоритмически неразрешима?
Предложил. Только с ограничением на длину последовательности. А неразрешима для бесконечности, как и многие другие задачи данного типа. А если вводишь разумные ограничения, то внезапно, они становятся разрешимыми (хоть и не за разумное время).
Здравствуйте, Pzz, Вы писали:
Pzz>Вопрос был, как я его понял, о существовании других алгоритмически неразрешимых задач, кроме проблемы остановки и "похожих" на него.
Нет, вопрос о том, для каких задач нельзя проверить, остановятся они или нет.
Здравствуйте, Pzz, Вы писали:
Pzz>невозможно написать программу, которая глядя на последовательность символов, сможет определить, случайная она или псевдослучайная
Если нельзя обнаружить никакую разницу, то не пофиг ли?
Здравствуйте, Codealot, Вы писали:
C> ·>Да полно, например, неразрешимость Диофантовых Уравнений. C> А как это связано с проблемой остановки?
Эквивалентностью. Вот тут
