AFAIK, turing berechenbare Zahlen sind Zahlen, deren i-ter Index von einer Turing-Maschine zurückgegeben werden kann. Also wäre eine nicht-berechenbare Zahl etwas wie eine Zahl, deren Dezimalpunkte entschieden werden, wenn ein anderes Programm bei einer anderen Eingabe anhält usw. Aber wiederum ist PI eine reelle Zahl, die nicht von einer T.M. und kann daher nicht berechnet werden? Also, welche Schule des Denkens ist richtig?Ist PI eine errechnete Zahl?
Ja, π ist berechenbar. Es gibt ein paar äquivalente Definitionen für berechenbare, aber die nützlichste ist hier die, die Sie oben angegeben haben: Eine reelle Zahl r ist berechenbar, wenn es einen Algorithmus gibt, um seine n th Ziffer zu finden. Here ist ein solcher Algorithmus.
Ihr letztes Argument ist nicht Ton; Sie haben die Definition "kann die n th Ziffer" mit "kann alle Ziffern aufzählen" verwirrt. Letzteres ist keine nützliche Definition: Es schließt alle Irrationales und auch viele Rationales aus!
Eine interessante Tatsache ist, dass die berechenbaren Zahlen in der Tat zählbar sind, da wir die Turing-Maschinen, die sie produzieren, nach Gödel nummerieren können. Daher sind fast keine Reellen berechenbar.
Ich denke du meinst fast alle reellen Zahlen sind * nicht * berechenbar, da die Menge der Turing Maschinen zählbar ist. –
@larsmans: ja, natürlich =) – katrielalex
Danke für das Aufräumen! Prost! –
Ich bin nicht ganz sicher, was Sie mit "PI ist eine reelle Zahl, die nicht von einem T.M. aufgezählt werden kann". Ja, die reellen Zahlen sind nicht aufzählbar, aber ich sehe nicht, wie dies sich darauf auswirkt, ob PI berechenbar ist. '4' ist auch eine reelle Zahl, aber das bedeutet nicht, dass es nicht berechenbar ist. – sepp2k
Ähm, was ich meinte war, ich dachte, es würde eine unendlich lange Turing-Maschine brauchen, um PI zu berechnen, da PI selbst unendlich lang ist. –
@Gaurav: Würde es nach diesem Argument eine unendlich lange Turing-Maschine benötigen, um '1/3 'zu berechnen, da' 1/3 = 0.3333333 ... 'unendlich lang ist? – katrielalex