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

\setcounter{section}{18}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Entwerfe ein Programm für eine Registermaschine, die für
\mathl{r_i \geq r_j}{} die Differenz
\mathl{r_i-r_j}{} von zwei Registerinhalten berechnet.

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei
\mavergleichskette
{\vergleichskette
{b }
{ \in }{ \N_+ }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Entwerfe ein \definitionsverweis {Programm für eine Registermaschine}{}{,} das bei der Eingabe von
\mathl{(r_1 , \ldots , r_k)}{} in den ersten $k$ Registern die Zahl
\mathl{\sum_{i=1}^k r_ib^{i}}{} berechnet, ausdruckt und anhält.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{b \in \N_{\geq 2}}{.} Entwerfe ein \definitionsverweis {Programm für eine Registermaschine}{}{,} das bei Eingabe von
\mathl{z}{} im ersten Register die $b$-adische Ziffernentwicklung
\mathl{z=\sum_{i=0}^k s_i b^{i}}{} \zusatzklammer {mit \mathlk{0 \leq r_i \leq b-1}{}} {} {} berechnet, nach und nach die Ziffern $s_i$ \zusatzklammer {beginnend mit \mathlk{i=0}{}} {} {} ausdruckt und schließlich anhält.

}
{} {}

\inputaufgabe
{}
{

Es sei
\mathl{b \in \N_{\geq 2}}{.} Entwerfe ein \definitionsverweis {Programm für eine Registermaschine}{}{,} das zur Eingabe von
\mathl{z}{} im ersten Register die $b$-adische Ziffernentwicklung
\mathl{z=\sum_{i=1}^k s_i b^{i}}{} \zusatzklammer {mit \mathlk{0 \leq r_i \leq b-1}{}} {} {} berechnet, nach und nach die Exponenten $i$ und die zugehörigen Ziffern $s_i$ \zusatzklammer {beginnend mit \mathlk{k}{} und $s_k$} {} {} ausdruckt und schließlich anhält.

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Entwerfe ein \definitionsverweis {Programm für eine Registermaschine}{}{,} das bei Eingabe von zwei natürlichen Zahlen \mathkor {} {n} {und} {k} {} in den Registern
\mathl{R_2,R_3}{} den \definitionsverweis {Binomialkoeffizienten}{}{} $\binom { n } { k }$ in $R_1$ ausgibt.

}
{} {}

\inputaufgabegibtloesung
{}
{

Entwerfe ein \definitionsverweis {Programm für eine Registermaschine}{}{,} das bei Eingabe von zwei natürlichen Zahlen \mathkor {} {a} {und} {b} {} in den Registern
\mathl{R_2,R_3}{} den \definitionsverweis {euklidischen Algorithmus}{}{} durchführt und das Ergebnis, also den größten gemeinsamen Teiler von \mathkor {} {a} {und} {b} {,} in $R_1$ ausgibt.

}
{} {}

\inputaufgabe
{}
{

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?

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabegibtloesung
{}
{

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
\mathl{P_1,P_2,P_3,P_4}{} geschrieben, die die folgende Bedeutung haben: $P_1$ ist das Vorspiel \zusatzklammer {$V$} {} {,} $P_2$ ist die Strophe \zusatzklammer {$S$} {} {,} $P_3$ ist der Refrain \zusatzklammer {$R$} {} {} und $P_4$ ist das Gitarrensolo \zusatzklammer {$G$} {} {.} Es soll nun aus den Programmabschnitten ein \zusatzklammer {anhaltendes} {} {} Programm zusammengesetzt werden, derart, dass beim Abspielen des Programms ein Lied der Form
\mathdisp {V-S-R-S-R-G-S-R-R} { }
erklingt. Dabei darf jeder der Programmabschnitte
\mathl{P_1,P_2,P_3,P_4}{} nur einmal im Programmcode auftauchen. Verwende ausschließlich die Grundbefehle.

}
{} {}

\inputaufgabe
{}
{

Welches Bildungsgesetz liegt der Folge
\mathdisp {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.)}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabegibtloesung
{3}
{

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

}
{} {}

\inputaufgabe
{5}
{

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

}
{} {}

\inputaufgabe
{3}
{

Entwerfe ein Programm für eine \definitionsverweis {Registermaschine}{}{,} das die Potenz
\mathl{r_i^{r_j}}{} berechnet \zusatzklammer {und ausgibt} {} {,} wobei \mathkor {} {r_i} {bzw.} {r_j} {} die Registerinhalte der Register
\mathbed {R_i, R_j} {}
{i \neq j} {}
{} {} {} {,} sind.

}
{} {}

\inputaufgabe
{3}
{

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

}
{} {}

\inputaufgabe
{4}
{

Entwerfe ein möglichst kurzes \zusatzklammer {also mit möglichst wenigen Befehlszeilen} {} {} \definitionsverweis {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.}