Exercise 1

Partielle Funktionen

Partielle Funktion

Eine partielle Funktion von nach ist eine Funktion

Die Menge ist ihr Definitionsbereich. Außerhalb von ist undefiniert.

Totale Funktion

Die Funktion heißt total, wenn .

Logarithmus und Subtraktion

Für gilt

Die partielle Subtraktionsfunktion ist nur definiert, wenn das Ergebnis nicht negativ ist:

Im Gegensatz dazu ist die abgeschnittene Subtraktion total.

Undefinierte Werte vergleichen

Wir verwenden „undefiniert“ als Wert, auf den wir und anwenden können. Zwei undefinierte Werte gelten dabei als gleich.

Für

gilt daher : Beide Werte sind undefiniert.

Gleichheit partieller Funktionen

Zwei partielle Funktionen sind gleich, wenn sie denselben Definitionsbereich haben und dort dieselben Werte annehmen:

Mit der obigen Konvention ist dies gleichbedeutend mit für alle , auch außerhalb ihres Definitionsbereichs.

Verknüpfung partieller Funktionen

Seien und partielle Funktionen. Ihre Verknüpfung wird berechnet, indem zuerst alle auf denselben Input angewendet werden und anschließend auf die Ergebnisse:

Der Wert ist genau dann definiert, wenn alle definiert sind und gilt.

Auch die Notation ist üblich. Für ist die Funktion .

Programme und partielle Funktionen

Der Output eines Programms auf Input bestimmt eine berechenbare partielle Funktion. Ihr Definitionsbereich besteht aus den Inputs, auf denen terminiert; das Programm muss nicht auf jedem Input terminieren.

K1

Welche der folgenden Aussagen gilt allgemein für partielle Funktionen , wobei die konstante Nullfunktion ist:

1. (Gemeint ist links die Verknüpfung von zweimal derselben Funktion mit der zweistelligen partiellen Subtraktionsfunktion.)
2. (Gemeint ist links die Verknüpfung der beiden Funktionen und mit der zweistelligen Multiplikationsfunktion; rechts analog.)
3. wenn für alle .
   (Gemeint ist links die Verknüpfung der Funktion mit der Funktion ; rechts analog.)
4. für alle .

Stimmt nicht. Gegenbeispiel:

Stimmt. Sei .

1. Falls :

1. Falls :

wenn für alle

Stimmt nicht. Wähle die partielle Funktion mit

Damit gilt für alle . Für gilt jedoch:

Die beiden Verknüpfungen sind daher nicht gleich.

für alle

Stimmt nicht. Gegenbeispiel mit :

K2

1. Sei . Gemeint ist die Verknüpfung von mit der totalen Funktion; alternativ (das macht keinen Unterschied): Verknüpfung von und der konstanten Funktion mit der zweistelligen Funktion.

Gilt dann (allgemein): ?

2. Sei

Gilt dann allgemein für alle ?

(1)

Nein. Wähle die überall undefinierte partielle Funktion , also .

Dann ist auch für jedes undefiniert. Somit haben und denselben leeren Definitionsbereich und es gilt .

(2)

Stimmt. Sei .

1. is definiert, dann

2. is undefiniert, dann

Die universelle Funktion

Sei eine partiell berechenbare (p.c.) Funktion die Folgendes erfüllt: Für jede partiell berechenbare (p.c.) einstellige Funktion gibt es ein mit: .

Damit meinen wir natürlich: für alle .

K3

Instruction

Zeigen Sie: Es gibt keine universelle t.c. Funktion, d. h.: Es gibt kein t.c. so dass für jedes t.c. gilt: Es gibt ein mit .

Solution

Angenommen, es gäbe eine universelle total berechenbare Funktion . Jede Zeile der folgenden Tabelle stellt eine Funktion dar:

Wir definieren durch

Da total berechenbar ist, ist auch total berechenbar: Auf Eingabe berechnen wir und addieren . Wegen der Universalität muss daher mit einer Zeile übereinstimmen:

Am Diagonaleintrag dieser Zeile, also für , folgt:

Dies ist ein Widerspruch. Somit existiert keine universelle total berechenbare Funktion.

K4

Instruction

Zeigen Sie (nur unter Verwendung von obiger Eigenschaft von , ohne Verwendung von Halteproblem etc.):

Es gibt keine total berechenbare (t.c.) Fortsetzung von .

Solution

Angenommen, es gäbe eine total berechenbare Fortsetzung von , d.h.:

Man konstruiere eine total berechenbare Funktion mit

Da total berechenbar ist, ist auch partiell berechenbar, d.h.:

Daraus folgt:

Insbesondere gilt für :

Da total ist, ist definiert. Wegen der Fortsetzungseigenschaft gilt somit:

Folglich:

Somit existiert keine total berechenbare Fortsetzung von

Primitiv rekursive Funktionen

Sie können im Folgenden (nur) für die folgenden Funktionen verwenden dass sie prim.r. sind:

(Rekursion muss nicht über das erste Argument laufen, Vertauschung via Projektionen.)

Eine Teilmenge heißt prim.r. wenn die charakteristische Funktion prim.r. ist. Eine Eigenschaft wird identifiziert mit der Teilmenge .

K5

Instruction

Zeigen Sie dass die folgenden Funktionen bzw. Eigenschaften primitiv rekursiv sind:

4. , der Rest der Division . Dabei können Sie für beliebige Werte wählen, z. B. .
5. ist eine Primzahl.

Hinweis: Sie können z. B. über die Eigenschaft „ist Teiler“ summieren.

(1)

Korrektheit

• : .
• : .
• : (truncated).

Primitive Rekursivität

Komposition der primitiv rekursiven Konstante , Projektion und abgeschnittenen Subtraktion.

(2)

Korrektheit

Primitive Rekursivität

Komposition der primitiv rekursiven Funktionen aus (1), abgeschnittener Subtraktion und Multiplikation.

(3)

Korrektheit

Für ist der Wert , sonst .

Primitive Rekursivität

Komposition der primitiv rekursiven Konstante , Funktion aus (1) und abgeschnittenen Subtraktion.

(4)

Wir definieren durch primitive Rekursion über :

wobei .

Den Rest um eine Einheit weiterschalten

Halte den Divisor fest. Beim Übergang von zu wird der bisherige Rest zunächst um erhöht. Sobald diese Einheiten einen ganzen Block der Größe bilden, wird dieser Block abgezogen: Der neue Rest ist dann .

Für zeigen die drei Felder, wann ein Block voll ist. Türkise Punkte sind bisherige Einheiten; der orange Punkt kommt hinzu.

Die Funktion prüft, ob ihre beiden Argumente und gleich sind. Sie liefert oben und unten ; die Multiplikation mit bestimmt, ob kein Block oder ein ganzer Block abgezogen wird. ist dabei nur ein Name für das bereits berechnete Ergebnis .

Korrektheit

Für gilt . Wir unterscheiden zwei Fälle:

• : Der neue Rest ist .
• : Der neue Rest ist .

Damit entspricht die Funktion dem Divisionsrest.

Für gilt , weshalb .

Primitive Rekursivität

Primitive Rekursion mit konstanter Basis und primitiv rekursiver Schrittfunktion aus Addition, Subtraktion, Multiplikation und (2).

(5) ist prim

Damit definieren wir die Anzahl der positiven Teiler von :

Die gesuchte charakteristische Funktion lautet:

Korrektheit

• : Die Summe ist leer, also . Somit ist nicht prim.
• : Nur teilt , also . Somit ist nicht prim.
• : Genau dann, wenn prim ist, besitzt genau zwei positive Teiler, also .

Primitive Rekursivität

Teilbarkeit ist durch Komposition von (1) und (4) primitiv rekursiv; die Summe durch primitive Rekursion:

und der Vergleich mit sind Kompositionen primitiv rekursiver Funktionen.

K6+

Instruction

Die Ackermannfunktion ist wie folgt definiert:

1. Zeigen Sie dass wohldefiniert ist.

Für schreiben wir für die Funktion , .

Für jede totale Funktion schreiben wir wenn für alle die Ungleichung gilt.

2. Zeigen Sie, dass in beiden Argumenten streng monoton ist; außerdem: dass für alle gilt.
3. Seien und mit . Wenn¹ , dann gibt es ein mit .
4. Wenn durch primitive Rekursion aus und entsteht, und , gilt, dann gibt es ein mit .
5. Schließen Sie aus den vorigen Aufgaben: Für jede primitiv rekursive Funktion gibt es ein mit . Insbesondere ist nicht prim.r.

Offensichtlich (?) ist berechenbar, ist daher eine totale berechenbare Funktion die nicht prim.r. ist.

(1) Zeigen Sie, dass wohldefiniert ist.

Die Eindeutigeit folg taus:

Die Abdeckung folgt aus:

Die Fälle sind disjunkt und decken ab. Induktion über diese wohlgeordnete Menge liefert daher für jedes Paar genau einen Wert.

(2)

Strenge Monotonie im zweiten Argument

Hypothese

Voraussetzung

Linke Seite

Herleitung

Für gilt:

Die gleiche Umformung wird auf den inneren Ausdruck angewendet, bis erreicht ist. Für besteht die Komposition nur aus .

Rechte Seite

Herleitung

Für gilt mit der Formel für die linke Seite:

Für gilt die Ungleichung trivialerweise. Es verbleibt zu zeigen:

Setze

dann verbleibt zu zeigen, dass

Hypothese (2)

Voraussetzung (2) ( )

Schritt (2)

(3)

(4)

(5)

Z1

Schreiben Sie ein Programm bzw. skizzieren Sie einen Algorithmus (in einfachem Pseudocode), ohne rekursive Funktionsaufrufe, welches bei Eingabe den Wert von berechnet. (Sie dürfen z. B. beliebig große mehrdimensionale Arrays verwenden.)

Footnotes

1. ist Abkürzung für: . ↩