Das Zombie-Missverständnis der theoretischen Informatik

Das Zombie-Missverständnis der theoretischen Informatik

Einleitung

• Im Lehrbuch "Introduction to the Theory of Computation" von Michael Sipser gibt es eine perfekte Übungsaufgabe
• Aufgabe: "Wenn die Funktion f:{0,1}*→{0,1} je nach Existenz Gottes 1 oder 0 zurückgibt, ist f dann berechenbar?"
• Antwort: "Ja, f ist berechenbar" (weil konstante Funktionen berechenbar sind)

Das Konzept der Berechenbarkeit

• Berechenbarkeit wird auf Funktionen oder unendliche Sequenzen angewendet
• Sie wird nicht auf einzelne Ja/Nein-Fragen oder einzelne ganze Zahlen angewendet
• Wie schwierig es ist, ein Programm zu schreiben, hat nichts mit Berechenbarkeit zu tun

Das P-gegen-NP-Problem

• Das P-gegen-NP-Problem ist eine einzelne Ja/Nein-Frage
• NP-Härte wird auf Funktionen oder Sprachen angewendet
• Das P-gegen-NP-Problem kann weder unberechenbar noch NP-hart sein

Die Busy-Beaver-Funktion

• Die Busy-Beaver-Funktion ist unberechenbar
• Einzelne ganze Zahlen wie BB(6) sind berechenbar
• Die gesamte BB-Funktion ist unberechenbar

Das Zombie-Missverständnis der theoretischen Informatik

• Konzepte, die für unendliche Sequenzen und Funktionen gelten, werden fälschlich auf einzelne ganze Zahlen und offene Probleme angewendet
• Die Unberechenbarkeit des Halteproblems wird mit Gödels Unvollständigkeit verwechselt

Frage an die Leser

• Frage an die Leser, wie sich dieses Zombie-Missverständnis verhindern ließe

Zusammenfassung von GN⁺

• Dieser Beitrag behandelt häufig auftretende Missverständnisse in der theoretischen Informatik
• Berechenbarkeit gilt für Funktionen oder unendliche Sequenzen, nicht für einzelne ganze Zahlen oder Ja/Nein-Fragen
• Das P-gegen-NP-Problem ist eine einzelne Frage und hat nichts mit dem Konzept der NP-Härte zu tun
• Die Busy-Beaver-Funktion ist unberechenbar, aber einzelne Werte sind berechenbar
• Dieser Beitrag hilft dabei, die Grundkonzepte der theoretischen Informatik klar zu verstehen

[GN⁺]

Hacker-News-Kommentare

• Ob es einen Algorithmus zur Berechnung der Kolmogorov-Komplexität gibt, hängt mit Unendlichkeit zusammen

  • Es gibt keinen Algorithmus, der die Kolmogorov-Komplexität von Strings beliebiger Länge berechnet
  • Aber es gibt einen Algorithmus, der die Kolmogorov-Komplexität von Strings mit einer Länge kleiner als n berechnet
  • Das ist möglich, indem man eine riesige Nachschlagetabelle für alle möglichen Strings erstellt
  • Endliche Probleme lassen sich immer mit einem Programm lösen, unendliche hingegen nicht unbedingt

• Die Ansicht, dass konstruktive Mathematik besser zur menschlichen Intuition passt

  • Es gibt noch keinen Beweis dafür, dass ein Programm für das P=NP-Problem existiert
  • Mark Braverman bewies, dass alle (quadratischen) Julia-Mengen berechenbar sind, aber nicht einheitlich berechenbar
  • In der konstruktiven Mathematik wird die komplexe Ebene in mehrere Bereiche unterteilt, und für jeden Bereich wird bewiesen, dass die Julia-Menge darin kompakt ist

• Warum die Unentscheidbarkeit des Halteproblems schwer zu verstehen ist

  • Eines der Programme return true und return false liefert immer die richtige Antwort
  • Erst wenn man auf unendlich viele Maschinen-/Eingabe-Kombinationen erweitert, wird Entscheidbarkeit zu Unentscheidbarkeit

• Darstellung von Problemen, die Modallogik benötigen

  • Die Frage „Ist f berechenbar?“ ist modal gesehen die falsche Frage
  • Die Frage „Könnte f berechenbar sein?“ ist genauer
  • Das ist vergleichbar mit Compiler-Direktiven oder Pragmas

• Die verwirrende Darstellung der Funktion f

  • Die Funktion f verzweigt nicht abhängig vom Wert von „God exists“
  • f ist berechenbar, egal ob es 0 oder 1 ist
  • Die Verwirrung entsteht dadurch, dass freie Variablen in die Verzweigungsbedingung hineingeschoben werden

• Unterschiede in der Bedeutung von Entscheidbarkeit, Berechenbarkeit und Existenz

  • Im akademischen und im alltäglichen Kontext haben diese Begriffe unterschiedliche Bedeutungen
  • Große Zahlen existieren akademisch und sind berechenbar, passen praktisch aber nicht ins Universum

• Das Problem mit Fragen zu „God exists“

  • Es ist nicht klar, ob „God exists“ wahr oder falsch ist
  • Dieses Problem entsteht, wenn man natürliche Sprache und Mathematik vermischt

• Warum theoretische Informatik und Komplexitätstheorie für CS-Studierende schwierig sind

  • Begriffe wie NP-hard werden durch populäre Metaphern und Vorstellungen ersetzt

• Beschwerde über die Art der Textmarkierung im Blog

  • Die Hintergrundfarbe von ausgewähltem Text ändert sich nicht, was nicht intuitiv ist

• Vorschlag, „God exists“ durch eine andere mathematische Aussage zu ersetzen

  • „God exists“ sollte klar als wahr oder falsch definiert werden