- Berechenbarkeit und NP-hard in der theoretischen Informatik sind Konzepte, die auf Funktionen, Sprachen und unendliche Folgen angewendet werden, nicht auf einzelne ganze Zahlen oder einzelne Wahr/Falsch-Fragen
- In Sipsers Beispiel ist die „Funktion f, die immer 1 zurückgibt, falls Gott existiert, sonst immer 0“ in beiden Fällen eine konstante Funktion und daher berechenbar
- P vs NP ist kein Problem mit Eingabe, sondern eine einzelne Ja/Nein-Frage, daher kann man es an sich weder NP-hard noch unberechenbar nennen
- Die gesamte Busy-Beaver-Funktion ist unberechenbar, aber ein bestimmter Wert wie BB(6) lässt sich nicht auf dieselbe Weise behandeln, da es für jede ganze Zahl k ein Programm
print kgibt - Der Kern der immer wiederkehrenden Verwirrung besteht darin, Konzepte für unendliche Objekte auf einzelne Probleme anzuwenden; die Gewohnheit, die Unberechenbarkeit des Halteproblems mit Gödels Unvollständigkeit zu vermischen, gehört zur gleichen Kategorie
Der Umfang der Berechenbarkeit, den das Sipser-Beispiel zeigt
- In Michael Sipsers Introduction to the Theory of Computation gibt es eine Übungsaufgabe, die die Definition von Berechenbarkeit verdeutlicht
- Sei f:{0,1}*→{0,1} die Funktion, die immer 1 zurückgibt, wenn Gott existiert, und sonst immer 0
- Die Frage ist, ob f berechenbar ist, und die Antwort hängt nicht von religiösen Überzeugungen ab
- f ist berechenbar
- Die konstante Funktion, die immer 1 zurückgibt, ist berechenbar
- Die konstante Funktion, die immer 0 zurückgibt, ist ebenfalls berechenbar
- Wenn f eine von beiden ist, dann ist auch f berechenbar
- Eine parallele Frage mit derselben Struktur vermittelt dieselbe Intuition
- Bei der Frage „Ist n eine Primzahl, wenn bei Existenz Gottes n=3 und sonst n=5 ist?“ kann man Primzahl sagen, obwohl n nicht vollständig festgelegt ist, denn es ist bekannt, dass n ein Element von {3,5} ist
- Mit f ist es genauso: Es bleibt nur offen, welche der beiden konstanten Funktionen vorliegt, aber es ist hinreichend bestimmt, um als berechenbar zu gelten
Berechenbarkeit betrifft nicht die Schwierigkeit, ein Programm zu schreiben, sondern seine Existenz
- Berechenbarkeit ist ein Konzept, das auf Funktionen oder unendliche Folgen angewendet wird
- Auf einzelne Ja/Nein-Fragen oder einzelne ganze Zahlen wird Berechenbarkeit nicht in derselben Weise angewendet
- Die entscheidende Frage ist, ob ein Computerprogramm existiert, das Eingaben auf Ausgaben abbildet
- Wie schwer es ist, dieses Programm auszuwählen, zu finden oder zu schreiben, ist nicht Teil der Definition von Berechenbarkeit
- Selbst wenn man zur Programmierung erst die Existenz Gottes klären müsste, würde das die Einstufung der Berechenbarkeit nicht ändern
Warum man P vs NP nicht als NP-hard bezeichnen kann
- Die Frage „Ist die P-versus-NP-Frage selbst NP-hard und deshalb unlösbar?“ ist in den letzten 25 Jahren mehrfach wieder aufgetaucht
- NP-hard wird auf Funktionen oder Sprachen angewendet, die Eingaben erhalten, etwa 3SAT, Independent Set oder Clique
- Die Eingaben sind etwa Boolean-Formeln oder Graphen
- Die Ausgabe ist die Antwort für die jeweilige Eingabe
- Ein Problem heißt NP-hard, wenn man mit einem polynomiellen Algorithmus für dieses Problem per Reduktion auch alle Sprachen oder Funktionen in NP in polynomialer Zeit lösen könnte
- P vs NP ist aber keine Funktion oder Sprache, sondern eine einzelne Ja/Nein-Frage
- Es ist nicht ausgeschlossen, dass ihre Antwort unabhängig von den Axiomen der Zermelo-Fraenkel-Mengenlehre ist
- Aber man kann diese Frage an sich weder unberechenbar noch NP-hard nennen
- Ein schnelles Programm, das die P-vs-NP-Frage korrekt beantwortet, existiert formal
- Falls P=NP, ein Programm, das „P=NP“ ausgibt
- Falls P≠NP, ein Programm, das „P≠NP“ ausgibt
Dieselbe Verwirrung taucht beim Busy Beaver wieder auf
- Auch in den Kommentaren zu einem Beitrag über den bestimmten Busy-Beaver-5-Wert tauchte eine ähnliche Frage wiederholt auf
- „Was ist das kleinste n, ab dem der Wert von BB(n) unberechenbar wird?“
- „Kann BB(6) bereits unberechenbar sein?“
- Die Busy-Beaver-Funktion ist unberechenbar
- Aber auf einzelne ganze Zahlen wie BB(6) wird der Begriff der Berechenbarkeit nicht so angewendet
- Ganz gleich, als welche ganze Zahl k sich BB(6) herausstellt, es gibt ein Programm
print k - Dieses Programm gibt genau diese ganze Zahl aus
- Ganz gleich, als welche ganze Zahl k sich BB(6) herausstellt, es gibt ein Programm
- Stattdessen kann man fragen, für welches n der Wert von BB(n) in einem Axiomensystem wie der ZF-Mengenlehre unbeweisbar ist
- Aaronson und Adam Yedidia behandelten diese Frage 2016
- Der aktuelle Rekord ist n=745 und verbessert Aaronsons und Adams Wert n=8000
- Jede bestimmte ganze Zahl kann als „berechenbar“ gelten; unberechenbar ist die BB-Funktion als Ganzes
Warum dieses „Zombie-Missverständnis“ weiterlebt
- Der Kern der wiederkehrenden Verwirrung liegt darin, Konzepte, die für unendliche Folgen und Funktionen gedacht sind, fälschlich auf einzelne ganze Zahlen und offene Probleme anzuwenden
- Auch Fälle, in denen die Unberechenbarkeit des Halteproblems mit Gödels Unvollständigkeit vermischt wird, gehören in dieselbe Kategorie von Missverständnissen
- Beide sind eng miteinander verwandt
- Gödel erlaubt Aussagen über einzelne Aussagen
- Turings Begriff der Berechenbarkeit ist dagegen kein Konzept relativ zu einem bestimmten Axiomensystem, sondern ein absoluter Begriff
- Diese Erklärung dient als Referenzpunkt, auf den man verweisen kann, wenn dasselbe didaktische Missverständnis erneut auftaucht
- Die abschließende Frage richtet sich darauf, wie sich dieses „zombieartige“ Missverständnis zum Schweigen bringen lässt
1 Kommentare
Hacker-News-Kommentare
Dass das Konzept der Berechenbarkeit zwangsläufig Unendlichkeit einschließt, kann ziemlich kontraintuitiv sein
Wenn man zum Beispiel fragt, ob es einen Algorithmus gibt, der für einen beliebigen String s die Kolmogorov-Komplexität K(s) berechnet, dann lautet die bekannte Antwort „nein“. Es gibt keine Turing-Maschine, die Strings beliebiger Länge als Eingabe annimmt und K(s) berechnet, und der Beweis ist mit dem Halteproblem schnell geführt
Fragt man aber, ob es einen Algorithmus gibt, der für einen beliebigen String s mit Länge kleiner als n K(s) berechnet, dann lautet die Antwort „ja“. Für jedes n existiert ein solcher Algorithmus
Die Methode ist enttäuschend simpel: Man baut einfach eine Turing-Maschine mit einer riesigen Lookup-Tabelle, die für alle 2^n möglichen Strings den Wert K(s) enthält. Wie man diese Tabelle tatsächlich erhält, ist eine andere Frage, aber eine konkrete Implementierung hat eine endliche Beschreibung, und da K(s) für alle s endlich ist, existiert der Algorithmus
Deshalb sind endliche Fragen über endliche Objekte aus Sicht der Berechenbarkeit oft nicht besonders interessant. Man kann immer ein Programm schreiben, das einfach alle Antworten ausgibt; erst wenn sich die Frage auf eine unendliche Menge von Objekten erstreckt, wird interessant, ob etwas Endliches unendlich viele Fragen beantworten kann
Tatsächlich steht die Unendlichkeit hier für „approximatives, letztliches, stationäres Verhalten ab einem hinreichend großen N“ statt für irgendeinen einmaligen Trick
In der Praxis sind solche Tricks natürlich wichtig, und auch die Konstanten sowie Terme niedriger Ordnung, die bei Big-O-Vergleichen ignoriert werden, sind für die reale Performance entscheidend. Es gibt immer eine Spannung zwischen „Problemen, die groß genug sind, dass konstante Faktoren bedeutungslos werden“ und „Problemen, die klein genug sind, um in den Bereich zu fallen, den das Wort konstant stillschweigend meint“. Ein Beispiel sind 32-Bit-Integer, die so tun, als seien sie ganze Zahlen
Aus Sicht der Unendlichkeit sind alle endlichen Zahlen in Wirklichkeit sehr klein. Vom Stuhl am Ende des Universums aus gesehen unterscheiden sich 1 Meile und 1 Millimeter kaum
Dieses Szenario ist im Grunde „Hilberts Hotel der Unendlichkeit auf einem Computer“. Man kann bestehende Programme jeweils um einen Platz weiterschieben und ein neues Programm hinzufügen, während die für die Berechnung nötige Tabellengröße gleich bleibt
Allgemeiner gilt: Die meisten Menschen haben nur eine schwache Intuition dafür, wie Unendlichkeiten, Aleph-Zahlen und transfinites Rechnen funktionieren. Sie haben wenig Alltagsbezug und sind tief mit emergenten Eigenschaften von Mathematik sowie Kategorien- und Mengenlehre verflochten. Nicht nur ist Unendlich größer als jede endliche Zahl, manche Unendlichkeiten können auch größer sein als andere; das sieht man nicht sofort, wenn die Intuition bei einem schulischen Begriff von „unendlich“ stehenbleibt
Die interessantere Frage ist, ob es irgendein n < ∞ gibt, das den Algorithmus berechenbar macht; die Antwort ist natürlich nein, und die Turing-Auszeichnung ist dahin
Die Idee ist, alle möglichen Turing-Maschinen in aufsteigender Länge zu enumerieren und nach einer zu suchen, die s ausgibt. Wenn man alle kürzeren Maschinen ausprobiert hat und keine s ausgibt, dann hat man die kürzeste Maschine gefunden, die s ausgibt, und ihre Länge ist K(s). Andere Maschinen derselben oder größeren Länge könnten s ebenfalls ausgeben, aber K(s) ist der Wert der minimalen Länge und ändert sich daher nicht
Meiner Erfahrung nach passt hier konstruktive Mathematik besser zur Intuition der Menschen als klassische Informatik
Zum Beispiel gibt es noch keinen konstruktiven Beweis dafür, dass ein Programm existiert, das die Antwort auf das P=NP-Problem ausgibt
In meiner Arbeit habe ich dieses Problem auch im Zusammenhang mit berechenbaren Julia-Mengen behandelt. Mark Braverman bewies, dass alle quadratischen Julia-Mengen berechenbar sind, erklärte aber selbst, dass sein Beweis nicht uniform berechenbar ist. Stattdessen konstruiert man fünf Maschinen, die den Parameter der gewünschten Julia-Menge als Eingabe nehmen und versuchen, verschiedene Mengen in der gewünschten Auflösung zu zeichnen; für jede Julia-Menge zeichnet genau eine davon korrekt
In der konstruktiven Mathematik entspricht der konstruktive Begriff einer kompakten Menge grob dem Sinn von berechenbarer Menge, der für berechenbare Julia-Mengen gebraucht wird. Aber dass alle quadratischen Julia-Mengen kompakt sind, lässt sich konstruktiv nicht beweisen; stattdessen muss man die komplexe Ebene möglicher Parameter in mehrere Regionen aufteilen und dann für jede Region beweisen, dass die entsprechenden Julia-Mengen kompakt sind
In der klassischen Mathematik ist die Vereinigung dieser Regionen die gesamte komplexe Ebene, aber in der konstruktiven Mathematik gilt dieses Ergebnis nicht. Ebenso ist in der klassischen Mathematik die Vereinigung der positiven reellen Zahlen und der nicht-positiven reellen Zahlen die gesamte reelle Zahlengerade, in der konstruktiven Mathematik gilt auch das nicht
Der konstruktive Ansatz sagt präzise, welche Zusatzinformation nötig ist, um die Berechnung tatsächlich zu realisieren. Man muss nämlich feststellen, in welcher Region der komplexen Ebene der gegebene Parameter liegt; erst dann weiß man, welche der fünf Maschinen man ausführen muss, um das gewünschte Bild zu erhalten. Das wirkt wie eine viel befriedigendere Antwort
Die Leute wissen instinktiv, dass man wissen muss, in welchem Zweig einer Fallunterscheidung man sich befindet, und haben diese Tatsache nicht etwa vergessen, nur weil sie in klassischer Logik trainiert wurden
Ich frage mich auch, ob es zu der Frage „welche der fünf ist die richtige?“ einen Beweis gibt, der nur noch nicht gefunden wurde, oder ob das wie in ZFC als unentscheidbar gilt
Ich denke, das ist einer der Punkte, die das Verständnis der Unentscheidbarkeit des Halteproblems erschweren
Man möchte sagen: „Es gibt Maschinen, die so komplex sind, dass man nicht entscheiden kann, ob sie anhalten oder nicht“, aber von den trivialen Programmen
return trueundreturn falseliefert eines von beiden für jede beliebige Maschine und Eingabe immer die richtige Antwort.Man möchte vielleicht einwenden: „Diese Programme wissen nichts über Turing-Maschinen, also muss man sie ausschließen“, aber darum geht es bei Entscheidbarkeit nicht. Man könnte auch denken: „Es ist unentscheidbar, herauszufinden, welches der beiden Programme richtig ist“, aber auch darauf gibt es eine festgelegte, wahre oder falsche Antwort. Zum Unentscheidbaren kann es erst werden, wenn man auf die unendliche Menge von Maschinen-/Eingabe-Kombinationen erweitert.
Zum Beispiel ist jeder endlichdimensionale Vektorraum auf verschiedene Weisen isomorph zu seinem Dualraum und seinem Bidualraum, aber für Letzteres kann man über alle solchen Räume hinweg einen konsistenten „natürlichen“ Isomorphismus wählen, für Ersteres jedoch nicht.
Das führt zu Verwirrung wie: „Warum ist das nicht natürlich isomorph? Sie haben doch dieselbe Basislänge! Warum sollte es wichtig sein, ob es von einer Basis abhängt? Warum ist es bei anderen Beweisen in Ordnung, eine Basis zu wählen?“
Ich denke, das Problem an der Formulierung ist, dass sie modale Logik erfordert
„Falls Gott existiert, sei f:{0,1}*→{0,1} die konstante 1-Funktion, und falls Gott nicht existiert, die konstante 0-Funktion. Ist f berechenbar? Hinweis: Die Antwort hängt nicht vom religiösen Glauben ab.“
Die präzise Frage ist, ob f berechenbar wäre, also ob es eine Turing-Maschine M gibt mit f(x)=M(x) für alle x.
Die Antwort ist ja. Denn in jeder Welt gibt es eine triviale Turing-Maschine M=1_M oder M=0_M. Dagegen ist die ursprüngliche Formulierung „Ist f berechenbar?“ modal gesehen eine falsch gestellte Frage, eher wie das Sleeping-Beauty- oder das Red-Envelope-Paradoxon, also eine grammatikalisch ungenaue Frage.
Aus einer anderen Perspektive ähnelt die Abhängigkeit von Gott oder irgendeiner anderen möglicherweise realen Tatsache eher einer Compiler-Direktive oder einem Pragma, das zwar später ausgefüllt wird, aber vor der Verwendung festgelegt ist. Wenn man korrekt fragt, ist es nur eine Frage des Auspackens der strengen Definitionen von Funktion und Berechenbarkeit, und beide sind bei Sipser ausdrücklich definiert.
Gemeint ist, dass das Etikett namens f auf die konstante 1-Funktion zeigt, wenn Gott existiert, und auf die konstante 0-Funktion, wenn Gott nicht existiert, und wir nur vorab nicht wissen, welche von beiden gemeint ist. Da die Berechenbarkeit beider konstanten Funktionen trivial ist, ist das in Wirklichkeit keine Frage der Berechenbarkeit, sondern eher eine des Etiketts.
Wenn man bedenkt, dass schon die Tatsache, dass Wahrscheinlichkeitstheorie auf die Wirklichkeit anwendbar ist, äußerst rätselhaft ist und Gegenstand vieler wissenschaftlicher und philosophischer Untersuchungen war, ist das nicht überraschend.
Auch die vorgeschlagene Lösung der Form „would f be“ scheint nicht viel zu lösen. Der Zweck der „Gott“-Frage ist, den Leser von einem bestimmten P-NP-Problem wegzubringen und verstehen zu lassen, dass der Begriff der Berechenbarkeit bei konstanten Funktionen nutzlos ist. Damit dieser Vorschlag hilft, müsste er auch auf die ursprüngliche P-NP-Frage anwendbar sein, aber ich sehe noch nicht, wie ein modaler Zugang in eine wohldefinierte mathematische Frage hineinkommt.
„Falls Gott existiert, sei f:{0,1}→{0,1} die konstante 1-Funktion, und falls Gott nicht existiert, sei f:{0,1}→{0,1} die konstante 0-Funktion.“
Ob ein solches Prädikat dem eigenen Gottesbegriff entspricht, ist eine separate, nichtmathematische Frage.
Das ist ähnlich dazu, dass Menschen überrascht sind, wenn sie lernen, dass in der klassischen Logik eine falsche Aussage alles impliziert. In der Mathematik gibt es strenge formale Regeln, und es ist wichtig, Vorannahmen über die alltagssprachliche Bedeutung von Wörtern wie „impliziert“ oder „falls“ abzulegen.
Etwa G:t∈ℝ⁺->{0,1}, wobei G zum Zeitpunkt t den Wert 1 hat, wenn Gott existiert, und sonst 0.
Natürlich wird es noch interessanter, wenn man G in einem nichtinertialen Bezugssystem analysiert.
Sipser nutzt aus, dass die meisten Menschen den Unterschied zwischen Berechnung und empirischer Untersuchung nicht gut verstehen
„Existiert Gott?“ ist vielleicht eine unbeantwortbare Frage, aber darum geht es nicht. Die Antwort darauf zu finden, gehört von vornherein nicht in den Bereich der Berechnung. Berechnung ist nur ein Verfahren, das Eingaben auf Ausgaben abbildet, und in diesem Fall ist die Existenz Gottes eine der Eingaben.
Verwirrend ist, dass wir den Eingabewert tatsächlich nicht kennen, aber das Programm existiert trotzdem und ist trivial. Man kann es auch durch eine andere binäre empirische Frage ersetzen.
Zum Beispiel sei f:{0,1}* -> {0,1} gleich „1, wenn es in Paris mindestens eine mobile Toilette gibt, sonst 0“. Das ist berechenbar und kann mit einer wahren Eingabe tatsächlich ausgeführt werden. Die Funktion über Gott ist ebenfalls berechenbar, nur kann man sie nur mit einer vermuteten Eingabe ausführen. Es ist zwar nicht garantiert, dass die Ausgabe sinnvoll unserer Welt entspricht, aber es ist dennoch eine berechenbare Funktion.
Noch einfacher kann man nur f:{0,1}* -> {0,1} betrachten. „Gott existiert“ und „Gott existiert nicht“ sind jeweils mögliche Bitstrings. Wenn man fragt, ob es ein Programm geben kann, das bei einer dieser Eingaben 0 und bei der anderen 1 ausgibt, dann ist die Antwort natürlich ja. Ob die Eingabe empirisch wahr ist oder nicht, spielt keine Rolle.
Das f in der Frage ist keine Funktion, sondern ein Etikett. Wenn Gott existiert, bezeichnet f das stets 1 ausgebende f1, und wenn Gott nicht existiert, das stets 0 ausgebende f0. Daher ist das in Wirklichkeit keine Frage der Berechenbarkeit, sondern eine des Etiketts.
Das passiert ständig, weil Mathematiker und Informatiker der Bequemlichkeit halber verkürzte Formulierungen verwenden und Details weglassen.
Das ist nicht anders, als zu sagen: „Man multipliziert beide Seiten mit dx.“ Die Frage „Ist das Problem des Handlungsreisenden NP-schwer?“ bezieht sich auf eine Familie von Problemen, nicht auf eine einzelne konkrete Instanz. Wenn man einen bestimmten Graphen festhält, gibt es kein N, also ist er natürlich nicht NP-schwer.
Wenn man das weiß, ist es so selbstverständlich, dass es kaum erwähnenswert ist; für jemanden, der die Bedeutung der Begriffe nicht kennt, ist es aber völlig schwer zugänglich.
Ich hatte früher in einem anderen Fachgebiet eine ähnliche Art von Missverständnis. Ich betrachtete DNA als eine Art Code und glaubte, dass Dinge, die über ein Substrat direkt oder durch Modifikation der DNA Nachrichten austauschen, diesen Code ausführen. Als grobes Modell ist das nicht völlig nutzlos, aber man muss wissen, wann man diesem Modell nicht verfallen darf.
Für einen Biologen mit mathematischem Hintergrund ist es offensichtlich falsch, DNA direkt als Ausführungsmodell einer Turing-Maschine zu betrachten; für mich war das nicht so. Letztlich ist es ein Problem, das aus der Fremdheit des Grundwissens entsteht.
Wörter wie Entscheidbarkeit, Berechenbarkeit, Existenz und sogar Frucht haben in akademischen Kontexten andere Bedeutungen als im Alltag. Wenn man die alltagssprachliche Intuition in den wissenschaftlichen Kontext übernimmt, entstehen solche „dummen Fragen“.
Eine gewisse große Zahl auf Wikipedia „existiert“ und ist im wissenschaftlichen Sinn „berechenbar“, aber ihre Ziffern würden nicht in unser Universum passen.
Wenn man nicht sorgfältig liest, ist die Formulierung verwirrend.
Bei „Falls Gott existiert, sei f:{0,1}*→{0,1} die konstante 1-Funktion, und falls Gott nicht existiert, die konstante 0-Funktion. Ist f berechenbar?“ ist die Alternative kein Teil der Funktion.
Die Funktion f verzweigt nicht abhängig vom Wahrheitswert von „Gott existiert“; die Verzweigung liegt in der Metasprache. Wir wissen nicht, ob f=0 oder f=1 ist, aber in beiden Fällen sind die beiden möglichen Funktionen berechenbar, also ist auch f berechenbar.
Sogar wenn f diese Verzweigung tatsächlich enthielte und der Definitionsbereich der Funktion 0 (Gott existiert nicht) und 1 (Gott existiert) wäre, wäre sie immer noch eine berechenbare Funktion, in dem Sinn, dass man für jeden Wert im Definitionsbereich das Ergebnis berechnen kann.
Der Kern der Verwirrung liegt darin, eine freie Variable, deren Wert als unbekannt angesehen wird, als Verzweigungsbedingung in f hineinzuschieben.
Gegen das Beispiel „Falls Gott existiert, sei n=3, und falls Gott nicht existiert, sei n=5. Ist n eine Primzahl?“ würde ich gern Einwände erheben.
Hier wird das Prinzip vom ausgeschlossenen Dritten verwendet, um zu behaupten, n sei 3 oder 5, aber es gibt keine Rechtfertigung dafür, dass dieses Prinzip für die Aussage „Gott existiert“ gilt.
Wenn man hier schon hinterfragen will, ob dieses Prinzip gerechtfertigt ist, muss man auch rechtfertigen, warum ausgerechnet nur dieses Prinzip problematisiert wird. Warum verwirft man nicht auch das Explosionsprinzip und arbeitet in einer parakonsistenten Logik? Auch Kolmogorow sah in diesem Axiom ein ernstes Problem und hielt es anfangs für unvereinbar mit konstruktivistischer Logik.
Außerdem könnte je nach genauer Formalisierung dieser Aussage das Prinzip vom ausgeschlossenen Dritten gar nicht notwendig sein.
Gott muss nicht notwendigerweise an physikalische Gesetze oder grundlegende logische Notwendigkeiten gebunden sein. Ein solcher Gottesbegriff stammt aus bestimmten Strängen theologischer Argumentation und ist nicht der allgemeine Fall.
Wenn er wollte, könnte Gott 6 ungerade machen. Er könnte die gesamte Mathematik, die logische Konsistenz und das gesamte Universum verändern oder eine Welt erschaffen, in der nur 77 gerade ist und alle anderen Zahlen ungerade sind, und alle Mathematiker würden diese Anordnung für vollkommen konsistent und schon immer richtig halten.
Deshalb kann man sagen, dass die Antwort in gewissem Maß von religiösem Glauben abhängt.
Theoretische Informatik und Komplexitätstheorie scheinen für CS-Studierende oder Menschen in angrenzenden Branchen eine ähnliche Stellung zu haben wie die Teilchenphysik für die Allgemeinheit.
So wie die Allgemeinheit schon einmal von Verschränkung gehört hat, haben wir schon einmal von NP-Schwere gehört und ersetzen den eigentlichen mathematischen Gedankengang durch schlechte populäre Analogien und Fantasien.
Der Autor könnte sich aufgrund langer Ausbildung seine eigene sehr strenge Definition von Berechenbarkeit ausgesucht haben, dann einen ganzen Text über genau diese Definition des Wortes geschrieben haben und anschließend den Menschen in der Welt, die dasselbe Wort in einer anderen Definition verwenden, vorwerfen, dumme Fragen zu stellen.
Das passiert wirklich sehr oft, wenn man bei der Arbeit mit Wissenschaftlern oder mit Laien spricht. Sich auf gemeinsame Begriffe zu einigen ist schwierig, und anhand der eigenen Terminologie eine Grenze zu ziehen und dann von anderen zu verlangen, dass sie mitziehen, ist ermüdend.