Diskussion:Speedup-Theorem
Beschleunigungssätze[Quelltext bearbeiten]
Ich schlage eine Verschiebung nach Beschleunigungssatz vor. Dies ist der gängigere Begriff. 92.231.188.246 10:01, 11. Dez. 2011 (CET)
Zeitkomplexität[Quelltext bearbeiten]
Den Satz "Die zusätzliche Addition von (n + 2) ergibt sich aus der Notwendigkeit, das Eingabewort der Ausgangsmaschine vollständig einzulesen." kann ich nicht nachvollziehen. Wie kommt das +2 zustande? (nicht signierter Beitrag von 93.104.71.181 (Diskussion) 13:29, 22. Mär. 2013 (CET))
Beispiel aus der Mathematik - reale Rechner[Quelltext bearbeiten]
"Das Beispiel erklärt auch, warum Programme auf realen Rechnern nicht auf diese Art und Weise beschleunigt werden können. Anders als eine Turingmaschine können binäre Rechner kein anderes Alphabet außer verarbeiten." - im Gegenteil zeigt das Beispiel, warum 64-Bit-Rechner Arithmetik von genügend großen Zahlen "schneller" (d.h. mit weniger Elementaroperationen/Taktzyklen) als 8-Bit-Rechner durchführen können. Eine ALU arbeitet nicht auf Bit-Ebene, sondern auf größeren Einheiten. Die durch die Carry-Bits eigentlich lineare Abhängigkeit von der Anzahl der Eingabebits bei der Addition lassen sich durch erhöhten Schaltungsaufwand reduzieren (siehe z.B. CLA-Addierer). Ähnlich wie bei der Turing-Maschine wird auch die Beschleunigung der realen Maschine also durch erhöhte Komplexität der Verarbeitung (mehr Zustandsübergänge/beteiligte Gatter pro Operation) erkauft. --80.151.251.9 14:40, 29. Mai 2023 (CEST)