Immer wenn Leute nach dem Halteproblem in Bezug auf die Programmierung fragen, antworten die Leute mit "Wenn Sie nur eine Schleife hinzufügen, haben Sie das Halteprogramm und können daher nicht automatisierenAufgabe"

Macht Sinn. Wenn Ihr Programm eine Endlosschleife hat, können Sie bei der Ausführung Ihres Programms nicht wissen, ob das Programm noch Eingaben verarbeitet oder ob es sich nur um eine Endlosschleife handelt.

Aber einige davon scheinen nicht intuitiv zu sein. Was wäre, wenn ich einen Problemlöser schreiben würde, der Quellcode als Eingabe verwendet?rascher@localhost$ ./haltingSolver source.c

Wenn mein Code (source.c) so aussieht:

for (;;) {  /* infinite loop */  }

Es scheint, als wäre es für mein Programm ziemlich einfach, dies zu sehen. "Schauen Sie sich die Schleife und die Bedingung an. Wenn die Bedingung nur auf Literalen und keinen Variablen basiert, kennen Sie immer das Ergebnis der Schleife. Wenn Variablen vorhanden sind (z. B. while (x <10)), prüfen Sie, ob Diese Variablen werden immer geändert. Wenn nicht, kennen Sie immer das Ergebnis der Schleife. "

Zugegeben, diese Überprüfungen wären nicht trivial (Berechnung der Zeigerarithmetik usw.), aber es scheint nicht unmöglich. z.B:

int x = 0
while (x < 10) {}

festgestellt werden konnte. zusammen mit - wenn auch nicht trivial:

int x = 0
while (x < 10)
{
   x++;
   if (x == 10)
   {
      x = 0
   }
}

Was ist nun mit Benutzereingaben? Das ist der Kicker, das macht ein Programm unvorhersehbar.

int x = 0;
while (x < 10) 
{
   scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}

Jetzt kann mein Programm sagen: "Wenn der Benutzer eine 10 oder mehr eingibt, wird das Programm angehalten. Bei allen anderen Eingaben wird es erneut wiederholt."

Das bedeutet, dass auch bei Hunderten von Eingängen einer vorhanden istsollte in der Lage sein, die Bedingungen aufzulisten, unter denen das Programm gestoppt wird. In der Tat, wenn ich ein Programm schreibe, stelle ich immer sicher, dass jemand die Möglichkeit hat, es zu beenden! Ich sage nicht, dass die resultierende Liste von Bedingungen isttrivial zu schaffen, aber es scheint mir nicht unmöglich. Sie können Eingaben vom Benutzer entgegennehmen, sie zum Berechnen von Zeigerindizes usw. verwenden. Dies erhöht jedoch nur die Anzahl der Bedingungen, um sicherzustellen, dass das Programm beendet wird, und macht es nicht unmöglich, sie aufzulisten.

Was genau ist das Halteproblem? Was verstehe ich nicht über die Idee, dass wir kein Problem schreiben können, um Endlosschleifen zu erkennen? Oder warum sind "Schleifen" ein so oft genanntes Beispiel?

AKTUALISIEREN

Lassen Sie mich die Frage ein wenig ändern: Was ist das Halteproblem?wie trifft es auf computer zu? Und dann werde ich auf einige der Kommentare antworten:

Viele Leute haben gesagt, dass das Programm in der Lage sein muss, mit "beliebigen Eingaben" umzugehen. In Computern gibt es jedoch nie eine willkürliche Eingabe. Wenn ich nur ein einziges Datenbyte eingebe, habe ich nur 2 ^ 8 mögliche Eingaben. Also, als Beispiel:

int c = getchar()

switch (c) {
   case 'q':
      /* quit the program */
}

Auf einmal habe ich gerade alle Möglichkeiten berücksichtigt. Obc Hat das Bitmuster 0x71, macht es eine Sache. Für alle anderen Muster macht es etwas anderes. Sogar ein Programm, das willkürliche Texteingaben akzeptiert, ist niemals wirklich "willkürlich", da die Ressourcen endlich sind, was bedeutet, dass die Theorie von "willkürlich" zwar zutrifft ... aber nicht genau eins zu eins mit der Praxis.

Das andere Beispiel, das die Leute zitieren, ist folgendes:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
    else 
        n /= 2;

Wenn n eine 32-Bit-Ganzzahl ist ... dann kann ich Ihnen visuell sagen, ob dies zum Stillstand kommt oder nicht.

Ich denke, dieser Schnitt verlangt nichts, aber das überzeugendste Beispiel, das ich gesehen habe, istdieses:

Angenommen, Sie haben Ihr magisches Programm / Ihre magische Methode, um festzustellen, dass ein Programm anhält.

public bool DeterminesHalt(string filename, string[] args){
    //runs whatever program you tell it do, passing any args
    //returns true if the program halts, false if it doesn't
}

Nehmen wir nun an, wir schreiben ein kleines Stück Code wie ...

public static void Main(string[] args){
    string filename = Console.ReadLine(); //read in file to run from user
    if(DeterminesHalt(filename, args))
        for(;;);
    else
        return;
}

In diesem Beispiel können wir also ein Programm schreiben, das genau das Gegenteil unserer magischen Stoppmethode bewirkt. Wenn wir irgendwie feststellen, dass ein bestimmtes Programm anhält, springen wir einfach in eine Endlosschleife. Andernfalls beenden wir das Programm, wenn wir feststellen, dass sich das Programm in einer Endlosschleife befindet.

Andererseits, wenn Sie absichtlich ein Programm schreiben, das eine Endlosschleife enthält ... "Lösen des Halteproblems" ist irgendwie umstritten, nicht wahr?