Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 9

Aufgabe

Es sei ${}b\in \mathbb {N} _{+}$. Entwerfe ein Programm für eine Registermaschine, das bei der Eingabe von ${}(r_{1},\ldots ,r_{k})$ in den ersten ${}k$ Registern die Zahl ${}\sum _{i=1}^{k}r_{i}b^{i}$ berechnet, ausdruckt und anhält.

Aufgabe

Es sei ${}b\in \mathbb {N} _{\geq 2}$. Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von ${}z$ im ersten Register die ${}b$-adische Ziffernentwicklung ${}z=\sum _{i=0}^{k}s_{i}b^{i}$ (mit $0\leq r_{i}\leq b-1$) berechnet, nach und nach die Ziffern ${}s_{i}$ (beginnend mit $i=0$) ausdruckt und schließlich anhält.

Aufgabe

Es sei ${}b\in \mathbb {N} _{\geq 2}$. Entwerfe ein Programm für eine Registermaschine, das zur Eingabe von ${}z$ im ersten Register die ${}b$-adische Ziffernentwicklung ${}z=\sum _{i=1}^{k}s_{i}b^{i}$ (mit $0\leq r_{i}\leq b-1$) berechnet, nach und nach die Exponenten ${}i$ und die zugehörigen Ziffern ${}s_{i}$ (beginnend mit $k$ und ${}s_{k}$) ausdruckt und schließlich anhält.

Wir nennen ein Registerprogramm Zustands-periodisch, wenn zwei identische Zustände (d.h. identische Inhalte in allen Registern und identische Befehlszeilennummern) zu unterschiedlichen Zeitpunkten im Programmablauf eingenommen werden (bei leerer Anfangsbelegung).

Aufgabe

Man gebe ein Beispiel für ein Zustands-periodisches Programm.

Aufgabe

Zeige, dass ein nicht anhaltendes, Register-beschränktes Programm (d.h. es gibt eine Schranke ${}S\in \mathbb {N}$, die die Registerinhalte zu keinem Zeitpunkt des Programmablaufes überschreiten) Zustands-periodisch ist.

Aufgabe

Man gebe ein Beispiel für ein nicht anhaltendes Registerprogramm, das keine Periodizität im Ablauf der Befehlsnummern besitzt.

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> PDF-Version dieses Arbeitsblattes Zur Vorlesung (PDF)