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

Aus Wikiversity



Übungsaufgaben

Aufgabe

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


Aufgabe *

Erstelle ein Programm für eine Registermaschine, das abwechselnd und ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Sprungbefehl verwendet.


Aufgabe *

Erstelle ein Programm für eine Registermaschine, das abwechselnd und ausdruckt, das mit sechs Befehlszeilen auskommt und lediglich einen Druckbefehl verwendet.


Aufgabe *

Schreibe einen Programmabschnitt für eine Registermaschine, das zum Befehl wechselt, wenn im -ten Register der Wert steht, und ansonsten weiterläuft. Man verwende nur die Grundbefehle.


Aufgabe

Entwerfe ein Programm für eine Registermaschine, die für die Differenz von zwei Registerinhalten berechnet.


Aufgabe

Entwerfe ein Programm für eine Registermaschine, das entscheidet, ob der Registerinhalt des Registers die echte Potenz einer natürlichen Zahl ist.


Aufgabe

Es sei . Entwerfe ein Programm für eine Registermaschine, das bei der Eingabe von in den ersten Registern die Zahl berechnet, ausdruckt und anhält.


Aufgabe

Es sei . Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von im ersten Register die -adische Ziffernentwicklung (mit ) berechnet, nach und nach die Ziffern (beginnend mit ) ausdruckt und schließlich anhält.


Aufgabe

Es sei . Entwerfe ein Programm für eine Registermaschine, das zur Eingabe von im ersten Register die -adische Ziffernentwicklung (mit ) berechnet, nach und nach die Exponenten und die zugehörigen Ziffern (beginnend mit und ) ausdruckt und schließlich anhält.


Aufgabe

Entwerfe ein möglichst kurzes (also mit möglichst wenigen Befehlszeilen) Programm für eine Registermaschine, das bei leerer Startbelegung anhält und zum Schluss die Zahl im ersten Register hat.


Aufgabe

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe einer natürlichen Zahlen im Register die Fakultät in ausgibt.


Aufgabe

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von zwei natürlichen Zahlen und in den Registern den Binomialkoeffizienten in ausgibt.


Aufgabe *

Entwerfe ein Programm für eine Registermaschine, das bei Eingabe von zwei natürlichen Zahlen und in den Registern den euklidischen Algorithmus durchführt und das Ergebnis, also den größten gemeinsamen Teiler von und , in ausgibt.


Aufgabe

Es sei 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?


Aufgabe

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


Aufgabe

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


Aufgabe

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


Aufgabe *

Im Aufbau der Registermaschine wurde der Druckbefehl durch einen Musiktonbefehl ersetzt, der den Inhalt von in einen Ton umsetzt, damit man mit der Registermaschine auch komponieren bzw. Lieder kodieren kann. Für ein Lied wurden schon Programmabschnitte geschrieben, die die folgende Bedeutung haben: ist das Vorspiel (), ist die Strophe (), ist der Refrain () und ist das Gitarrensolo (). Es soll nun aus den Programmabschnitten ein (anhaltendes) Programm zusammengesetzt werden, derart, dass beim Abspielen des Programms ein Lied der Form

erklingt. Dabei darf jeder der Programmabschnitte nur einmal im Programmcode auftauchen. Verwende ausschließlich die Grundbefehle.


Aufgabe

Welches Bildungsgesetz liegt der Folge

zugrunde?

(Es wird behauptet, dass diese Aufgabe für Grundschulkinder sehr einfach und für Mathematiker sehr schwierig ist.)



Aufgaben zum Abgeben

Aufgabe * (3 Punkte)

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


Aufgabe (5 Punkte)

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


Aufgabe (3 Punkte)

Entwerfe ein Programm für eine Registermaschine, das die Potenz berechnet (und ausgibt), wobei bzw. die Registerinhalte der Register , , sind.


Aufgabe (3 Punkte)

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


Aufgabe (4 Punkte)

Entwerfe ein möglichst kurzes (also mit möglichst wenigen Befehlszeilen) Programm für eine Registermaschine, das bei leerer Startbelegung anhält und zum Schluss die Zahl im ersten Register hat.

Punkte gibt es nur für ziemlich kurze Programme. Für den Kurs-Rekord gibt es drei Extrapunkte.


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)