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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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

Aufgabe * Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 * Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

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 Aufgabe 18.17 ändern

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 * Referenznummer erstellen

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 Aufgabe 18.19 ändern

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)Referenznummer erstellen

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

Aufgabe (5 Punkte)Referenznummer erstellen

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

Aufgabe (3 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe (4 Punkte)Referenznummer erstellen

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.