Berechenbarkeit

Klaus Becker

TU Kaiserslautern

Die Möglichkeiten von Software

Herausgeber einer Software-Zeitschrift:

„Geben Sie einem Computer die richtige Software, und er wird tun, was immer Sie wünschen. Die Maschine selbst mag Grenzen haben, doch für die Möglichkeiten von Software gibt es keine Grenzen.“
(zitiert nach D. Harel: Das Affenpuzzle und weitere bad news aus der Computerwelt)

Teil 1

Berechenbarkeit als Problem

Grenzen von Software

Grundsatzfrage:

Gibt es Grenzen für die Möglichkeiten von Software?

Der Kern von Software

Algorithmen - der Kern von Software:

Wo liegen die Grenzen algorithmisch gesteuerter Systeme?
Gibt es Grenzen des algorithmisch Machbaren?

Die Suche nach Grenzen

Grundsatzfrage:

Gibt es Grenzen für die Möglichkeiten von Software?
Gibt es Grenzen für die Möglichkeiten von Algorithmen?

Vorgehensweise:

Um Aussagen über alle möglichen Algorithmen zu treffen, muss zunächst der Algorithmusbegriff präzisiert werden.

Was ist ein Algorithmus ?

Einfache Frage - viele Antworten:

Aho, Hopcroft, Ullman

Ein Algorithmus ist eine endliche Folge von Instruktionen, die alle eindeutig interpretierbar und mit endlichem Aufwand in endlicher Zeit ausführbar sind. Algorithmen enthalten Instruktionen zur Formulierung von (beliebig vielen) Wiederholungen anderer Instruktionen. Unabhängig von den Werten der Eingangsgrößen endet ein Algorithmus stets nach endlich vielen Instruktionsschritten. Ein Programm ist dann ein Algorithmus, wenn für alle möglichen Eingabewerte sichergestellt ist, dass keine Instruktion unendlich oft wiederholt wird.

Kronsjö

Ein Verfahren, beschrieben durch eine endliche Menge von eindeutig interpretierbaren Regeln, das eine endlich lange Folge von Operationen zur Lösung eines Problems oder einer speziellen Problemklasse beschreibt, wird Algorithmus genannt.

(http://www.swe.uni-linz.ac.at/teaching/lva/ss02/algo1_vorlesung/hinweise.html)

Was ist ein Algorithmus ?

Einfache Frage - viele Antworten:

Knuth

Ein Algorithmus muss nach endlich vielen Schritten enden. Jeder Schritt eines Algorithmus muss exakt beschrieben sein; die in ihm verlangten Aktionen müssen präzise formuliert und in jedem Falle eindeutig interpretierbar sein.

Ein Algorithmus hat keine, eine oder mehrere Eingangsgrößen, d.h. Größen, die von ihm benutzt und deren Werte vor Beginn seiner Ausführung festgelegt werden müssen.

Ein Algorithmus hat eine oder mehrere Ergebnisgrößen, d.h. Größen, deren Werte in Abhängigkeit von den Eingangsgrößen während der Ausführung des Algorithmus berechnet werden.

Ein Algorithmus muss so geartet sein, dass die in ihm verlangten Aktionen im Prinzip von einem Menschen in endlicher Zeit mit Papier und Bleistift ausgeführt werden können.

(http://www.swe.uni-linz.ac.at/teaching/lva/ss02/algo1_vorlesung/hinweise.html)

Was ist ein Algorithmus ?

Einfache Frage - viele Antworten:

Bauer, Goos

Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefasste, endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-) Schritte.

Rechenberg

Ein Algorithmus ist ein endliches schrittweises Verfahren zur Berechnung gesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl ausführbarer eindeutiger Operationen und einer Angabe über den nächsten Schritt besteht.

(http://www.swe.uni-linz.ac.at/teaching/lva/ss02/algo1_vorlesung/hinweise.html)

Der intuitive Algorithmusbegriff

„Definition:“

Ein Algorithmus ist eine Folge von Handlungsanweisungen zur Lösung eines Problems, die folgende Anforderungen erfüllt:

• Endlichkeit: Die Anweisungsfolge ist durch einen endlichen Text beschrieben.
• Ausführbarkeit: Die Anweisungen sind für den Empfänger (Mensch oder Maschine) verständlich formuliert und ausführbar.
• Eindeutigkeit: An jeder Stelle ist der Ablauf der Anweisungen eindeutig festgelegt.
• Allgemeinheit: Die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht nur für ein Einzelproblem.

(nach Gasper, Leiß, Spengler, Stimm: Technische und theoretische Informatik. bsv)

Unzulänglichkeit informeller Klärungen

„Definition:“

Ein Algorithmus ist eine Folge von Handlungsanweisungen zur Lösung eines Problems, die folgende Anforderungen erfüllt:

• Endlichkeit: Die Anweisungsfolge ist durch einen endlichen Text beschrieben.
• Ausführbarkeit: Die Anweisungen sind für den Empfänger (Mensch oder Maschine) verständlich formuliert und ausführbar.

• Eindeutigkeit: An jeder Stelle ist der Ablauf der Anweisungen eindeutig festgelegt.
• Allgemeinheit: Die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht nur für ein Einzelproblem.

Die oben aufgeführte Begriffsklärung ist keine präzise Definition im mathematischen Sinne.

Ziel: Präzisierung

„Definition:“

Ein Algorithmus ist eine Folge von Handlungsanweisungen zur Lösung eines Problems, die folgende Anforderungen erfüllt:

• Endlichkeit: Die Anweisungsfolge ist durch einen endlichen Text beschrieben.
• Ausführbarkeit: Die Anweisungen sind für den Empfänger (Mensch oder Maschine) verständlich formuliert und „ausführbar“.

• Eindeutigkeit: An jeder Stelle ist der Ablauf der Anweisungen eindeutig festgelegt.
• Allgemeinheit: Die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht nur für ein Einzelproblem.

Ziel ist es, die informelle Begriffsklärung durch eine präzise Definition im mathematischen Sinne zu ersetzen.

Präzisierungsansätze

Grundschema eines algorithmisch gesteuerten Systems

Präzisierungsansätze:

Maschinenorientierter Ansatz: Präzisierung des Prozessors

Zuordnungsorientierter Ansatz: Präzisierung der E/A-Zuordnungen

Anweisungsorientierter Ansatz: Präzisierung der zulässigen Anweisungen

Grundidee: Berechnungsmodelle

Präzisierung mit Berechnungsmodellen

Die Festlegung, was ein Algorithmus ist, bezieht sich auf ein streng definiertes Berechnungsmodell, das genau vorschreibt, was unter „ausführbar“ zu verstehen ist.

Grundlegende Schwierigkeit des Präzisierungsverfahrens

Wird mit Hilfe des Berechnungsmodells wirklich der intuitive Algorithmusbegriff adäquat erfasst?

Teil 2

Kara als Berechnungsmodell

Kara

Kara ist ein Marienkäfer.
Kara lebt in einer Welt mit

• unbewegliche Baumstümpfen,
• Pilzen, die Kara verschieben kann und
• Kleeblättern, die Kara legen und aufnehmen kann.

Lit.:: Reichert / Nievergelt / Hartmann: Programmieren mit Kara, Springer-Verlag 2004.
Software: www.educeth.ch/karatojava

Kara

Kara hat Sensoren, mit denen er/sie die Umwelt wahrnimmt:		Kara versteht einige Befehle, die er/sie folgsam ausführt:
	stehe ich vor einem Baumstumpf?		mache einen Schritt vorwärts!
	ist links von mir ein Baumstumpf?		drehe um 90° nach links!
	ist rechts von mir ein Baumstumpf?		drehe um 90° nach rechts!
	stehe ich vor einem Pilz?		lege ein Kleeblatt hin!
	stehe ich auf einem Kleeblatt?		nimm ein Kleeblatt auf!

Kara soll ein Problem lösen

Kara soll bis zum nächsten Baumstumpf, einmal um ihn herum und anschließend zurück zum Ausgangspunkt laufen.

AZ:
...
ZZ:

Kara-Algorithmus

Akt. Zustand:	Bedingung:	Aktionen:	Neuer Zustand:
markieren			hin
hin	nein		hin
hin	ja	...	zurück
zurück	nein		zurück
zurück	ja		stop

Übung

Entwickeln Sie einen Kara-Algorithmus zur Lösung des Problems:

AZ:	Kara sieht in Blickrichtung eine beliebig lange Baumstumpfreihe.
ZZ:	Kara umläuft die Baumstümpfe und bleibt stehen.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Lösung des Problems:

AZ:

Kara sieht in Blickrichtung eine beliebig lange vertikale Baumstumpfreihe.

ZZ:

Kara umläuft die Baumstumpfreihe und bleibt in der Verlängerung seines Wegs stehen.

Übung

Gibt es einen Kara-Algorithmus zur Lösung des Problems, bei dem Kara keine Blätter ablegen darf?

AZ:

ZZ:

Präzisierung des Algorithmusbegriffs

Von klaren Vorgaben zu präzisen Begriffsdefinitionen

Sei A die Menge der Kara-Aktionen:
A = {move, turnLeft, turnRight, putLeaf, removeLeaf}
Sei A´ die Menge der eingeschränkten Kara-Aktionen:
A´ = {move, turnLeft, turnRight}

Sei B die Menge der Kara-Bedingungen:
B = {treeFront, treeLeft, treeRight, mushroomFront, onLeaf, not treeFront, treeFront and (not onLeaf), ..., true}

Präzisierung des Algorithmusbegriffs

Akt. Zustand:	Bedingung:	Aktionen:	Neuer Zustand:
markieren			hin
hin	nein		hin
hin	ja	...	zurück

Definition:
Ein Kara-Algorithmus ist eine Paar (Z, F) bestehend aus einer endlichen Menge Z von Zuständen, die einen ausgezeichneten Startzustand enthält, und einer Funktion F, die die Arbeitsweise von Kara wie folgt festlegt: F ordnet Zustands-Bedingungs-Kombinationen (z, b) mit z?Z und b?B eine Aktionen-Zustands-Kombination (a, z´) zu, wobei a eine endliche (evtl. leere) Folge von Aktionen aus A ist und z´?Z den Folgezustand darstellt.
Ein Read-Only-Kara-Algorithmus ist ein Kara-Algorithmus, bei dem nur Aktionen aus der eingeschränkten Menge A´vorkommen.

Zur Lösung des Baumumrundungsproblems

Von präzisen Begriffsdefinitionen zu nachweisbaren Aussagen

Satz:
Es gibt einen Kara-Algorithmus, der das „vertikale Baumumrundungsproblem“ löst.

(Möglichkeits-) Beweis:
Der Beweis erfolgt konstruktiv, indem man einen geeigneten Kara-Algorithmus angibt.
Grundidee: Kara legt beim Weg „nach oben“ neben jeden Baumstumpf ein Kleeblatt. Kara zählt auf diese Weise mit, an wie vielen Baumstümpfen er/sie vorbeiläuft. Kara transportiert anschließend jedes dieser abgelegten Kleeblätter auf die „andere Seite des Baumstumpfs“. Damit ist Kara in der Lage, die gewünschte Endposition zu bestimmen.

Zur Lösung des Baumumrundungsproblems

Von präzisen Begriffsdefinitionen zu nachweisbaren Aussagen

Satz:
Es gibt keinen Read-Only-Kara-Algorithmus, der das „vertikale Baumumrundungsproblem“ löst.

(Unmöglichkeits-) Beweis:
Der Beweis wird durch Widerspruch geführt: Man nimmt an, es gebe einen solchen Algorithmus und führt diese Annahme zum Widerspruch.
Da das „vertikale Baumumrundungsproblem“ für Read-Only-Kara-Algorithmen strukturell ähnlich zum „anbn-Spracherkennungs-problem“ für endliche Automaten ist, kann der Nachweis, dass es keinen Read-Only-Kara-Algorithmus gibt, der das „vertikale Baumumrundungsproblem“ löst, völlig analog zum „anbn-Spracherkennungsproblem“ geführt werden.

Teil 3

Kara-Berechenbarkeit

Kara lernt rechnen

Im Folgenden betrachten wir eine spezielle Klasse von Problemen, die Kara lösen soll. Es handelt sich hier um „Berechnungs-probleme“, die Kara mit Hilfe von Kleeblättern ausführen soll.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Addition:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Kara hat eine Blattreihen der Länge m+n erzeugt.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Subtraktion:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Falls m≥n ist, hat Kara eine Blattreihe der Länge m-n erzeugt.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Subtraktion:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Falls m<n ist, kommt Kara nicht mehr klar und dreht sich ständig im Kreis herum.

Übung

Entwickeln Sie einen Kara-Algorithmus zum Verdoppeln:

AZ:	Kara steht vor einer beliebig langen Blattreihe der Länge n (die auch 0 sein kann).
ZZ:	Kara hat eine Blattreihe der Länge 2n erzeugt.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Multiplikation:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Kara hat eine Blattreihe der Länge m·n erzeugt.

Übung

Entwickeln Sie einen Kara-Algorithmus zur Multiplikation:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Kara hat eine Blattreihe der Länge m·n erzeugt, ohne die Zellenreihe, in der die Blätter liegen, zu verlassen.

Berechnete Funktion

Vom informellen Begriff zur präzisen Begriffsdefinition

Verdoppeln:

AZ:	Kara steht vor einer beliebig langen Blattreihe der Länge n (die auch 0 sein kann).
ZZ:	Kara hat eine Blattreihe der Länge 2n erzeugt.

Kara berechnet die Verdopplungsfunktion f: N → N mit f(n) = 2n.

Berechnete Funktion

Subtraktion:

AZ:	Kara steht vor zwei beliebig langen, durch eine leere Zelle getrennte Blattreihen der Längen m und n (die auch 0 sein können).
ZZ:	Falls m<n ist, kommt Kara nicht mehr klar und dreht sich ständig im Kreis herum.

Kara berechnet die Subtraktionsfunktion f: N x N → N mit:

Präzisierung von Berechenbarkeit

Definition:
Eine Funktion f: N → N heißt Kara-berechenbar, gdw gilt:
Es gibt einen Kara-Algorithmus mit der folgenden Eigenschaft:

AZ:	Kara steht vor einer Blattreihe der Länge n.
ZZ:	Fall 1: f(n) ist definiert: Kara hat eine Blattreihe der Länge f(n) erzeugt und hält. Fall 2: f(n) ist undefiniert: Kara hält nicht.

Analog für f: N x N x ... x N → N

Berechenbarkeitsaussagen

Neue Fragen

Welche Funktionen sind Kara-berechnenbar, welche evtl. nicht?

Teil 4

Turingmaschinen

Alan Turing

Turings Idee

Vom Rechnen zu den „Computing maschines“

„Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used.

(Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 1936)

Turings Idee

Vom Rechnen zu den „Computing maschines“

„Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. ...“

(Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 1936)

Turings Idee

Vom Rechnen zu den „Computing maschines“

„The behaviour of the computer at any moment is determined by the symbols which he is observing and his “state of mind” at that moment. ...“
„Let us imagine the operations performed by the computer to be split up into “simple operations” which are so elementary that it is not easy to imagine them further divided. ...“

(Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 1936)

Turingmaschine

Turingmaschine

Zustandsübergang:

Turingmaschinenaktionen:

Beispiel

Berechnungsproblem: Addition von „Strichzahlen“

Turingmaschine (dargestellt mit einem Zustandsgraphen):

Beispiel

Turingmaschine (dargestellt mit einem Zustandsgraphen):

Turingmaschine (dargestellt mit einer Zustandstafel):

Beispiel

Übung

Berechnungsproblem: Verdopplung von „Strichzahlen“

Entwickeln und testen Sie eine Turingmaschine zur Verdopplung von Strichzahlen. Beschreiben Sie die Turingmaschine mit einem Zustandsgraph und einer Zustandstabelle. Zum Testen können Sie den MPG-Turing-Simulator benutzen.

Präzisierung von Berechenbarkeit

Definition:
Eine Funktion f: N → N heißt Turingmaschinen-berechenbar, gdw gilt: Es gibt eine Turingmaschine T mit der folgenden Eigenschaft:

AZ:	Auf dem Band befindet sich n dargestellt als Strichzahl.
ZZ:	Fall 1: f(n) ist definiert: T hält und hat f(n) dargestellt als Strichzahl erzeugt. Fall 2: f(n) ist undefiniert: T hält nicht.

Analog für f: N x N x ... x N → N

Variation der Turingmaschine

Berechnungsproblem: Verdopplung von „Strichzahlen“

Variation der Turingmaschine

Berechnungsproblem: Verdopplung von „Strichzahlen“

Kara als Variation der Turingmaschine

Übung

Lösen Sie das Verdopplungsproblem (oder das Multiplikationsproblem) mit Hilfe einer 2-Band-Turingmaschine und mit Hilfe einer zweidimensionalen Turingmaschine.

Äquivalenz von Turingmaschinenmodellen

Problem

Was leisten Mehr-Band-Turingmaschinen bzw. zweidimensionale Turingmaschinen mehr als Ein-Band-Turingmaschinen?

Beweisidee

Simulation der Aktionen einer Zwei-Band-TM auf einem Band

Äquivalenz der Turingmaschinenmodelle

Problem

Was leisten Mehr-Band-Turingmaschinen bzw. zweidimensionale Turingmaschinen mehr als Ein-Band-Turingmaschinen?

Teil 5

Universelle Turingmaschine

Universelle Berechnungsmodelle

Computer sind programmierbar!

Ein universelles Berechnungsmodell sollte in der Lage sein, nicht nur Eingabedaten in einer ganz bestimmten Weise zu verarbeiten, sondern Eingabedaten nach einem beliebigen, ebenfalls einzugebenden Verarbeitungsprogramm zu verarbeiten.

Universelle Berechnungsmodelle

Universelle Turingmaschine als Turingmaschinen-Interpreter

Eine universelle Turingmaschine besitzt die Fähigkeit, beliebige andere Turingmaschinen zu simulieren. Als Eingabe erhält sie die Beschreibung der zu simulierenden Turingmaschine und der Daten auf dem Eingabeband für diese Turingmaschine.

Universelle Berechnungsmodelle

Beispiel: Invertieren einer 01-Zeichenkette

Eine universelle Turingmaschine besitzt die Fähigkeit, beliebige andere Turingmaschinen zu simulieren. Als Eingabe erhält sie die Beschreibung der zu simulierenden Turingmaschine und der Daten auf dem Eingabeband für diese Turingmaschine.

Universelle Berechnungsmodelle

Simulation von Ein-Band-Turingmaschinen mit einer univers. TM

Vgl.: Turingkara - Aufgaben: Die universelle Turingmaschine

Universelle Berechnungsmodelle

Simulation von Ein-Band-Turingmaschinen mit einer univers. TM.

Kodierung: alter Zustand als Strichzahl+1; Leerzeichen; altes Zeichen; neues Zeichen; Bewegung; neuer Zustand als Strichzahl+1

Vgl.: U. Mayr: Theoretische Informatik am PC, S. 18 ff. Programm: Bsp-206.tm

Übung

Testen Sie die universelle Turingmaschine der Turing-Kara-Umgebung bzw. des MPG-Simulators. Versuchen Sie insbesondere zu verstehen, wie diese universelle Turingmaschine arbeitet. Sie können auch die jeweils vorgegebene Turingmaschine und Bandbelegung durch eine andere ersetzen.

Universelle Turingmaschine

Bemerkungen zum Beweis:
Die Existenz einer universellen Turingmaschine zeigt man, indem man eine TM konstruiert, die sich wie ein Turingmaschinen-Interpreter verhält, d. h. diese (zweidimensionale oder Mehr-Band-) Turingmaschine simuliert das Verhalten einer beliebig vorgegebenen Ein-Band-Turingmaschine bei einer beliebig vorgegebenen Bandbelegung. Die vorgegebene Turingmaschine und die vorgegebene Bandbelegung müssen dabei geeignet kodiert werden.

Teil 6

Registermaschinen

Präzisierung des Algorithmusbegriffs

Grundschema eines algorithmisch gesteuerten Systems

Präzisierungsansätze:

Maschinenorientierte Ansätze:

- Kara („mehr als ein Spielzeug“)

- Turingmaschine („abstraktes Rechnermodell“)

- Registermaschine („an realen Rechnern orientiertes Modell“)

Berechnungsmodell „Registermaschine“

An realen Rechnern orientiertes Berechnungsmodell

Registermaschinenbefehle

An realen Rechnern orientiertes Berechnungsmodell

Registermaschine in Aktion

Verhaltensbeschreibung

Die Registermaschine berechnet die Verdopplungsfunktion auf natürlichen Zahlen, d. h.:
f: N → N mit f(n) = 2n

Präzisierung von Berechenbarkeit

Definition:
Eine Funktion f: N → N heißt Registermaschinen-berechenbar, gdw gilt: Es gibt eine Registermaschine mit der folgenden Eigenschaft

AZ:	Im Registern R1 befindet sich der Ausgangswert.
ZZ:	Fall 1: f(n) ist definiert: Die RM hält und in R0 befindet sich der Ergebniswert. Fall 2: f(n) ist undefiniert: Die RM hält nicht.

Analog für f: N x N x ... x N → N

Äquivalenzsatz

Beweis:
Der Beweis wird konstruktiv geführt. Man konstruiert mit Hilfe einer Turingmaschine einen Registermaschinen-Interpreter und umgekehrt mit Hilfe einer Registermaschine einen Turingmaschinen-Interpreter.

Teil 7

LOOP- und WHILE-Programme

Präzisierung des Algorithmusbegriffs

Grundschema eines algorithmisch gesteuerten Systems

Präzisierungsansätze:

Anweisungsorientierte Ansätze:

- Die Programmiersprache „LOOP“

- Die Programmiersprache „WHILE“

- Die Programmiersprachen „Pascal“, „Delphi“, „Java“, ...

LOOP-Programme

Bestandteile von LOOP-Programmen

Aufbau eines LOOP-Programms

Jede Wertzuweisung der Form x_i := c oder x_i := x_j oder x_i := x_j + c ist ein LOOP-Programm.

Falls P1 und P2 LOOP-Programme sind, dann ist auch die Sequenz P1; P2 ein LOOP-Programm.

Falls P ein LOOP-Programm ist, dann ist auch LOOP x_i DO P END ein LOOP-Programm.

LOOP-Programme

Beispiel eines LOOP-Programms

x₀ := x₁;

LOOP x₂ DO x₀ := x₀ + 1 END

Ausführung der LOOP-Anweisung

Eine LOOP-Anweisung der Form LOOP x_i DO P END wird wie folgt ausgeführt: Die LOOP-Anweisung P wird sooft ausgeführt, wie der Wert der Variablen x_i zu Beginn beträgt.

Bedeutung eines LOOP-Programms

WHILE-Programme

Bestandteile von WHILE-Programmen

Aufbau eines WHILE-Programms

Jede Wertzuweisung der Form x_i := c oder x_i := x_j oder x_i := x_j + c ist ein WHILE-Programm.

Falls P1 und P2 WHILE-Programme sind, dann ist auch die Sequenz P1; P2 ein WHILE-Programm.

Falls P ein WHILE-Programm ist, dann ist auch WHILE x_i ≠ 0 DO P END ein WHILE-Programm.

WHILE-Programme

Beispiel eines WHILE-Programms

x₀ := x₁;

WHILE x₂ ≠ 0 DO x₀ := x₀ + 1; x₂ := x₂ - 1 END

Ausführung der WHILE-Anweisung

Eine WHILE-Anweisung der Form WHILE x_i ≠ 0 DO P END wird wie folgt ausgeführt: Das WHILE-Programm P wird solange ausgeführt, wie der Wert der Variablen x_i ungleich Null ist.

Bedeutung eines WHILE-Programms

Präzisierung von Berechenbarkeit

Analog für f: N x N x ... x N → N

Übung

Aufgabe 1
Entwickeln Sie ein LOOP-Programm / WHILE-Programm zur Berechnung der Verdopplungsfunktion / Multiplikationsfunktion.

Aufgabe 2
Welche Funktion wird durch das folgende WHILE-Programm berechnet?
x₀ := x₁;
WHILE x₂ ≠ 0 DO x₀ := x₀ + 1 END

Aufgabe 3
Gibt es Funktionen, die mit keinem LOOP-Programm berechnet werden können?

Unterschied LOOP-WHILE

Unterschied: LOOP-berechenbar - WHILE-berechenbar

Die Ausführung jedes LOOP-Programms endet immer. Ein WHILE-Programm kann dagegen eine Endlosschleife enthalten.
x₀ := x₁;
WHILE x₂ ≠ 0 DO x₀ := x₀ + 1 END
Das gezeigte WHILE-Programm berechnet die Funktion f: N → N mit f(m, n) = IF(n=0, m, ⊥).

Äquivalenzsatz

Beweis:
Der Beweis wird konstruktiv geführt. Man konstruiert zu jeder Registermaschine ein entsprechendes WHILE-Programm und umgekehrt zu jedem WHILE-Programm eine entsprechende Registermaschine.

Teil 8

Rekursive Funktionen

Rekursive Funktionen

Grundschema eines algorithmisch gesteuerten Systems

Grundidee:

Man beschreibt die berechenbaren E/A-Zuordnungen wie folgt:
Einige einfache Grundfunktionen werden als „berechenbar“ erklärt. Des weiteren werden einige einfache Konstruktionsprinzipien angegeben, die beschreiben, wie man aus „berechenbaren Funktionen“ weitere „berechenbare Funktionen“ erhält. Die zentrale Konstruktionsoperation ist die dabei die Rekursion.

Rekursives Berechnungsschema

Beispiel: Addition natürlicher Zahlen

add(x,0) = x
add(x,s(y))= s(add(x,y))

Bemerkungen:

Die Nachfolgerfunktion s: N → N, die jeder natürlichen Zahl ihren direkten Nachfolger zuordnet, wird als gegebene berechenbare Funktion betrachtet.
Die Funktion add: N x N → N, die je zwei natürlichen Zahlen ihre Summe zuordnen soll, wird rekursiv festgelegt:
- Zunächst wird der Rekursionsanfang „addiere zur Zahl x die Zahl 0“ festgelegt.
- Anschließend wird der Fall „addiere zur Zahl x den Nachfolger s(y) einer Zahl y“ auf den Fall „addiere zu x die Zahl y“ rekursiv reduziert.
Bei der Festlegung werden hier die Konstruktionsoperationen „Rekursion“ und „Funktionskomposion“ und die Grundfunktion „s“ benutzt.

Rekursives Berechnungsschema

Beispiel: Addition natürlicher Zahlen

add(x,0) = x
add(x,s(y))= s(add(x,y))

Berechnung rekursiv festgelegter Funktionen

Übung

Entwickeln Sie rekursive Berechnungsschemata für die folgenden Funktionen. Benutzen Sie nur die vorgegebene Nachfolgerfunktion s und bereits definierte Funktionen (wie add).

Übung

Untersuchen Sie die folgenden rekursiven Berechnungsschemata und beschreiben Sie die jeweils berechneten Funktionen.

test(0)=1
test(s(x))=0
pred(0)=0
pred(s(x))=x
subtr(x,0)=x
subtr(x,s(y))=pred(subtr(x,y))
absdiff(x,y)=add(subtr(x,y),subtr(y,x))
equal(x,y)=test(absdiff(x,y))

Übung

Welche Berechnungsschemata sind korrekt, sinnvoll?

subtr2(x, 0) = x
subtr2(0, y) = y
subtr2(s(x), s(y)) = subtr2(x, y)
subtr3(x, 0) = x
subtr3(0, y) = y
subtr3(x, y) = subtr3(s(x), s(y))
add2(x, 0) = x
add2(x,y)= add(s(x),pred(y)))

Primitive Rekursion

Rekursive Problemreduktionen:

add(x,s(y))= s(add(x,y))
add2(x,y)= add2(s(x),pred(y)))
subtr(x,s(y))=pred(subtr(x,y))
subtr2(s(x), s(y)) = subtr2(x, y)
subtr3(x, y) = subtr3(s(x), s(y))

Primitives Reduktionsschema:

add(x,s(y))= s(add(x,y))
f(x₁,...,x_n ,s(y)) = h(x₁,...,x_n ,y,f(x₁,...,x_n,y))

In einem Schritt wird nur ein Argument um 1 reduziert.

Primitive Rekursion

Primitives Reduktionsschema:

add(x,0) = x
add(x,s(y))= s(add(x,y))

Formalisierung

f(x₁,...,x_n ,0) = g(x₁,...,x_n)
f(x₁,...,x_n ,s(y)) = h(x₁,...,x_n ,y,f(x₁,...,x_n,y))

Rekursionsanfang: Die Funktion f kommt nicht auf der rechten Seite vor.
Rekursionsschritt: Die Funktion f kommt auf der rechten Seite vor, aber nur ein Argument wird um 1 reduziert.

Primitiv rekursive Funktionen

Übung

Testen Sie das folgende rekursive Berechnungsschemata zur sogenannten Ackermann-Funktion. Was beobachtet man, wenn die Parameter (insbesondere der zweite) nicht sehr klein gewählt werden?

Ack(0,y)=s(y)
Ack(s(x),0)=Ack(x,1)
Ack(s(x),s(y))=Ack(x,Ack(s(x),y))

Ackermannfunktion

Rekursive Definition:

Ack(0,y)=s(y)
Ack(s(x),0)=Ack(x,1)
Ack(s(x),s(y))=Ack(x,Ack(s(x),y))

Beachte:
Es handelt sich hier nicht um ein primitiv rekursives Rekursionsschema.

Man muss zeigen, dass die Ackermannfunktion sich nicht mit Hilfe eines primitiv rekursiven Rekursionsschemas darstellen lässt. Zum Beweis zeigt man, dass die Ackermann-Funktion schneller wächst als jede primitiv rekursive Funktion.

Übung

Wir betrachten die folgende informell definierte Funktion. Berechnen Sie f(5, 2) und f(2, 5). Beschreiben Sie das Verhalten der Funktion f.

f(x, y) = „das kleinste z mit y+z=x“

Partiell rekursive Funktionen

Beweis: siehe Fachliteratur

Äquivalenzsatz

Beweis: siehe Fachliteratur

Teil 9

Church-Turing-These

Berechnungsmodelle

Grundschema eines algorithmisch gesteuerten Systems

Präzisierungsansätze:

Maschinenorientierter Ansatz: Turingmaschine, Registermaschine

Zuordnungsorientierter Ansatz: partiell rekursive Funktion

Anweisungsorientierter Ansatz: WHILE, Pascal, Delphi, C, Java, ...

Äquivalenzsatz

Bem.:
Alle Ansätze zur Präzisierung führen auf dieselbe Klasse berechenbarer Funktionen.

Church-Turing-These

Literaturhinweise

Gasper, Leiß, Spengler, Stimm: Technische und theoretische Informatik. Bayerischer Schulbuch-Verlag 1992.

U. Mayr: Theoretische Informatik am PC. SIL-Studienmaterial Band 142, Speyer 1994.

Reichert, Nievergelt, Hartmann: Programmieren mit Kara. Springer-Verlag 2004.

D. Harel: Das Affenpuzzle und weitere bad news aus der Computerwelt. Springer-Verlag 2002.

U. Schöning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag 2001.