Anzeige:
Ergebnis 1 bis 4 von 4

Thema: Berechenbarkeit von Grenzwerten geometrischer Reihen

  1. #1
    Registrierter Benutzer Avatar von Phylax
    Registriert seit
    10.06.2008
    Beiträge
    26

    Berechenbarkeit von Grenzwerten geometrischer Reihen

    Grüße an alle,

    nachdem ich bisher schon in allerlei Lebenslagen Hilfe im LaTeX-Forum gefunden habe, fühle ich mich auch mit einer Frage zur theoretischen Informatik gut aufgehoben (bin selbst Philosoph, also fachfremd):

    Es geht um die Frage, ob eine Turing-Maschine den Grenzwert einer unendlichen geometrischen Reihe berechnen kann, wenn man ihr eine Regel eingibt, mit der diese Reihe rekursiv erzeugt werden kann (hoffe, dass ich mich richtig ausgedrückt habe). Konkret geht es um die Reihe 1/2 + 1/4 + 1/8 ... die bekanntermaßen zu 1 konvergiert.

    Gibt es einen Algorithmus, der den Wert 1 berechnen kann? Gemeint ist nicht, dass eine beträchtliche Anzahl der Additionen durchgeführt und dann gerundet wird, sondern sozusagen ein "Beweis", dass der Grenzwert genau 1 ist.

    Bin für alle Hinweise dankbar; eine kurze Darstellung eines Algorithmus in Pseudocode wäre mir sehr willkommen (ggf. auch eine reale Implementierung).

    Beste Grüße

    Phylax

  2. #2
    Registrierter Benutzer Avatar von John W
    Registriert seit
    29.01.2010
    Beiträge
    211
    Wenn man sich die Zwischenergebnisse mal ansieht, erkennt man als Mensch schnell einen Zusammenhang:
    Code:
    1/2
    3/4
    7/8
    15/16
    ...
    Wenn man für n recht große Zahlen einsetzt, bekommt man aufgrund von Rundungsfehlern irgendwann 1 raus - die Turing-Maschine müsste also eigentlich nur rechnen, bis Rundungsfehler immer den gleichen Wert liefern.
    Was braucht man dafür? Schleifen, etwas Speicher und bedingte Sprünge - alles in einer Turing-Maschine enthalten, sollte also möglich sein, wenn man irgendwie auch die Regelmäßigkeit finden kann; hab da aber wenig Ahnung von, vielleicht hilft es dir ja zumindest beim Ansatz.

  3. #3
    saar
    Gast
    Geht's hier wirklich nur um geometrische Reihen oder etwa um allgemeine Reihen? Eine geometrische Reihe ist bestimmt durch einen Startwert a_0 sowie einen Quotienten q (siehe http://de.wikipedia.org/wiki/Geometrische_Reihe). Daraus ergibt sich dann die Formel für die n-te Partialsumme: s_n = a_0*(1-q^(n+1))/(1-q) falls q != 1 ist. Daraus erhält man dann:
    Falls a_0 == 0: Reihe konvergiert gegen 0
    Für a_0 != 0:
    Falls q <= -1: Reihe ist divergent
    Falls -1 < q < 1: Reihe konvergiert gegen a_0/(1-q)
    Falls q >= 1: Reihe ist divergent

    Wenn also eine "berechenbare Regel" für die Folgenglieder gegeben ist, kann daraus a_0 und q berechnet werden und mittels obiger Fallunterscheidungen ergibt sich dann die Berechenbarkeit der Konvergenz und ggf. des Grenzwertes.

  4. #4
    Registrierter Benutzer
    Registriert seit
    17.10.2014
    Beiträge
    22
    hört sich kompliziert an..

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •