In welchem ​​Sinne „existiert“ eine Zahl, wenn sie sich als unberechenbar erweist?

Beantwortung Ihrer drei mathematischen/existentiellen Fragen der Reihe nach:

• Ja. Es gibt ein TM, das, wenn es auf einem leeren Band gestartet wird, schließlich (nach endlich vielen Schritten) mit der genauen Dezimalerweiterung von anhält$x=\Sigma\left(10^{100},10^{100}\right)$auf dem Band. Dasselbe gilt für$x\bmod 4$oder$x^x$ oder jede andere natürliche Zahl .
• Es gibt keine natürliche Zahl, „die nicht in endlicher Zeit berechnet werden kann“.
• Für natürliche Zahlen gibt es dieses Problem nicht.

Andererseits ist die Beweisbarkeit ein weiteres Problem: Es gibt keine natürliche Zahl$n$so dass ZFC beweist $\ BB(7918)=n,$und neuerdings haben wir das für alle$m\ge 748,$es gibt keine natürliche Zahl$n$so dass ZFC beweist$BB(m)=n.$(Hier$BB$ist die Busy Beaver-Funktion bezüglich der Anzahl der Schritte, die vor dem Anhalten unternommen werden.)

NB : Da sich Ihre Fragen (und Ihr gesamtes Intro) um natürliche Zahlen zu drehen schienen , ist dies der Kontext meiner obigen Antworten. Ganz anders verhält es sich im größeren Kontext der reellen Zahlen . Beachten Sie, dass jede natürliche Zahl eine endliche Darstellung hat, was der Hauptgrund dafür ist, dass sie berechenbar ist. Im Gegensatz dazu erfordert eine reelle Zahl typischerweise eine unendliche Darstellung, was die Möglichkeit eröffnet , nicht berechenbar zu sein. (Es stellt sich heraus, dass fast alle reellen Zahlen nicht berechenbar sind.)

Meiner Ansicht nach entstehen solche Fragen, weil nicht zwischen Absicht (Beschreibung einer Sache, arithmetischer Ausdruck, Quellcode eines Programms usw.) und Ausdehnung (beschriebene Sache, Ergebnis der Auswertung des Ausdrucks, Beobachtbares) unterschieden wird Verhalten des kompilierten Programms usw.). Vielleicht wird der folgende "Theorem" den Unterschied deutlich machen.

Satz. Jede natürliche Zahl ist berechenbar.

Nachweisen. Das müssen wir für jede natürliche Zahl zeigen$n$, gibt es eine Turing-Maschine, deren Ausgabe (sagen wir) eine unäre Darstellung von ist$n$. Wir gehen per Induktion vor. Es gibt sicherlich eine Turing-Maschine, deren Ausgang leer ist, also eine Repräsentation von$0$. Wenn wir eine Turing-Maschine haben, deren Ausgabe eine unäre Darstellung von ist$n$Es ist klar, dass wir es so modifizieren können, dass es nur eine weitere Einheit ausgibt, um eine unäre Darstellung von zu erhalten$n + 1$. Also ist jede natürliche Zahl tatsächlich berechenbar. ◼

An dem obigen Beweis ist nichts auszusetzen, aber trotzdem fühlen Sie sich möglicherweise nicht in der Lage, die Schlussfolgerung zu akzeptieren. Der einzige Ausweg ist der Schluss, dass es ein Problem mit der Interpretation der Aussage des Theorems gibt. Was dies tatsächlich beweist, ist, dass jede natürliche Zahl in Erweiterung berechenbar ist. Dieser Beweis hat nichts mit Natural-Numbers-in-Intension zu tun.

Um irgendetwas mathematisch Strenges über natürliche Zahlen in der Absicht sagen zu können, müssen wir zuerst ein mathematisches Modell zur "Beschreibung natürlicher Zahlen" auswählen. Leider gibt es keine kanonische Auswahl, und verschiedene Auswahlmöglichkeiten haben unterschiedliche Ausdruckskraft. Wenn Sie "Beschreibung einer natürlichen Zahl" als "Turing-Maschine, die sie berechnet" definieren, dann ist tautologisch jede natürliche Zahl-in-Intension berechenbar. Sie können es aber auch als „Formel“ definieren$\phi$in der Sprache der Mengenlehre mit mindestens einer freien Variablen$n$so dass ZFC beweist$\exists ! n \in \mathbb{N} . \phi$". In diesem Fall ist zwar nicht jede natürliche Zahl-in-Intension berechenbar – oder anders ausgedrückt, es gibt kein Verfahren (berechenbar oder nicht!), das die Formel umwandelt$\phi$in eine Turing-Maschine, die (ZFC beweist) die eindeutige natürliche Zahl berechnet$\phi$beschreibt.

Ich denke, diese Reihe von Fragen und Forschungsrichtungen ist eine der interessantesten in der Philosophie und den Grundlagen der Mathematik! Ich beantworte zuerst Ihre letzte Frage: Es gibt eine Vielzahl mathematischer Systeme, die auf verschiedene Weise versuchen, die Frage zu beantworten, dass nur berechenbare Objekte existieren dürfen. Ein gutes Beispiel ist das Teilsystem der Arithmetik zweiter Ordnung$RCA_0$, was für das rekursive Verständnisaxiom steht. Dieser Satz von Axiomen ist viel schwächer als beispielsweise die Peano-Arithmetik und ein Versuch, den Begriff der „berechenbaren Arithmetik“ zu erfassen. Aus rechnerischer Sicht hat es viele nette Eigenschaften, wie die Tatsache, dass jede Menge, in der nachgewiesen werden kann, existiert$RCA_0$hat ein Computerprogramm zum Testen der Mitgliedschaft, und tatsächlich kann ein solches Programm mehr oder weniger mechanisch aus dem Existenzbeweis rekonstruiert werden (dies ist mehr oder weniger die Curry-Howard-Korrespondenz, siehe Wikipedia und diesen Teil von Wikibooks Haskell für mehr).

Sie können auch einen Teil der alltäglichen Mathematik in machen$RCA_0$, wie der Beweis des Zwischenwertsatzes, die Existenz algebraischer Schließungen von Körpern, Gödels Korrektheitssatz für die Logik erster Ordnung und (eine schwache Version des) Vollständigkeitssatzes für denselben. Viele mathematische Aussagen von Interesse erweisen sich jedoch als nicht haltbar$RCA_0$, zum Beispiel ist es nicht so, dass jede beschränkte, wachsende Folge von reellen Zahlen eine obere Schranke hat - gerade weil es berechenbare Folgen von reellen Zahlen gibt, deren obere Schranken unberechenbar sind! Ein Beispiel für eine solche Folge ist eine Folge von unteren Schranken für die Haltewahrscheinlichkeit von Chaitin . Infolgedessen macht man Mathematik in$RCA_0$ist in vielerlei Hinsicht nicht sehr schön, oder zumindest ist es eine ganz andere mathematische Welt als die, an die die meisten reinen Mathematiker gewöhnt sind.

Mehr dazu$RCA_0$, siehe zum Beispiel Subsystems of Second Order Arithmetic von Stephen G. Simpson. Das Projekt der berechenbaren Grundlagen der Mathematik ist für verschiedene Definitionen des Wortes berechenbar ein weitreichendes, zu umfangreich, um hier alles Relevante aufzunehmen. Stichworte, die hier hilfreich sein könnten, sind „Konstruktivismus“, z. B. Bishops Foundations of Constructive Analysis, „recursive analysis“ und „recursive counterexamples“, und abhängige Typentheorie, wie sie in den Programmiersprachen Idris und LEAN verwendet wird.

Zu Ihrer zweiten Frage: Ja, die Beziehung zwischen Aussagen, die unabhängig von einer Reihe von Axiomen sind, und Zahlen, die nicht berechnet werden können, ist sowohl intuitiv als auch formal stark. Das klassische Beispiel für eine Aussage, die beispielsweise von ZFC unabhängig ist, ist, dass ZFC konsistent ist, was wir als bezeichnen werden$Con(ZFC)$. Aber$Con(ZFC)$ist gleichbedeutend mit einer Aussage über ein bestimmtes Computerprogramm: „Das Computerprogramm, das alle Beweise in ZFC durchsucht und anhält, wenn es einen Widerspruch findet, hält nicht an“. Das wiederum hängt (neben anderen nicht berechenbaren Funktionen) mit der Busy Beaver-Funktion zusammen. Nehmen wir insbesondere an, „das Computerprogramm, das alle Beweise in ZFC durchsucht und anhält, wenn es einen Widerspruch findet“, ist eine Turing-Maschine mit$X$Zustände. Dann jede Aussage über den Wert von$\Sigma(X)$bedeutet entweder$Con(ZFC)$oder$\neg Con(ZFC)$, aber wie wir wissen, beweist ZFC keine dieser Behauptungen, ZFC kann es nicht beweisen$\Sigma(X)$gleich einem bestimmten endlichen Wert ist.

Hier gibt es eine Subtilität, die teilweise in der Antwort von res angesprochen wird : ZFC beweist die oberflächlich bezogene Aussage: „Es gibt eine Turing-Maschine, die ausgibt$\Sigma(X)$“. Aber das ist in gewisser Weise trivial, denn ZFC beweist die Aussagen „es gibt eine Turing-Maschine, die 1 ausgibt“ und „es gibt eine Turing-Maschine, die 2 ausgibt“ usw., was es „für alle natürlichen Zahlen“ beweisen lässt$n$, gibt es eine Drehmaschine, die n” ausgibt. Kombiniert mit der ebenfalls trivialen Aussage „$\Sigma(X)$eine natürliche Zahl ist“, erhalten wir jetzt natürlich „es gibt eine Turing-Maschine, die ausgibt$\Sigma(X)$“, aber dieser Satz kann jetzt gesehen werden, um nicht zu erfassen, was er zu bedeuten scheint. Wir wollen nicht nur wissen, dass eine der Turing-Maschinen auf der Welt die gesuchte Zahl ausgibt, wir wollen wissen, welche, und da kann uns ZFC nicht helfen. Tatsächlich wird sich jedes Axiomensystem, das rekursiv aufzählbar ist (es gibt ein Computerprogramm, das alle möglicherweise unendlichen Sätze von Axiomen ausdruckt), letztendlich nicht beweisen$\Sigma(Y)$für ein ausreichend großes Y durch das gleiche oben angegebene Argument.

Für den Beweis von Adam Yedidia und Scott Aaronson, dass der Wert für Y in ZFC höchstens 8000 beträgt (später auf 748 reduziert), siehe A Relatively Small Turing Machine Whose Behavior Is Independentof Set Theory und Aaronsons Blogbeitrag darüber . Weitere Informationen zur Busy Beaver-Funktion und ihrer Beziehung zu den Grundlagen der Mathematik finden Sie in Aaronsons The Busy Beaver Frontier .

Ich habe Ihre erste Frage zuletzt stehen lassen, weil sie in gewisser Weise die heikelste und philosophischste ist. Zum Beispiel ist es sicherlich wahr, dass ZFC (und tatsächlich PA und andere ziemlich schwache mathematische Systeme) die Aussage beweisen

Unterschiedliche Menschen haben unterschiedliche Reaktionen auf diesen philosophischen Punkt. Zum Beispiel basiert das gesamte Gebiet der konstruktiven Mathematik weitgehend auf „wir sollten keine Zahlen und allgemeiner mathematische Objekte haben, deren Existenz bewiesen, aber nicht tatsächlich konstruiert ist“, für unterschiedliche Formalisierungen dessen, was genau „konstruiert“ bedeutet. Die meisten Mathematiker hingegen haben sich darüber entweder keine Gedanken gemacht, machen sich darüber keine allzu großen Gedanken oder akzeptieren, dass sie mit Objekten arbeiten, die sich (manchmal) grundlegend von denen unterscheiden, die berechenbar sind. Zwei Gründe, um zu glauben, dass die letzte Idee nicht zu verrückt ist: Erstens geht es in der Mathematik immer darum, unbekannte Dinge herauszufinden. Wenn ich eine Zahl definiert habe$Q$über$Q = 1$Wenn$P \not= NP$anders$Q = 0$, dann haben wir auch keine gute Möglichkeit, den Wert von zu beweisen$Q$ist, obwohl die meisten Mathematiker denken, dass ZFC dies beweist$Q=1$, und sicherlich, dass der Wert von$Q$ist nicht unabhängig von ZFC. Zweitens ist dies unscharfer, aber ein Großteil der Mathematik stützt sich auf Objekte, die zumindest intuitiv nicht berechenbar sind, z. B. reelle Zahlen. Die Vorstellung eines Kontinuums von reellen Zahlen, das sich in beide Richtungen unendlich weit ausdehnt und keine „Lücken“ hat, ist in gewisser Weise sehr intuitiv und passt nicht wirklich gut zu meiner Vorstellung davon, was ein Computer eigentlich leisten kann ! Sie können reelle Zahlen als Cauchy-Folgen codieren, die (einige davon) als endliche Computerprogramme darstellbar sind, aber ich denke sicherlich nicht die meiste Zeit an ein Computerprogramm, das (endliche Darstellungen von) Cauchy-Folgen umhermischt, wenn ich an Theoreme wie denke „Jede monoton steigende Folge reeller Zahlen hat eine kleinste obere Schranke“.

Obwohl diese Antwort bereits sehr lang geworden ist, wäre sie schließlich wahrscheinlich nicht vollständig, ohne zumindest einen weiteren philosophischen Punkt zu erwähnen: Formalismus versus Platonismus. Kurz gesagt, der Formalismus sagt „alles, was ein Mathematiker tut, ist in den Symbolen kodiert, in der Mathematik dreht sich alles um die formale Ableitung von Theoremen aus Axiomen durch Beweise“, während der Platonismus sagt, „mathematische Objekte existieren in gewissem Sinne wirklich, es gibt ein ‚wahres Tatsächliches‘. was Sie meinen, wenn Sie 'natürliche Zahl' sagen, abgesehen davon, dass Ihre Beweise über natürliche Zahlen Symbolen auf einer Seite entsprechen, die den mathematischen Beweisregeln folgen". Diese philosophische Kluft bezieht sich auf unsere obige Diskussion, weil (soweit ich das beurteilen kann) ein Formalist sagen würde, dass es keine wirkliche „Tatsache“ über den Wert von gibt$\Sigma(1000)$, oder irgendein anderer Wert von$\Sigma$für diese Angelegenheit. Da bleibt nur die Tatsache, dass ZFC beweist$\Sigma(3)=6$, und ZFC beweist keinen Wert für$\Sigma(1000)$. Während ein Platoniker sagen würde$\Sigma(3)$ist wirklich 6, wenn ich eine „natürliche Zahl“ definiere und ein Computerprogramm und so weiter, dann ist da etwas Reales, das ich damit meine, es sind nicht nur Symbole. Ebenso gibt es einen wahren Wert von$\Sigma(1000)$, wenn Sie mir ein bestimmtes Computerprogramm geben, wenn ich es auf meinem Laptop ausführen würde, würde es einfach anhalten oder nicht anhalten, ZFC kann das nicht für alle Programme beweisen, sicher, aber das bedeutet nicht, dass es nicht so ist richtig oder falsch.

Ein Grund, diese letztere Position für sinnvoll zu halten, ist, dass es nur ein Axiom der Form gibt$\Sigma(X)=n$, Wo$n$ist eine Dezimalerweiterung einer natürlichen Zahl, die mit ZFC konsistent ist (vorausgesetzt, ZFC ist konsistent). Dies ist mit der Tatsache vereinbar, dass der Wert von$\Sigma(1000)$ist unabhängig von ZFC, weil dies einfach garantiert (über den Vollständigkeitssatz von Gödel), dass es zwei Axiome gibt, die beide mit ZFC übereinstimmen:$\Sigma(1000)=n$Und$\Sigma(1000) \not = n$, für eine explizit ausgeschriebene natürliche Zahl$n$. Viel Glück beim Herausfinden, was relevant ist$n$ist doch!

Gibt es eine Version der Mathematik oder ein Axiomensystem, das dieses Problem löst? (dh wo die Wohldefiniertheit eines Objekts der Berechenbarkeit entspricht?)

Es gibt eine Philosophie der Mathematik, die als Konstruktivismus bekannt ist und behauptet, dass mathematische Objekte nur dann existieren, wenn sie explizit konstruiert werden können. "Wohl definiert" ist hier nicht wirklich der richtige Begriff, wir sollten bei "vorhanden" bleiben, aber im Prinzip sollte dies die gesuchte Antwort sein. Zitat Wikipedia :

Nimmt man beispielsweise die algorithmische Sichtweise ein, dann sind die hier konstruierten reellen Zahlen im Wesentlichen das, was man klassischerweise als berechenbare Zahlen bezeichnen würde.

Für die von Ihnen gestellte Frage ist dies einfach nicht der Fall, solange Sie eine gute Definition von "wohldefiniert" haben. Wenn Sie eine Methode zur Berechnung der gewünschten Zahl auf ein Blatt Papier schreiben können (und vorausgesetzt, Sie beweisen, dass Ihre Definition impliziert, dass sie eindeutig ist), können Sie auch einen Code schreiben, der sie mit der gewünschten Genauigkeit berechnet, und dies definiert Ihre Turing Maschine. Also eigentlich würde ich sagen, dass wohldefiniert und berechenbar zwei Synonyme sind.

Ich werde die Antwort von res vorsichtig zurückdrängen und eine alternative Perspektive bieten, in der diese Zweifel, die Sie haben, tatsächlich gerechtfertigt sind.

Anstelle von Mengenlehre, die ZFC mit klassischer Logik bedeutet, arbeiten wir in der Tat mit Intuitionistischer Logik , mit IZF statt ZFC, was ziemlich ähnlich ist, mit Ausnahme von Choice, das wir sowieso nicht wirklich brauchen, wenn wir über Turingmaschinen und natürliche Zahlen sprechen.

Nehmen wir eine Familie von Prädikaten$\Gamma(n, m)$(sagen$\Gamma(n, m):=\Sigma(n, n) = m$zum Beispiel) und das sagen$\Gamma$ist eine berechenbare Zahl , wenn es eine Turing-Maschine gibt, die als Eingabe dient$n$und kehrt zurück$m$so dass$\Gamma(n, m)$hält.

Lassen Sie uns nun noch einmal Ihre 3 Fragen beantworten:

1. Im IZF kann die Zahl 4 (und die meisten Zahlen, die Sie berechnen können) nachgewiesen werden . Jedoch,$\Sigma(n, n)$im Allgemeinen nicht: Tatsächlich müssten Sie beweisen, dass entweder ein beliebiges TM ewig laufen muss oder nach einer bestimmten Anzahl von Schritten anhält. Dafür braucht man wirklich die ausgeschlossene Mitte.

2. Die Existenz einer „nicht berechenbaren“ Zahl in diesem Sinne impliziert den Unvollständigkeitssatz ziemlich direkt: Wenn die Arithmetik vollständig wäre, könnten Sie jede Zahl berechnen, indem Sie alle Beweise aufzählen und aufhören, sobald Sie einen Beweis von haben$\Gamma(\overline{n},\overline{m})$(die Sie schließlich in einer vollständigen Theorie finden müssen, falls eine solche vorhanden ist$m$existiert).

3. Man kann zeigen (unter der Annahme einiger standardmäßiger und notwendiger Konsistenzaussagen), dass if$IZF \vdash \forall n\exists m, \Gamma(n,m)$dann gibt es tatsächlich eine berechenbare Funktion$f$so dass für jede Zahl$k$,$IZF\vdash \Gamma(\overline{k},\overline{f(k)})$, eine Eigenschaft, die, wie Sie bemerkt haben, für ZFC nicht gilt. Es ist erwähnenswert, dass die Umkehrung unmöglich gelten kann: Es muss immer eine berechenbare Funktion geben$g$so dass es kein Prädikat gibt$P$mit$IZF\vdash \forall n\exists m, P(n, m)$, Und$P(k, l)$hält genau wann$l = g(k)$.