Rekursion versus Iteration

[Wildcard]

Dass sich daraus nun so ein Thread entwicklen würde, habe ich nicht intendiert, aber ich finde es mal ganz lustig über solche Dinge zu diskutieren, anstatt irgendeinem/-er Java-Anfänger/-in zum N-ten Mal bestimmte Dinge zu erläutern.

Stimme ich dir voll und ganz zu!

Mir passt jetzt der "Schuh" durchaus, dir auch?

Schön das wir jetzt beide neue Schuhe haben :wink:

 

[Sym]

Aber BTW: Schreib du doch einmal einen performanten Fibo-Algorithmus. Ich habe hier einen, der schafft Fibo(192) in 10 Millisekunden. Anstatt große Töne zu spucken, selber programmieren, ok?

Ist ja nicht böse gemeint
BTW:
So? laut Zeitmessung 0, aber das hat keine Aussagekraft bei einem Durchlauf :wink:

public class Fibo
{
    public static final double a = (1.0 + Math.sqrt(5))/2.0;
    public static final double b = (1.0 - Math.sqrt(5))/2.0;
    public static final double c = 1.0/Math.sqrt(5);
    
    static double fibonacci(int n) 
    {
        return c*(Math.pow(a,n)-Math.pow(b,n));
    }
    public static void main(String[] args)
    {
        long time = System.currentTimeMillis(); 
        System.out.println(System.currentTimeMillis()-time);
        System.out.println((int)fibonacci(192));
        
    }
}

Der Algorithmus ist es gar nicht wert, ein Algorithmus geschimpft zu werden. Da wird einfach die explizite Formel genutzt. :LOL:
Mein bisher schnellster Algorithmus (bis auf die o.g Lösung ) war die Matrix-Vektor Multiplikation der entsprechenden Matrix.

 

[Bleiglanz]

@kopfsalat: immer locker bleiben, es geht mir einzig und allein um eine gewisse Genauigkeit und Schärfe der Begriffe

Am liebsten würde ich ja nur folgendes antworten:
Eine "berechenbare irrationale Zahl" ist natürlich eine irrationale Zahl, die berechenbar ist.
D.h., sie ist eine irrationale Zahl (hat also eine unendliche nicht-periodische Dezimaldarstellung), aber sie ist keine zusammenhangslose 'gewürfelte' Ziffernfolge, sondern die Ziffernfolge lässt sich berechnen. Das geschieht unter Angabe eines Algorithmus (in seiner Definition als beliebige Berechnungsvorschrift), der z.B. auf einer Potenzreihe basieren kann und auf endlich viel Platz beschrieben werden kann.

Wir sind uns wohl einig was wir mit "Berechenbarkeit" meinen? Nämlich die einzig existierende Definition, für die man laut Church jede sinnvolle bekannte Definition einsetzen kann, nehmen wir von mir aus Turingmachinenberechenbarkeit (ist ja egal)

Eine reelle Zahl x kann in dieser Definition gar nicht berechenbar sein (weil in diesem Kontext reelle Zahlen überhaupt nicht vorkommen), dagegen könnte es einen Algorithmus D geben, der bei eingabe einer natürlichen Zahl k die ersten k Ziffern der Dezimalentwicklung von x berechnet. Das soll vermutlich deine Definition von "berechenbarer reeller Zahl" sein.

Finde ich ganz OK als Definition für "berechenbare reelle Zahl", IMHO macht es aber keinen Sinn zu sagen, dass der Algorithmus D den WERT dieser Zahl berechnet

Das Ergebnis der Berechnung einer Berechnungsvorschrift ist berechenbar.

Frage: Ist als Ergebnis eine relle Zahl erlaubt?

PI ist berechenbar. Punkt.

In obigem Sinn ja, allerdings macht der Algorithmus etwas anderes als man umgangssprachlich erwarten würde: er "berechnet" nicht die Zahl Pi, sondern für gegebenes k die ersten k Dezimalziffern.

Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst - kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???

Du wirfst gedanklich die Begriffe "n-te Partialsumme" und den "Wert der Reihe" (also 'nach' dem Grenzübergang n gegen unendlich) durcheinander.
Der Wert der Reihe (also der Limes der Partialsummen) ist der exakte Wert von PI.

Tu ich nicht, das ist mir noch nie passiert dass ich die beiden verwechsle. Dieser Wert kann überhaupt nicht in irgendeiner Rechenmaschine "dargestellt werden", also kannst IMHO nicht sagen, dass es eine Maschine gibt, die diesen Wert "berechnet"

Anhand einer solchen Darstellung kann man natürlich ein Verfahren ableiten, um PI als Dezimalzahl darzustellen. Eine Darstellung als Dezimalzahl kann natürlich auf endlich viel Platz nur eine Näherung sein, aber das ist egal, da der Computer ja ohne Fehlabweichungen auch mit dem Wert der Reihe rechnen kann, wenn er dies geschickt anhand einer geeigneten Darstellung tut (insbesondere nicht als binär codierte Fließkomma-Zahl).

Hä? Wie soll er mit "dem Wert der Reihe" rechnen, wenn er diesen Wert gar nicht kennt?? Er kann natürlich Berechnungen mit der Näherung durchführen - und bei geschickter Programmierung auch für das Ergebnis wieder Zusicherungen über die Genauigkeit machen (sog. Intervall-Artithmetik)

Die Zeichenkette 'PI' bezeichnet dasselbe wie eine entsprechende Reihendarstellung, nämlich den exakten Wert der Kreiszahl. Indem man symbolisch mit diesen Darstellungen rechnen kann, ist die Konsequenz, dass man also mit einem Computer mit (berechenbaren) irrationalen Zahlen ohne Fehler rechnen kann. Der Wert des Ausdrucks 'PI/2' z.B. als Ausgabe einer Rechnung ist also das exakte Ergebnis. Du hattest den Ausdruck PI/2 vorhin so verächtlich erwähnt. Wenn mir mein Rechner als Ergebnis PI/2 liefert, dann freue ich mich darüber, dass er das exakte Ergebnis - obwohl irrational - berechnen und ausgeben kann. Das Ergebnis 1,5707963267 wäre nicht so interessant, da man niemals wüßte, ob das Ergebnis nun wirklich PI/2 ist, oder nur nah dran.

Du freust dich nur deshalb, weil zufällig PI zum Alphabet deiner Symbol-Manipulations-Maschine gehört, über die allermeisten Wörter, die von dieser Maschine ausgespuckt werden würdest du dich wohl nicht freuen!

Schon wahr, das symbolische Rechnen hat einen gewissen Sex-Appeal. Aber angenommen, dein symbolischer Kalkulator gibt dir eine hyperkomplizierte Formel aus (eine unendliche Reihe oder was schlimmeres): der "Wert" könnte Pi sein oder auch nicht, wie willst du das entscheiden??

Immerhin weiss ich, was ich mit dem Begriff 'berechenbar' meine.

es muss was sonderbares sein

Nach der Churchschen These lässt sich übrigens alles Berechenbare durch eine entsprechend äquivalente Codierung einer entsprechenden Berechnungsvorschrift auf einer Turingmaschine, und damit auch auf einem PC ausführen.
Interessant dabei ist, dass es abzählbar unendlich viele Berechnungsvorschriften gibt, aber z.B. überabzählbar unendlich viele Dezimalzahlen (mit unendlich vielen Nachkommastellen). Daher gibt es "unendlich mal mehr" nicht-berechenbare Zahlen.

wohl war, wenn man "berechenbare reelle Zahl" so definiert wie oben gesagt

Die Energie, so ausführlich zu antworten ziehe ich übrigens daraus, dass es mich in diesem Beitrag gestört hatte, wie vehement herablässig urteilend einige deiner Aussagen in diesem Thread auf mich wirkten, obwohl Du teilweise nur zu weniger als 100% zu wissen scheinst, wie konform deine Aussagen mit bestehenden Definitionen sind.

Über die konformität meiner Aussagen mit "bestehenden Definitionen" bin ich mir schon im klaren, glaubs mir

Einfacher: Manchmal stimmen deine Aussagen einfach nicht, und du bist nicht bereit, das einzusehen.

Ja, warum sagst du mir dann keine?? Die "stimmen nicht", weil wir unter den verwendeten Begriffen etwas ganz anderes verstehen (also meine Aussage "Alle Quargl sind Quirgl" ist in deinen Augen falsch, weil bei dir ein Quirgl eben etwas ganz anderes ist...

oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread

Das fördert Fehlinformation, und kommt vermutlich bei den wenigsten gut an. Deswegen wollte ich hier mal ein paar Aussagen von dir inhaltlich unter die Lupe nehmen (und von mir aus gerne auch weiter inhaltlich diskutieren), aber ohne dich persönlich anzugreifen.

das hast du eben ganz genau nicht gemacht. Wenn du das tun willst, dann schreib bitte vorher auf, was du unter

"berechenbarer reeller Zahl"

verstehen willst.

 

[Bleiglanz]

ACH JA, UM MAL ZUM THEMA ZURÜCKZUKOMMEN

wollte ich eigentlich ganz am anfang schreiben, bin leider abgeschwoffen

bei manchen Rekursionen ("deterministisch") besteht die möglichkeit zur Optimierung:

Die naive rekursive Implementierung f(n)=f(n-1)+f(n-2) hat einen gewaltigen Nachteil, weil nämlcih f(1) vieeeel zu oft berechnet wird

wenn man man genau hinschaut

f(n-1)
/* wenn ich hier reinrekursiere...
dann wird doch f(n-2) eh mit berechnet
...
am besten ich lass mir f(n-2) als seiteneffekt mit zurückgeben
.....
das funktioniert ja dann auch "rekursiv..."
*/

+

f(n-2)

 

[kopfsalat]

(...)dann schreib bitte vorher auf, was du unter "berechenbarer reeller Zahl" verstehen willst.

Na, dass hier:

Wozu führte Turing die Idee einer solchen Maschine ein? Mit ihrer Hilfe definierte er eine "berechenbare Zahl" ("computable number") als reelle Zahl, für die eine passend programmierte Turing-Maschine jede Dezimalstelle ausgeben kann, ausgehend von einem leeren Band. Turing zeigte, dass die Menge der berechenbaren Zahlen abzählbar ist, und gab auch eine nicht-berechenbare Zahl an.

Hinter deinem Wiki-Link stand zwar auch die Definition einer berechenbaren reellen Zahl, aber etwas versteckt:

Zudem lassen sich geeignete Wörter definieren, die eine schnell konvergierende Approximation von reellen Zahlen darstellen. Über solche Wörter lässt sich der Berechenbarkeitsbegriff auf die Menge der reellen Zahlen ergänzen.

Deine Vermutung im letzten Beitrag also...

In obigem Sinn ja, allerdings macht der Algorithmus etwas anderes als man umgangssprachlich erwarten würde: er "berechnet" nicht die Zahl Pi, sondern für gegebenes k die ersten k Dezimalziffern.
(...)
wohl war, wenn man "berechenbare reelle Zahl" so definiert wie oben gesagt

...ist richtig, den 'im obigen Sinne' bezeichnet genau den Sinn, den Turing ursprünglich beabsichtigte, und dann so definiert hat, und der genau so auch gelehrt wird.

oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread

Hier ein paar Aussagen von dir:

(allein um eine einzige reelle zahl zu speichern bräuchte der "unendlich" viel RAM)

...müsste ergänzt werden zu: um eine einzige reelle Zahl in ihrer Dezimaldarstellung, also in Form der Aneinanderreihung der Koeffizienten der gegen sie konvergierenden Potenzreihe (für die Dezimalbruchentwicklung mit z=1/10) hinzuschreiben, bräuchte man "unendlich" viel RAM. Wählt aber man eine andere Potenzreihe als diese (mit demselben Wert), so kann man z.B. bei Wurzeln/Sinussen/e/ln/... einfach ein einfaches auf rationalen Zahlen arbeitendes Bildungsgesetz derer sämtlichen Koeffizienten angeben, speichern und damit auch weiterarbeiten. Also braucht man dafür nur endlich viel RAM.

kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden

'Algorithmus' hat mehrere Definitionen, und diese unterscheiden sich zum Teil sehr stark im Umfang dessen, was sie als Algorithmus durchgehen lassen. Der 'weiteste' Begriff ist sicherlich die Beschreibung einer Turingmaschine als Algorithmusbeschreibung zu sehen. Dann ist selbst das einfache Hinschreiben der Zahl '2' ein Algorithmus, wie jedes andere denkbare und beliebig komplizierte IO-Verfahren auch. Letztere Definition haben wir innerhalb einer Vorlesung genutzt (in einer anderen eine andere Definition, welche den Vorteil hat, dass dann nicht einfach jedes Verfahren ein Algorithmus ist, aber den Nachteil, dass die Grenze immer schwammig ist). Deine Aussage ist somit aber inkorrekt. Das ist wie mit N. Manche Profs nutzen die Definition 0 ist in N, andere die Definition, 0 ist nicht in N.

Diese beiden Aussagen waren nur 2 Zeilen voneinander entfernt, gleich aus deinem nächsten Beitrag stammt diese:

..., denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.

Nein, "dafür" sind keine Algorithmen bekannt, was du meinst sind NÄHERUNGSFORMELN

Wie zwei Beiträge vorher von mir schon erwähnt: beliebig genau berechnen (hier im Sinne: die Dezimalstellen ausgeben) bedeutet, mit beliebig starker, aber endlicher Näherung zu berechnen. Dafür sind Algorithmen bekannt. (Und abgesehen davon: daher ist die entsprechende Zahl als berechenbar definiert.)

Soweit dazu.

Jetzt versuche ich nochmal mit folgendem aufzuräumen:

Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst - kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???
(...)
Dieser Wert kann überhaupt nicht in irgendeiner Rechenmaschine "dargestellt werden", also kannst IMHO nicht sagen, dass es eine Maschine gibt, die diesen Wert "berechnet"

Durch die geeignete Wahl der Darstellung (insbesondere nicht als Dezimalzahl, also als Folge der Koeffizienten... (s.o.)), lässt sich sqrt(5) - wie auch zig andere irrationale Zahlen - zu 100%, absolut ohne Informationsverlust, binär codiert in einem Rechner speichern, indem man entweder einfach 'sqrt(5)' speichert (womit man noch nicht soo gut rechnen kann, ausser z.B. sqrt(5) * sqrt(45) = sqrt(225) = 15, was nun schon möglich ist), oder aber indem man für andere Berechnungen auf geeignetere Darstellungen zurückgreift, wo die Koeffizienten der Potenzreihe einem klaren Bildungsgesetz unterliegen. Dann kann man diese Reihen z.B. zusammenaddieren, die Brüche erweitern, kürzen, Teleskopsummen bilden, kreuz und quer hin und herrechnen (alles automatisiert), und gelangt dann auf mehr oder weniger schöne Ausdrücke als Ergebnis, welche wiederum stellvertretend für den exakten Wert des Ergebnisses stehen.

Du freust dich nur deshalb, weil zufällig PI zum Alphabet deiner Symbol-Manipulations-Maschine gehört, über die allermeisten Wörter, die von dieser Maschine ausgespuckt werden würdest du dich wohl nicht freuen!

Es kommt auf den Zweck an. Wenn ich in Spielen irgendwelche Koordinaten zu berechnen wünsche, dann brauche ich diese Genauigkeit nicht, und mir reichen die schnell zu berechnenden Fliesskomma-Näherungen. Aber in vielen anderen Anwendungen der Mathematik bringt es einem Mathematiker viiiell mehr, einen auch komplizierten Ausdruck zu erhalten, als irgendeine wertlose Dezimalzahl - selbst wenn der Ausdruck sehr kompliziert ist. Man sieht dann darin z.B. Parallelen zu anderen Ausdrücken, etc. Auch kann es nur so passieren, das man z.B. als Ergebnis eine natürliche Zahl erhält, und weiss, dass diese das exakte Ergebnis ist.
Bei weitem nicht alle berechenbare Zahlen haben schließlich so ein einfaches Bildungsgesetz wie PI, sqrt, ln, e, etc., aber trotzdem können sie in Computern gespeichert und verarbeitet werden.
Da der Mensch aber oft auch eine Vorstellung von der Größe der Zahl wünscht, rechnet er dann noch anhand dieser Formel eine Näherung in Dezimaldarstellung aus, und kann dann fröhlich seine Ordnungsrelation anwenden.

MuPad, Maple, Mathematica, etc. können mit sämtlichen berechenbaren Zahlen rechnen.

(btw: ich bin ganz locker :wink: Das ist nur das generelle Foren-Problem, dass man seinen Worten so schlecht und mißverständlich einen eindeutigen Unterton zuordnen kann.)

 

[Bleiglanz]

(...)dann schreib bitte vorher auf, was du unter "berechenbarer reeller Zahl" verstehen willst.

Na, dass hier:

Wozu führte Turing die Idee einer solchen Maschine ein? Mit ihrer Hilfe definierte er eine "berechenbare Zahl" ("computable number") als reelle Zahl, für die eine passend programmierte Turing-Maschine jede Dezimalstelle ausgeben kann, ausgehend von einem leeren Band. Turing zeigte, dass die Menge der berechenbaren Zahlen abzählbar ist, und gab auch eine nicht-berechenbare Zahl an.

Warum sagst du das nicht gleich

oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread

Hier ein paar Aussagen von dir:

(allein um eine einzige reelle zahl zu speichern bräuchte der "unendlich" viel RAM)

...müsste ergänzt werden zu: um eine einzige reelle Zahl in ihrer Dezimaldarstellung, also in Form der Aneinanderreihung der Koeffizienten der gegen sie konvergierenden Potenzreihe (für die Dezimalbruchentwicklung mit z=1/10) hinzuschreiben, bräuchte man "unendlich" viel RAM. Wählt aber man eine andere Potenzreihe als diese (mit demselben Wert), so kann man z.B. bei Wurzeln/Sinussen/e/ln/... einfach ein einfaches auf rationalen Zahlen arbeitendes Bildungsgesetz derer sämtlichen Koeffizienten angeben, speichern und damit auch weiterarbeiten. Also braucht man dafür nur endlich viel RAM.

Das ist jetzt wirklich Käse, natürlich habe ich nicht Zahlen wie 0,1 oder 2 gemeint

Dein Einwand ist wie IMHO nicht korrekt, denn eine "Darstellung" einer reellen Zahl innerhalb eines Rechners als "symbolische Formel -Bildungsgesetz- für die Koeffizienten" ist ja nichts anderes, als eine etwas umgeschriebene Turingmschine (d.h. du speicherst den Algorithmus von dem oben die Rede war)

Was ich meinte ist der WERT einer irrationalen reellen Zahl..., aber wenn du meinst, dass

"Wert einer reellen Zahl" == "formale Repräsentation einer Turingmaschine, die für gegebenen Input k die ersten k Ziffern berechnet

ist meine Aussage wohl falsch

kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden

'Algorithmus' hat mehrere Definitionen, und diese unterscheiden sich zum Teil sehr stark im Umfang dessen, was sie als Algorithmus durchgehen lassen. Der 'weiteste' Begriff ist sicherlich die Beschreibung einer Turingmaschine als Algorithmusbeschreibung zu sehen. Dann ist selbst das einfache Hinschreiben der Zahl '2' ein Algorithmus, wie jedes andere denkbare und beliebig komplizierte IO-Verfahren auch. Letztere Definition haben wir innerhalb einer Vorlesung genutzt (in einer anderen eine andere Definition, welche den Vorteil hat, dass dann nicht einfach jedes Verfahren ein Algorithmus ist, aber den Nachteil, dass die Grenze immer schwammig ist). Deine Aussage ist somit aber inkorrekt. Das ist wie mit N. Manche Profs nutzen die Definition 0 ist in N, andere die Definition, 0 ist nicht in N.

Oh man, lies dir mal den Kontext durch?! Diese Aussage war natürlich falsch, weil ja in diesem Thread jemand unterwegs ist, der "dafür" das Wort Algorithmus verwendet!

..., denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.

Nein, "dafür" sind keine Algorithmen bekannt, was du meinst sind NÄHERUNGSFORMELN

Wie zwei Beiträge vorher von mir schon erwähnt: beliebig genau berechnen (hier im Sinne: die Dezimalstellen ausgeben) bedeutet, mit beliebig starker, aber endlicher Näherung zu berechnen. Dafür sind Algorithmen bekannt. (Und abgesehen davon: daher ist die entsprechende Zahl als berechenbar definiert.)
Soweit dazu.

jo, gut dass das jetzt geklärt ist: "beliebig genau" heisst für jedes gegebene FESTE k die ersten k Dezimalziffern berechnen zu können

Jetzt versuche ich nochmal mit folgendem aufzuräumen:

Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst - kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???
(...)
Dieser Wert kann überhaupt nicht in irgendeiner Rechenmaschine "dargestellt werden", also kannst IMHO nicht sagen, dass es eine Maschine gibt, die diesen Wert "berechnet"

Durch die geeignete Wahl der Darstellung ... lässt sich sqrt(5) ..... wie auch zig andere irrationale Zahlen - zu 100%, absolut ohne Informationsverlust, binär codiert in einem Rechner speichern....

typischer Fall von Verwechslung: wir reden die ganze Zeit von sqrt(5) und jetzt fängst du wieder mit dem String "sqrt(5)" an.

MuPad, Maple, Mathematica, etc. können mit sämtlichen berechenbaren Zahlen rechnen.

Die können sogar VIEL mehr, nämlich mit ALLLEN reellen Zahlen rechnen, denn ist x obige konkret von Turing vorgelegte nicht berechenbare reele zahl (oder einfach nur IRGENDEINE reelle Zahl), dann können Mupad, Maple und Mathematika ohne Probleme

sin(x), cos(x), sqrt(x)

"berechnen", in dem sie einfach diese strings ausspucken...

Das ist vermutlich einfach eine Geschmackfrage, meiner Meinung nach kann Maple nämlich überhaupt nicht mit Zahlen rechnen [wenn man von der Numerik mal absieht...], und wenn Maple auf seinem Bildschirm nach dem Prompt den String

"sqrt(5)"

ausgibt, dann hat Maple in meinen Augen nicht die Zahl sqrt(5) berechnet,,,,

locker bleiben!

 

[kopfsalat]

Ahoi, ich bins nochmal, allerdings habe ich nicht viel Zeit, da ich gleich für eine Woche ins schöne Konstanz fahre!

typischer Fall von Verwechslung: wir reden die ganze Zeit von sqrt(5) und jetzt fängst du wieder mit dem String "sqrt(5)" an.

Das meinte ich mit Trennung von einer Zahl selbst und ihrer Darstellung.

Jede Art und Weise, eine Zahl irgendwie graphisch zu veranschaulichen, ist eine symbolische Darstellung.
Eine Zeichenkette, wie 2 oder 3,234 oder 0x124 oder 0110101001110011010101100 oder 23^3 oder sqrt(5) oder PI oder eine Potenzreihe mit bestimmten Koeffizienten oder ein beliebiger Ausdruck kann eine Zahl darstellen.
Für das Rechnen damit braucht man dann ein umfangreiches Sammelsurium an äquivalenten Ersetzungen, so wie z.B. das kleine Einmaleins eines zusammen mit z.B. dem Stellenwertsystem eines ist, aber auch die Umwandlung von PI in eine geeignete äquivalente Potenzreihe.
Jeder Rechenschritt, auch 1+1=2, ist eine symbolische Termersetzung. Die Semantik dahinter jedoch liefert uns Zusammenhänge zwischen Zahlen, die wir nun mal völlig losgelöst von ihrer Darstellung annehmen. 1+1=2 bezeichnet dasselbe wie z.B. *?*_** oder auch add(sqrt(1), pow(13,0)) = sqrt(4)

Ich verstehe nicht, warum deiner Auffassung nach eine Turingmaschine mit der Zahl 5 rechnen kann, aber mit sqrt(5) nicht ?

Eine Turingmaschine arbeitet doch immer nur auf symbolischen Darstellungen einer Zahl (selbst unäre Codierung ist nur eine Darstellung), und nutzt für verschiedene Codierungen verschiedene Verfahren.
Wenn eine Turingmaschine nicht mit dem zur Zeichenkette 'sqrt(5)' gehörenden Zahlenwert rechnen kann, dann kann sie es auch nicht mit der zur Zeichenkette '3' oder '4.5' gehörenden Zahlenwert.
Andererseits:
Wenn man es so sehen möchte, dass eine Turingmaschine mit dem Wert der Zahl '3' oder '4.5' rechnen kann, dann kann sie es auch mit 'sqrt(5)'.

Dein Einwand, dass Turingmaschinen dann mit ALLEN reellen Zahlen rechnen können ist interessant!
Natürlich könnte man sagen X, Y seien jeweils eine nicht-berechenbare Zahl, und Z = X+Y.
Dann könnte man sagen, man kann damit rechnen ? (Definitionssache)
(Es könnte sogar sein, dass Z eine natürliche Zahl ist !)
Allerdings ist das ziemlich 'pathologisch'. Im Gegensatz zu allen anderen Zahlen kann man die nicht-berechenbaren ja nicht in einen äquivalenten arithmetischen Ausdruck wandeln, und daher nicht im 'klassischen Sinne' damit 'rechnen'. (was immer das genau ist)
Für eine exakte Beschreibung einer nicht-berechenbaren Zahl, anhand derer man sie mit anderen bekannten Zahlen verknüpfen kann und ggf. die Ausdrücke danach vereinfachen, bräuchte man tatsächlich unendlich viel Platz.
Aber: von mir aus können wir das gerne so definieren. :wink:

(timeout)

Whoops, ich muss gleich los. Meine nächste Antwort kann etwas dauern, ich weiß nicht, wie es da mit Internet aussieht.
Hau rein + bis denne!
kopfsalat

 

[Bleiglanz]

Ich verstehe nicht, warum deiner Auffassung nach eine Turingmaschine mit der Zahl 5 rechnen kann, aber mit sqrt(5) nicht ?

Weil sqrt(5) für einen Rechner (und auch für Menschen?) ein undurchschaubares Mysterium ist; das ist ja in Wahrheit nur eine operative Definition ("ziehe die Quadratwurzel aus der Zahl 5"); das Ergebnis - der "Wert" von sqrt(5) , die reelle Zahl, die mit sich selbst multipliziert 5 ergibt - kann aber von Computern/Menschen/usw. nicht "erfasst" oder "gewusst" oder was auch immer werden.

Du kannst natürlich - um von der Turingmaschinen-Sprechweise zur Grammatik-Sprechweise zu wechseln - eine Sprache angeben, zu deren Elementarsymbolen "sqrt" gehört; das ist aber dann ganz was anderes!

Sagen wir die Ziffern von 0-9 gehören zu deinen Elementarsymbolen, dann ist alles unproblematisch, weil dann die Common-Sense-Interpretation

"123" ist die Zahl 123

problemlos funktioniert (nur in diesem Sinn kann eine Turingmaschine mit den natürlichen Zahlen rechnen): Die Interpretation "1" ist 1, "2" ist 2 usw. funktioniert und alles ist schön endlich...

Um mein Statement mal anders zu formulieren:

Es gibt keine Turingmaschine, die mit sqrt(5) rechnen kann, aber man kann eine bauen, die mit "sqrt(5)" rechnen kann

 

[kopfsalat]

@Bleiglanz (und auch @ll)...
Hi, bin wieder zurück (s.o. - und es gab kein (!) Internet dort),

Es gibt keine Turingmaschine, die mit sqrt(5) rechnen kann, aber man kann eine bauen, die mit "sqrt(5)" rechnen kann

Langsam wird es philosophisch. :wink:

Als Elementarsymbole habe ich nicht die Ziffern 0,..,9 gesehen, sondern nur 0 und 1.
Dann sind Ganzzahlen/Fließkommazahlen/Brüche auch nur Bitstring-Codierungen (Integer-Zweierkomplement, IEEE-float, etc.) zusammen mit darauf definierten Operationen +-*/, etc. Dann hat man doch sowas wie eine Algebra und das heißt dann ja, dass man damit 'Rechnen' kann. (Mit 'damit' meine ich hier mit z.B. dem Wert 5 selbst)

Wenn man nun eine andere geeignete in sich abgeschlossene und semantisch korrekte Codierung nutzt, welche z.B. noch weit mehr umfasst, und dafür dann Operationen +-*/ etc. darauf definiert, dann hat man doch ebenfalls sowas wie eine Algebra und kann damit meiner Auffassung nach 'Rechnen'. (Mit 'damit' wäre dann hier sowas wie der Wert von sqrt(5) selbst gemeint).

Aber ich weiss nicht genau, wie man 'Rechnen' allgemeinhin definiert (wird aber ggf. auch Stoff von 'Einführung in die Algebra' nächstes Semester sein).

Allerdings vermute ich, dass 'Rechnen' immer auf irgendeine symbolische Abstraktion angewiesen ist, auf deren Ebene dann symbolische Operationen definiert sind, deren Interpretation 'korrekte' Ergebnisse liefert. Daher sehe ich keinen Unterschied zwischen "Rechnen mit "5"" und "Rechnen mit "sqrt(5)""

Vielleicht ist dies hier der Kern davon (?):
Ich finde es richtig, zu sagen: Eine Turingmaschine kann mit sämtlichen berechenbaren Zahlen 'rechnen'.
Du hingegen meinst: Eine Turingmaschine kann nur mit den rationalen Zahlen 'rechnen' (also den berechenbaren Zahlen ohne die irrationalen) ?

Ich werd mich da schonmal auf die Suche nach einer Antwort machen. ???:L :###