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

\setcounter{section}{19}

\zwischenueberschrift{Übungsaufgaben}

\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.

}
{} {}

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

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

Zeige: Die Menge $T$ aller
\mathl{n \in \N}{} die $\alpha$ erfüllen, d.h.
\mavergleichskettedisp
{\vergleichskette
{T }
{ =} { { \left\{ n \in \N \mid \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
\mathl{T \subseteq \N}{,} sondern auch für Teilmengen aus $L^S$.


\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {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$-\definitionsverweis {Ausdrücke}{}{} gibt.

}
{} {}

\inputaufgabe
{}
{

Es sei $S$ ein \definitionsverweis {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$-\definitionsverweis {Tautologien}{}{} gibt.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}