Grenzen der Berechenbarkeit Klaus Becker 2004. KB Grenzen der Berechenbarkeit 2 Die Möglichkeiten von Software Geben Sie einem Computer die richtige Software,

Grenzen der BerechenbarkeitGrenzen der Berechenbarkeit

Klaus Becker2004

2

KB

Gre

nze

n d

er

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

Gre

nze

n d

er

Bere

chen

bark

eit

Teil 1 Teil 1

Nicht-berechenbare Funktionen

4

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das ProblemDas Problem

Ist jede Funktion f: N N auch berechenbar?Ist jede Funktion f: N N auch berechenbar?

Menge der Funktionen von N nach N

Menge der berechenbaren

Funktionen von N nach N

?

?

n 2n

n s(n)

n prim(n)

5

KB

Gre

nze

n d

er

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.

Präzisierung von BerechenbarkeitPräzisierung von Berechenbarkeit

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

II

z0

II II

6

KB

Gre

nze

n d

er

Bere

chen

bark

eit

AbzählverfahrenAbzählverfahrenTuringmaschinen kann man abzählen (d. h. durchnummerieren).Turingmaschinen kann man abzählen (d. h. durchnummerieren).

Es gibt nur endlich viele Turingmaschinen mit 1 Zustand. Diese können der Reihe nach abgezählt werden.

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000

Z000 ' ' 'I' L Z000Z000 'I' ' ' L Z000

...

0

1

2

3

4

7

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

Ergänzen Sie die begonnene Abzählung um weitere Turing-maschinen mit genau einem Zustand. Wie viele gibt es insgesamt?

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000

Z000 ' ' 'I' L Z000Z000 'I' ' ' L Z000

0

1

2

3

4

8

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

9

KB

Gre

nze

n d

er

Bere

chen

bark

eit

AbzählverfahrenAbzählverfahren

Turingmaschinen kann man abzählen.Turingmaschinen kann man abzählen.

Es gibt nur endlich viele Turingmaschinen mit 2 Zuständen. Diese können ebenfalls der Reihe nach abgezählt werden.

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' R Z000

...

0

10

KB

Gre

nze

n d

er

Bere

chen

bark

eit


Turingmaschinen kann man abzählen.Turingmaschinen kann man abzählen.

Die gesamte Menge der Turingmaschinen kann abgezählt werden, indem man zunächst die mit 1 Zustand durchnummeriert, dann die mit 2 Zuständen u.s.w..

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

...

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' R Z000

...

0

1

..

36

11

KB

Gre

nze

n d

er

Bere

chen

bark

eit

AbzählbarkeitAbzählbarkeit

D. h., die Elemente von M können durchnummeriert werden. Alle Elemente aus M müssen bei der Nummerierung erfasst werden. Wiederholungen sind bei der Nummerierung zugelassen.

SatzDie Menge der Turingmaschinen (über dem Eingabealphabet {'I'}) ist abzählbar.

SatzDie Menge der Turingmaschinen (über dem Eingabealphabet {'I'}) ist abzählbar.

D. h., die Turingmaschinen lassen sich durchnummerieren:

T0; T1; T2; ...

Definition: Eine Menge M heißt abzählbar genau dann, wenn es eine Abbildung von den natürlichen Zahlen N in M gibt, bei der alle Elemente aus M als Bildelemente natürlicher Zahlen erfasst werden.

Definition: Eine Menge M heißt abzählbar genau dann, wenn es eine Abbildung von den natürlichen Zahlen N in M gibt, bei der alle Elemente aus M als Bildelemente natürlicher Zahlen erfasst werden.

12

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

Überprüfen Sie, ob die aufgelisteten Turingmaschinen Funktionen f: N N berechnen. Wenn ja, welche?

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000

...

Z000 ' ' ' ' R Z000Z000 'I' 'I' R Z001Z001 ' ' ' ' R Z000Z001 'I' ' ' S Z000

0

1

2

3

..

x

13

KB

Gre

nze

n d

er

Bere

chen

bark

eit

LösungLösung

Überprüfen Sie, ob die aufgelisteten Turingmaschinen Funktionen f: N N berechnen. Wenn ja, welche?

f: n

f: n

f: 0 0 n n-1 (n > 0)

f: n

...

Keine Funktion

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

Z000 ' ' 'I' R Z000Z000 'I' ' ' R Z000

...


0

1

2

3

..

x

14

KB

Gre

nze

n d

er

Bere

chen

bark

eit


Berechenbare Funktionen kann man abzählen.Berechenbare Funktionen kann man abzählen.

Wir streichen all die Turingmaschinen, die keine Funktion f: N N berechnen. Die verbleibenden Turingmaschinen entsprechen genau den Turing-berechenbaren Funktionen.

f0: n

f1: n

f2: 0 0 n n-1 (n > 0)

...

Keine Funktion

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

...


0

1

2

..

x

15

KB

Gre

nze

n d

er

Bere

chen

bark

eit


f0: n

f1: n

f2: 0 0 n n-1 (n > 0)

...

Keine Funktion

Z000 ' ' ' ' R Z000Z000 'I' ' ' R Z000

Z000 ' ' ' ' L Z000Z000 'I' ' ' L Z000

Z000 ' ' ' ' S Z000Z000 'I' ' ' S Z000

...


0

1

2

..

x

SatzDie Menge der Turingmaschinen-berechenbaren Funktion f: N N ist abzählbar.

SatzDie Menge der Turingmaschinen-berechenbaren Funktion f: N N ist abzählbar.

16

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ZwischenstandZwischenstand

Die Menge der berechenbaren Funktionen ist abzählbar.Die Menge der berechenbaren Funktionen ist abzählbar.




?

?

f0, f1, f2, f3, ...

17

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Existenz nicht-berechenbarer Existenz nicht-berechenbarer FunktionenFunktionen

Definition einer neuen Funktion f: N NDefinition einer neuen Funktion f: N N

f(0) = f0(0)+1, falls f0(0) definiert ist, sonst f(0) = 0




...

f(n) = fn(n)+1, falls fn(n) definiert ist, sonst f(n) = 0

...

f f0

f f1

f f2

f f3

...

f f0

...

Die Funktion f: N N unterscheidet sich von allen berechenbaren Funktionen, kann also selbst nicht berechenbar sein.

Die Funktion f: N N unterscheidet sich von allen berechenbaren Funktionen, kann also selbst nicht berechenbar sein.

18

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Existenz nicht-berechenbarer Existenz nicht-berechenbarer FunktionenFunktionen

SatzEs gibt Funktionen f: N N, die nicht (Turingmaschinen-) berechenbar sind.

SatzEs gibt Funktionen f: N N, die nicht (Turingmaschinen-) berechenbar sind.




f

?

f0, f1, f2, f3, ...

19

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Teil 2 Teil 2

Rado´sche Sigma-Funktion

20

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Geht es auch konkreter?Geht es auch konkreter?

Ziel ist es, eine Funktion, die nicht berechenbar ist, expliziter zu beschreiben. Ziel ist es, eine Funktion, die nicht berechenbar ist, expliziter zu beschreiben.




?

f0, f1, f2, f3, ...

Rado´sche -Funktion

21

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Biber-TuringmaschinenBiber-Turingmaschinen

Eine Biber-TM ist eine eindimensionale TM, die in jedem Arbeitsschritt genau eine Rechts- oder Linksbewegung macht und nur einen „Baumstamm“ erzeugt.

Eine Biber-TM startet in einer leeren Welt, erzeugt „Baumstämme“ und hält nach endlich vielen Arbeitsschritten.

Vorher:

Nachher:

Biber-TM:

22

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

Gesucht ist eine Biber-TM mit genau 2 Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme erzeugt, bevor sie hält. Eine solche TM heißt „fleißiger Biber“ (mit 2 Zuständen) bzw. „busy beaver TM“.

Biber-Wettbewerb: Biber-Wettbewerb:

Gesucht ist eine Biber-TM mit genau 3 (bzw. 4) Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme erzeugt, bevor sie hält. Eine solche TM heißt „fleißiger Biber“ (mit 3 bzw. 4 Zuständen) bzw. „busy beaver TM“.

23

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Fleißige BiberFleißige Biber

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

Z0 I I L Z1Z0 ' ' I R Z1

Z1 I I S Z0Z1 ' ' I L Z0

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

Z0 I I L Z2Z0 ' ' I R Z1

Z1 I I S Z1Z1 ' ' I L Z0

Z2 I I S Z2Z2 ' ' I L Z1

Fleißiger Biber mit 2 Zuständen: Fleißiger Biber mit 2 Zuständen:

Fleißiger Biber mit 3 Zuständen: Fleißiger Biber mit 3 Zuständen:

24

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Definition (Tibor Rado, 1962): Die Funktion : N N ist wie folgt festgelegt: (n) bezeichne die maximale Anzahl von Baumstämmen, die eine Biber-TM mit genau n Zuständen (außer dem Stop-Zustand) erzeugen kann.

Definition (Tibor Rado, 1962): Die Funktion : N N ist wie folgt festgelegt: (n) bezeichne die maximale Anzahl von Baumstämmen, die eine Biber-TM mit genau n Zuständen (außer dem Stop-Zustand) erzeugen kann.

Rado´sche Sigma-FunktionRado´sche Sigma-Funktion

n

0

1

2

3

4

5

6

...

(n)

0

1

4

6

13

4098

1,2910865

...

25

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Rado´sche Sigma-FunktionRado´sche Sigma-FunktionSatzDie Rado´sche -Funktion ist nicht Turingmaschinen-berechenbar.

SatzDie Rado´sche -Funktion ist nicht Turingmaschinen-berechenbar.

Beweis:

Der Beweis benutzt die folgenden (leicht zu zeigenden) Eigenschaften der -Funktion:

(n) n für alle n N,

(n) < (n+1) für alle n N (Monotonie von ).

Der Beweis wird durch Widerspruch geführt. Annahme: Es gibt eine Turingmaschine T, mit der berechnet werden kann. Die Anzahl der Zustände von T bezeichnen wir mit k.AZ: II

ZZ: I I II

z0T :

26

KB

Gre

nze

n d

er

Bere

chen

bark

eit


Man zeigt zunächst, dass es eine Turingmaschine Tn mit n Zuständen gibt, der auf einem leeren Band eine Baumstammreihe mit genau n Baumstämmen erzeugt:

AZ:

ZZ: I I

z0T2:

Man zeigt anschließend, dass es eine Turingmaschine TV mit 5 Zuständen gibt, der eine gegebene, beliebig lange Baumstammreihe verdoppelt:

AZ:

ZZ: I I

z0TV:

II

I I

27

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Tn: erzeugt eine Baumstammreihe der Länge n


Wir verknüpfen die 3 Turingmaschinen jetzt wie folgt zu einer neuen Turingmaschine Tn,V, :

AZ:

ZZ: I I

z0

ZZ: I I

TV: erzeugt eine Baumstammreihe der Länge 2n

I I

ZZ: I I

T : erzeugt eine Baumstammreihe der Länge (2n)

I I II I I ...

Beachte: Tn,V, hat n+5+k Zustände und erzeugt eine Baumstammreihe der Länge (2n).

28

KB

Gre

nze

n d

er

Bere

chen

bark

eit


Wir vergleichen jetzt diese zusammengesetzte Turingmaschine Tn,V, mit einem fleißigen Biber TFB(n+5+k) mit n+5+k Zuständen:

Tn,V, hat n+5+k Zustände und erzeugt (2n) Baumstämme.

TFB(n+5+k) hat n+5+k Zustände und erzeugt (n+5+k) Baumst.

Da ein fleißiger Biber die maximal mögliche Anzahl von Baumstämmen erzeugt, gilt (für alle n N): (n+5+k) (2n).

Sei n = 2(5+k). Dann gilt:

n+5+k = 3(5+k)

2n = 4(5+k), also n+5+k < 2n.

Aus der Monotonie von folgt: (n+5+k) < (2n).

Es ergibt sich also ein Widerspruch. Da alle Schlüsse korrekt sind, muss die Annnahme falsch sein.

29

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Teil 2 Teil 2

Entscheidbarkeit

30

KB

Gre

nze

n d

er

Bere

chen

bark

eit

TextverarbeitungsprogrammeTextverarbeitungsprogramme

eingabe: TStringList

ausgabe: string

function verarbeiten(s: TStringList): string

31

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Name des Programms: function verarbeiten(s: TStringList):

string

Ein einfaches BeispielEin einfaches Beispiel

uPunkt:verarbeiten

Text

Mit Hilfe eines Textverarbeitungsprogramms soll entschieden werden, ob ein eingegebener Text mit einem Punkt endet.

Mit Hilfe eines Textverarbeitungsprogramms soll entschieden werden, ob ein eingegebener Text mit einem Punkt endet.

ja, falls der Text mit einem Punkt endet

nein, sonst

32

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Ein einfaches BeispielEin einfaches Beispiel

procedure TForm1.BVerarbeitenClick(Sender: TObject);

var eingabe: TStringList; ausgabe: string;

function verarbeiten(s: TStringList): string; var a: string; h: string; begin h := s.Strings[s.Count-1]; if h[length(h)] = '.' then a := 'ja' else a := 'nein'; result := a; end;

begineingabe := TStringList(MEingabe.Lines);ausgabe := verarbeiten(eingabe);PAusgabe.Caption := ausgabe;end;

33

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das Textverarbeitungsprogramms kann man auch auf den Quelltext des Textverarbeitungsprogramms selbst anwenden.


SelbstanwendungSelbstanwendung

34

KB

Gre

nze

n d

er

Bere

chen

bark

eit

SelbstanwendungSelbstanwendung

uPunkt:verarbeiten

uPunkt.~pas

ja



35

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Hilfe, mein Rechner hängt!Hilfe, mein Rechner hängt!

Jeder hat schon einmal die Erfahrung gemacht, dass der Rechner aus irgendwelchen Gründen nicht mehr reagiert. Die Ursache kann eine Endlosschleife sein.

Jeder hat schon einmal die Erfahrung gemacht, dass der Rechner aus irgendwelchen Gründen nicht mehr reagiert. Die Ursache kann eine Endlosschleife sein.

x0 := x1;

WHILE x2 0 DO x0 := x0 + 1 END

36

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

uWhile1:verarbeiten

Text

ja, falls der Text die Zeichenkette ‘while‘ enthält

nein, sonst

Erstellen Sie ein Textverarbeitungsprogramms, mit dem man entscheiden kann, ob der eingegebene Text die Zeichenkette ‘while‘ enthält.

Erstellen Sie ein Textverarbeitungsprogramms, mit dem man entscheiden kann, ob der eingegebene Text die Zeichenkette ‘while‘ enthält.

37

KB

Gre

nze

n d

er

Bere

chen

bark

eit

ÜbungÜbung

uWhile2:verarbeiten

Text

Gerät in eine Endlosschleife, falls der Text die Zeichenkette ‘while‘ enthält

nein, sonst

Erstellen Sie zunächst ein Textverarbeitungsprogramms, mit dem man entscheiden kann, ob der eingegebene Text die Zeichenkette ‘while‘ enthält. Das Textverarbeitungsprogramm soll mindestens eine while-Schleife enthalten. Ändern Sie es anschließend so ab, dass folgendes Verhalten auftritt:

Erstellen Sie zunächst ein Textverarbeitungsprogramms, mit dem man entscheiden kann, ob der eingegebene Text die Zeichenkette ‘while‘ enthält. Das Textverarbeitungsprogramm soll mindestens eine while-Schleife enthalten. Ändern Sie es anschließend so ab, dass folgendes Verhalten auftritt:

38

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das (spezielle) HalteproblemDas (spezielle) Halteproblem

halten

uProgramm.~pas

ja, falls uProgramm:verarbeiten bei Eingabe von uProgramm.~pas hält

nein, sonst

Kann man eine Funktion programmieren, mit der man entscheiden kann, ob ein Textverarbeitungsprogramm bei der Analyse des eigenen Quelltextes hält?

Kann man eine Funktion programmieren, mit der man entscheiden kann, ob ein Textverarbeitungsprogramm bei der Analyse des eigenen Quelltextes hält?

Annahme: Man kann diese Funktion programmieren. Annahme: Man kann diese Funktion programmieren.

39

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das (spezielle) HalteproblemDas (spezielle) Halteproblem

Annahme: Man kann die Funktion „halten“ programmieren. Dann ergänzen wir das Programm wie folgt:Annahme: Man kann die Funktion „halten“ programmieren. Dann ergänzen wir das Programm wie folgt:

procedure TForm1.BVerarbeitenClick(Sender: TObject); var eingabe: TStringList; ausgabe: string; function halten(s: TStringList): string; begin ... end; function verarbeiten(s: TStringList): string; begin if halten(s)='ja' then while true do; result := 'haelt'; end;begineingabe := TStringList(MEingabe.Lines);ausgabe := verarbeiten(eingabe);PAusgabe.Caption := ausgabe;end;

uSeltsam

40

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Ein seltsames ProgrammEin seltsames Programm

uSeltsam:verarbeiten

uProgramm.~pas

keine Ausgabe, wenn uProgramm:verarbeiten bei Eingabe von uProgramm.~pas hält, da Endlosschleife

‘haelt‘, wenn uProgramm:verarbeiten bei Eingabe von uProgramm.~pas nicht hält

Seltsam dreht den Spieß um.Seltsam dreht den Spieß um.

41

KB

Gre

nze

n d

er

Bere

chen

bark

eit



uSeltsam.~pas

keine Ausgabe, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas hält, da Endlosschleife

‘haelt‘, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas nicht hält

Seltsam analysiert sein eigenes Halteverhalten.Seltsam analysiert sein eigenes Halteverhalten.

42

KB

Gre

nze

n d

er

Bere

chen

bark

eit



uSeltsam.~pas

hält nicht, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas hält

hält, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas nicht hält

Hält uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas? Hält uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas?

Man kann es nicht klären, ohne sich in Widersprüche zu verwickeln.Man kann es nicht klären, ohne sich in Widersprüche zu verwickeln.

43

KB

Gre

nze

n d

er

Bere

chen

bark

eit



uSeltsam.~pas

hält nicht, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas hält

hält, wenn uSeltsam:verarbeiten bei Eingabe von uSeltsam.~pas nicht hält

Die Annahme, dass man eine Funktion programmieren kann, mit der man entscheiden kann, ob ein Textverarbeitungsprogramm bei der Analyse des eigenen Quelltextes hält, muss falsch sein.

Die Annahme, dass man eine Funktion programmieren kann, mit der man entscheiden kann, ob ein Textverarbeitungsprogramm bei der Analyse des eigenen Quelltextes hält, muss falsch sein.

Woran liegt es, dass man widersprüchliche Ergebnissen erhält?Woran liegt es, dass man widersprüchliche Ergebnissen erhält?

44

KB

Gre

nze

n d

er

Bere

chen

bark

eit

EntscheidbarkeitEntscheidbarkeit

Algorithmus

Wort

ja, falls das Wort zur Sprache gehört

nein, falls das Wort nicht zur Sprache gehört

Beachte: Der Algorithmus muss für jede Eingabe halten und eine der beiden Ausgaben ´ja´ bzw. ´nein´ erzeugen. Beachte: Der Algorithmus muss für jede Eingabe halten und eine der beiden Ausgaben ´ja´ bzw. ´nein´ erzeugen.

Definition: Eine Sprache über einem Alphabet heißt (Delphi-) entscheidbar, wenn es einen (Delphi-) Algorithmus gibt, der für jedes Wort über dem Alphabet feststellt, ob es zur Sprache gehört oder nicht.

Definition: Eine Sprache über einem Alphabet heißt (Delphi-) entscheidbar, wenn es einen (Delphi-) Algorithmus gibt, der für jedes Wort über dem Alphabet feststellt, ob es zur Sprache gehört oder nicht.

45

KB

Gre

nze

n d

er

Bere

chen

bark

eit

EntscheidbarkeitEntscheidbarkeit

uWhile:verarbeiten

Text

ja, falls der Text die Zeichenkette ‘while‘ enthält

nein, sonst

Beispiel: Die Sprache der ASCII-Texte, die die Zeichenkette ‘while‘ enthalten, ist (Delphi-) entscheidbar. Beispiel: Die Sprache der ASCII-Texte, die die Zeichenkette ‘while‘ enthalten, ist (Delphi-) entscheidbar.

46

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Unentscheidbarkeit des Halte-ProblemsUnentscheidbarkeit des Halte-Problems

SatzDie Sprache der Delphi-Textverarbeitungsprogramme, die bei Eingabe des eigenen Quelltextes halten, ist nicht (Delphi-) entscheidbar.

SatzDie Sprache der Delphi-Textverarbeitungsprogramme, die bei Eingabe des eigenen Quelltextes halten, ist nicht (Delphi-) entscheidbar.

uProgramm.~pas

ja, falls uProgramm:verarbeiten bei Eingabe von uProgramm.~pas hält

nein, sonst

Kurz: Das spezielle Halteproblem (Hält ein ein Programm, wenn es seinen eigenen Quelltext bearbeitet?) ist nicht entscheidbar.

Kurz: Das spezielle Halteproblem (Hält ein ein Programm, wenn es seinen eigenen Quelltext bearbeitet?) ist nicht entscheidbar.

47

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Unentscheidbarkeit des Halte-ProblemsUnentscheidbarkeit des Halte-Problems

SatzDas allgemeine Halteproblem (Hält ein ein Programm, wenn es Daten bearbeitet?) ist nicht entscheidbar.

SatzDas allgemeine Halteproblem (Hält ein ein Programm, wenn es Daten bearbeitet?) ist nicht entscheidbar.

uProgramm.~pas +Daten

ja, falls uProgramm:verarbeiten bei Eingabe der Daten hält

nein, sonst

Fazit: Es gibt keinen Algorithmus, mit dem man allgemein vorab testen kann, ob ein Programm bei der Verarbeitung von Daten hält.

Fazit: Es gibt keinen Algorithmus, mit dem man allgemein vorab testen kann, ob ein Programm bei der Verarbeitung von Daten hält.

48

KB

Gre

nze

n d

er

Bere

chen

bark

eit

49

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Teil 3 Teil 3

Semi-Entscheidbarkeit

50

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das 10. Hilbert`sche ProblemDas 10. Hilbert`sche Problem

Diophantische Gleichungen:

Hat eine Polynomgleichung (in der verschiedene Variablen mit verschiedenen Exponenten vorkommen können) mit ganzzahligen Koeffizienten eine ganzzahlige Lösung?

Diophantische Gleichungen:

Hat eine Polynomgleichung (in der verschiedene Variablen mit verschiedenen Exponenten vorkommen können) mit ganzzahligen Koeffizienten eine ganzzahlige Lösung?

x3 + 5x2y2z – xz + 37 = 0 ja: x = 1; y = 2; z = -2

x2 +1 = 0 nein!

51

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das 10. Hilbert`sche ProblemDas 10. Hilbert`sche Problem

Polynomgleichung

ja, falls die Polynomgleichung eine ganzzahlige Lösung hat

nein, sonst

SatzDas 10. Hilbertsche Problem (Hat eine Polynomgleichung mit ganzzahligen Koeffizienten eine ganzzahlige Lösung?) ist nicht entscheidbar.

SatzDas 10. Hilbertsche Problem (Hat eine Polynomgleichung mit ganzzahligen Koeffizienten eine ganzzahlige Lösung?) ist nicht entscheidbar.

52

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das 10. Hilbert`sche ProblemDas 10. Hilbert`sche ProblemEin Algorithmus zur Lösung von Diophantischen Gleichungen:Ein Algorithmus zur Lösung von Diophantischen Gleichungen:

Eingabe: Gleichung; z. B.: x3 + 5x2y2z – xz + 37 = 0

Probiere systematisch alle möglichen Belegungen der in der Gleichung vorkommenden Variablen aus, ob sie die Gleichung erfüllen. Stoppe, wenn eine passende Belegung gefunden wurde. Im Beispiel:

x = 0; y = 0; z = 0: neinx = 1; y = 0; z = 0: neinx = -1; y = 0; z = 0 neinx = 0; y = 1; z = 0 nein...x = 1; y = 2; z = -2 ja

Ausgabe: Lösbarkeit; im Beispiel: ja

53

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Semi-EntscheidbarkeitSemi-Entscheidbarkeit

Der Algorithmus zur Lösung von Diophantischen Gleichungen hat folgendes Verhalten:Der Algorithmus zur Lösung von Diophantischen Gleichungen hat folgendes Verhalten:

Beachte: Der Algorithmus liefert nur in den Fällen, in denen eine Lösung existiert, ein positives Ergebnis, in anderen Fällen liefert er kein Ergebnis.

Beachte: Der Algorithmus liefert nur in den Fällen, in denen eine Lösung existiert, ein positives Ergebnis, in anderen Fällen liefert er kein Ergebnis.

Diophantische Gleichung

ja, falls die Gleichung eine ganzzahlige Lösung hat

hält nicht, sonst

54

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Definition: Eine Sprache über einem Alphabet heißt semi-entscheidbar, wenn es einen Algorithmus gibt, der für jedes Wort über dem Alphabet, das zur Sprache gehört, dies auch mitteilt.

Definition: Eine Sprache über einem Alphabet heißt semi-entscheidbar, wenn es einen Algorithmus gibt, der für jedes Wort über dem Alphabet, das zur Sprache gehört, dies auch mitteilt.


Algorithmus

Wort

ja, falls das Wort zur Sprache gehört

hält nicht, falls das Wort nicht zur Sprache gehört

Beachte: Falls der Algorithmus lange Zeit noch nicht gestoppt hat, ist nicht klar, ob das Wort zur Sprache gehört oder nicht.

Beachte: Falls der Algorithmus lange Zeit noch nicht gestoppt hat, ist nicht klar, ob das Wort zur Sprache gehört oder nicht.

55

KB

Gre

nze

n d

er

Bere

chen

bark

eit


SatzEine Sprache L ist entscheidbar genau dann, wenn sowohl L als auch das Komplement von L semi-entscheidbar sind.

SatzEine Sprache L ist entscheidbar genau dann, wenn sowohl L als auch das Komplement von L semi-entscheidbar sind.

Beweis:Die Richtung von links nach rechts ist klar. Für die Umkehrung sei A1 ein Semi-Entscheidungsalgorithmus für L und A2 ein entsprechender Algorithmus für das Komplement von L. Der folgende Algorithmus liefert ein Entscheidungsverfahren:

Eingabe: Wort w

FÜR s = 1, 2, 3, ... TUE

WENN A1 bei Eingabe von w in s Schritten stoppt, DANN Ausgabe: ja

WENN A2 bei Eingabe von w in s Schritten stoppt, DANN Ausgabe: nein

56

KB

Gre

nze

n d

er

Bere

chen

bark

eit

57

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Teil 4 Teil 4

Exkurs in die Geschichte der Informatik

58

KB

Gre

nze

n d

er

Bere

chen

bark

eit

David Hilbert David Hilbert

59

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Hilbert´s Rede auf dem Kongress 1900Hilbert´s Rede auf dem Kongress 1900

Wer von uns würde nicht gern den Schleier lüften, unter dem die Zukunft verborgen liegt, um einen Blick zu werfen auf die bevorstehenden Fortschritte unsrer Wissenschaft und in die Geheimnisse ihrer Entwickelung während der künftigen Jahrhunderte! Welche besonderen Ziele werden es sein, denen die führenden mathematischen Geister der kommenden Geschlechter nachstreben? welche neuen Methoden und neuen Thatsachen werden die neuen Jahrhunderte entdecken - auf dem weiten und reichen Felde mathematischen Denkens?

Die Geschichte lehrt die Stetigkeit der Entwickelung der Wissenschaft. Wir wissen, daß jedes Zeitalter eigene Probleme hat, die das kommende Zeitalter löst oder als unfruchtbar zur Seite schiebt und durch neue Probleme ersetzt. Wollen wir eine Vorstellung gewinnen von der muthmaßlichen Entwickelung mathematischen Wissens in der nächsten Zukunft, so müssen wir die offenen Fragen vor unserem Geiste passiren lassen und die Probleme überschauen, welche die gegenwärtige Wissenschaft stellt, und deren Lösung wir von der Zukunft erwarten. Zu einer solchen Musterung der Probleme scheint mir der heutige Tag, der an der Jahrhundertwende liegt, wohl geeignet; denn die großen Zeitabschnitte fordern uns nicht blos auf zu Rückblicken in die Vergangenheit, sondern sie lenken unsere Gedanken auch auf das unbekannte Bevorstehende. ...

60

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Hilbert´s Rede auf dem Kongress 1900Hilbert´s Rede auf dem Kongress 1900

2. Die Widerspruchslosigkeit der arithmetischen Axiome

Wenn es sich darum handelt, die Grundlagen einer Wissenschaft zu untersuchen, so hat man ein System von Axiomen aufzustellen, welche eine genaue und vollständige Beschreibung derjenigen Beziehungen enthalten, die zwischen den elementaren Begriffen jener Wissenschaft stattfinden. Die aufgestellten Axiome sind zugleich die Definitionen jener elementaren Begriffe und jede Aussage innerhalb des Bereiches der Wissenschaft, deren Grundlagen wir prüfen, gilt uns nur dann als richtig, falls sie sich mittelst einer endlichen Anzahl logischer Schlüsse aus den aufgestellten Axiomen ableiten läßt. Bei näherer Betrachtung entsteht die Frage, ob etwa gewisse Aussagen einzelner Axiome sich untereinander bedingen und ob nicht somit die Axiome noch gemeinsame Bestandteile enthalten, die man beseitigen muß, wenn man zu einem System von Axiomen gelangen will, die völlig von einander unabhängig sind.Vor Allem aber möchte ich unter den zahlreichen Fragen, welche hinsichtlich der Axiome gestellt werden können, dies als das wichtigste Problem bezeichnen, zu beweisen, daß dieselben untereinander widerspruchslos sind, d.h. daß man auf Grund derselben mittelst einer endlichen Anzahl von logischen Schlüssen niemals zu Resultaten gelangen kann, die miteinander in Widerspruch stehen.

61

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Das Hilbert´sche ProgrammDas Hilbert´sche Programm

Widerspruchsfreiheit:Die Formalisierung soll widerspruchsfrei sein (d. h.: keine zwei sich ausschließenden Aussagen können hergeleitet werden).

Vollständigkeit:Jede wahre mathematische Aussage kann hergeleitet werden.

Entscheidbarkeit:Es gibt ein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht.

Ziel: Formalisierung der MathematikZiel: Formalisierung der Mathematik

62

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Kurt GödelKurt Gödel

63

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Ergebnisse von GödelErgebnisse von Gödel

In jedem formalen System, das widerspruchsfrei ist, existieren Aussagen, die wahr sind, aber innerhalb des Systems nicht hergeleitet werden können. Das bedeutet, es bleiben immer wahre Aussagen übrig, die nicht herleitbar sind.

Wenn ein formales System widerspruchsfrei ist, dann kann man innerhalb des Systems nicht herleiten, dass es widerspruchsfrei ist.

Gödelsche Unvollständigkeitssätze (1931)Gödelsche Unvollständigkeitssätze (1931)



Hilbertsche Programm: Formalisierung der MathematikHilbertsche Programm: Formalisierung der Mathematik

64

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Alan TuringAlan Turing

http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Turing.html

65

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Alonzo ChurchAlonzo Church

66

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Präzisierung des AlgorithmusbegriffsPräzisierung des Algorithmusbegriffs

Gibt es ein Verfahren, mit dem man für jede beliebige mathematische Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht?

Mathematische Präzisierung des Begriffs „Verfahren“ bzw. (in heutiger Terminologie) des Begriffs „Algorithmus“

Entscheidungsproblem:Entscheidungsproblem:

Grundlegende Schwierigkeit:Grundlegende Schwierigkeit:

67

KB

Gre

nze

n d

er

Bere

chen

bark

eit

Ergebnis von Turing und ChurchErgebnis von Turing und Church

Es gibt kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht.

Turing und Church (1936)Turing und Church (1936)



Entscheidbarkeit:Es gibt ein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie ableitbar ist oder nicht.

Hilbertsche Programm: Formalisierung der MathematikHilbertsche Programm: Formalisierung der Mathematik

68

KB

Gre

nze

n d

er

Bere

chen

bark

eit

LiteraturhinweiseLiteraturhinweise

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

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

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

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

J. Casti: Das Cambridge Quintett. Berlin Verlag 1998.

D. R. Hofstadter: Gödel, Escher, Bach. Klett-Cotta 1985.

Documents

Grenzen der Berechenbarkeit Klaus Becker 2004. KB Grenzen der Berechenbarkeit 2 Die Möglichkeiten von Software Geben Sie einem Computer die richtige Software,