Guten Abend, beschäftige mich zur Zeit mit Registermaschinen. Ich habe sehr viel Recherchiert und immernoch nicht herausfinden können, wo Registermaschinen in der Informatik bzw. in der Praxis angewendet werden. Ich weiß nur, dass man die Berechenbarkeit und die Komplexität damit herausfinden kann, aber mehr leider nicht. Ich hoffe, Sie können mir weiterhelfen. Viele Grüße.
:
Verschoben durch User
Jeder normale Computer und Mikrocontroller ist eine Registermaschine, das Gegenteil, die reine Stack-Maschine, wären absolute Exoten, ich bin nicht mal sicher ob Forth Chips ohne Register sind: http://www.greenarraychips.com/ (und zu faul, deren Datenblätter zu lesen).
In der theoretischen Informatik ist eine Registermaschine einfach nur ein Modell mit dem man arbeiten kann, ohne den expliziten Begriff einer 'Variablen' benutzen zu müssen. Lies an dieser Stelle "Register == Variable" Denn Begriff der Variablen möchte man vermeiden, weil damit unweigerlich einhergeht, wo diese Variable gespeichert wird, bzw. weil damit dann die damit zusammengehörenden Fragestellungen wie Adressierung und Zugriff auftauchen. Das alles ist in der theoretischen Informatik völlig uninteressant. Man benötigt einen Mechanismus in dem man Werte 'parken' und für Berechnungen zur Verfügung stellen kann. Die nennt man dann eben Register.
:
Bearbeitet durch User
Die JVM ist eine reine Stackmaschine ohne Register. Aber die ist nunmal kein realer Prozessor...
Michael B. schrieb: > nicht mal sicher ob Forth Chips ohne Register sind: Ich denke letzten Endes hat jeder existierende reale Chip Register in der einen oder anderen Form. Und sei es nur um den Stackpointer bzw. den Programm Counter halten zu können.
Registermaschinen können auch nur in der Theoretischen Informatik eingesetzt werden, die Forderung nach Unendlich vielen unendlich breiten Registen steht der praktischen Realisierung etwas im Weg
Dennis K. schrieb: > Ich weiß nur, dass man die Berechenbarkeit und die Komplexität damit > herausfinden kann, aber mehr leider nicht. Bei beiden Themen begegnet man in der Informatik hauptsächlich der Turingmaschine. Die ist freilich so abstrakt, dass all jene, die mit der Arbeitsweise realer Rechner vertraut sind, die Arbeitsweise der Turingmaschine für einigermassen bescheuert halten könnten. Die Rolle der formalen Registermaschinen beschränkt sich im Grunde darauf, ein theoretisches Bindeglied zwischen der Turingmaschine und Arbeitsweise realer Computer herzustellen. Wenn man dann beweist, dass Registermaschine und Turingmaschine in den mathematischen Aussagen äquivalent sind, ist man mit der Turingmaschine versöhnt und kann mit ihr brav weiter seine theoretische Informatik betreiben.
:
Bearbeitet durch User
Vielen Dank für die Informationen. Leider hab ich noch ein paar Fragezeichen im Kopf. Ich muss ein Text verfassen und darin die relevanz der Registermaschinen in der Informatik beschreiben also den Anwendungsbezug. Leider kann ich dazu nichts formulieren, da ich keine geeignete Literatur finde. Viele Grüße.
PS: Man muss bei diesen Begriffen den Kontext beachten. So finden sich sowohl in der theoretischen Informatik als auch in realen Computern Stackmaschinen, aber die Bedeutung dieser Begriffe ist recht verschieden. Mit den Registermaschinen ist das nicht anders. Ich gehe aufgrund der Erwähnung von Berechenbarkeit und Komplexitätstheorie davon aus, dass hier der Kontext der theoretischen Informatik gemeint ist. Wobei dann Begriffe wie JVM oder RISC etwas am Thema vorbei gehen.
:
Bearbeitet durch User
Genau, es ist der Kontext der theoretischen Informatik gemeint. Ich weiß leider es nicht, wie ich die Relevanz in Text-Form beschreiben soll. Ich denke, ich kann nicht einfach schreiben, dass in realen Pcs sich Registermaschinen befinden. Wie würdet Ihr anfangen so etwas zu formulieren? Ich verzweile schon :(
Dennis K. schrieb: > Wie würdet Ihr anfangen so etwas zu formulieren? Ich würde damit anfangen, klar zu stellen, dass es sich dabei um ein Konstrukt der theoretischen Informatik handelt. Im Grund würde man so ein Teil nicht brauchen. Denn es wurde schon gezeigt, dass eine Turing Maschine alles berechnen kann, was prinzipiell berechnbar ist. Leider ist aber eine Turing Maschine so primitiv, dass es schwierig und sehr umfangreich sein kann, zu zeigen dass eine Turing Maschine ein bestimmtes Problem lösen kann, und wie sie das machen könnte. Daher benutzt man als Hilfskonstrukt eine Registermaschine. Es wurde gezeigt, dass sich die Aussagekraft eine Registermaschine nicht von der einer Turing Maschine unterscheidet. Was die eine kann, kann die andere auch. D.h. anstatt unendlich lange zu versuchen, alles auf einer Turing Maschine abzubilden, geht man den einfacheren Weg das gesuchte auf einer Registermaschine abzubilden. Denn man hat ja gelernt: geht es auf einer Registermaschine, dann geht es auch auf einer Turing Maschine. Und eine Turing Maschine kann alles berechnen, was prinzipiell mit einem Computer berechnbar ist. Zudem ist eine Registermaschine näher an der Arbeitsweise heutiger Computer (SPezialrechner mal ausgenommen). D.h. wenn man sein Problem mit einer Registermaschine gelöst bekommen hat, dann hat man auch schon eine recht gute Vorlage dafür, wie man die Dinge auf heutigen COmputer abbilden könnte. Eine Turing Maschine ist hingegen zwar sehr einfach, aber genau das ist auch das Problem: Habe ich ein Problem auf eine Turing Maschine abgebildet, dann taugt das nicht besonders gut für eine reale Implementierung. Eine Turing Maschine ist dazu zu weit von realer Hardware entfernt (wenn es auch möglich wäre so eztwas zu bauen. Aber so etwas würde niemand ernsthaft benutzen wollen. Eine Turing-Maschine ist tatsächlich ein Konstrukt das ausserhalb der theoretischen Informatik keinerlei Bedeutung hat). Ich würde mich sogar soweit aus dem Fenster lehnen, dass ich sagen würde das eine Registermaschine eine 'auf praktisch benutzbar aufgebohrte Turing Maschine' handelt. Dann kann man mal erklären, was eigentlich eine Turing Maschine ist und dann den Übergang zu einer Register Maschine ziehen, erwähnen dass es unterschiedliche Registermaschinen gibt und noch so einiges aus dem zugeh. Wikipedia Artikel einbauen.
:
Bearbeitet durch User
Hier auch noch mein Senf: Es gibt neben der Turingmaschine ziemlich viele gleichmächtige Modelle für die Berechenbarkeit. Hier sind ein paar Beispiele: https://de.wikipedia.org/wiki/Berechenbarkeitstheorie#Andere_Modelle_f.C3.BCr_Berechenbarkeit_mit_gleicher_Leistungsf.C3.A4higkeit Die beiden ältesten dieser Modelle, die Turingmaschine und der Lambda- Kalkül (beide von 1936), sind gleichzeitig auch mit die abstraktesten. Abstrakt bedeutet Reduktion auf das Wesentliche,weswegen diese Modelle leichter handhabbar in mathematischen Beweisen, formalen Definitionen usw. sind. Damit hängt auch zusammen, dass sich Ergebnisse von abstrakten Modellen leichter auf weniger abstrakte übertragen lassen als umgekehrt. So lässt sich bspw. eine Turingmaschine ganz leicht in C programmieren, hingegen einen C-Interpreter auf einer Turingmaschine zu implementieren ist eine ziemlich schwierige Aufgabe. So kommen in der Berechenbarkeitstheorie der Turingmaschine und dem Lambda-Kalkül – evtl. noch zusammen mit den µ-rekursiven Funktionen – die wohl größte Bedeutung zu. In der Komplexitätstheorie ist die Turingmaschine als ältester Vertreter der höchsten Mächtigkeitklasse von Automaten das meistgenutzte Modell. Wozu man dann überhaupt die Registermaschine? Die Registermaschine ist später als die meisten anderen Modelle (1963) eingeführt worden, sicherlich auch inspiriert von den Computern, die es zur Zeit der Entstehung der Turingmaschine und des Lambda-Kalküls noch nicht gab, inzwischen aber zu Tausenden installiert wurden (z.B. die IBM 1401). Es entwickelten sich nach und nach etliche Varianten (man könnte sie auch "Ausbaustufen" nennen), von primitiven Maschinen, die nur zählen und mit 0 vergleichen konnten bis hin zu Maschinen, die in vielerlei Hinsicht (Befehlssatz, Arithmetikoperationen, Von-Neumann- Architektur usw.) einem realen Computer (aber im Gegensatz zu diesem mit unendlich breiten Speicherworten) entsprechen. Im Abschnitt "Historical development of the register machine model" des englischen Wikipedia-Artikel zu dem Thema sind einige der Beweggründe für die Einführung der Registermaschine als ein weiteres Modell der Berechenbarkeit aufgeführt: https://en.wikipedia.org/wiki/Register_machine#Historical_development_of_the_register_machine_model Trotz alledem scheinen heute die Registermaschinen, wenn man sich die Studienpläne der Informatikstudiengänge anschaut, in der theoretischen Informatik eher ein Schattendasein zu fristen. Soviel zum Thema "Relevanz". Ich glaube, wenn du – ausgehend von den Wikipedia-Artikeln (deutsch und englisch) – noch ein Bisschen weiterrecherchierst, insbesondere im Zusammenhang mit Berechenbarkeits- und Komplexitätstheorie, solltest du ziemlich schnell genügend Material für dein Referat (oder was immer das am Ende werden soll) zusammenbekommen.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.