Ist PI eine Turing berechenbare Zahl? [geschlossen]

Question

AFAIK, Turing berechenbare Zahlen sind Zahlen, deren i-te Index kann durch eine Turing-Maschine zurückgeführt werden. So eine nicht-berechenbare Zahl so etwas wie eine Zahl, der Dezimalzahlen entschieden, ob ein anderes Programm Aussetzer auf einem anderen Eingang wäre, etc. Aber dann wieder, ist PI eine reelle Zahl, das von einem T. M. aufgezählt läßt mich nicht und somit kann nicht berechnet werden? So welche Schule des Denkens ist richtig?

Answer 1

Ja, π ist berechenbar. Es gibt ein paar äquivalenten Definitionen der berechenbaren, aber die nützlichste hier ist diejenige, die Sie oben angegeben haben: eine reelle Zahl r berechenbar ist, wenn es einen Algorithmus gibt seine nth Zahl zu finden. Hier ist ein solcher Algorithmus.

Ihr letztes Argument ist nicht stichhaltig; Sie haben die Definition verwechseln mit „die Ziffern können alle aufzählen“ „können die nth Ziffer finden“. Letzteres ist nicht eine brauchbare Definition: es Regeln Sie alle irrationalen und viele rationals auch

Eine interessante Tatsache ist, dass die berechenbaren Zahlen in der Tat zählbar sind, da wir können Gödel-Nummer der Turing-Maschinen, die sie produzieren. Daher fast keine reellen Zahlen berechenbar.