Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 9/latex
\setcounter{section}{9}
\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
{}
{
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.
}
{} {}
| << | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >> |
|---|