Was sind berechenbare Zahlen und welche philosophische Bedeutung haben sie?

Alle mathematischen Formalisierungen der (intuitiven) Berechenbarkeit sind bekanntlich äquivalent, insbesondere sind sie alle äquivalent zur Berechenbarkeit auf der universellen Turingmaschine. Die technologische Umsetzung ist also irrelevant. Die Church-Turing-These besagt, dass dies im Umfang mit dem übereinstimmt, was "von einem Menschen berechenbar" ist, ohne Einschränkungen durch Zeit und Ressourcen. Dies ist offensichtlich eine philosophische Aussage, und einige sind anderer Meinung, wenn auch eine kleine Minderheit, aber insbesondere frühe Intuitionisten wie Brouwer und Weyl, Gödel und Lucas. Ihnen zufolge weist der menschliche Geist die Fähigkeit auf, algorithmische Berechnungen kreativ zu „überschreiten“, siehe Hat Gödels Argument, dass der Geist mächtiger als Computer ist, die Inkonsistenzlücke?Neuere Intuitionisten/Konstruktivisten, mit Ausnahme von Dummett, akzeptieren dies im Allgemeinen.

Berechenbare Zahlen sind die reellen Zahlen, für die es einen Algorithmus gibt, der bei gegebener gewünschter Genauigkeit die Annäherung der Zahl an diese Genauigkeit in endlich vielen Schritten zurückgibt. Das sind die reellen Zahlen, die Konstruktivisten und Finitisten in ihren Versionen der reellen Analyse zulassen würden. Im weiteren Sinne werden Erweiterungen dieser Denkrichtung auf die Erkenntnistheorie diskutiert unter Haben Einschränkungen der Berechenbarkeit und der Rechenressourcen irgendwelche Konsequenzen für die Erkenntnistheorie? Siehe auch Was sind die "undefinierbaren Zahlen" in der realen Analyse und Philosophie? für eine verwandte Klasse reeller Zahlen.

Der Hauptunterschied besteht darin, dass definierbare Zahlen die volle Stärke der Mengenlehre nutzen können, während berechenbare Zahlen auf die Ressourcen der Arithmetik beschränkt sind. Hier ist ein Beispiel für eine nicht berechenbare, aber definierbare Zahl. Zählen Sie alle wohlgeformten arithmetischen Sätze nach Gödelzahlen auf und definieren Sie eine reelle Zahl zwischen 0 und 1 wie folgt: Die n-te Ziffer in ihrer Dezimalerweiterung ist 0, wenn der n-te Satz falsch ist, 1, wenn er wahr ist, und 2, falls n keine Gödelzahl eines Satzes ist. Es ist definierbar, weil das Wahrheitsprädikat der Arithmetik definierbar ist (in der Mengenlehre, nicht in der Arithmetik), und wir können sogar einige seiner Ziffern leicht berechnen, zB diejenigen, die bewiesenen Theoremen oder ihren Negationen entsprechen. Aber es ist unberechenbar, weil es keinen Algorithmus gibt, um die Wahrheit von, sagen wir, der Goldbach- oder der Primzahlzwillings-Vermutung zu entscheiden. Es ist interessant, dass, während Konstruktivisten und Intuitionisten die Existenz dieser Zahl ablehnen würden, frühe Intuitionisten die Existenz von Unindividualisierten akzeptiertennicht berechenbare reelle Zahlen, die auf der direkten Intuition des "Werdens" gesetzloser Folgen basieren, siehe Wird Aristoteles' Auflösung von Zenos Paradoxien durch Bewegung im intuitionistischen Kontinuum bestätigt?

Die berechenbaren Zahlen sind nicht technologieabhängig. Ein universeller Computer kann jedes endliche physikalische System mit jeder gewünschten Genauigkeit simulieren. Und es kann nicht nur Ein- und Ausgang, sondern auch die Zwischenstufen zwischen Ein- und Ausgang mit beliebiger Genauigkeit simulieren:

http://www.daviddeutsch.org.uk/wp-content/ItFromQubit.pdf .

Die philosophische Bedeutung dieser Eigenschaft der Berechnungstheorie besteht darin, dass sie die Gesetze der Physik überprüfbarer macht. Wenn Sie eine Vorstellung davon haben, wie ein physikalisches System funktioniert, können Sie seine Konsequenzen mit einem Computer berechnen, indem Sie ihn entsprechend programmieren. Sie können diese Folgen dann mit dem vergleichen, was tatsächlich passiert.

Die Gesetze der Physik besagen, dass, wenn Sie einen bestimmten endlichen Satz von Berechnungen durchführen und diese Berechnungen in Netzwerken zusammenstellen können, Sie alle Berechnungen durchführen können, die nach den Gesetzen der Physik zulässig sind. Wenn die Gesetze der Physik anders wären, könnten andere Operationen zulässig sein und sie könnten andere Konsequenzen für das haben, was berechnet werden könnte. Als Beispiel siehe "The Beginning of Infinity" von David Deutsch, Kapitel 8. Die tatsächlichen Gesetze der Physik erlauben also eine begrenzte Teilmenge der Menge aller möglichen Abstraktionen. Wir haben derzeit keine Erklärung dafür, warum diese bestimmte Teilmenge zulässig ist, was ein philosophisches Problem ist.

Am einfachsten können berechenbare Zahlen – einschließlich berechenbarer Probleme – von einem Rechengerät wie Taschenrechnern, Computern und, nun ja, Menschen gelöst werden, wenn Sie philosophisch so geneigt sind.

Ganz allgemein kann sich die Philosophie Fragen der Metarechenbarkeit nähern: Was ist eine berechenbare Maschine oder ein berechenbares Gerät? Sind Menschen Computergeräte/Maschinen? Was ist Berechenbarkeit?

Genauer gesagt nimmt das philosophische Interesse an der Berechenbarkeit die Form der mathematischen Analyse an. Bereitstellung rigoroser Definitionen und Verteidigung komplexer und rechnerischer Geräte und Funktionen, die sich auf grundlegende mathematische Fragen wie die Mengenlehre stützen.

Für eine reichhaltigere Lektüre als meine siehe Immermans Artikel in der Stanford Encyclopedia of Philosophy, „Computability and Complexity“.

Eine berechenbare Zahl ist eine reelle Zahl, die von einem Algorithmus mit beliebiger Genauigkeit berechnet werden kann . Da ein Algorithmus nur eine endliche Folge von Anweisungen ist, kann er – und ist es tatsächlich in einem digitalen Computer – als eine eindeutige endliche Folge von Einsen und Nullen dargestellt werden, die auch die eindeutige binäre Darstellung einer natürlichen Zahl ist. Daher gibt es höchstens so viele berechenbare Zahlen wie Algorithmen. Daher sind berechenbare Zahlen höchstens zählbar. Da die Menge aller reellen Zahlen überabzählbar unendlich ist (Cantor), gibt es überabzählbar unendlich mehr nicht berechenbare reelle Zahlen als berechenbare.

Obwohl diese Antwort als "oberflächlich", vereinfachend oder offensichtlich angesehen werden kann, wird sie zumindest eine andere Sichtweise liefern.
So wie ich es verstehe, ist eine „ berechenbare Zahl“ eine Zahl, die von einem „Computer“ berechnet werden kann .
Jeder physische "Computer" hat bestimmte Einschränkungen. Daher ist jede Zahl, die "außerhalb" der Beschränkungen des Computers liegt, eine nicht berechenbare Zahl (durch den gegebenen Computer).
Alle physischen Computer haben Einschränkungen, daher gibt es nicht berechenbare Zahlen .
Ein Beispiel dafür ist (1)/(0) (Eins dividiert durch Null).

Obwohl die meisten Computer jetzt vor der Division durch Null "geschützt" sind, würden frühe Computer "für immer hängen bleiben" (bis Sie auf Reset drücken oder das Gerät ausschalten), wenn Sie es irgendwie geschafft haben, durch Null zu dividieren.

Meine Interpretation ihrer „philosophischen Bedeutung“ ist, dass es „Dinge“ gibt, die unsere Fähigkeiten übersteigen.