Unlösbare mathematische Probleme -> theo. Informatik

[Styx]

Wobei man dazu sagen muss, dass eine Turingmaschine ein unendlich langes Speicherband hat und das Problem deswegen nicht entscheidbar ist. In der Realität gibts aber keine Computer mit unendlich vielem Speicher, was dazu führt, dass man das Problem theoretisch mit Brute Force lösen könnte Allerdings würde das einige Milliarden Jahre (wahrscheinlich weit untertrieben) dauern, wenn die Stromzufuhr lange genug gewährleistet werden kann

Solange der Speicher und das Alphabet begrenzt ist, kann man jedes Problem theoretisch mit Brute Force entscheiden.

 

[refri89]

Hab noch nicht exakt verstanden um was es geht, aber vielleicht paßt auch das: (Wikipedia,"Quadratur des Kreises")


Die Quadratur des Kreises ist ein klassisches Problem der Geometrie. Die Aufgabe besteht darin, aus einem gegebenen Kreis ein Quadrat mit demselben Flächeninhalt zu konstruieren. Sie ist äquivalent zur so genannten Rektifikation des Kreises, also der Konstruktion einer geraden Strecke, die dem Kreisumfang entspricht. Beschränkt man die Konstruktionsmittel auf Lineal und Zirkel, ist die Aufgabe unlösbar. Dies konnte jedoch erst im Jahr 1882 vom deutschen Mathematiker Ferdinand von Lindemann bewiesen werden.

Beweis der Unmöglichkeit

Ferdinand von Lindemann konnte 1882 schließlich beweisen, dass PI nicht algebraisch, sondern transzendent ist. Deshalb ist PI nicht konstruierbar und die Quadratur des Kreises unmöglich.

 

[asdfman]

Wobei man dazu sagen muss, dass eine Turingmaschine ein unendlich langes Speicherband hat und das Problem deswegen nicht entscheidbar ist.

Was für ein Blödsinn. Das Halteproblem ist generell nicht entscheidbar. Ein Beispiel dazu gibt es in den
SICP vorlesungen. Ich gebe das mal hier wieder.

Man definiert eine Funktion "diag1", die ein Argument p annimmt. Wenn es sicher ist, p auf p anzuwenden,
also, wenn die Anwendung von p auf p irgendwann hält, so führt diag1 eine Endlosschleife aus. Ansonsten
gebe sie 3 zurück.

Hier die Definition der Funktion:

(define diag1
  (lambda (p)
    (if (safe? p p)
        (inf)
        3)))

(define inf
  (lambda ()
    ((lambda (x) (x x))
     (lambda (x) (x x)))))

Wendet man nun diag1 auf diag1 an, und substituiert diag1 für p in der Funktion, so wird geprüft, ob es
sicher ist, diag1 auf diag1 anzuwenden. Dafür gibt es zwei Möglichkeiten. Wenn es sicher wäre, diag1 auf
diag1 anzuwenden, hieße das, diese Anwendung müsste irgendwann anhalten. Die Definition der Funktion
verlangt aber, dass in diesem Fall eine Endlosschleife ausgeführt wird.
Im anderen Fall, also dass (safe? diag1 diag1) ergäbe, dass die Anwendung eine Endlosschleife ergibt, gibt
die Anwendung aber eine 3 zurück.

Das ist ein Widerspruch, also kann es eine Funktion safe? nicht geben. Völlig egal, ob der Speicher begrenzt
ist, oder unendlich.

€: Ein zweites Beispiel geht folgendermaßen:

Man definiere eine weitere Funktion "diag2" mit einem Argument p, die prüft, ob die Anwendung von p auf p
sicher ist. Ist das der Fall, gebe etwas Anderes zurück, als die Anwendung von p auf p. Ansonsten gebe false
zurück.

(define diag2
  (lambda (p)
    (if (safe? p p)
        (other-than (p p))
        false)))

(define other-than
  (lambda (x)
    (if (eq? x 'a)
        'b
        'a)))

other-than prüft hier, ob ihr Argument der Buchstabe "a" ist. Ist das so, gibt sie "b" zurück, ansonsten "a". Das
heißt ganz klar: Egal, was ihr Argument ist, die Funktion gibt immer etwas Anderes zurück. Wie verlangt.

Wendet man nun wieder diag2 auf diag2 an, so wird nur p auf p angewendet, wenn es sicher ist, dies zu tun.
Gibt es also eine Funktion safe? dann ist diag2 immer definiert und damit sicher. Also muss die Anwendung von
diag2 auf diag2 immer zu (other-than (diag2 diag2)) reduziert werden. Also wäre, wenn es eine Funktion gäbe,
die erkennt, ob eine Funktion anhält, oder eine Endlosschleife ergibt, die Anwendung von diag2 auf diag2 immer
etwas Anderes als die Anwendung von diag2 auf diag2. Auch das ist offensichtlich ein Widerspruch, also
zeigt auch das, dass es keine solche Funktion safe? geben kann.

 

[Styx]

Du hast recht, dieses Beispiel hatte ich total vergessen. Meine Aussage ist also nicht auf alle unentscheidbaren Probleme anwendbar. Nichtsdestotrotz ist ein real existierender Computer keine echte Turingmaschine

 

[kuddlmuddl]

Ich will natürlich jetzt nicht deine (asdfman) Beispiele anzweifeln, die vom MIT stammen.

Aber die Sätze von Wiki:

Eine wichtige Schlussfolgerung aus der Berechenbarkeitstheorie ist, dass es keinen Algorithmus geben kann, der über jedes in einer bestimmten Turing-vollständigen Programmiersprache geschriebene Programm aussagen kann, ob es in endlicher Zeit abbricht oder für immer in einer Schleife bleibt (siehe Halteproblem).

(von Turing-Vollständigkeit)

und auch

Das Selbstanwendbarkeitsproblem von Turingmaschinen ist nicht entscheidbar
Die wichtigste Fragestellung bezüglich des Halteproblems ist hier, ob es entscheidbar ist, also ob eine Turingmaschine existiert, die für jedes Paar aus kodierter Turingmaschine und Eingabe berechnen kann, ob die kodierte Maschine auf dieser Eingabe anhält. In der praktischen Informatik lautet die Frage: Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d. h. nicht endlos weiterläuft?

Alan Turing bewies 1936, dass es keine Turingmaschine gibt, die das Halteproblem für alle Eingaben löst.

(von Das Selbstanwendbarkeitsproblem von Turingmaschinen ist nicht entscheidbar)

hätte ich jetzt so interpretiert, dass es nicht möglich ist einen universellen Halte-Checker zu bauen. Also dass zu jedem Halte-Checker-Programm, was andere Programme auf Endlosschleifen prüft immer ein Beispiel konstruiert werden kann, was von genau diesem Halte-Checker nicht erkannt wird.

Deins ist ja aber viel mehr, oder nicht?. Das wären doch dann 2 Beispiele, für die es garnicht erst möglich ist einen Haltechecker zu bauen!
Also nicht nur "Man kann immer ein nicht-checkbares Beispiel zu einem Halte-Checker finden" sondern sogar "Es gibt Beispiele die von keinen Checker auf einen Halt prüfbar sind".

Und das hab ich noch nirgens gelesen.... Aber genau das Halteproblem ist so ein Beispiel für ein un-checkbares Problem dachte ich?
Oder versteh ich da was falsch?

so im Sinne von Prädikatenlogischen Aussagen:
Für alle Haltechecker HC:
Es existiert ein Beispiel B:
HC kann B nicht auf einen Halt prüfen

gegen die andere Aussage:

Es existiert ein Beispiel B:
Für alle Haltechecker HC gilt:
HC kann B nicht auf einen Halt prüfen

also getauschte Quantoren

 

[asdfman]

Sicher gibt es eine gewaltige Menge an Programmen, die trivial geprüft werden können. Ein Programm wie

(define double
  (lambda (x)
    (* x 2)))

hält immer. Entweder gibt es die Eingabe mal 2 aus, oder produziert einen Fehler (wenn x keine Zahl ist).
Also kann es immer Programme geben, die für bestimmte vorgegebene Programme entscheiden können, ob
dieses hält.
Das Halteproblem bezieht sich aber eben auf ein universelles Programm, das für jedes Programm und jede
Eingabe entscheiden kann, ob es hält oder nicht. Und das kann es nicht geben.