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

\setcounter{section}{19}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

Bestimme die symbolische und die numerische Kodierung des folgenden Programms für eine Registermaschine.
\mathdisp {1. \, \, 3+} { }

\mathdisp {2. \, \, 2-} { }

\mathdisp {3. \, \,C(2,4)} { }

\mathdisp {4. \, \, C(3,1)} { }

\mathdisp {5. \text{ Drucke}} { }

\mathdisp {6. \text{ Halte an}} { . }

}
{} {}

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.

}
{} {}

\inputaufgabegibtloesung
{}
{

Die Registerabteilung des VW-Konzerns hat \zusatzgs {ohne Wissen des Vorstandes und am Aufsichtsrat vorbei} {} in jedes real existierende Registerprogramm $P$ an einer willkürlich gewählten Stelle die aufeinanderfolgenden Befehlszeilen eingebaut \zusatzklammer {und dabei die Zeilennummern und die Sprungbefehlsnummern angepasst, $k$ ist die Nummer eines in $P$ nicht verwendeten Registers und $h'$ ist die neue Haltebefehlsnummer} {} {}
\mathdisp {k+} { }

\mathdisp {k+} { }

\mathdisp {\text{Drucke}} { }

\mathdisp {C(k,h')} { . }
\aufzaehlungdrei{Ändert sich durch diese Manipulation die Halteeigenschaft des Programms? }{Ändert sich durch diese Manipulation die Programmabbildung? }{Nachdem der Skandal herauskommt und die Öffentlichkeit eine Erklärung fordert, diskutieren Vorstand, Aufsichtsrat und Abteilungsleiter die folgenden möglichen Stellungsnahmen für die anstehende Pressekonferenz:

a) Man wollte Speicherplatz sparen.

b) Man wollte aus Werbezwecken erreichen, dass jedes Registerprogramm mindestens einmal \anfuehrung{VW}{} ausdruckt.

c) Man wollte einen Beitrag zur Entschleunigung leisten, indem man manche Programme etwas langsamer macht.

d) Man wollte einen Beitrag zur Entschleunigung leisten, indem man alle Programme etwas langsamer macht.

Welche dieser Erklärungen passen inhaltlich zu den Manipulationen? }

}
{} {}

\inputaufgabe
{}
{

Entwerfe ein Programm für eine Registermaschine, das genau dann anhält, wenn die \definitionsverweis {Goldbachsche Vermutung}{}{} falsch ist.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass das in Aufgabe 18.17 entworfene \definitionsverweis {Programm für eine Registermaschine}{}{} bei Eingabe einer natürlichen Zahlen $n$ im Register
\mathl{R_1}{} genau dann nicht anhält, wenn die Zahl $n$ eine negative Antwort zum Collatz-Problem liefert.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{4}
{

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
{4}
{

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

}
{} {}

\inputaufgabe
{2}
{

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

}
{} {}

\inputaufgabe
{3}
{

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
{3}
{

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.

}
{} {}