Błąd opóźnił Vistę

mozart Problem zatrzymania! 29.10.06, 22:52

de.wikipedia.org/wiki/Halteproblem
"Durch einen Widerspruchsbeweis lässt sich zeigen, dass eine solche
Turingmaschine nicht existiert.

Auf jedes Kalkül, das mächtig genug ist, lässt sich Turings Beweis übertragen.
Die Beweisidee lässt sich einfach auch in Pseudocode darstellen:

Angenommen, es gibt eine Funktion haltetest:

haltetest(Programm, Eingabe)
1 wenn Programm(Eingabe) terminiert
2 dann return Ja
3 sonst return Nein

Dann lässt sich diese im folgenden Programm verwenden:

test(Programm)
1 solange haltetest(Programm, Programm) == Ja
2 führe aus keine Aktion

Wenn man nun der Prozedur test sich selbst als Eingabedaten übergibt und sie
somit von der Methode haltetest auf Terminierung prüfen lässt, kann diese kein
richtiges Ergebnis liefern:

test(test); //Dieser Aufruf terminiert genau dann,
// wenn er nicht terminiert. (Widerspruch!)

* liefert haltetest(test,test) JA, so hieße dies, dass test(test) terminiert
– aber die Bedingung haltetest(Programm,Programm) innerhalb von test ist gerade
dann immer wahr, so dass test(test) eben nicht terminiert, weil die
while-Schleife niemals beendet wird. Das ist ein Widerspruch!
* liefert haltetest(test,test) NEIN (es terminiert nicht), so ist die
Bedingung der while-Schleife niemals wahr, und test(test) terminiert sofort. Das
ist ebenfalls ein Widerspruch!

Das heißt nun, es gibt keine Turingmaschine, die, erhält sie als Eingabe die
Codierung einer Turingmaschine M und eine zugehörige Eingabe w, Ja ausgibt, wenn
M auf w hält und Nein ausgibt, wenn M nicht auf w hält.

Es gibt aber eine Turingmaschine, die immer dann Ja ausgibt, wenn M auf w hält,
aber endlos arbeitet, wenn M nicht auf w hält. Diese muss lediglich die
Berechnung der Turingmaschine simulieren, und Ja ausgeben, nachdem diese
Simulation ggf. hält. Das Halteproblem gehört deshalb zu den semi-entscheidbaren
Problemen.

Bemerkenswert ist, dass im Beweis die hypothetische Funktion haltetest nur in
der Form haltetest(Programm,Programm) benutzt wird. Dies bedeutet, dass man die
Lösbarkeit des Halteproblems in seiner vollen Allgemeinheit gar nicht zu
unterstellen braucht, um zu einem Widerspruch zu gelangen. Es lässt sich mit
derselben Idee beweisen, dass das spezielle Halteproblem, bei dem nur
entschieden werden soll, ob ein Programm bei Eingabe seiner eigenen Kodierung
hält, nicht entscheidbar ist.

Viele weitere Variationen des Halteproblems sind ebenfalls nicht entscheidbar,
so zum Beispiel die Frage, ob eine Turingmaschine bei der leeren Eingabe hält.
Die Nichtentscheidbarkeit des (speziellen) Halteproblems ist die Grundlage
vieler weiterer Nichtentscheidbarkeitsaussagen, kulminierend in der Aussage des
Satz von Rice, nach dem die Frage, ob die von einem Algorithmus berechnete
Funktion eine nichttriviale Eigenschaft hat, nicht entscheidbar ist."

Inaczej mowiac mozliwe jest napisanie programu, ktory bedzie biegl bez konca.
Tego "bledu" nie wykryje zaden kompilator!

Drzewko
Od najstarszego
Od najnowszego

Gość: Kurt Gödel Błąd opóźnił Vistę IP: *.o.pppool.de 27.10.06, 00:09

Nie istnieje zaden formalny system regul bledu! To fundamentalne prawo
matematyczne znajduje swoj wyraz I prawie programisty: Nie istnieje program bez
bledu!
- Gość: manhu Re: Błąd opóźnił Vistę IP: *.neoplus.adsl.tpnet.pl 28.10.06, 14:57
  
  Co ty bredzisz? Znajdź błąd tu:)
  begin
  end.
  
  Ot ludzie są omylni i jak program jest odrobinę:) bardziej skomplikowany to ... zrobią błędy.
  - mozart Problem zatrzymania! 29.10.06, 22:52
    
    de.wikipedia.org/wiki/Halteproblem
    "Durch einen Widerspruchsbeweis lässt sich zeigen, dass eine solche
    Turingmaschine nicht existiert.
    
    Auf jedes Kalkül, das mächtig genug ist, lässt sich Turings Beweis übertragen.
    Die Beweisidee lässt sich einfach auch in Pseudocode darstellen:
    
    Angenommen, es gibt eine Funktion haltetest:
    
    haltetest(Programm, Eingabe)
    1 wenn Programm(Eingabe) terminiert
    2 dann return Ja
    3 sonst return Nein
    
    Dann lässt sich diese im folgenden Programm verwenden:
    
    test(Programm)
    1 solange haltetest(Programm, Programm) == Ja
    2 führe aus keine Aktion
    
    Wenn man nun der Prozedur test sich selbst als Eingabedaten übergibt und sie
    somit von der Methode haltetest auf Terminierung prüfen lässt, kann diese kein
    richtiges Ergebnis liefern:
    
    test(test); //Dieser Aufruf terminiert genau dann,
    // wenn er nicht terminiert. (Widerspruch!)
    
    * liefert haltetest(test,test) JA, so hieße dies, dass test(test) terminiert
    – aber die Bedingung haltetest(Programm,Programm) innerhalb von test ist gerade
    dann immer wahr, so dass test(test) eben nicht terminiert, weil die
    while-Schleife niemals beendet wird. Das ist ein Widerspruch!
    * liefert haltetest(test,test) NEIN (es terminiert nicht), so ist die
    Bedingung der while-Schleife niemals wahr, und test(test) terminiert sofort. Das
    ist ebenfalls ein Widerspruch!
    
    Das heißt nun, es gibt keine Turingmaschine, die, erhält sie als Eingabe die
    Codierung einer Turingmaschine M und eine zugehörige Eingabe w, Ja ausgibt, wenn
    M auf w hält und Nein ausgibt, wenn M nicht auf w hält.
    
    Es gibt aber eine Turingmaschine, die immer dann Ja ausgibt, wenn M auf w hält,
    aber endlos arbeitet, wenn M nicht auf w hält. Diese muss lediglich die
    Berechnung der Turingmaschine simulieren, und Ja ausgeben, nachdem diese
    Simulation ggf. hält. Das Halteproblem gehört deshalb zu den semi-entscheidbaren
    Problemen.
    
    Bemerkenswert ist, dass im Beweis die hypothetische Funktion haltetest nur in
    der Form haltetest(Programm,Programm) benutzt wird. Dies bedeutet, dass man die
    Lösbarkeit des Halteproblems in seiner vollen Allgemeinheit gar nicht zu
    unterstellen braucht, um zu einem Widerspruch zu gelangen. Es lässt sich mit
    derselben Idee beweisen, dass das spezielle Halteproblem, bei dem nur
    entschieden werden soll, ob ein Programm bei Eingabe seiner eigenen Kodierung
    hält, nicht entscheidbar ist.
    
    Viele weitere Variationen des Halteproblems sind ebenfalls nicht entscheidbar,
    so zum Beispiel die Frage, ob eine Turingmaschine bei der leeren Eingabe hält.
    Die Nichtentscheidbarkeit des (speziellen) Halteproblems ist die Grundlage
    vieler weiterer Nichtentscheidbarkeitsaussagen, kulminierend in der Aussage des
    Satz von Rice, nach dem die Frage, ob die von einem Algorithmus berechnete
    Funktion eine nichttriviale Eigenschaft hat, nicht entscheidbar ist."
    
    Inaczej mowiac mozliwe jest napisanie programu, ktory bedzie biegl bez konca.
    Tego "bledu" nie wykryje zaden kompilator!
    - Gość: Jan Re: Problem zatrzymania! IP: *.internetdsl.tpnet.pl 30.10.06, 14:13
      
      > Inaczej mowiac mozliwe jest napisanie programu, ktory bedzie biegl bez konca.
      > Tego "bledu" nie wykryje zaden kompilator!
      
      A skąd pomysł że to jest błąd? Celem każdego systemu operacyjnego jest 'bieganie
      bez końca'.
      - mozart Re: Problem zatrzymania! 30.10.06, 23:45
        
        1. Nie istnieje zaden kompilator mogacy wykryc bledy skladni
        2. Mozliwa jest modyfikacja kodu zrodlowego, tak aby program biegl bez konca
        (patrz exploity, robaki, wirusy, trojany)
        3. Nie istnieje zaden konsystentny system operacyjny (zawsze znajdzie sie jakas
        zmienna,funkcja, ktore sa niejednoznacznie zdefinowane).
        Wn: Zaden system operacyjny nigdy nie bedzie w 100% bezpieczny.

Najnowsze z forum Internet

Zaloguj się