Diskussion:Speedup-Theorem
Beschleunigungssätze
BearbeitenIch schlage eine Verschiebung nach Beschleunigungssatz vor. Dies ist der gängigere Begriff. 92.231.188.246 10:01, 11. Dez. 2011 (CET)
Zeitkomplexität
BearbeitenDen 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
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)