Um zu beantworten, "welche Probleme durch Rechnen gelöst werden können", haben wir die Theorie der Berechenbarkeit entwickelt. Gibt es für die berechenbaren Probleme eine Theorie zur Beantwortung der Frage "Ist das Programm, das ich bekomme, das einfachste?"
Ich glaube nicht, dass die Komplexität der Berechnungen die Frage beantwortet. Ich denke, es wird überlegt, wie lange wir brauchen (obwohl abstrakt gemessen).
Ich bin nicht sicher, ob die algorithmische Informationstheorie die Frage beantwortet. Es scheint, dass die Theorie über Größe spricht, wo die Äquivalenz von minimaler Größe und einfachster für mich nicht offensichtlich ist (zumindest fühlen sie sich für mich anders an).
Ich denke, die Theorie sollte zumindest "einfache" oder "einfachere als" Beziehung definieren.
Ich bin jetzt überzeugt, dass ich mich mit Kolmogorov-Komplexität befassen sollte. Ich möchte jedoch erklären, was ich dachte, als ich die Frage stellte.
Wenn ich ein Programm verbessere, versuche ich, unnötige Verbindungen zwischen verschiedenen Teilen des Programms zu reduzieren (möglicherweise Teile neu zu teilen, damit es weniger oder schwächere Verbindungen geben kann). Da die Verbindungen reduziert sind, fühlt sich das Programm "einfacher" an. Daher die Wahl des Wortes "einfach", wenn ich die Frage formuliere. Es ist sehr wahrscheinlich, dass auch die Größe des Programms abnimmt, aber das ist ein guter Nebeneffekt, nicht das Hauptziel. Offensichtlich kann der Verbesserungsprozess nicht ewig dauern. Es gibt einen Punkt, an dem ich aufhören sollte. Wenn ich mich nur unter Berücksichtigung der "Struktur" (Entschuldigung für ein anderes undefiniertes Konzept) oder der "Beziehung" davon überzeugen kann, dass nichts mehr getan werden kann?
Hier enthält eine bessere Beschreibung meines Begriffs von Komplexität.
Olaf Sporns (2007) Komplexität . Scholarpedia , 2 (10): 1623
Antworten:
Dieses Problem wird in der Algorithmic Information Theory untersucht. Was Sie definieren, heißt Kolmogorov-Chaitin-Komplexität.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
Und es scheint, dass der Begriff der Einfachheit, den Sie benötigen, über den Begriff des Komplexitätsmaßes formalisiert werden kann, der durch Blums Axiome formalisiert wird.
http://en.wikipedia.org/wiki/Blum_axioms
Es scheint auch möglich zu sein, Kolmogorovs Komplexität zu verallgemeinern, um andere Komplexitätsmaßnahmen zu berücksichtigen. Siehe Referenz unten. (Der Wikipedia-Artikel über die Komplexität von Kolmogorov befasst sich mit diesem Problem.)
Burgin1990 - Verallgemeinerte Kolmogorov-Komplexität und andere Maßnahmen zur doppelten Komplexität Kybernetik und Systemanalyse Band 26, Nummer 4, 481-490
quelle
Die Antwort auf die erste Frage lautet: Ja, es gibt eine Theorie, es ist eine algorithmische Informationstheorie, und diese werden als elegante Programme bezeichnet (von Gregory Chaitin).
Für die zweite Frage zu "Ist das Programm, das ich bekomme, das einfachste"?
Es gibt keine Antwort , da es sich um eine nicht berechenbare Frage handelt. Es ist nicht möglich zu beweisen, dass ein Programm ein elegantes Programm ist.
Ich habe eine Antwort gegeben, um die Erwähnung über elegante Programme hinzuzufügen .
quelle
Es gibt verschiedene Ansätze, um zu entscheiden, was ein einfacher Code ist und was nicht.
Leider gibt es keine automatische Methode, um dies zu bestimmen. Beispielsweise schlägt die Kolmogorov-Komplexität mit rekursiven Funktionen fehl. Einige rekursive Funktionen (logisch tief) sind einfach, aber das Verständnis dafür ist nicht so einfach.
Nach meiner Erfahrung arbeitete unser Team in einem System und wir fanden ein "einfaches" Verfahren in Oracle (nicht mehr als 50 Zeilen) ... und wir versuchten es zu verstehen, es dauerte 2 Monate (und mehrere Besprechungen), um es vollständig zu verstehen es nicht durch die Komplexität des Codes, sondern durch die Logik hinter jeder Variablen.
Ich denke, der Weg, um festzustellen, wie einfach ein Code ist, ist: "Lesen Sie einen Code und berücksichtigen Sie die Zeit, die benötigt wird, um ihn zu verstehen."
Also "Das einfachste Programm, um ein Problem zu lösen?" kann unterteilt werden in:
a) Einfachheit des Codes (klarer Code), aber zu subjektiv.
b) Überkomplexität der Funktion, wenn ich ein X-Problem habe, muss ich die DX (Delta X) -Aufgabe lösen, um es zu lösen, wobei DX zu X tendieren muss.
Zum Beispiel, wenn mein Problem (eins) ist "einen Apfel schälen" und ich muss es dann in PHP (und Sprache) tun
Wenn ich sehr viel Glück habe und PHP die Funktion function_peel_apple () hat, dann ist es der einfachste Code aller Zeiten. X = 1 DX = 1, rufe einfach die Funktion auf und fertig!.
Im Gegenteil, wenn ich nicht so viel Glück habe, aber die Funktion function_peel () und function_get_apple () existiere, dann ist X = 1 (ein Problem) und DX = 2 (zwei Aufgaben).
Wenn im schlimmsten Fall keine Funktion vorhanden ist, muss ich eine (oder mehrere) selbst erstellen und mehrere Aufgaben hinzufügen, bevor das Problem gelöst werden kann. Das ist jetzt ein komplexes Programm.
quelle