Oder es gibt einen allgemeinen Algorithmus für ein Problem beim Herunterfahren.
Aber wie immer gibt es Nuancen.
Bei Interesse bitte ich um Katze.
Einführung
1936 bewies Alan Turing, dass es keinen allgemeinen Algorithmus gibt, der andere Algorithmen analysiert und angibt, ob das Programm hängen bleibt oder nicht.
Ich möchte sofort alle e punktieren und die von mir verwendeten Begriffe beschreiben, damit es kein Verständnis gibt.
Programm friert ein - der Algorithmus arbeitet unendlich lange, unabhängig von der Geschwindigkeit der Befehlsausführung und der parallelen Datenverarbeitung. Egal wie groß ein Supercomputer ist, der Algorithmus läuft immer unendlich lange.
Ausführen eines Programms in einer endlichen Zeit - der Algorithmus auf jeder Maschine beendet seine Berechnungen, egal wie umfangreich sie sind. Wenn ein Algorithmus beispielsweise 300 Millionen Jahre lang ausgeführt wird, bedeutet dies nicht, dass er einfriert. Er muss lediglich 300 Millionen Jahre lang mit aktuellen Ressourcen ausgeführt werden und endet IMMER.
Jetzt können Sie fortfahren.
Turings Beweis kann wie folgt beschrieben werden: Es gibt ein bestimmtes Orakel S (Algorithmus), an dessen Eingabe eine Beschreibung des Algorithmus N und der Eingabedaten X bereitgestellt wird. Das Programm stoppt und gibt 1 zurück, wenn der Algorithmus N nicht stoppt, und empfängt X am Eingang.
Das Programm stoppt nicht anders, wenn der Algorithmus N nach dem Empfang einer Eingabe X stoppt. Wenn wir unsere Beschreibung von uns unserem Orakel zuführen, gibt es einen Widerspruch und der Algorithmus widerspricht sich selbst. Details finden Sie im
Wiki .
Oracle existiert, aber er braucht einen Bruder
Sie sind nicht verwirrt von der Tatsache, dass das Orakel einfrieren sollte, wenn der von ihm analysierte Algorithmus stoppt. Ich bin direkt verwirrt von dieser Tatsache. Zum Beweis werden wir die Schlussfolgerung des Orakels leicht korrigieren. Lassen Sie das Orakel 1 oder 0 zurückgeben. Nun, Sie fragen, nichts hat sich geändert, wenn wir auf den Pseudocode schreiben:
If ((N)==0){
While (true){
}
}
, , :
, , :
S1 0 1 0 1 , .
S2 0 1 , . 1 1 , 0 . 0 , 1 .
, . .
, , . , , .
, . , .
:
If ((N)==0){
While(true){
}
}
If ((N)==0){
While(true){
}
}
.
.
, . , . - , .
, , . , .