Können Tests das Fehlen von Fehlern zeigen?

18

(n+1) Punkte sind erforderlich, um ein Polynom des Grades eindeutig zu bestimmenn; Beispielsweise bestimmen zwei Punkte in einer Ebene genau eine Linie.

Wie viele Punkte sind erforderlich, um eine berechenbare Funktion eindeutig zu bestimmen f:NN, angesichts der Länge eines Programms, das f in einer festen Sprache berechnet ? (dh eine Schranke für die Kolmogorov-Komplexität von ).f

Die Idee ist, dass man zumindest theoretisch die Korrektheit eines Programms beweisen kann, indem man genügend Tests durchführt.

Wenn man ein Programm der Länge , das berechnet , gibt es eine Grenze für die Anzahl von Funktionen, die mit einer Quelllänge von höchstens berechnet werden könnenL f LPLfL .

Deshalb müsste man "nur" beweisen, dass:

  • f kann mit einer Quellenlänge L berechnet werdenL
  • berechnet keine andere in L Bytes oder wenigerberechenbare Funktion(durch Testen)PL

Diese Idee hat wahrscheinlich keine praktischen Konsequenzen (die Grenzen sind sicherlich exponentiell).

pbaren
quelle
4
Angenommen , Ihre Beschreibungen der Funktionen in binären gegeben sind, dann gibt es höchstens von Beschreibungslänge höchstens L . Das Problem ist nun, dass im Gegensatz zu Polynomen zwei verschiedene berechenbare Funktionen auf unendliche Weise dieselben Werte für eine unendliche Anzahl von Eingaben annehmen können. So scheint mir dein Problem unmöglich. 2L+11L
Bruno
Ich verstehe deine Idee. Aber zwei verschiedene berechenbare Funktionen der Beschreibungslänge <= L sollten sich irgendwann unterscheiden (für manche n0). Konnte man den Wert von n0 bei L finden?
pbaren
4
Sie können einen solchen Punkt finden, wenn es einen gibt. Berechnen Sie einfach die Funktionen für alle Werte mit Hilfe der Schwalbenschwanzführung. Wenn dies nicht der Fall ist, werden Sie nie wissen, dass es unentscheidbar ist, dass die Länge der Programmgröße nicht überschritten wird.
Kaveh
7
Eigentlich @Kaveh, indem Sie Ihr eigenes Argument, eine obere auf gebunden sagt Ihnen etwas über , wo sie sich unterscheiden, einfach nicht berechenbar etwas. Wenn K ( f ) L und f g , dann K ( x ) 2 L + c wobei c die Länge des Algorithmus ist man (@Kaveh) beschrieben , und x ist die erste Zeichenfolge , auf der f und g unterscheiden. Insbesondere xK(f)K(f)LfgK(x)2L+ccxfgxwird durch eine Busy-Biber-ähnliche Funktion von . Es , alle2L+c so, dass K ( x ) 2 L + c ist oder BB berechnet wird, ist immer noch nicht berechenbar. Also @pbaren: es gibt eine Grenze, aber es ist viel mehr als nur exponentiell, es ist nicht berechenbar. xK(x)2L+c
Joshua Grochow
6
@Kaveh: Das habe ich mit einer "Busy-Beaver-like" -Funktion gemeint: Sei die Länge der längsten Saite, deren Kolmogorov-Komplexität (fix a universal machine) höchstens n beträgt . Es gibt nur endlich viele solcher Saiten, so dass dies bis zur Wahl der Universalmaschine genau definiert ist. Dann ist B B ' ( 2 L + c ) eine Obergrenze: wenn zwei (gesamt berechenbare) Funktionen der Kolmogorov-Komplexität höchstens L in allen Punkten bis zur Länge B B ' ( 2 L + c ) übereinstimmenBB(n)nBB(2L+c)LBB(2L+c)Dann sind sie gleich.
Joshua Grochow

Antworten:

9

(Dies war als Kommentar gedacht, ging aber lange). Sehr interessante Frage. Wenn Sie bereit sind, über andere Komplexitätsmaßnahmen als die von Kolmogorov nachzudenken, gibt es in der Lerntheorie einige Antworten, die Sie zufriedenstellen könnten. Ich überlasse es den Experten auf dem Gebiet.

Wenn ich mich nicht irre, hat Valiant in "Eine Theorie des Lernbaren" bewiesen, dass eine Boolesche Funktion mit einer Polynomzahl von "positiven Punkten" auf der Größe ihrer k-CNF-Formel (für jedes feste k) rekonstruiert werden kann , und ich meine mit "positiven Punkten" diejenigen der Form (x1,,xn,1) ).

In Knuths TAOCP 7.2.1.6 wird auf verblüffende Weise gezeigt (anhand des Weihnachtsbaummusters), dass Sie für die Rekonstruktion einer monote-booleschen Funktion (dh, die in jeder Variablen nicht abnimmt) genau ( n ) benötigen(n+1n/2+1) Punkte.

Diego de Estrada
quelle
7

In Anlehnung an Deigos Antwort besagen die Standardwerte für die Komplexität der Stichproben aus der Lerntheorie, dass Sie, wenn Sie mit der Suche nach einem "ungefähr korrekten" Programm zufrieden sind, nicht viele Punkte ausprobieren müssen. Nehmen wir an, wir kodieren Programme in Binärform, so dass es nur Programme der Länge d gibt. Nehmen wir auch an, dass es eine gewisse Verteilung über Eingabebeispiele D gibt . Vielleicht ist es Ihr Ziel, ein Programm zu finden, von dem Sie sich ziemlich sicher sind, dass es fast richtig ist ("wahrscheinlich ungefähr korrekt", dh wie im Valiants PAC-Lernmodell). Das heißt, Sie möchten einen Algorithmus ausführen, der eine kleine Anzahl von Abtastwerten x D zusammen mit f ( x ) aufnimmt.2dDxDf(x)und wird mit einer Wahrscheinlichkeit von mindestens ein Programm P ausgeben, das mit f in mindestens einem ( 1 - ϵ ) Bruchteil der aus D gezogenen Eingaben übereinstimmt . (1δ)Pf(1ϵ)D

Wir werden einfach Beispiele x D zeichnen und jedes Programm P mit einer Länge d ausgeben, das in allen Beispielen mit f übereinstimmt . (Eine ist garantiert vorhanden, da wir annehmen, dass f höchstens d Kolmogorov-Komplexität hat ) ...mxDPdffd

Wie groß ist die Wahrscheinlichkeit, dass ein bestimmtes Programm , das bei mehr als einem Viertel der Beispiele mit f nicht übereinstimmt, mit den von uns ausgewählten m Beispielen übereinstimmt ? Es ist höchstens ( 1 - ϵ ) m . Wir möchten diese Wahrscheinlichkeit nehmen höchstens sein δ / 2 d , so dass wir eine Vereinigung über alle gebundenes nehmen 2 d Programme und sagen , dass mit einer Wahrscheinlichkeit von mindestens 1 - δ , kein „schlechtes“ Programm steht im Einklang mit unseren gezogen Beispielen . Beim Lösen sehen wir, dass es ausreicht, nur m 1 zu nehmen Pfϵm(1ϵ)mδ/2d2d1δ Beispiele. (dh nur linear viele in der Kolmogorov-Komplexität vonf

m1ϵ(d+log1/δ)
f ...)

Übrigens, Argumente wie dieses können verwendet werden, um "Occam's Razor" zu rechtfertigen: Angesichts einer festgelegten Anzahl von Beobachtungen unter allen Theorien, die sie erklären, sollten Sie diejenige mit der geringsten Kolmogorov-Komplexität wählen, da die geringste Wahrscheinlichkeit einer Überanpassung besteht.

Natürlich, wenn Sie nur ein einziges festes Programm auf diese Weise überprüfen wollen, brauchen Sie nur Beispiele ...O(log(1/δ)/ϵ)

Aaron Roth
quelle
3

Llg|N|f|N|fLlg|N|Bits.

F={fi:iN}fifi(x)=1i=xfi(x)=0ixfilg|N|iO(1)

fiififjijf|N|fi|N|1

DW
quelle
0

Sie können das Programm beliebig lang machen. Sie können also bei jedem Programm entscheiden, ob seine Sprache der Sprache dieses Programms entspricht. Das kann man nach dem Satz von Rice nicht tun.

Zirui Wang
quelle
1
Sie sind der Ansicht, dass die Idee, das Programm durch Ausführen auf mehreren Instanzen zu überprüfen, im Allgemeinen nicht funktioniert.
Tsuyoshi Ito