Halten der Problemtheorie vs. Praxis

Question

Es wird oft behauptet, dass das Halteproblem unentscheidbar ist.Und es ist in der Tat nicht trivial.

aber nur für ein willkürliches Programm.

gab es eine Studie in Bezug auf Studienklassen, die Menschen normalerweise machen?

Es kann manchmal leicht sein, ein Programm zu analysieren und alle seine Freiheitsgrade aufzählen und zu dem Schluss zu schließen, dass er halt wird.

hat beispielsweise jemals eine Anstrengung, eine Programmiersprache (wirklich Skripting wirklich) zu erstellen, die eingehalten wird?Es wäre nicht weit verbreitet, sondern könnte für Missionskritische Module noch nützlich sein.

Answer 1

Sprachen, die garantiert bleiben, haben einen weiten Verbreitungsverbrauch gesehen. Sprachen wie COQ / AGDA / IDRIS sind alle in dieser Kategorie. Viele viele Typsysteme sind tatsächlich gewährleistet, um beispielsweise das System F oder einen seiner Varianten zu stoppen. Es ist üblich, dass die Häanzheit eines Typensystems zum Abkochen ist, um sich zu beweisen, dass alle Programme darin normalisieren. Eine starke Normalisierung ist im Allgemeinen ein sehr wünschenswertes Eigentum in der Programmiersprache Forschung.

Ich habe in der Praxis nicht viel Erfolg gesehen, um unendlich in der Praxis zu fangen. Euclids Algorithmus ist ein bekanntes Beispiel für eine primitive rekursive Funktion, die nicht unkompliziert ist, um primitiv rekursiv zu sein. Es fehlschlägt die Kontrolleure, die einfach nach einem abnehmenden Parameter suchen (oder ein einfaches Muster der abnehmenden Parameter wie Fötus-Kündigungskontrolle). Um dies mit primitiv rekursiven Kombinatoren zu implementieren, müssen Sie einen Beendigungsnachweis für den Algorithmus als Parameter in der Funktion in der Funktion kodieren.

Ich kann mir keine Ergebnisse für Verfahrenssprachen von der Oberseite meines Kopfes vorstellen, und die meisten Ergebnisse in Funktionssprachen nutzen eine Art Einschränkung, die offensichtlich kündigen, anstatt zu versuchen, eine Art komplexer Analyse durchzuführen, um sicherzustellen, dass mehr natürliche Programme enden.

Answer 2

Es gibt frühere und aktuelle Forschung darüber. Ein solches Problem wird als Kündigungsanalyse , und ein kurzer Blick auf Google (Gelehrter) liefert mehrere alte wie sowie neue Publikationen dazu:

.
1. 2005, Terminierung Analyse von Funktionsprogrammen höherer Ordnung ;
2. 2006, automatisierte Kündigungsanalyse für Haskell < / a>;
3. 2008, Terminierungsanalyse von Logikprogrammen auf der Grundlage von Abhängigkeit Diagramme ;
4. 2010, Schleifen-Zusammenfassung und Terminierungsanalyse ;
5. 2014, Termination Analyse durch Lernen abschließende Programme ;
6. 2015, Terminierungsanalyse mit rekursiven Anrufgraphen ;
7. 2019, statische Terminierungsanalyse für ereignisgesteuerte verteilte Algorithmen < / a>;
8. 2019, Implementierung von Kündigungsanalysen zur Quantenprogrammierung ;

einschließlich vorhandener Sprachen mit integrierten Mechanismen dafür wie:

• Mercury ; .
• idris, coq, agda;

Answer 3

Microsoft has developed a practical code checker (whose name escapes me at the moment) which performs halt-testing. It exploits the fact that the code it checks is human-written and not arbitrary, just as you suggest. More importantly, it bypasses the impossibility proof by being allowed to return the answer 'Cannot decide' if it runs into code too difficult to check.

Answer 4

There are only 2 types of infinite programs:

1. Those that repeat their own state after a point (cyclical)
2. Those that grow indefinitely in used memory

Those in 1st type, follow this pattern:

Where there is a pair of distinct indices i and j such that xi = xj, and after which the cycle repeats itself again (thanks to the deterministic nature of programs). In this case the inputs x, contain the whole memory and variables used by the algorithm, plus the current instruction pointer.

Cycle detection algorithms work very well in practice for this type and can prove that a given cyclical program will never finish, usually after a small number of steps, for most random programs.

Proving those in the 2nd type is where the challenge is. One could argue that type 2 can never exist in reality (as all computers have finite memory) but that is not very useful in practice because the memory used may grow very slowly for a regular computer to ever be full. A simple example of that is a binary counter that never stops and never repeats its full state completely.

Answer 5

There is a huge class of functions that are trivially guaranteed to halt: Everything with a finite number of loops, with an upper limit for the number of iterations for each loop determined before the loop is started.

If you have a random program, it can be difficult to prove whether or not it halts. Programs that are written for a purpose are usually much easier.

Answer 6

The smart contracts functions in the Ethereum blockchain are an example of a system that needs the guarantee of halting, not to stall the whole chain.

Every function has a gas cost, and the gas cost translates into real Ethereum coins. A transaction fee must be paid to call the contract. If the gas used in the contract exceed the gas paid with the transaction fee, the computation terminates immediately.