При наличии программы и входных данных она останавливается или запускается навсегда?
Известно, что некоторые проблемы неразрешимы, но, тем не менее, можно добиться определенного прогресса в их решении. Например, проблема остановки неразрешима, но можно добиться практического прогресса в создании инструментов для обнаружения потенциальных бесконечных циклов в вашем коде. Проблемы с...
Я знаю, что проблема остановки вообще неразрешима, но есть некоторые машины Тьюринга, которые явно останавливаются, и некоторые, которые явно не делают. Из всех возможных машин Тьюринга самая маленькая, где никто не может доказать, останавливается она или...
Известно, что с помощью счетного набора алгоритмов (характеризуемых числом Гёделя) мы не можем вычислить (построить двоичный алгоритм, который проверяет принадлежность) все подмножества N. Доказательство может быть обобщено следующим образом: если бы мы могли, то множество всех подмножеств N было...
Мне было интересно, есть ли хорошая библиография попыток исследовать гипотезу Коллатца как формальную грамматику? (или любые другие попытки в сообществе CS иметь дело с этим классом порождающих явлений и их «препятствующими»...
Я жду определенного ответа на заглавный вопрос. Существует ли набор правил, который переводит любую программу в конфигурацию конечных фигур на бесконечной доске, например, если черно-белые играют только легальные ходы, игра заканчивается за конечное время, если программа останавливается? Правила те...
Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи,...
Есть ли машина Тьюринга, которая может решить, остановятся ли почти все другие машины Тьюринга? Предположим, у нас есть некоторое перечисление машин Тьюринга и некоторое представление о «размере» набора натуральных чисел ‖ ⋅ ‖ , и мы определяем:N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\|...
Конструктивная теория типов с ее базовой интерпретацией под соответствием Карри Ховарда состоит только из полных вычислимых функций. В литературе некоторые говорили об использовании «теории вычислительных типов» для представления не-завершения в функциональных программах, но в работах, с которыми я...
Поскольку оба доказательства используют диагональный аргумент, мне интересно, существует ли неясная связь между существованием несчетных бесконечных множеств и неразрешимостью проблемы остановки. Была бы решаема проблема остановки, если бы все множества были...
У меня наивный вопрос: существует ли машина Тьюринга, завершение которой истинно, но недоказуемо какой-либо естественной, последовательной и конечно аксиоматизируемой теорией? Я прошу простое доказательство существования, а не конкретный пример. Это может быть связано с порядковым анализом ....