Staat und Zeit transending Logik und Programmablauf?
https://stackoverflow.com/questions/163492
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Frage mich, ob es überhaupt jeden möglichen Zustand einer Anwendung Index mit einigen Referenzschlüssel nützlich wäre ...
Bedeutung, sagen wir ein Programm, das beginnt nur so viele mögliche Ergebnisse, sagen 8.
aber wenn jedes Ergebnis erreicht wird durch viele weitere Logikzustände treten durch, und zwischen jedem Zweig betrachtet wird, ein Staat zu sein und ist mit einem Schlüssel zugeordnet.
Es könnte vielen Speicher in großen Programmen nehmen, aber wenn wir direkt einen Schlüssel zugreifen können (der Schlüssel könnte auf Zeit oder Tiefe der Logik basieren), dann könnten wir sofort durch eine der möglichen Situationen durchqueren, ohne starten zu müssen der gesamte Prozess immer wieder mit neuen Daten.
Denken Sie daran, wie ein Baum, in dem der Knoten ohne Kinder Endergebnisse ist, und jeder Zweig zwischen einem Knoten und seinen Eltern oder Kindern ist ein ‚Staat‘, die jeweils unterschiedlich verkeilt. So, während es nur 8 Blätter oder endgültige Ergebnisse des Prozesses sind, könnte es viele ‚Staaten‘ sein, je nachdem, wie tief die Logik geht hinunter den Baum, bevor er aus Kindern ausgeführt wird.
Vielleicht für Simulationen, aber es wäre eine Tonne Speicherplatz verbrauchen.
Lösung
Ryan, die Antwort ist definitiv ja.
Im Gegensatz zu der ersten Antwort, das Halteproblem beweist gar nichts. In der Tat, Ryan, was Sie vorschlagen beweist das Halteproblem falsch gilt nicht für echten digitalen Computer, und ich habe dieses sehr Beispiel als Beweis dafür vor verwendet.
In einem deterministischen digitalen System (das heißt ein Programm auf realen digitalen Hardware ausgeführt wird), die Anzahl der möglichen Zustände ist endlich, und damit alle möglichen Zustände sind zählbare.
Die genaue Menge an Speicher für den Hash erforderlich wäre:
(2)*(program state size)*(number of initial states)
Der Anfangszustand würde Ihr Hash-Schlüssel sein, und Endzustand würde der Hash-Wert sein, und dann würden Sie ein Schlüssel / Wert-Paar für jeden Anfangszustand haben.
für ein Betriebssystem, der „Programmzustand size“ ist 2 ^ (total Gigabits Speicher über alle Systemgeräte). Offensichtlich ein so großes Allzweck-Programm wäre eine unpraktische Größe des Speichers Hash erfordern und wäre ohnehin nicht sinnvoll sein, da ich das System selbst verweis / nicht reduzierbar komplex (dh nächste Benutzereingabe auf früherem Systemausgang abhängt).
Erklärung:
Dies ist sehr nützlich, denn wenn man Index alle möglichen Anfangszustand und assoziieren sie mit dem Abschluss Zustand, würden Sie die Laufzeit eines Programms effektiv bringen Null! Jede von Null meine ich eine sehr schnelle O (1) Laufzeit -. Die Zeit, die den Abschluss Zustand zu sehen (wenn es beendet wird)
Ausführen eines Programms, von jedem aller möglichen Zustände beginnen, wird zeigt Zyklen eine Art Zustandskarte zur Verfügung stellen. Das Halteproblem ist daher gelöst, weil es nur drei (eigentlich vier Kollabieren zu drei) Möglichkeiten gegeben jeden möglicher Ausgangszustand ist:
- Das Programm wird einen zuvor angetroffenen Zustand (seit dem Anfangszustand), bevor Ausschöpfung aller möglichen Zustände und daher logisch neu eingeben Schleifen für immer.
- Das Programm erreicht einen Zustand als „Abschluss“ identifiziert, bevor es eine Chance hat, einen zuvor angetroffenen Zustand oder erschöpfen alle möglichen Zustände (seit dem Anfangszustand). erneut eingeben
-
oder 4. Das einfachste Programm von einem Anfangszustand beginnen, wird alle möglichen Zustände genau einmal eingeben und dann keine andere Wahl hat, aber bis (3) Halt oder (4) erneut eingeben einen zuvor angetroffenen Zustand und Schleife für immer .
for (int i = 0; true; i ++); // Ich werde max-Wert erreichen, rollen zurück auf Null, an dem Punkt der sie den Ausgangszustand erneut eingegeben haben
Also, im Grunde Ihr Index wie folgt beschrieben werden:
- Für jeden Anfangszustand gibt es genau eine oder Null beendet Staaten.
Mit anderen Worten, für jeden Ausgangszustand, das Programm entweder erreicht einen Abschlusszustand oder ein Zustand tritt wieder seit dem Anfangszustand und Zyklen endlos bereits begegnet.
Also, für jedes Programm läuft auf deterministische digitale Hardware , ist es absolut möglich (aber oft nicht praktikabel ) alle seine Zustände zu bestimmen, und ob es hält oder Schleifen für immer.
- Die Praktikabilität hängt einzig und allein von der Anzahl der gültigen Anfangszuständen Sie haben (die Sie reduzieren können drastisch mit Eingabebedingungen), und wie machbar es ist die Zeit, um das Programm für jeden von ihnen zu laufen Kündigung und speichern den resultierenden Zustand in der Hash-Tabelle.
Neben jedem Programm, Laufzeit eines O Forcing (1) Betrieb, andere Verwendungen von Staat Erfassung umfassen die save-Zustandsfunktion in Spielkonsole Emulatoren und Hibernate-Funktion von Computern (wenn auch nicht eine perfekte Wiederherstellung des Zustandes, da einige Systemspeicher muss für den Code verwendet werden, die nie (zB GPU-Speicher)) gespeichert werden können, um den Zustand und einige Speicher wieder her.
Was dies beweist, ist, dass jedes Programm kann durch eine Hash-Tabelle dargestellt werden. Jedes Programmkann durch eine anfängliche-to-Endzustands-Übergang Karte dargestellt werden. Alle Programme können mit einem massiven Speicher-Footprint zu einer großen Funktion vereinfacht werden!
Andere Tipps
Dies wäre nicht möglich, dass ein allgemeines Programm zu lösen. Das Halteproblem beweist, dass unmöglich ist, zu bestimmen, ob ein Programm anhalten wird. Das Problem der Bestimmung, ob ein bestimmte Zustand möglich ist reduzierbar auf das Halteproblem, also entweder nicht auflösbar.
Ich denke, dieser Ansatz völlig unlösbar wäre für, na ja, alles.
Als Suchproblem, es ist zu groß. Wenn wir, dass jeder Zustand annehmen kann bis zu 10 Ergebnissen führen (obwohl ich diese Zahl denke wirklich gering ist), dann schaut nur 20 Schritte voraus, wir jetzt den Überblick über 200 Milliarden Möglichkeiten zu halten haben.
Und denken Sie daran, dass jeder Schritt in einer Schleife zählt als Verzweigungspunkt. Wenn wir also einen Code, der wie folgt aussieht:
for (int i=0; i < 100; i++)
some_function();
Dann ist die Anzahl der möglichen Zustände ist (Anzahl der Verzweigungen innerhalb some_function) ^ 100
Während Josh richtig ist, dass Sie nicht das liberalste Version dieses Problem aufgrund der Mehrdeutigkeit beantworten können, können Sie sie beantworten, wenn Sie einige Einschränkungen auf Ihrem Szenario platzieren. Es gibt einen großen Unterschied zwischen dem Zustand des Programms und dem Stand der Mitsprachegeschäftseinheiten.
Zum Beispiel, sagen Sie eine Workflow-orientierte Anwendung, die von einem DFA (State Machine) definiert ist. Sie könnten tatsächlich dann mit einer ID von einer Art einen bestimmten Punkt in diesen DFA zuordnen.
Also ja, es ist lenkbar, aber nicht ohne Einschränkungen.
Dies ist auf der Funktionsebene durchgeführt; es ist eine Technik namens memoization .
Forschung kripke Strukturen und Modallogik. Dies ist ein Ansatz bei der Modellierung Programmen gemacht. Ich vergesse, was die klassischen Systeme, die diesen Ansatz verwenden sind.
