Может ли тестирование показать отсутствие ошибок?

$(n + 1)$ точек необходимы для однозначного определения многочлена степени ; например, две точки на плоскости определяют ровно одну линию.$n$

Сколько точек требуется для однозначного определения вычислимой функции , учитывая длину программы, которая вычисляет на фиксированном языке? (т.е. оценка колмогоровской сложности ).f $f : N \rightarrow N$$f$$f$

Идея состоит в том, что, по крайней мере теоретически, можно доказать правильность программы, выполнив достаточное количество тестов.

Если есть программа длины , которая вычисляет , существует ограничение на число функций , которые могут быть вычислены с длиной источника не более .L f $P$$L$$f$$L$

Следовательно, нужно «только» доказать, что:

• $f$ может быть вычислено с длиной источника$\leq L$
• $P$ не вычисляет никакую другую функцию, вычисляемую в байтах или меньше (путем тестирования)$L$

Эта идея, вероятно, не имеет практических последствий (границы обязательно должны быть экспоненциальными).

(Это подразумевалось как комментарий, но продолжалось долго). Очень интересный вопрос Если вы готовы подумать о других мерах сложности, кроме Колмогорова, то в теории обучения есть некоторые ответы, которые могут вас удовлетворить. Я оставляю это для экспертов в области.

Например, если я не ошибаюсь, в «Теории обучаемого» Валиант доказал, что булева функция может быть реконструирована по полиномиальному числу «положительных точек» по размеру ее формулы k-CNF (для любого фиксированного k и я имею в виду с «положительными точками» те формы ).$(x_1,\ldots,x_n,1)$

В TAOCP 7.2.1.6 Кнута удивительным образом показано (с использованием шаблона рождественской елки), что для восстановления монотонной булевой функции (т. Е. Неубывания по каждой переменной) вам нужно точно баллов.${n+1 \choose \lfloor n/2\rfloor+1}$

Чтобы продолжить в соответствии с ответом Дейго, стандартные границы сложности выборки из теории обучения говорят вам, что если вы удовлетворены тем, что нашли программу, которая «приблизительно верна», вам не нужно пытаться использовать очень много пунктов вообще. Допустим , мы кодирующая программы в двоичном виде , так что есть только программы длины д. Давайте предположим также , что существует некоторое распределение по входных примеров D . Возможно, ваша цель состоит в том, чтобы найти программу, в которой вы почти уверены, что она почти правильная («Вероятно, приблизительно правильная», то есть, как в модели обучения PAC Valiants). То есть вы хотите запустить алгоритм, который будет принимать небольшое количество выборок x ∼ D вместе с f ( x $2^d$$D$$x \sim D$$f(x)$И будет с вероятностью , по меньшей мере выходной какая - то программа P , которая совпадает с F , по меньшей мере, ( 1 - е ) доли входов , взятых из D . $(1-\delta)$$P$$f$$(1-\epsilon)$$D$

Мы просто нарисуем примеров x ∼ D и выведем любую программу P длины ≤ d, которая согласуется с f на всех примерах. (Одно гарантированно существует, так как мы предполагаем, что f имеет колмогоровскую сложность не более d ) ...$m$$x \sim D$$P$$\leq d$$f$$f$$d$

Какова вероятность того, что конкретная программа которая не согласна с f на более чем 1/3 части примеров, согласуется с m выбранными нами примерами? Это самое большее ( 1 - ϵ ) м . Мы бы хотели, чтобы эта вероятность была не более δ / 2 d, чтобы мы могли взять объединение, связанное со всеми 2 d программами, и сказать, что с вероятностью не менее 1 - δ ни одна «плохая» программа не согласуется с нашими нарисованными примерами. , Решая, мы видим, что достаточно взять только m ≥ $P$$f$$\epsilon$$m$$(1-\epsilon)^m$$\delta/2^d$$2^d$$1-\delta$ примеры. (то есть только линейно много в колмогоровской сложностиf...)

Кстати, подобные аргументы можно использовать для оправдания «бритвы Оккама»: учитывая фиксированное количество наблюдений, среди всех теорий, которые их объясняют, вы должны выбрать ту, которая имеет наименьшую колмогоровскую сложность, поскольку вероятность переобучения минимальна.

Конечно, если вы хотите проверить только одну фиксированную программу таким образом, вам нужны только примеры ...$O(\log(1/\delta)/\epsilon)$

Вот тривиальный ответ: предполагая, что , тогда вам нужно знать значение f вообще | N | указывает однозначно определить ф . Поэтому подход, который вы набросали, вам совсем не поможет, если только вы не знаете, что длина L программы очень мала: намного короче, чем lg | N | биты.$L \ge \lg |N|$$f$$|N|$$f$$L$$\lg |N|$

Рассмотрим семейство функций , где f i определяется как функция f i ( x ) = 1, если i = x, и f i ( x ) = 0, если i ≠ x . Обратите внимание, что колмогоровская сложность вычислений f i составляет около lg | N | биты, так как вы можете жестко закодировать значение $F=\{f_i:i\in N\}$$f_i$$f_i(x) = 1$$i=x$$f_i(x)=0$$i\ne x$$f_i$$\lg |N|$$i$в исходном коде, а затем все, что вам нужно, это простой условный оператор ( дополнительно).$O(1)$

Однако вы не сможете отличить функцию от функции «все нули», если не протестируете ее на входе i . Вы не можете отличить f i от f j, если вы не проверите на входе i или j . Таким образом, вам нужно оценить F на всех | N | входы, чтобы однозначно определить, с каким f i мы имеем дело. (Хорошо, технически, вам нужно оценить это при | N | - 1 входах, но неважно.)$f_i$$i$$f_i$$f_j$$i$$j$$f$$|N|$$f_i$$|N|-1$

Вы можете сделать программу произвольно долго. Таким образом, для любой программы вы можете решить, является ли ее язык эквивалентным языку этой программы. Вы не можете сделать это по теореме Райс.