Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 18

Übungsaufgaben

Aufgabe

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Quadratzahlen ausdruckt.

Aufgabe *

Erstelle ein Programm für eine Registermaschine, das abwechselnd ${}1$ und ${}0$ ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.

Aufgabe *

Erstelle ein Programm für eine Registermaschine, das abwechselnd ${}1$ und ${}0$ ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Druckbefehl verwendet.

Aufgabe *

Schreibe einen Programmabschnitt ${}C(i,j,k)$ für eine Registermaschine, das zum Befehl ${}j$ wechselt, wenn im ${}i$-ten Register der Wert ${}k$ steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.

Aufgabe

Entwerfe ein Programm für eine Registermaschine, die für ${}r_{i}\geq r_{j}$ die Differenz ${}r_{i}-r_{j}$ von zwei Registerinhalten berechnet.

Aufgabe

Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt ${}r_{i}$ des Registers ${}R_{i}$ die echte Potenz einer natürlichen Zahl ist.

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.

Aufgabe

Entwerfe ein möglichst kurzes (also mit möglichst wenigen Befehlszeilen) Programm für eine Registermaschine, das bei leerer Startbelegung anhält und zum Schluss die Zahl ${}20$ im ersten Register hat.

Aufgabe

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe einer natürlichen Zahlen ${}n$ im Register ${}R_{1}$ die Fakultät ${}n!$ in ${}R_{1}$ ausgibt.

Aufgabe

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von zwei natürlichen Zahlen ${}n$ und ${}k$ in den Registern ${}R_{2},R_{3}$ den Binomialkoeffizienten ${}{\binom {n}{k}}$ in ${}R_{1}$ ausgibt.

Aufgabe *

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von zwei natürlichen Zahlen ${}a$ und ${}b$ in den Registern ${}R_{2},R_{3}$ den euklidischen Algorithmus durchführt und das Ergebnis, also den größten gemeinsamen Teiler von ${}a$ und ${}b$, in ${}R_{1}$ ausgibt.

Aufgabe

Es sei ${}P$ ein Programm für eine Registermaschine, es sei eine feste Anfangsbelegung gegeben und es sei vorausgesetzt, dass das Programm, angesetzt auf diese Anfangsbelegung, irgendwann anhält. Zeige, dass man den Ablauf des Programms, also die schrittweise Abfolge der Veränderungen der Registerinhalte, auch durch ein Programm realisieren kann, bei dem der Sprungbefehl nicht verwendet wird. Wozu braucht es dann eigentlich den Sprungbefehl?

Aufgabe

Zeige, dass es kein Programm für eine Registermaschine gibt, das bei jeder Anfangsbelegung sämtliche Register leert.

Aufgabe

Beschreibe ein Verfahren, das alle prädikatenlogischen Ausdrücke ausgibt (dabei sei vorausgesetzt, dass die Variablen, die Konstanten, die Relationssymbole und die Funktionssymbole in einer aufgezählten Form vorliegen).

Aufgabe

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe einer natürlichen Zahlen ${}n$ im Register ${}R_{1}$ den Collatz-Algorithmus durchführt, dabei die sukzessiven Werte ausdruckt und insbesondere anhält, wenn der Wert ${}1$ erreicht wird.

Aufgabe *

Im Aufbau der Registermaschine wurde der Druckbefehl durch einen Musiktonbefehl ersetzt, der den Inhalt von ${}R_{1}$ in einen Ton umsetzt, damit man mit der Registermaschine auch komponieren bzw. Lieder kodieren kann. Für ein Lied wurden schon Programmabschnitte ${}P_{1},P_{2},P_{3},P_{4}$ geschrieben, die die folgende Bedeutung haben: ${}P_{1}$ ist das Vorspiel (${}V$), ${}P_{2}$ ist die Strophe (${}S$), ${}P_{3}$ ist der Refrain (${}R$) und ${}P_{4}$ ist das Gitarrensolo (${}G$). Es soll nun aus den Programmabschnitten ein (anhaltendes) Programm zusammengesetzt werden, derart, dass beim Abspielen des Programms ein Lied der Form

$V-S-R-S-R-G-S-R-R$

erklingt. Dabei darf jeder der Programmabschnitte ${}P_{1},P_{2},P_{3},P_{4}$ nur einmal im Programmcode auftauchen. Verwende ausschließlich die Grundbefehle.

Aufgabe

Welches Bildungsgesetz liegt der Folge

$1,\,11,\,21,\,1211,\,111221,\,312211,\,...$

zugrunde?

(Es wird behauptet, dass diese Aufgabe für Grundschulkinder sehr einfach und für Mathematiker sehr schwierig ist.)

Aufgaben zum Abgeben

Aufgabe * (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Primzahlen ausdruckt.

Aufgabe (5 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Glieder der in Aufgabe 18.19 beschriebenen Folge ausdruckt.

Aufgabe (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das die Potenz ${}r_{i}^{r_{j}}$ berechnet (und ausgibt), wobei ${}r_{i}$ bzw. ${}r_{j}$ die Registerinhalte der Register ${}R_{i},R_{j}$, ${}i\neq j$, sind.

Aufgabe (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Mersenne-Primzahlen ausdruckt.

Aufgabe (4 Punkte)

Entwerfe ein möglichst kurzes (also mit möglichst wenigen Befehlszeilen) Programm für eine Registermaschine, das bei leerer Startbelegung anhält und zum Schluss die Zahl ${}100$ im ersten Register hat.

Punkte gibt es nur für ziemlich kurze Programme. Für den Kurs-Rekord gibt es drei Extrapunkte.