Diskussion:Registermaschine
aus Wikipedia, der freien Enzyklopädie
Soweit wie ich weiß, besteht der minimale Befehlssatz einer Registermaschine aus nur drei verschiedenen Befehlen. Damit lassen sich alle im ursprünglichen Beitrag angeführten Befehle außer den 'indireken Befehlen' ausdrücken.
Diese sind funktional aber ohnehin nicht erforderlich, da ein Registermaschinenprogramm nur auf Datensätzen mit endlicher Registerzahl operieren muss.
Auch der Befehl 'END' ist nicht unbedingt notwendig, da jede Befehlsnummer die keinem Befehl zugeordnet ist, als Endmarke verstanden werden kann. Ein Sprung zu einem nichtexistenten Befehl terminiert dann das Programm.
Ich mag ja falsch liegen, aber dies entspricht nun gar nicht mehr meinem Verständnis einer Registermaschine. Jedenfalls hat es mit dem, was ich gerade in meinem Studium gelernt habe, nicht viel gemeinsam... Natürlich ist dies alles reine Definitionssache; und es mag viele Definitionen einer Registermaschiene geben, aber diese Definition macht einem das Leben nur unnötig schwer. Gerade deshalb gibt es ja neben der Turingmaschine auch noch die Registermaschine. Und Deine Definition erinnert mich mehr an die Turingmaschine als an die Registermasche. In Deiner Definition beinhaltet auch jeder Befehl einen Sprung, was einem realem Rechner lange nicht so nahe kommt.
Wo hast Du diese Variante her?
Ich würde dies ganz gerne wieder auf das zurücksetzen was ich geschrieben habe.
Gruß niks
Ich habe dieses Registermaschinenmodell auch aus meinem Studium. Allerdings habe ich das ganze noch um einiges theoretischer gelernt und eine, meiner Meinung nach, etwas verständlichere Definition für 'Registermaschine' verwendet.
Wieso macht sie einem das Leben unnötig schwer?
Wenn du damit die Befehlsanzahl meinst, so gibt es sicher Menschen die meinen Desto weniger Befehle, desto besser als auch Menschen die meinen Desto mehr Befehle, desto besser.
Dieses Kommentar lässt sich sicher auch auf andere Unterschiede zwischen unseren Definitionen übertragen.
Ich bin mit der Registermaschine als Maschinenmodell im Bereich der Berechenbarkeit und Entscheidbarkeit in Berührung gekommen. Dort ist es von Vorteil, die Maschine, bei gleich bleibender Funktonalität, möglichst klein und simpel zu halten.
In welchem Bereich hast du die Registermaschine kennengelernt?
Ich finde die ursprüngliche Definition einer Registermaschine weitaus treffender. Ich würde evtl. nicht alle Befehle wieder reinnehmen, aber sowas wie ADD, SUB, MULT und DIV darf schon dabei sein und ist durchaus üblich. Die starke Minimierung macht hier meiner Meinung nach wenig Sinn, da gerade die Anlehnung an reale Rechner gewünscht ist und selbst bekannte RISC Prozessoren weitaus mehr als drei Befehle besitzen. Aus diesem Grund würde ich auch wieder die Begriffe Akkumulator und Befehlszähler verwenden. Gruß, --zap 18:59, 16. Jul 2004 (CEST)
Nun ich habe meine Definition ebenfalls im Zusammenhang mit der Berechenbarkeit und Entscheidbarkeit gelernt. Wir haben dieses Thema aber so behandelt, daß alle Beweise am Modell der Turingmaschine durchgeführt wurden. Diese ist ja bekanntlich sehr einfach gehalten. Daher erinnert mich Deine Definition auch eher an die der Turingmaschine. In meiner Vorlesung wurde der Beweis geführt, daß die Registermaschiene polynominiell durch eine Turingmaschine simuliert werden kann. (Umgekerht auch.) So wurde die Registermaschine als Verbindungsstück zwischen den sehr theoretischen Beweisen (an der Turingmaschine) zu den real existierenden PC's vorgestellt. Daher auch die starke Anlehnung an reale PC's. Um Beweise zu führen ist dann die viel einfachere Turingmaschine besser geeignet. Da gilt natürlch einfacher = besser... Da hier mit der Turingmaschine schon ein sehr einfach gehaltenes Rechnermodell vorhanden ist würde ich die Registermaschine wieder "komplizierter" machen. (Also aus meiner Sicht wieder so wie ich es ürsprünglich hatte...)
(Sorry, daß erst jetzt wieder vorbeischaue)
Gruß
--niks 13:03, 2. Aug 2004 (CEST)
In diesem Fall haben wir wohl die Situation, dass das Wort Registermaschine mit relativ vielen (einander ähnlichen) Konstrukten assoiziiert wird. Daher schlage ich vor, dass wir den Artikel in mehrere Artikel aufspalten.
Einer davon sollte der Hauptartikel Registermaschine sein, in dem sich jene Fakten über die Registermaschine(n) befinden über die wir uns einig sind (Prinzipieller Zweck, Verhältnis zur Turingmaschine).
Von dort aus können wir dann auf die einzelnen Spielarten der Registermaschine verweisen.
Gruß
divisor 19:27, 17. Aug 2004 (CEST)
- Ich glaube auch, dass hier zwei Spielarten durcheinander geworfen worden sind. Registermaschinen kenne ich aus der Theoretischen Informatik, die RAM ist mir in einer Vorlesung zur geometrischen Algorithmen begegnet, ich vermute deren Definition steht im Algorithmenbuch von Aho et al. Vermutlich wird die RAM noch etwas weniger abstrakt sein, als die Registermaschine, da sie z.B. komplexere reelle Operationen zulässt, was definitiv keine Registermaschine macht. Dazu braucht man in der Theorie schon besondere Turingmaschinen, die Typ-2 Maschinen. --Marc van Woerkom 17:41, 28. Sep 2004 (CEST)
-
- Grundsätzlich sind Registermaschinen und RAM's (Random Access Machine) nicht unterschiedlich. "Registermaschine" ist meiner Meinung nach nur der dt. Begriff dafür. Wegener ("Theoretische Informatik") hat eine Definition mit LOAD, STORE, ADD SUB, MULT, DIV etc... Papdimitriou ("Computational Complexity") gibt eine RAM an mit READ, STORE, LOAD, ADD, SUB, HALF usw. Beide haben Register, Akkumulator und PC. Ich denke wir sollten diese Gemeinsamkeiten in den Vordergrund stellen und nicht die Besonderheiten, welche einzelne Definitionen mit sich bringen. --zap 18:11, 29. Sep 2004 (CEST)
- Es sind doch offensichtlich zwei Modelle mit gleichem Namen, aber deutlich verschiedenen Zielsetzungen. Das sollte man nicht vermischen. Die von Dir genannten Autoren, bzw. das von mir genannte Buch von Aho versucht die Komplexität von Algorithmen zu bestimmen, dafür wird die RAM oder real RAM benutzt. Das andere Modell, die Registermaschine mit Inkrement, Dekrement und Test wird für die Berechenbarkeits- bzw. Rekursionstheorie verwendet, ist deswegen möglichst einfach, da hier ja die Berechenbarkeit bestimmter Operationen auf abzählbaren Mengen untersucht wird. Ich denke es sind drei Artikel Registermaschine (Begriffsklärung), Registermaschine (Komplexitätstheorie) und Registermaschine (Berechenbarkeitstheorie) sinnvoll. --Marc van Woerkom 08:44, 30. Sep 2004 (CEST)
- Grundsätzlich sind Registermaschinen und RAM's (Random Access Machine) nicht unterschiedlich. "Registermaschine" ist meiner Meinung nach nur der dt. Begriff dafür. Wegener ("Theoretische Informatik") hat eine Definition mit LOAD, STORE, ADD SUB, MULT, DIV etc... Papdimitriou ("Computational Complexity") gibt eine RAM an mit READ, STORE, LOAD, ADD, SUB, HALF usw. Beide haben Register, Akkumulator und PC. Ich denke wir sollten diese Gemeinsamkeiten in den Vordergrund stellen und nicht die Besonderheiten, welche einzelne Definitionen mit sich bringen. --zap 18:11, 29. Sep 2004 (CEST)
Ich denke meine Version der Registermaschine könnten wir unter Registermaschine (abstrakt), und deine Version unter Registermaschine (prozessornah) ablegen.
Oder sollten wir das besser sein lassen, und beide Registermaschinen in dem selben Artikel beschreiben?
Was meinst du dazu?
divisor 20:10, 22. Sep 2004 (CEST)
Da es hier tatsächlich zwei verschiedene Definitionen mit dem selben Namen gibt, stimme ich dem Vorschlag, beide Definitionen zu erwähnen zu. Ob dabei in einem oder zwei Artikeln ist eigentlich egal, aber ich denke, daß zwei Artikel weniger Verwirrung stiften. Einen Allgemeinen Artikel mit zwei Verweisen auf die anderen beiden ist dann auch nicht verkehrt. --niks 11:16, 8. Okt 2004 (CEST)
Also gut, dann schreiben wir die Artikel Registermaschine (Begriffsklärung), Registermaschine (Komplexitätstheorie) und Registermaschine (Berechenbarkeitstheorie). Auf gehts!
divisor 18:28, 12. Okt 2004 (CEST)
Ich habe die Aufspaltung provisorisch durchgeführt, und werde mich jetzt um die Registermaschine (Berechenbarkeitstheorie) kümmern.
divisor 18:57, 12. Okt 2004 (CEST)
Hi, ich finde die Unterscheidung ist irreführend. Warum ausgerechnet zwei "Typen"? Das Konzept der Registermaschine findet doch auch in anderen Bereichen Anwendung (nicht nur in der Komplexitätstheorie und der Berechnungstheorie). Und auch innerhalb der Gebiete sind Abstufungen möglich. Das es unterschiedliche Definitionen für verschiedene Anwendungen gibt ist ja selbstverständlich. Dabei entstehen aber nicht neue Begriffe oder gar Konzepte, die neue Artikel rechtfertigen. Für mich ist es jedenfalls nicht offensichtlich, dass es sich um zwei unterschiedliche Modelle handelt. Was eine Registermaschine ausmacht ist:
- wahlfreier Speicherzugriff (realisiert durch Register)
- Befehlszeiger/-zähler
- einfache Programmierung durch entsprechenden Befehlssatz
In der englischen Wikipedia gehört zu einer RAM sogar noch der indirekte Registerzugriff, sowie einfache arithmetische Operationen.
Wenn wir das so beibehalten, müßten wir konsequenterweise auch andere Maschinen nach Anwendungen unterscheiden. Turingmaschinen gibt es zum Beispiel auch in großer Vielfalt mit verschiedenen Zielsetzungen und dennoch ändert sich das Konzept nicht. Deshalb gibt es auch nur einen Artikel "Turingmaschine". Es ist auch schon jetzt zu erkennen, dass wir viel Redundanz haben werden.
Hier nochmal die Faustregel aus Begriffsklärung:
Faustregel: Wenn ein Wort dieselbe Bedeutung in verschiedenen Zusammenhängen hat, gehören diese in einen Artikel. Wenn ein Wort mehrere grundlegend verschiedene Bedeutungen hat, braucht es mehrere Artikel und eine Begriffsklärung.
--zap 22:28, 12. Okt 2004 (CEST)
- Es macht einen gewaltigen Unterschied für die Analyse der Berechenbarkeit einer Funktion aus, ob man es mit Registermaschinen auf Datentypen zu tun hat, die abzählbar sind oder nicht. Einen Computergeometer wird hingegegen weniger jucken, ob er eine Real oder Rational RAM zur Analyse der Komplexität seiner Algorithmen verwendet. Daher würde ich auf jedenfall schonmal dringend zwischen den sehr scharf definierten Registermaschinen der Berechenbarkeitstheorie und den sonstigen RAMs unterscheiden. --Marc van Woerkom 00:14, 13. Okt 2004 (CEST)
-
- Die Analyse der Berechenbarkeit ist aber nur ein Anwendungsfeld der Registermaschine und gehört damit in denselben Artikel. --zap 12:46, 15. Okt 2004 (CEST)
Ich halte die Trennung in Registermaschine (Komplexitätstheorie) und Registermaschine (Berechenbarkeitstheorie) für kontraproduktiv und verweirrend: das Konzept ist das selbe, der Grund sie zu verwenden auch. Natürlich gibt es unterschiedliche varianten und definitionen, die sollten aber ein einem Artikel erläutert und die unterschiede erklärt werden, so wie bei der Turingmaschine. -- D. Düsentrieb ⇌ 20:03, 14. Okt 2004 (CEST)
Die Einwände gegen eine Teilung sind durchaus gerechtfertigt. Ganz besonders aufgrund der Tatsache, dass nun noch eine weitere Definition auf der Hauptseite dazugefügt wurde, welche sich mit der Definition bei Registermaschine (Berechenbarkeitstheorie) zu decken scheint.
Der Artikel über die Turingmaschine profitiert meiner Meinung nach davon, dass es nur eine einzige ziemlich dominante bzw. bekannte Definition ihrer selbst gibt. Andere formale Definitionen bzw. Spielarten sind dadurch relativ schnell abhandelbar.
Bei der Registermaschine scheint es (zumindest im deutschsprachigen Wikipedia) noch keine dominante Definition zu geben, obwohl es aufgrund der neuen Definition auf der Hauptseite zur Zeit 2:1 für die Berechenbarkeitstheorie-Registermaschine zu stehen scheint. (Ich habe natürlich keine Ahnung davon wie es diesbezüglich bei den deutschsprachigen Wikipedianern aussieht.)
Aus diesem Grund scheint es mir weiter angebracht, beide (vom der Motivation her verschiedene) Definitionen der besseren Übersichtlichkeit wegen in zwei Artikel zu stecken, seperat weiterzuentwickeln und zu sehen ob sich eine gewisse Dominanz herausbildet.
Wenn dies geschehen ist, könnte der dominante Artikel auf die Hauptseite gestellt werden, und von dort auf die andere Definition verweisen.
divisor 23:42, 29. Okt 2004 (CEST)
Weiters gibt es auch einen englischen Artikel über die Registermaschine. (en:Register_machine)
divisor 13:59, 30. Okt 2004 (CEST)
