{"id":468,"date":"2012-10-04T18:34:06","date_gmt":"2012-10-04T16:34:06","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=468"},"modified":"2020-10-28T22:30:58","modified_gmt":"2020-10-28T21:30:58","slug":"ti-normale-und-allgemeine-registermaschinen","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=468","title":{"rendered":"TI: normale und allgemeine Registermaschinen (Update)"},"content":{"rendered":"

Update<\/strong>: im Hinblick auf die Lernziele zu Kurseinheit 1, habe ich diesen Eintrag etwas \u00fcberarbeitet um ihn im neuen Beitrag<\/a> verwenden zu k\u00f6nnen.<\/p>\n

Wichtig vorab<\/strong>: lasst euch nicht von den mathematischen Definitionen erschrecken. Sie werden nach der Einf\u00fchrung der formalen Definition noch einmal informell (und hoffentlich verst\u00e4ndlich) erl\u00e4utert. Auch wenn euch die Definitionen unn\u00f6tig erscheinen, ist es in der Mathematik \u00fcblich etwas unmissverst\u00e4ndlich auszudr\u00fccken. Die formale Definition ist daher leider notwendig und durchaus hilfreich bei den Pr\u00fcfungen und den Einsendeaufgaben. Aber mal Butter bei die Fische:<\/p>\n

Wir unterscheiden die Maschinen in normale Registermaschinen und allgemeine Registermaschinen. Der Unterschied zwischen den beiden ist, dass die allgemeinen Registermaschinen zus\u00e4tzliche, komplexe Funktionen anbieten. Diese m\u00fcssen jedoch durch normale Registermaschinen ausgedr\u00fcckt werden k\u00f6nnen. Als Beispiel dient der (komplexe) Vergleich von zwei Registern, welcher durch eine normale Registermaschine ausgedr\u00fcckt werden kann.<\/p>\n

Die Registermaschine verf\u00fcgt \u00fcber Register $$R_0, R_1, R2, …$$ zum Speichern nat\u00fcrlicher Zahlen. Eine Belegung der Register wird mit einer Funktion $$d: \\mathbb{N} \\rightarrow \\mathbb{N}$$ realisiert. $$d(i)$$ ist der Inhalt des Registers $$R_i$$. Die Datenmenge der Registermaschine ist damit $$D := \\mathbb{N}^{\\mathbb{N}} = \\{d \\mid d : \\mathbb{N} \\rightarrow \\mathbb{N}\\}$$. Die Funktion $$d(i)$$ l\u00e4sst sich auch als konkrete Belegung der Register mit $$(d(0), d(1), d(2), …)$$ darstellen, z.B. „(3, 1, 5, …)“. Man verwendet hier so viele Funktionswerte, d.h. belegte Register wie notwendig. Alle anderen Register sind mit 0 belegt. Zus\u00e4tzlich wird mit der Ausgabecodierung $$AC: D \\rightarrow \\mathbb{N}$$ mit $$AC(d) := d(0)$$ definiert, dass das Ergebnis stets im Register $$R_0$$ stehen soll.<\/p>\n

Die einzigen Operationen, die eine normale Registermaschine<\/strong> kann ist<\/p>\n

    \n
  1. addiere 1 in $$R_i$$ ($$R_i := R_i + 1$$)<\/li>\n
  2. subtrahiere 1 in $$R_i$$ ($$R_i := R_i \\dot{-} 1$$), arithemtische Differenz ($$a – b := ( a – b$$ falls $$a \\geq b$$, 0 sonst), z.B. 5 $$\\dot{-}$$ 7 = 0, aber 7$$\\dot{-}$$ 5 = 2<\/li>\n
  3. teste ob in $$R_i$$ eine 0 steht. ($$R_i = 0$$)<\/li>\n<\/ol>\n

    Alle anderen Operationen finden sich in einer allgemeinen Registermaschine wieder und werden, wie erw\u00e4hnt, durch die drei Operationen der normalen Registermaschine ausgedr\u00fcckt. Nun definieren wir die beiden Arten der Registermaschine formal und erkl\u00e4ren die Definition. Anschlie\u00dfend folgt ein Beispiel f\u00fcr eine Funktion, deren Berechenbarkeit wir durch eine allgemeine Registermaschine beweisen. Ihre komplexen Funktionen bilden wir dann mit einer normalen Registermaschine nach.<\/p>\n

    Definition Registermaschine<\/h1>\n

    Eine k-stellige ($$k \\in \\mathbb{N} $$) Registermachine ist wie folgt definiert: $$M = (F, \\mathbb{N}^k, \\mathbb{N}, EC^{(k)}, AC) $$. Stelligkeit bedeutet einfach nur die Anzahl der verwendeten Register. Ist die Stelligkeit mit $$k = 0$$ angegeben, gilt $$D:=\\{\\}$$, d.h. die Registerbelegung ist $$(0,0,…)$$.<\/p>\n