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

18

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

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

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

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

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

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

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

pbaren
источник
4
Предположим , что ваши описания функций приведены в двоичной системе , то есть не более 2L+11 из длины описания в большинстве L . Но теперь проблема в том, что в отличие от полиномов, две различные вычислимые функции могут легко принимать одинаковые значения на бесконечном числе входных данных. Таким образом, ваша проблема кажется мне невозможной.
Бруно
Я понимаю вашу идею. Но две различные вычислимые функции длины описания <= L должны отличаться в некоторой точке (для некоторого n0). Можно ли найти значение n0 для данного L?
Пбарен
4
Вы можете найти такую ​​точку, если она существует, просто вычислите функции для всех значений, используя ласточкин хвост, но если этого не произойдет, вы никогда не узнаете, что это неразрешимо, длина верхней границы размера программы ничего не меняет.
Каве
7
На самом деле, @Kaveh, по вашему собственному аргументу, верхняя граница говорит вам кое-что о том, где они различаются, но не что-то вычисляемое. Если K ( f ) L и f g , то K ( x ) 2 L + c, где c - длина алгоритма, который вы (@Kaveh) описали, а x - первая строка, в которой f и g различаются. В частности, хK(f)K(f)LfgK(x)2L+ccxfgxограничен некоторой Busy-beaver-подобной функцией . Однако найти все x такие, что K ( x ) 2 L + c или вычислить BB, все еще не вычислимо. Итак, @pbaren: граница есть, но она гораздо больше, чем просто экспоненциальная, она неисчислима. 2L+cxK(x)2L+c
Джошуа Грохов
6
@Kaveh: Это то, что я имел в виду под функцией «Busy-beaver-like»: пусть будет длиной самой длинной строки, чья колмогоровская сложность (исправить универсальную машину) не больше n . Существует только конечное число таких строк, так что это четко определено до выбора универсальной машины. Тогда B B ( 2 L + c ) является верхней границей: если две (полностью вычислимые) функции колмогоровской сложности не более, чем L, сходятся во всех точках до длины B B ( 2 L + c )BB(n)nBB(2L+c)LBB(2L+c)тогда они равны.
Джошуа Грохов

Ответы:

9

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

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

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

Диего де Эстрада
источник
7

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

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

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

m1ϵ(d+log1/δ)
f

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

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

Аарон Рот
источник
3

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

Рассмотрим семейство функций , где f i определяется как функция f i ( x ) = 1, если i = x, и f i ( x ) = 0, если i x . Обратите внимание, что колмогоровская сложность вычислений f i составляет около lg | N | биты, так как вы можете жестко закодировать значение IF={fi:iN}fifi(x)=1i=xfi(x)=0ixfilg|N|iв исходном коде, а затем все, что вам нужно, это простой условный оператор ( дополнительно).O(1)

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

DW
источник
0

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

Зируй Ван
источник
1
У вас есть верное замечание, что идея проверки программы путем ее запуска в нескольких случаях не будет работать вообще.
Цуёси Ито