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

Übungsaufgaben

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.

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

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

Aufgabe Referenznummer erstellen

Es seien ${}T,S\subseteq \mathbb {N}$ entscheidbare Mengen. Zeige, dass dann auch die Vereinigung ${}T\cup S$, der Durchschnitt ${}T\cap S$ und auch das Komplement ${}\mathbb {N} \setminus T$ entscheidbar sind.

Aufgabe Referenznummer erstellen

Zeige, dass es nur abzählbar viele entscheidbare Teilmengen von ${}\mathbb {N}$ gibt.

Aufgabe Referenznummer erstellen

Es sei ${}\alpha \in L^{\mathrm {Ar} }$ ein Ausdruck in der Sprache der Arithmetik (mit den Konstanten ${}0,1$, den Funktionssymbolen ${}+,\cdot$ und dem Relationssymbol ${}\geq$), der keine Quantoren enthält und nur eine einzige Variable ${}x$.

Zeige: Die Menge ${}T$ aller ${}n\in \mathbb {N}$ die ${}\alpha$ erfüllen, d.h.

${}T={\left\{n\in \mathbb {N} \mid \mathbb {N} {\frac {n}{x}}\vDash \alpha \right\}}\,,$

ist entscheidbar.

In den folgende Aufgaben verwenden wir den Begriff der Aufzählbarkeit nicht nur für Teilmengen ${}T\subseteq \mathbb {N}$, sondern auch für Teilmengen aus ${}L^{S}$.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet mit einer ${}R$-Aufzählung der in ${}S$ vorkommenden Variablen, Konstanten und Funktionssymbole. Zeige, dass es auch eine ${}R$-Aufzählung der ${}S$- Terme gibt.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet mit einer ${}R$-Aufzählung der in ${}S$ vorkommenden Variablen, Konstanten, Funktionssymbole und Relationssymbole. Zeige, dass es auch eine ${}R$-Aufzählung der ${}S$- Ausdrücke gibt.

Aufgabe Referenznummer erstellen

Es sei ${}S$ ein Symbolalphabet mit einer ${}R$-Aufzählung der in ${}S$ vorkommenden Variablen, Konstanten, Funktionssymbole und Relationssymbole. Zeige, dass es auch eine ${}R$-Aufzählung der ${}S$- Tautologien gibt.

Aufgaben zum Abgeben

Aufgabe (4 Punkte)Referenznummer erstellen

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 (4 Punkte)Referenznummer erstellen

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

Aufgabe (2 Punkte)Referenznummer erstellen

Zeige, dass jede endliche Teilmenge ${}T\subseteq \mathbb {N}$ der natürlichen Zahlen entscheidbar ist.

Aufgabe (3 Punkte)Referenznummer erstellen

Es seien ${}A,B\subseteq \mathbb {N}$ Teilmengen, deren symmetrische Differenz ${}A\mathop {\triangle } B$ endlich sei. Zeige, dass ${}A$ genau dann aufzählbar bzw. entscheidbar ist, wenn ${}B$ aufzählbar bzw. entscheidbar ist.

Aufgabe (3 Punkte)Referenznummer erstellen

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge der natürlichen Zahlen. Es gebe ein Programm für eine Registermaschine, das die Elemente von ${}T$ in aufsteigender Reihenfolge ausgibt. Zeige, dass ${}T$ entscheidbar ist.