Рассмотрим проблемы решения, изложенные на каком-то «разумном» формальном языке Скажем, формулы в арифметике Пеано высшего порядка с одной свободной переменной в качестве системы отсчета, но я в равной степени заинтересован и в других моделях вычислений: диофантовых уравнениях, словесных задачах при переписывании правил с использованием машин Тьюринга и т. Д. Ответ выражается в любом Классическая формализация была бы хороша, хотя, если вы знаете, насколько выбор формализации влияет на ответ, это также было бы интересно.
Учитывая длину от постановки задачи принятия решения, мы можем определить число из разрешимых утверждений длины и числа неразрешимых утверждений длины .
Что известно об относительном росте и ? Другими словами, если я случайно выберу правильную задачу решения, какова вероятность того, что она будет разрешима для данной длины оператора?
Вдохновленный этим вопросом, который задает вопрос, «большинство ли проблем и алгоритмов разрешимы». Ну, если вы не фильтруете по интересам, не так ли?
источник
Ответы:
См. Исследование Чейтина по Омеге, которое, насколько я понимаю, показывает, что неразрешимые проблемы [перефразируют] довольно многочисленные, распространенные или плотные среди утверждений, выбранных случайным образом. Однако вы должны быть осторожны при определении и потому что они могут быть фактически невычислимыми функциями. Есть также некоторые связи с занятыми исследованиями бобра . Идентификация разрешимых и неразрешимых утверждений кажется вполне аналогичной доказательству того, что занятые бобры останавливаются или не останавливаются. (например, некоторые из всех утверждений имеют вид «занятый бобер [x] останавливается»).U( N) Д ( Н)
источник