Соотношение разрешимых проблем

20

Рассмотрим проблемы решения, изложенные на каком-то «разумном» формальном языке Скажем, формулы в арифметике Пеано высшего порядка с одной свободной переменной в качестве системы отсчета, но я в равной степени заинтересован и в других моделях вычислений: диофантовых уравнениях, словесных задачах при переписывании правил с использованием машин Тьюринга и т. Д. Ответ выражается в любом Классическая формализация была бы хороша, хотя, если вы знаете, насколько выбор формализации влияет на ответ, это также было бы интересно.

Учитывая длину от постановки задачи принятия решения, мы можем определить число из разрешимых утверждений длины и числа неразрешимых утверждений длины .ND(N)NU(N)N

Что известно об относительном росте и ? Другими словами, если я случайно выберу правильную задачу решения, какова вероятность того, что она будет разрешима для данной длины оператора?U(N)D(N)

Вдохновленный этим вопросом, который задает вопрос, «большинство ли проблем и алгоритмов разрешимы». Ну, если вы не фильтруете по интересам, не так ли?

Жиль "ТАК - перестань быть злым"
источник
4
Итак, вы по существу спрашиваете, насколько большая часть описываемых языков разрешима? Если мы рассмотрим все языки, то эта доля, очевидно, равна 0, так как существует несчетное количество языков.
Алекс тен Бринк
@AlextenBrink Точнее, я спрашиваю, насколько большая часть языковых описаний являются разрешимыми языками. Это может иметь значение: количество эквивалентных описаний языка коррелирует с его разрешимостью. PS Не стесняйтесь редактировать мой вопрос, если вы не думаете, что он выражен четко.
Жиль "ТАК ... перестать быть злым"
5
Это кажется каким-то образом связанным (и более сложным) с константой Чейтина, но мне еще предстоит найти способ сказать, что не вычислимо. en.wikipedia.org/wiki/Chaitin's_constantD(N)
jmad
1
связанный вопрос: какова вероятность того, что случайная машина Тьюринга с n состояниями разрешима?
Kaveh
2
Вот аналогичный вопрос по математике : плотность остановки машин Тьюринга
Kaveh

Ответы:

2

См. Исследование Чейтина по Омеге, которое, насколько я понимаю, показывает, что неразрешимые проблемы [перефразируют] довольно многочисленные, распространенные или плотные среди утверждений, выбранных случайным образом. Однако вы должны быть осторожны при определении и потому что они могут быть фактически невычислимыми функциями. Есть также некоторые связи с занятыми исследованиями бобра . Идентификация разрешимых и неразрешимых утверждений кажется вполне аналогичной доказательству того, что занятые бобры останавливаются или не останавливаются. (например, некоторые из всех утверждений имеют вид «занятый бобер [x] останавливается»).U(N)D(N)

ВЗН
источник
1
Обе функции, конечно, вообще не вычислимы. Однако не исключено нахождение явных границ для их асимптотического отношения, так же как можно найти границы для числа несжимаемых строк размера n.
Коди