Berechenbarkeit Klaus Becker 2004. KB Berechenbarkeit 2 Die Möglichkeiten von Software Geben Sie einem Computer die richtige Software, und er wird tun,

BerechenbarkeitBerechenbarkeit

Klaus Becker2004

2

KB

Bere

chen

bark

eit

Die Möglichkeiten von Software Die Möglichkeiten von Software

„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)

Herausgeber einer Software-Zeitschrift:Herausgeber einer Software-Zeitschrift:

3

KB

Bere

chen

bark

eit

Teil 1 Teil 1

Berechenbarkeit als Problem

4

KB

Bere

chen

bark

eit

Grenzen von SoftwareGrenzen von Software

Daten

?

Software

Grundsatzfrage:Grundsatzfrage:

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

5

KB

Bere

chen

bark

eit

Der Kern von SoftwareDer Kern von Software

Algorithmen – der Kern von Software: Algorithmen – der Kern von Software:

binaeres_suchen (wonach)

links:= Anfang

rechts:= Ende

Wiederhole bis gefunden

oder links > rechts

Berechne mittlere Position

zwischen links und rechts

wonach < wert(pos)ja nein

rechts:= pos -1

wonach > wert(pos)ja nein

links:= pos +1

lineare_suche (wonach)

Wiederhole bis gefunden oder alles durchlaufen

wert[pos]=wonachja nein

gefunden!

merke pos

Gehe zur

nächsten pos

Wo liegen die Grenzen algorithmisch gesteuerter Systeme?

Gibt es Grenzen des algorithmisch Machbaren?

6

KB

Bere

chen

bark

eit

Die Suche nach GrenzenDie Suche nach Grenzen

Grundsatzfrage:Grundsatzfrage:

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

Vorgehensweise:Vorgehensweise:

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

Möglichkeitsnachweis:Möglichkeitsnachweis:

Man entwickelt einen Algorithmus und implementiert die zugehörige Software.

Unmöglichkeitsnachweis:Unmöglichkeitsnachweis:

Man muss zeigen, dass es keinen Algorithmus gibt, der das gestellte Problem löst. D. h.: Jeder mögliche Algorithmus löst nicht das gestellte Problem.

7

KB

Bere

chen

bark

eit

Was ist ein Algorithmus ?Was ist ein Algorithmus ?

Einfache Frage – viele Antworten: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)

8

KB

Bere

chen

bark

eit


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.



9

KB

Bere

chen

bark

eit


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.



10

KB

Bere

chen

bark

eit

Der intuitive AlgorithmusbegriffDer intuitive Algorithmusbegriff

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.

„Definition:“„Definition:“

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

11

KB

Bere

chen

bark

eit

Unzulänglichkeit informeller KlärungenUnzulänglichkeit informeller Klärungen



- Ausführbarkeit: Die Anweisungen sind für den Empfänger (Mensch oder Maschine) verständlich formuliert und ausführbar.




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

Was heißt das?

12

KB

Bere

chen

bark

eit

Ziel: PräzisierungZiel: Präzisierung



- Ausführbarkeit: Die Anweisungen sind für den Empfänger (Mensch oder Maschine) verständlich formuliert und „ausführbar“.




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

Muss präzisiert werden

13

KB

Bere

chen

bark

eit

PräzisierungsansätzePräzisierungsansätze

“Prozessor”Anweisungen

Eingaben

Ausgaben

Grundschema eines algorithmisch gesteuerten SystemsGrundschema eines algorithmisch gesteuerten Systems

Präzisierungsansätze: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

14

KB

Bere

chen

bark

eit

Grundidee: BerechnungsmodelleGrundidee: Berechnungsmodelle

Präzisierung mit BerechnungsmodellenPrä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äzisierungsverfahrensGrundlegende Schwierigkeit des Präzisierungsverfahrens

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

15

KB

Bere

chen

bark

eit

Teil 2 Teil 2

Kara als Berechnungsmodell

16

KB

Bere

chen

bark

eit

KaraKara

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

17

KB

Bere

chen

bark

eit

KaraKara

Kara hat Sensoren, mit denen er/sie die Umwelt wahrnimmt:

stehe ich vor einem Baumstumpf?

ist links von mir ein Baumstumpf?

ist rechts von mir ein Baumstumpf?

stehe ich vor einem Pilz?

stehe ich auf einem Kleeblatt?

Kara versteht einige Befehle,die er/sie folgsam ausführt:

mache einen Schrittvorwärts!

drehe um 90° nach links!

drehe um 90° nach rechts!

lege ein Kleeblatt hin!

nimm ein Kleeblatt auf!

18

KB

Bere

chen

bark

eit

Kara soll ein Problem lösenKara 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:

19

KB

Bere

chen

bark

eit

Kara-AlgorithmusKara-Algorithmus

Bedingung: Aktionen:Akt. Zustand: Neuer Zustand:

markieren hin

hin nein hin

hin ja zurück...

zurück nein zurück

zurück ja stop

mark. hin stop/ Blatt hinlegen

Vor Baum? nein / vorwärts

Vor Baum? ja / links; ...

zurück

Auf Blatt? nein / vorwärts

Auf Blatt? ja / links; links

20

KB

Bere

chen

bark

eit

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

ÜbungÜbung

AZ: Kara sieht in Blickrichtung eine beliebig lange Baumstumpfreihe.

ZZ: Kara umläuft die Baumstümpfe und bleibt stehen.

21

KB

Bere

chen

bark

eit

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

ÜbungÜbung

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.

22

KB

Bere

chen

bark

eit

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

ÜbungÜbung

AZ: ZZ:

23

KB

Bere

chen

bark

eit

Präzisierung des AlgorithmusbegriffsPräzisierung des Algorithmusbegriffs

Von klaren Vorgaben zu präzisen BegriffsdefinitionenVon klaren Vorgaben zu präzisen Begriffsdefinitionen

Sei A die Menge der Kara-Aktionen:

Sei B die Menge der Kara-Bedingungen:

B = {treeFront, treeLeft, treeRight, mushroomFront, onLeaf, not treeFront, treeFront and (not onLeaf), ..., true}

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

24

KB

Bere

chen

bark

eit

Präzisierung des AlgorithmusbegriffsPräzisierung des Algorithmusbegriffs

Bedingung: Aktionen:Akt. Zustand: 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 zZ und bB 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.

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 zZ und bB 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.

25

KB

Bere

chen

bark

eit

Zur Lösung des Zur Lösung des BaumumrundungsproblemsBaumumrundungsproblems

Von präzisen Begriffsdefinitionen zu nachweisbaren AussagenVon präzisen Begriffsdefinitionen zu nachweisbaren Aussagen

(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.

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

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

26

KB

Bere

chen

bark

eit

(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.

Zur Lösung des Zur Lösung des BaumumrundungsproblemsBaumumrundungsproblems

Von präzisen Begriffsdefinitionen zu nachweisbaren AussagenVon präzisen Begriffsdefinitionen zu nachweisbaren Aussagen

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

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

27

KB

Bere

chen

bark

eit

Teil 3 Teil 3

Kara-Berechenbarkeit

28

KB

Bere

chen

bark

eit

Kara lernt rechnen 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.

29

KB

Bere

chen

bark

eitÜbungÜ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.

30

KB

Bere

chen

bark

eitÜbungÜbung

Entwickeln Sie einen Kara-Algorithmus zur Subtraktion:


ZZ: Falls mn ist, hat Kara eine Blattreihe der Länge m-n erzeugt.

31

KB

Bere

chen

bark

eitÜbungÜbung

Entwickeln Sie einen Kara-Algorithmus zur Subtraktion:


ZZ: Falls m<n ist, kommt Kara nicht mehr klar und dreht sich ständig im Kreis herum.

32

KB

Bere

chen

bark

eitÜbungÜ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.

33

KB

Bere

chen

bark

eitÜbungÜbung

Entwickeln Sie einen Kara-Algorithmus zur Multiplikation:


ZZ: Kara hat eine Blattreihe der Länge mn erzeugt.

34

KB

Bere

chen

bark

eitÜbungÜbung

Entwickeln Sie einen Kara-Algorithmus zur Multiplikation:


ZZ: Kara hat eine Blattreihe der Länge mn erzeugt, ohne die Zellenreihe, in der die Blätter liegen, zu verlassen.

35

KB

Bere

chen

bark

eit

Berechnete FunktionBerechnete Funktion

Vom informellen Begriff zur präzisen BegriffsdefinitionVom 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.

36

KB

Bere

chen

bark

eit

Berechnete FunktionBerechnete Funktion

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

Subtraktion:


ZZ: Falls m<n ist, kommt Kara nicht mehr klar und dreht sich ständig im Kreis herum.

f(m,n) = m-n falls m n

undefiniert falls m < n

37

KB

Bere

chen

bark

eit

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.

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.

Präzisierung von BerechenbarkeitPräzisierung von Berechenbarkeit

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

38

KB

Bere

chen

bark

eit

BerechenbarkeitsaussagenBerechenbarkeitsaussagen

Neue FragenNeue Fragen

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

Satz:Die folgenden Funktionen sind Kara-berechnenbar:• f(n) = 2n• f(m, n) = m + n• f(m, n) = IF(mn, m-n, )• f(m, n) = mn

Satz:Die folgenden Funktionen sind Kara-berechnenbar:• f(n) = 2n• f(m, n) = m + n• f(m, n) = IF(mn, m-n, )• f(m, n) = mn

39

KB

Bere

chen

bark

eit

Teil 4 Teil 4

Turingmaschinen

40

KB

Bere

chen

bark

eit

Alan TuringAlan Turing

http://www.alanturing.net/

Alan Mathison Turing FRS OBE (born 23 June 1912 at 2 Warrington Crescent, London W9, died 7 June 1954 at his home in Wilmslow, Cheshire) contributed to mathematics, cryptanalysis, logic, philosophy, biology, and formatively to computer science, cognitive science, Artificial Intelligence and Artificial Life.

Educated at Sherborne School in Dorset, Turing went up to King's College, Cambridge in October 1931 to read Mathematics. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. ...

Alan Mathison Turing FRS OBE (born 23 June 1912 at 2 Warrington Crescent, London W9, died 7 June 1954 at his home in Wilmslow, Cheshire) contributed to mathematics, cryptanalysis, logic, philosophy, biology, and formatively to computer science, cognitive science, Artificial Intelligence and Artificial Life.

Educated at Sherborne School in Dorset, Turing went up to King's College, Cambridge in October 1931 to read Mathematics. He was elected a Fellow of King's in March 1935, at the age of only 22. In the same year he invented the abstract computing machines - now known simply as Turing machines - on which all subsequent stored-program digital computers are modelled. ...

41

KB

Bere

chen

bark

eit

Turings IdeeTurings Idee

Vom Rechnen zu den „Computing maschines“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.

3 6 2 7

7 2

2 5 2

9 7 2

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

42

KB

Bere

chen

bark

eit



„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. ...“

6 2 73


2 5 2 7 2

43

KB

Bere

chen

bark

eit



„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. ...“

6 2 73


q0

Ein-/Ausgabeband

Schreib-/Lesekopf

Zustandsbasierte

Verarbeitungseinheit

44

KB

Bere

chen

bark

eit

TuringmaschineTuringmaschine

...I I I I I

...

Turingmaschine

Ein-/Ausgabeband

Schreib-/Lesekopf

Zustandsbasierte


45

KB

Bere

chen

bark

eit

TuringmaschineTuringmaschine

Turingmaschinenaktionen:Turingmaschinenaktionen:

R ein Feld nach rechts

L ein Feld nach links

S stopp

Zustandsübergang:Zustandsübergang:

a ; b ; R

Geschriebenes Zeichen

Aktion

Gelesenes Zeichen

46

KB

Bere

chen

bark

eitBeispielBeispiel

Turingmaschine (dargestellt mit einem Zustandsgraphen):Turingmaschine (dargestellt mit einem Zustandsgraphen):

AZ:

Berechnungsproblem: Addition von „Strichzahlen“Berechnungsproblem: Addition von „Strichzahlen“

I II II

ZZ: I I I II

z0

S

z0

I; I; R

; I; Rz1

; ; L

I; I; R

z2

I; ; Lz3

; ; R

I; I; L

z4

I; I; S

47

KB

Bere

chen

bark

eitBeispielBeispiel

Turingmaschine (dargestellt mit einem Zustandsgraphen):Turingmaschine (dargestellt mit einem Zustandsgraphen):

z0

I; I; R

; I; Rz1

; ; L

I; I; R

z2

I; ; Lz3

; ; R

I; I; L

z4

I; I; S

Turingmaschine (dargestellt mit einer Zustandstafel):Turingmaschine (dargestellt mit einer Zustandstafel):

alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand

Z0 I I R Z0Z0 ' ' I R Z1

Z1 I I R Z1Z1 ' ' ' ' L Z2

...

48

KB

Bere

chen

bark

eit

PräzisierungPräzisierung

Definition: Eine Turingmaschine ist ein Tupel T = (X, B, b, Z, z0, ) bestehend aus - einer endlichen, nichtleeren Menge X von Eingabezeichen,

- einer Menge B mit X B von Bandzeichen,- einem speziellen Bandzeichen b B \ X („Blank“), - einer endlichen, nichtleeren Menge Z von Zuständen,- einem Anfangszustand z0Z,- einer Überführungsfunktion : Z x B B x {L, R, S} x Z

Definition: Eine Turingmaschine ist ein Tupel T = (X, B, b, Z, z0, ) bestehend aus - einer endlichen, nichtleeren Menge X von Eingabezeichen,

- einer Menge B mit X B von Bandzeichen,- einem speziellen Bandzeichen b B \ X („Blank“), - einer endlichen, nichtleeren Menge Z von Zuständen,- einem Anfangszustand z0Z,- einer Überführungsfunktion : Z x B B x {L, R, S} x Z

alter gelesenes geschrieb. Kopf- neuer Zustand Zeichen Zeichen bewegung Zustand

Z0 I I R Z0Z0 ' ' I R Z1

Z1 I I R Z1Z1 ' ' ' ' L Z2

...

49

KB

Bere

chen

bark

eitÜbungÜbung

AZ:

Berechnungsproblem: Verdopplung von „Strichzahlen“Berechnungsproblem: Verdopplung von „Strichzahlen“

II

ZZ: I I II

z0

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.

50

KB

Bere

chen

bark

eit

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.

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.



II

z0

II II

51

KB

Bere

chen

bark

eit

Variation der TuringmaschineVariation der Turingmaschine

AZ: I I II

ZZ: I I II

z0

I I II I I II


z0

I ;II;RR

; ;LSz1

; ;RS

I ;I ;LS

z2

; ;SSz3

I ;II;RR

2-Band-Turingmaschine

52

KB

Bere

chen

bark

eit

Variation der TuringmaschineVariation der Turingmaschine


2-dimensionale Turingmaschine

53

KB

Bere

chen

bark

eit

Kara als Variation der TuringmaschineKara als Variation der Turingmaschine

2-dimensionale Turingmaschine

Kara

54

KB

Bere

chen

bark

eitÜbungÜbung

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

55

KB

Bere

chen

bark

eit

Äquivalenz von Äquivalenz von TuringmaschinenmodellenTuringmaschinenmodellen

Satz

Eine Funktion f: N x N x ... x N N ist mit einer Ein-Band-Turingmaschine berechenbar

gdw

sie mit einer Zwei-Band-Turingmaschine berechenbar ist

gdw

sie mit einer Mehr-Band-Turingmaschine berechenbar ist.

Satz

Eine Funktion f: N x N x ... x N N ist mit einer Ein-Band-Turingmaschine berechenbar

gdw

sie mit einer Zwei-Band-Turingmaschine berechenbar ist

gdw

sie mit einer Mehr-Band-Turingmaschine berechenbar ist.

Problem Problem

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

56

KB

Bere

chen

bark

eit

BeweisideeBeweisidee

z0

I II

I

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

z0

I II

I I*I *

I I*I *I

zi

zj

Vgl.: U. Mayr: Theoretische Informatik am PC. (Programm: Bsp-a5.tm)

57

KB

Bere

chen

bark

eit

Äquivalenz der Äquivalenz der TuringmaschinenmodelleTuringmaschinenmodelle

Satz

Eine Funktion f: N x N x ... x N N ist mit einer eindimensionalen (Ein-Band-) Turingmaschine berechenbar

gdw

sie mit einer zweidimensionalen Turingmaschine berechenbar ist.

Satz

Eine Funktion f: N x N x ... x N N ist mit einer eindimensionalen (Ein-Band-) Turingmaschine berechenbar

gdw

sie mit einer zweidimensionalen Turingmaschine berechenbar ist.

Problem Problem

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

58

KB

Bere

chen

bark

eit

59

KB

Bere

chen

bark

eit

Teil 5 Teil 5

Universelle Turingmaschine

60

KB

Bere

chen

bark

eit

Universelle BerechnungsmodelleUniverselle Berechnungsmodelle

Computer sind programmierbar! Computer sind programmierbar!

Daten

Programm

Daten

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.

Computer alsprogrammierbar

esSystem

61

KB

Bere

chen

bark

eit

Universelle TuringmaschineUniverselle TuringmaschineUniverselle Turingmaschine als Turingmaschinen-InterpreterUniverselle Turingmaschine als Turingmaschinen-Interpreter

Eingabeband

Turingmaschine

Ausgabeband

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.

UniverselleTuringmaschine

62

KB

Bere

chen

bark

eit

Universelle TuringmaschineUniverselle Turingmaschine

Beispiel: Invertieren einer 01-ZeichenketteBeispiel: Invertieren einer 01-Zeichenkette

10110111#

01001000#

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.

UniverselleTuringmaschine

z1

1;0;R0;1;R

#;#;Sz0

63

KB

Bere

chen

bark

eit

Universelle TuringmaschineUniverselle TuringmaschineSimulation von Ein-Band-Turingmaschinen mit einer univers. TMSimulation von Ein-Band-Turingmaschinen mit einer univers. TM

Kodierung der TM

Ein-/Ausgabeband

Vgl.: Turingkara – Aufgaben: Die universelle Turingmaschine

Aktueller Zustand

z1

1;0;R0;1;R

#;#;Sz0

64

KB

Bere

chen

bark

eit

Universelle TuringmaschineUniverselle TuringmaschineSimulation von Ein-Band-Turingmaschinen mit einer univers. TM.Simulation von Ein-Band-Turingmaschinen mit einer univers. TM.

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

0 R I1 * I * ...

I

1 0 #

10#

z0

1;0;R0;1;R

#;#;Sz1

Ein-/Ausgabe-BandAktueller Zustand

Kodierung der Turing-Tafel

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

65

KB

Bere

chen

bark

eitÜbungÜ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.

66

KB

Bere

chen

bark

eit

Universelle TuringmaschineUniverselle Turingmaschine

SatzEs gibt universelle Turingmaschinen.SatzEs gibt universelle Turingmaschinen.

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.

67

KB

Bere

chen

bark

eit

Teil 6Teil 6

Registermaschinen

68

KB

Bere

chen

bark

eit

Präzisierung des Algorithmusbegriffs Präzisierung des Algorithmusbegriffs


Eingaben

Ausgaben



Maschinenorientierte Ansätze:

- Kara („mehr als ein Spielzeug“)

- Turingmaschine („abstraktes Rechnermodell“)

- Registermaschine („an realen Rechnern orientiertes Modell“)

69

KB

Bere

chen

bark

eit

Berechnungsmodell Berechnungsmodell „Registermaschine“„Registermaschine“

An realen Rechnern orientiertes Berechnungsmodell An realen Rechnern orientiertes Berechnungsmodell

0 JMP 4 1 DEC 1 2 INC 0 3 INC 2 4 TST 1> 5 JMP 1 6 JMP 10 7 DEC 2 8 INC 0 9 TST 2 10 JMP 7 11 HLT

0: 01: 52: 03: 04: 0..

Speicher (Registern)

RegisterAdresse BefehlProgr.zähler


70

KB

Bere

chen

bark

eit

RegistermaschinenbefehleRegistermaschinenbefehle

> x INC i Erhöhe Register i um 1.Gehe zu Zeile x+1.

> x DEC i Erniedrige Register i um 1.Gehe zu Zeile x+1.

> x JMP i Gehe zu Zeile i.

> x TST iWenn Register i ungleich 0 ist, dann gehe zu Zeile x+1, sonst zu Zeile x+2.

> x HLT Beende die Bearbeitung.

71

KB

Bere

chen

bark

eit

Registermaschine in AktionRegistermaschine in Aktion> 0 JMP 4 1 DEC 1 2 INC 0 3 INC 2 4 TST 1 5 JMP 1 6 JMP 10

7 DEC 2 8 INC 0 9 TST 2 10 JMP 7 11 HLT

0: 01: 52: 03: 04: 0..

0 JMP 4 1 DEC 1 2 INC 0 3 INC 2> 4 TST 1 5 JMP 1 6 JMP 10


0: 01: 52: 03: 04: 0..

0 JMP 4 1 DEC 1 2 INC 0 3 INC 2 4 TST 1> 5 JMP 1 6 JMP 10


0: 01: 52: 03: 04: 0..

0 JMP 4> 1 DEC 1 2 INC 0 3 INC 2 4 TST 1 5 JMP 1 6 JMP 10


0: 01: 52: 03: 04: 0..

72

KB

Bere

chen

bark

eit

VerhaltensbeschreibungVerhaltensbeschreibung

0: 01: n2: 03: 04: 0..

Zustand vorher

RM-Programm

0: 2n1: 02: 03: 04: 0..

Zustand nachher

Die Registermaschine berechnet die Verdopplungsfunktion auf natürlichen Zahlen, d. h.:

f: N N mit f(n) = 2n

> 0 JMP 4 1 DEC 1 2 INC 0 3 INC 2 4 TST 1 5 JMP 1 6 JMP 10 7 DEC 2 8 INC 0 9 TST 2 10 JMP 7 11 HLT

73

KB

Bere

chen

bark

eit

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.

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.



0 n 0 0 ...

... ...f(n)

... ...

74

KB

Bere

chen

bark

eit

ÄquivalenzsatzÄquivalenzsatz

SatzEine Funktion f: N x N x ... x N N ist Turingmaschinen-berechenbar gdw sie Registermaschinen-berechenbar ist.

SatzEine Funktion f: N x N x ... x N N ist Turingmaschinen-berechenbar gdw sie Registermaschinen-berechenbar ist.

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.

75

KB

Bere

chen

bark

eit

Teil 7 Teil 7

LOOP- und WHILE-Programme

76

KB

Bere

chen

bark

eit

Präzisierung des Algorithmusbegriffs Präzisierung des Algorithmusbegriffs


Eingaben

Ausgaben



Anweisungsorientierte Ansätze:

- Die Programmiersprache „LOOP“

- Die Programmiersprache „WHILE“

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

77

KB

Bere

chen

bark

eit

LOOP-Programme LOOP-Programme

Bestandteile von LOOP-ProgrammenBestandteile von LOOP-Programmen

Variablen: x0 x1 x2 ...

Konstanten: 0 1 2 ...

Trennsymbole: ; :=

Operatoren: + -

Schlüsselwörter: LOOP DO END

Jede Wertzuweisung der Form xi := c oder xi := xj oder xi := xj + 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 xi DO P END ein LOOP-Programm.

Aufbau eines LOOP-ProgrammsAufbau eines LOOP-Programms

78

KB

Bere

chen

bark

eit

LOOP-Programme LOOP-Programme

Ausführung der LOOP-AnweisungAusführung der LOOP-Anweisung

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

x0 := x1;

LOOP x2 DO x0 := x0 + 1 END

Beispiel eines LOOP-ProgrammsBeispiel eines LOOP-Programms

{x0: [...]; x1: [5]; x2: [3]; x3: [...]; ... }

x0 := x1;

LOOP x2 DO x0 := x0 + 1 END

{x0: [8]; x1: [5]; x2: [3]; x3: [...]; ... }

Bedeutung eines LOOP-ProgrammsBedeutung eines LOOP-Programms

Das Programm berechnet die Additionsfunktion auf natürlichen Zahlen: f(m, n) = m + n

79

KB

Bere

chen

bark

eit

WHILE-Programme WHILE-Programme

Bestandteile von WHILE-ProgrammenBestandteile von WHILE-Programmen

Variablen: x0 x1 x2 ...

Konstanten: 0 1 2 ...

Trennsymbole: ; :=

Operatoren: + -

Schlüsselwörter: WHILE DO END

Jede Wertzuweisung der Form xi := c oder xi := xj oder xi := xj + 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 xi 0 DO P END ein WHILE-Programm.

Aufbau eines WHILE-ProgrammsAufbau eines WHILE-Programms

80

KB

Bere

chen

bark

eit

WHILE-Programme WHILE-Programme

Ausführung der WHILE-AnweisungAusführung der WHILE-Anweisung

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

x0 := x1;

WHILE x2 0 DO x0 := x0 + 1; x2 := x2 - 1 END

Beispiel eines WHILE-ProgrammsBeispiel eines WHILE-Programms

{x0: [0]; x1: [5]; x2: [3]; x3: [0]; ... }

x0 := x1;

WHILE x2 0 DO x0 := x0 + 1; x2 := x2 - 1 END

{x0: [8]; x1: [5]; x2: [0]; x3: [0]; ... }

Bedeutung eines WHILE-ProgrammsBedeutung eines WHILE-Programms

Das Programm berechnet die Additionsfunktion auf natürlichen Zahlen: f(m, n) = m + n

81

KB

Bere

chen

bark

eit

Definition: Eine Funktion f: N N heißt LOOP-/WHILE-berechenbar, gdw gilt: Es gibt ein LOOP-/WHILE-Programm mit der Eigenschaft:

AZ: Die Variable x1 enthält den Ausgangswert:

{x0: [0]; x1: [n]; x2: [0]; x3: [0]; ... }

ZZ: Fall 1: f(n) ist definiert:Die Ausführung des Programms endet und x0 enthält

den Ergebniswert.

{x0: [f(n)]; x1: [...]; x2: [...]; x3: [...]; ... }

Fall 2: f(n) ist undefiniert:Die Ausführung des Programms endet nicht.

Definition: Eine Funktion f: N N heißt LOOP-/WHILE-berechenbar, gdw gilt: Es gibt ein LOOP-/WHILE-Programm mit der Eigenschaft:

AZ: Die Variable x1 enthält den Ausgangswert:

{x0: [0]; x1: [n]; x2: [0]; x3: [0]; ... }

ZZ: Fall 1: f(n) ist definiert:Die Ausführung des Programms endet und x0 enthält

den Ergebniswert.

{x0: [f(n)]; x1: [...]; x2: [...]; x3: [...]; ... }

Fall 2: f(n) ist undefiniert:Die Ausführung des Programms endet nicht.



82

KB

Bere

chen

bark

eitÜbung Übung

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

Aufgabe 2Welche Funktion wird durch das folgende WHILE-Programm berechnet?

x0 := x1;

WHILE x2 0 DO x0 := x0 + 1 END

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

83

KB

Bere

chen

bark

eit

Unterschied LOOP-WHILEUnterschied LOOP-WHILE

Die Ausführung jedes LOOP-Programms endet immer. Ein WHILE-Programm kann dagegen eine Endlosschleife enthalten.

Unterschied: LOOP-berechenbar - WHILE-berechenbarUnterschied: LOOP-berechenbar - WHILE-berechenbar

x0 := x1;

WHILE x2 0 DO x0 := x0 + 1 END

SatzEs gibt Funktionen f: N x N x ... x N N, die WHILE-berechenbar, aber nicht LOOP-berechenbar sind.

SatzEs gibt Funktionen f: N x N x ... x N N, die WHILE-berechenbar, aber nicht LOOP-berechenbar sind.

Das gezeigte WHILE-Programm berechnet die Funktion f: N N mit f(m, n) = IF(n=0, m, ).

84

KB

Bere

chen

bark

eit


SatzEine Funktion f: N x N x ... x N N ist WHILE-berechenbar gdw sie Registermaschinen-berechenbar ist.

SatzEine Funktion f: N x N x ... x N N ist WHILE-berechenbar gdw sie Registermaschinen-berechenbar ist.

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.

85

KB

Bere

chen

bark

eit

Teil 8 Teil 8

Rekursive Funktionen

86

KB

Bere

chen

bark

eit

Rekursive FunktionenRekursive Funktionen



Eingaben

Ausgaben

Grundidee: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.

87

KB

Bere

chen

bark

eit

Rekursives BerechnungsschemaRekursives Berechnungsschema

Beispiel: Addition natürlicher ZahlenBeispiel: Addition natürlicher Zahlen

add(x,0) = x

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

Bemerkungen: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.

88

KB

Bere

chen

bark

eit

Rekursives BerechnungsschemaRekursives Berechnungsschema

Beispiel: Addition natürlicher ZahlenBeispiel: Addition natürlicher Zahlen

add(x,0) = x


Berechnung rekursiv festgelegter FunktionenBerechnung rekursiv festgelegter Funktionen

add(3,2)

= s(add(3,1))

= s(s(add(3,0)))

= s(s(3))

= s(4)

= 5

>add(3,2)

>add(3,1)

>add(3,0)

<add(3,0)=3

<add(3,1)=4

<add(3,2)=5

89

KB

Bere

chen

bark

eitÜbungÜbung

Entwickeln Sie rekursive Berechnungsschemata für die folgenden Funktionen. Benutzen Sie nur die vorgegebene Nachfolgerfunktion s und bereits definierte Funktionen (wie add). mult(x, y) Beschreibt die übliche Multiplikation

natürlicher Zahlen

fakt(x) Beschreibt die Fakultätsfunktion:f(0) = 1, f(1) = 1, f(2) = 2*1, f(3) = 3*2*1, ...

exp(x, y) Beschreibt die Potenzbildung für natürliche Zahlen, d. h.:exp(2, 3) = 23

90

KB

Bere

chen

bark

eitÜbungÜbung

Untersuchen Sie die folgenden rekursiven Berechnungsschemata und beschreiben Sie die jeweils berechneten Funktionen.test(0)=1test(s(x))=0

pred(0)=0pred(s(x))=x

subtr(x,0)=xsubtr(x,s(y))=pred(subtr(x,y))

absdiff(x,y)=add(subtr(x,y),subtr(y,x))

equal(x,y)=test(absdiff(x,y))

91

KB

Bere

chen

bark

eitÜbungÜbung

Welche Berechnungsschemata sind korrekt, sinnvoll?

subtr2(x, 0) = xsubtr2(0, y) = ysubtr2(s(x), s(y)) = subtr2(x, y)

subtr3(x, 0) = xsubtr3(0, y) = ysubtr3(x, y) = subtr3(s(x), s(y))

add2(x, 0) = xadd2(x,y)= add(s(x),pred(y)))

92

KB

Bere

chen

bark

eit

Primitive RekursionPrimitive Rekursion

Rekursive Problemreduktionen:Rekursive Problemreduktionen:


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:Primitives Reduktionsschema:


f(x1,...,xn,s(y)) = h(x1,...,xn,y,f(x1,...,xn,y))

In einem Schritt wird nur ein Argument um 1 reduziert.

93

KB

Bere

chen

bark

eit

Primitive RekursionPrimitive Rekursion

Primitives Reduktionsschema:Primitives Reduktionsschema:

add(x,0) = x


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.

FormalisierungFormalisierung

f(x1,...,xn,0) = g(x1,...,xn)

f(x1,...,xn,s(y)) = h(x1,...,xn,y,f(x1,...,xn,y))

94

KB

Bere

chen

bark

eit

Primitiv rekursive FunktionenPrimitiv rekursive Funktionen

SatzDie folgenden Funktionen sind primitiv rekursiv:• f(m, n) = m + n• f(m, n) = IF(mn, m-n, 0)• f(m, n) = mn• ...

SatzDie folgenden Funktionen sind primitiv rekursiv:• f(m, n) = m + n• f(m, n) = IF(mn, m-n, 0)• f(m, n) = mn• ...

Definition: Eine Funktion f: N x ... x N N heißt primitiv rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition und primitiver Rekursion als Konstruktionsoperationen berechnen.

Definition: Eine Funktion f: N x ... x N N heißt primitiv rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition und primitiver Rekursion als Konstruktionsoperationen berechnen.

95

KB

Bere

chen

bark

eitÜbungÜbung

Ack(0,y)=s(y)

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

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

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?

96

KB

Bere

chen

bark

eit

AckermannfunktionAckermannfunktion

Rekursive Definition: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))

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.

SatzDie Ackermann-Funktion ist nicht primitiv rekursiv.SatzDie Ackermann-Funktion ist nicht primitiv rekursiv.

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

97

KB

Bere

chen

bark

eitÜbungÜbung

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

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

98

KB

Bere

chen

bark

eit

Definition: Eine Funktion f: N x ... x N N heißt partiell rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition, primitiver Rekursion und dem „das kleinste“-Operator als Konstruktionsoperationen berechnen.

Definition: Eine Funktion f: N x ... x N N heißt partiell rekursiv, gdw gilt: Die Funktion f lässt sich mit Hilfe der Nachfolgerfunktion s als Grundfunktion sowie Funktionskomposition, primitiver Rekursion und dem „das kleinste“-Operator als Konstruktionsoperationen berechnen.

Partiell rekursive FunktionenPartiell rekursive Funktionen

Beweis: siehe Fachliteratur

SatzDie Ackermann-Funktion ist partiell rekursiv.SatzDie Ackermann-Funktion ist partiell rekursiv.

99

KB

Bere

chen

bark

eit


Satz

Eine Funktion f: N x N x ... x N N ist primitiv rekursiv gdw sie LOOP-berechenbar ist.

Eine Funktion f: N x N x ... x N N ist partiell rekursiv gdw sie WHILE-berechenbar ist.

Satz

Eine Funktion f: N x N x ... x N N ist primitiv rekursiv gdw sie LOOP-berechenbar ist.

Eine Funktion f: N x N x ... x N N ist partiell rekursiv gdw sie WHILE-berechenbar ist.

Beweis: siehe Fachliteratur

100

KB

Bere

chen

bark

eit

101

KB

Bere

chen

bark

eit

Teil 9 Teil 9

Church-Turing-These

102

KB

Bere

chen

bark

eit

BerechnungsmodelleBerechnungsmodelle



Eingaben

Ausgaben


Maschinenorientierter Ansatz: Turingmaschine, Registermaschine

Zuordnungsorientierter Ansatz: partiell rekursive Funktion

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

103

KB

Bere

chen

bark

eit


Satz

Gegeben ist eine Funktion f: N x N x ... x N N. Die folgenden Aussagen sind äquivalent:

- f ist Turingmaschinen-berechenbar.

- f ist Registermaschinen-berechenbar.

- f ist WHILE-berechenbar,

- f ist partiell rekursiv.

- f ist Pascal-berechenbar.

- ...

Satz

Gegeben ist eine Funktion f: N x N x ... x N N. Die folgenden Aussagen sind äquivalent:

- f ist Turingmaschinen-berechenbar.

- f ist Registermaschinen-berechenbar.

- f ist WHILE-berechenbar,

- f ist partiell rekursiv.

- f ist Pascal-berechenbar.

- ...

Bem.:

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

104

KB

Bere

chen

bark

eit

Church-Turing-TheseChurch-Turing-TheseThese

Die Klasse der im intuitiven Sinn berechenbaren Funktion ist genau die Klasse der Turingmaschinen-berechenbaren Funktionen bzw. die Klasse der partiell rekursiven Funktionen bzw. die Klasse der WHILE-berechenbaren Funktionen bzw. ...

These

Die Klasse der im intuitiven Sinn berechenbaren Funktion ist genau die Klasse der Turingmaschinen-berechenbaren Funktionen bzw. die Klasse der partiell rekursiven Funktionen bzw. die Klasse der WHILE-berechenbaren Funktionen bzw. ...

105

KB

Bere

chen

bark

eit

LiteraturhinweiseLiteraturhinweise

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.

Documents

Berechenbarkeit Klaus Becker 2004. KB Berechenbarkeit 2 Die Möglichkeiten von Software Geben Sie einem Computer die richtige Software, und er wird tun,