137
Berechenbarkeit Klaus Becker 2014

Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

Embed Size (px)

Citation preview

Page 1: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

Berechenbarkeit

Klaus Becker

2014

Page 2: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

2 Berechenbarkeit

Page 3: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

3 Teil 1

Das Halteproblem

Page 4: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

4 Frustrierende Erlebnisse

Jeder kennt diese Situation: Man hat ein Programm entwickelt und will es testen. Aber, nichts tut sich, Python liefert kein Ergebnis.

Mein Rechner hat sich schon wieder aufgehängt!

Page 5: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

5 Endlosschleife

Aufgabe 1Findest du den Fehler? Korrigiere ihn und teste dann die Funktion noch einmal.

Aufgabe 2Es gibt typische Fehler, die eine Endlosschleife verursachen. Beschreibe den Fehler, der hier vorliegt.

Aufgabe 3Es ist nicht immer so einfach wie oben, Endlosschleifen direkt am Quelltext zu erkennen. Verdeutliche das mit selbst gewählten Beispielen.

Mein Rechner hat sich schon wieder aufgehängt!

def primzahl(n): if n == 1: prim = False else: prim = True i = 2 while i < n: if n % i == 0: prim = False return prim

Page 6: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

6 Das Halteproblem

Gibt es ein Python-Programm (dargestellt als Python-Funktion), mit dessen Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann?

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

istHaltend

False

"""def primzahl(n): if n == 1: prim = False else: prim = True i = 2 while i < n: if n % i == 0: prim = False return prim"""

daten

quelltext

71

Page 7: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

7 While-Analyse

Vereinfachung des Problems: Getestet werden soll zunächst, ob ein Python-Programm eine while-Anweisung enthält.

falls das Python-Programm eine While-Anweisung enthält,sonst

True

False

Python-Programm

enthaeltWhile

Page 8: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

8 Eine Vereinfachung

Zur Vereinfachung der Programmanalyse betrachten wir nur solche Programme, die sich ganz einfach in ihre Bestandteile (man sagt hier auch Token) zerlegen lassen. Mit Hilfe von Leerzeichen (und Zeilenumbrüchen) sollen hier jeweils alle Programmeinheiten getrennt vorliegen. Man kann auf diese Vereinfachung verzichten, muss dann aber viel mehr Analysearbeit leisten.

def primzahl(n): if n == 1: prim = False else: prim = True i = 2 while i < n: if n % i == 0: prim = False return prim

def primzahl ( n ) : if n == 1 : prim = False else : prim = True i = 2 while i < n : if n % i == 0 : prim = False return prim

Page 9: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

9 Eine Vereinfachung

Mit der split-Funktion kann man jetzt die Bestandteile des vorgegebenen Quelltextes direkt auflisten.

>>> quelltext = """def primzahl ( n ) : if n == 1 : prim = False else : prim = True i = 2 while i < n : if n % i == 0 : prim = False return prim"""

>>> quelltext.split()['def', 'primzahl', '(', 'n', ')', ':', 'if', 'n', '==', '1', ':', 'prim', '=', 'False', 'else', ':', 'prim', '=', 'True', 'i', '=', '2', 'while', 'i', '<', 'n', ':', 'if', 'n', '%', 'i', '==', '0', ':', 'prim', '=', 'False', 'return', 'prim']

Page 10: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

10 Eine Vereinfachung

Aber, Achtung! Es gibt Fälle, bei denen die beschriebene Vorgehensweise nicht zum gewünschten Ergebnis führt. Wir ignorieren diese Fälle hier.

>>> quelltext = """def test ( ) : s = ' while ' return s"""

>>> quelltext.split()['def', 'test', '(', ')', ':', 's', '=', "'", 'while', "'", 'return', 's']>>>

Page 11: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

11 Aufgabe

Ergänze die Funktionsdefinition von enthaeltWhile. Teste die Funktion anschließend mit geeigneten Quelltexten (in Tokenform).

def enthaeltWhile ( quelltext ) : tokenliste = quelltext . split ( ) … return …

# TestquelltextPrimzahl = """def primzahl ( n ) : if n == 1 : prim = False else : prim = True i = 2 while i < n : if n % i == 0 : prim = False return prim"""

print(enthaeltWhile(quelltextPrimzahl))

Page 12: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

12 Aufgabe

Die Funktion enthaeltWhile kann auch ihren eigenen Quelltext analysieren. Probiere das einmal aus.

def enthaeltWhile ( quelltext ) : tokenliste = quelltext . split ( ) … return …

# TestquelltextEnthaeltWhile = """def enthaeltWhile ( quelltext ) : tokenliste = quelltext . split ( ) … return …"""

print(enthaeltWhile(quelltextEnthaeltWhile ))

Versuche, eine Funktion enthaeltRekursion zu entwickeln, die überprüft, ob der Funktionsname in der weiteren Funktionsdefinition noch einmal vorkommt.

Page 13: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

13 Aufgabe

Wie könnte man die Funkton enthaeltWhile zu einer Funktion istHaltend weiterentwickeln? Welche Prüfungen könnte man vorsehen?

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

falls das Python-Programm eine While-Anweisung enthält,sonst

True

False

Python-Programm

enthaeltWhile

Page 14: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

14 Aufgabe

Beurteile den eingeschlagenen Weg, die Existenz von Endlosschleifen über Eigenschaften des Quelltextes herauszufinden. Wie vielversprechend ist dieser Weg?

def naechstePrimzahl(n): gefunden = False while not gefunden: if primzahl(n): gefunden = True else: n = n+1 return n

def naechstesPrimzahlzwillingspaar(n): gefunden = False while not gefunden: if primzahl(n) and primzahl(n+2): gefunden = True else: n = n+1 return (n, n+2)

def naechsteNichtZu6erZahlBenachbartePrimzahl(n): gefunden = False while not gefunden: if primzahl(n) and ((n+1)%6 > 0) and ((n-1)%6 > 0): gefunden = True else: n = n+1 return n

Hält immer - kann aber sehr lange dauern.

Hält für kleine n. Ob dies für alle n gilt, ist nicht bekannt.

Hält außer für 1, 2 und 3 nie.

Page 15: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

15 Ein neuer Weg

Wir überlegen uns Konsequenzen, die sich ergeben würden, wenn wir die gesuchte Funktionsdefinition hätten.

def istHaltend (quelltext, daten): ... return ...

Was wäre, wenn es diese Funktionsdefinition gäbe?

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

Page 16: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

16 Aufgabe

(a) Warum müsste hier der Wert True ausgegeben werden?

# Funktionsdefinitionen

def istHaltend (quelltext, daten): ... return ...

# Funktionsaufruf

quelltextEnthaeltWhile = """def enthaeltWhile ( quelltext ) : tokenliste = quelltext . split ( ) gefunden = False for token in tokenliste : if token == 'while' : gefunden = True return gefunden"""print(istHaltend(quelltextEnthaeltWhile, quelltextEnthaeltWhile))

(b) Konstruiere einen Beispielquelltext, bei dem der Wert False ausgegeben wird, wenn das übergebene Programm den eigenen Quelltext analysiert.

Page 17: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

17 Umkehr des Halteverhaltens

Eine etwas seltsame Funktion:

def umkehrHalteverhalten (quelltext):

def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False

falls das Python-Programm bei der Verarbeitung des eigenen Quelltextes nicht hält,sonst

hält und liefert False

hält nicht

Python-Programm

umkehrHalteverhalten

Page 18: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

18 Aufgabe

(a) Welches Ergebnis erwartest du beim folgenden Beispielaufruf?

# Funktionsdefinitionendef umkehrHalteerhalten(quelltext):

def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False

# FunktionsaufrufquelltextEnthaeltWhile = """def enthaeltWhile ( quelltext ) : tokenliste = quelltext . split ( ) gefunden = False for token in tokenliste : if token == 'while' : gefunden = True return gefunden"""print(umkehrHalteerhalten(quelltextEnthaeltWhile))

Page 19: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

19 Aufgabe

(b) Welches Ergebnis erwartest du beim folgenden Beispielaufruf?

# Funktionsdefinitionen

def umkehrHalteerhalten(quelltext):

def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False

# Funktionsaufruf

quelltextLoop = """def loop (quelltext): while True: pass return True"""print(umkehrHalteerhalten(quelltextLoop))

Page 20: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

# Funktionsdefinitionendef umkehrHalteerhalten(quelltext): def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False# FunktionsaufrufquelltextUmkehrHalteverhalten = """def umkehrHalteerhalten(quelltext): def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False"""print(umkehrHalteerhalten(quelltextUmkehrHalteverhalten))

20 Aufgabe

(c) Und welches Ergebnis ergibt sich hier ???

Page 21: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

21 Lösbarkeit des Halteproblems

Halteproblem:

def istHaltend (quelltext, daten): ... return ...

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

Annahme:

Es gibt eine Python-Funktionsdefinition für die Funktion istHaltend.

Page 22: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

22 Lösbarkeit des Halteproblems

Eine seltsame Funktion zur Umkehrung des Halteverhaltens:

def umkehrHalteverhalten (quelltext):

def istHaltend(quelltext, daten): ... return ...

if istHaltend(quelltext, quelltext) == True: while True: pass else: return False

falls das Python-Programm bei der Verarbeitung des eigenen Quelltextes nicht hält,sonst

hält und liefert False

hält nicht

Quelltext

umkehrHalteverhalten

istHaltend

Quelltext

Quelltext

False

True

Page 23: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

23 Lösbarkeit des Halteproblems

Verarbeitung des eigenen Quelltextes:

# Funktionsdefinitionendef umkehrHalteverhalten(quelltext): def istHaltend(quelltext, daten): ... return ... if istHaltend(quelltext, quelltext) == True: while True: pass else: return False# FunktionsaufrufquelltextUmkehrHalteverhalten = """def umkehrHalteverhalten(quelltext): def istHaltend(quelltext, daten): ... return ... if istHaltend(quelltext, quelltext) == True: while True: pass else: return False"""print(umkehrHalteverhalten(quelltextUmkehrHalteverhalten))

Page 24: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

24 Lösbarkeit des Halteproblems

Fall 1: Wir nehmen an, dass die Funktion umkehrHalteverhalten bei der Verarbeitung des eigenen Quelltextes hält. Dann liefert istHaltend(quelltextUmkehrHalteverhalten, quelltextUmkehrHalteverhalten) den Wert True. Die Funktion umkehrHalteverhalten gerät dann aber in eine Endlosschleife - und hält folglich nicht.

Fall 2: Wir nehmen an, dass die Funktion umkehrHalteverhalten bei der Verarbeitung des eigenen Quelltextes nicht hält. Dann liefert istHaltend(quelltextUmkehrHalteverhalten, quelltextUmkehrHalteverhalten) den Wert False. Die Funktion umkehrHalteverhalten liefert dann ebenfalls das Ergebnis False. Das bedeutet aber, dass die Funktion hält - im Gegensatz zur gemachten Annahme.

In beiden Fällen verwickelt man sich in Widersprüche.

Die Ursache der Widersprüche kann nur in der getroffen Annahme liegen. Die Annahme, dass es eine Funktionsdefinition für die Funktion istHaltend gibt, muss also falsch sein.

umkehrHalteverhalten(quelltextUmkehrHalteverhalten)

Page 25: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

25 Unlösbarkeit des Halteproblems

Gibt es ein Python-Programm (dargestellt als Python-Funktion), mit dessen Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann?

def umkehrHalteverhalten (quelltext):

def istHaltend(quelltext, daten):

...

return ...

if istHaltend(quelltext, quelltext) == True:

while True:

pass

else:

return False

Was wäre, wenn es diese Funktionsdefinition gäbe?

Dann könnte man diese Funktionsdefinition erstellen!

Diese Funktionsdefinition kann es aber nicht geben, weil sich hieraus eine Funktion mit einem widersprüchlichen Verhalten ergeben würde.

Page 26: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

26 Unlösbarkeit des Halteproblems

Satz (über die Lösbarkeit des Halteproblems in Python):

Man kann in Python keine Funktion entwickeln, die bei Übergabe einer beliebigen Python-Funktionsdefinition und eines beliebigen Datentupels entscheidet, ob die betreffende Funktion bei der Verarbeitung der Daten hält oder nicht. Das Halteproblem für Python-Programme ist demnach nicht mit einer Python-Funktion entscheidbar.

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

Keine Funktionsdefinition in Python möglich!

Page 27: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

27 Zur Tragweite des Ergebnisses

In einer Computerzeitschrift hat einmal gestanden: „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.“

Schön wäre es! Es gibt Probleme in der Computerwelt, die so schwierig sind, dass sie die Grenzen des Computer-Machbaren sprengen. Das Halteproblem ist ein Beispiel für ein solches Problem. Es gibt bis jetzt keine Software, mit der man vorweg testen kann, ob ein Programm in eine Endlosschleife gerät, und es wird sie auch nie geben. Informatiker können nachweisen, dass sie nicht in der Lage sind, eine solche Software zu entwickeln. Es liegt dabei nicht am Unvermögen der Informatiker, sondern an den Grenzen der algorithmischen Problemlösemethode.

Diese Tatsache an sich ist auch etwas frustrierend. Aber gut, dass man darüber so genau Bescheid weiß!

Satz (über die Lösbarkeit des Halteproblems in Python):

Man kann in Python keine Funktion entwickeln, die bei Übergabe einer beliebigen Python-Funktionsdefinition und eines beliebigen Datentupels entscheidet, ob die betreffende Funktion bei der Verarbeitung der Daten hält oder nicht. Das Halteproblem für Python-Programme ist demnach nicht mit einer Python-Funktion entscheidbar.

Page 28: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

28 Zur Tragweite des Ergebnisses

Wir haben das Halteproblem speziell für die Programmiersprache Python untersucht und Programme in Form von Python-Funktionsdefinitionen betrachtet.

Das Halteproblem ist damit nur für Python-Programme geklärt. Die folgenden Abschnitte sollen zeigen, wie man algorithmische Lösbarkeit von Problemen (wie z.B. dem Halteproblem) allgemein klärt.

Satz (über die Lösbarkeit des Halteproblems in Python):

Man kann in Python keine Funktion entwickeln, die bei Übergabe einer beliebigen Python-Funktionsdefinition und eines beliebigen Datentupels entscheidet, ob die betreffende Funktion bei der Verarbeitung der Daten hält oder nicht. Das Halteproblem für Python-Programme ist demnach nicht mit einer Python-Funktion entscheidbar.

Page 29: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

29 Teil 2

Exkurs - Lösbarkeit von Problemen

Page 30: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

30 Ein einfaches Problem

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Page 31: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

31 Eine Lösung mit 5 Strecken

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Mit 5 Strecken schafft das jeder.

Page 32: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

32 Eine Lösung mit 4 Strecken

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Mit 4 Strecken ist das schon schwieriger.

Die oben gezeigte Lösung des Neun-Punkte-Problems benutzt einen kleinen "Trick": Der Streckenzug verlässt das vorgegebene Punktegitter.

Page 33: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

33 Eine Lösung mit drei Strecken

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Mit drei Strecken geht das auch – wenn die Punkte eine Ausdehnung haben.

Page 34: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

34 Eine Lösung mit einer Strecken

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Es geht auch mit einer Strecke – wenn man den Streckenbegriff geeignet interpretiert.

Page 35: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

35 Ein Zwischenfazit

Schwierigkeit:

Bei der Formulierung des Problems wurde versäumt, die erlaubten Operationen zur Lösung des Problems zu präzisieren.

Kann man alle neun Punkte mit fünf / vier / drei / … Strecken verbinden, ohne den Stift abzusetzen?

Ausweg: Präzisierung des Problems

Kann man das Neun-Punkte-Problem mit vier / drei / … Strecken auch dann noch lösen, wenn alle Eckpunkte des Streckenzugs zum vorgegebenen Punktegitter gehören und die Punkte keine Ausdehnung haben bzw. alle Strecken nur durch die Punktmitten verlaufen?

Page 36: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

36 Präzisierung des Problems

Um Aussagen über die (Un-) Lösbarkeit eines Problems zu ermöglichen, muss man in der Regel genaue Vereinbarungen über die erlaubten Operationen machen.

Wir haben gesehen, dass das Neun-Punkte-Problem lösbar ist, wenn man Streckenzüge zulässt, die das vorgegebene Punktegitter verlassen.

Wir verschärfen jetzt die Anforderungen an die erlaubten Operationen und betrachten im Folgenden ausschließlich Streckenzüge mit den folgenden Eigenschaften:

Der Streckenzug besteht aus aneinandergefügten Strecken, deren Anfangs- und Endpunkte jeweils Punkte des vorgegebenen Punktegitters sind. Mittelpunkte der Strecken können dabei ebenfalls Punkte des vorgegebenen Punktegitters sein. Wir nennen solche Streckenzüge "gitterbasiert".

Beispiele für gitterbasierte Streckenzüge: (ADG)(GHI)(IFC)(CE) und (AE)(EC)(CFI)(ID)

Page 37: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

37 Lösung des präzisierten Problems

Das zu klärende Problem lautet jetzt: Gibt es einen gitterbasierten Streckenzug mit 4 Teilstrecken, der alle 9 Punkte des vorgegebenen Punktegitters umfasst?

Wir können jetzt wie folgt argumentieren: Wenn alle 9 Punkte in einem gitterbasierten Streckenzug vorkommen sollen, dann muss dieser Streckenzug aus 4 Teilstrecken bestehen, die alle jeweils 3 Punkte des Gitters erfassen (beachte, dass es 3 Nahtstellen geben muss und 4*3-3 = 9). Es gibt insgesamt 8 Strecken mit 3 Gitterpunkten: (ADG), (BEH), (CFI), (ABC), (DEF), (GHI), (AEI), (CEG). Jetzt kann man (mit etwas Fleiß) alle Fälle durchspielen. Dabei zeigt sich, dass man einen Streckenzug mit 3 aneinanderhängenden Strecken (mit jeweils 3 Gitterpunkten) nicht mit einer der vorgegebenen 8 Strecken fortsetzen kann.

Page 38: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

38 Lösbarkeit von Problemen

Der Nachweis, dass ein Problem lösbar ist, wird meist durch Angabe einer Lösung erbracht.

Viel schwieriger ist es in der Regel nachzuweisen, dass ein Problem unlösbar ist. Man muss dann Aussagen über alle denkbaren Problemlösemöglichkeiten machen, also sowohl über die, die man schon erprobt hat, als auch über die, an die man noch gar nicht gedacht hat.

Ein sicheres Fundament erhalten Unlösbarkeitsnachweise, wenn die zur Lösung einsetzbaren Mittel präzisiert werden. Im Fall des Neun-Punkte-Problems wurde hierzu zunächst der Begriff "gitterbasierter Streckenzug" geklärt. Mit Hilfe dieses Begriffes konnte dann die Unlösbarkeit bzgl. der vorgenommenen Präzisierung begründet werden.

Page 39: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

39

Algorithmische Lösbarkeit v. Problemen

Wir haben gezeigt, dass das Halteproblem mit den Mitteln von Python nicht lösbar ist. Ist es damit aber auch algorithmisch unslösbar?

Wie die Betrachtungen zum Neun-Punkte-Problem zeigen, sollte man eher vorsichtig sein. Über unkonventionelle Wege könnte es ja durchaus möglich sein, das Halteproblem algorithmisch zu lösen

Die einzige Möglichkeit, um zu einem befriedigenden und nicht auf Spekulation basierenden Ergebnis zu gelangen, besteht darin, die Mittel beim algorithmischen Problemlösen zu präzisieren. Hierzu ist muss der Algorithmusbegriff präzisiert werden.

Satz (über die Lösbarkeit des Halteproblems in Python):

Man kann in Python keine Funktion entwickeln, die bei Übergabe einer beliebigen Python-Funktionsdefinition und eines beliebigen Datentupels entscheidet, ob die betreffende Funktion bei der Verarbeitung der Daten hält oder nicht. Das Halteproblem für Python-Programme ist demnach nicht mit einer Python-Funktion entscheidbar.

Halteproblem:

Gibt es einen Algorithmus, mit dessen Hilfe man Endlosschleifen bei beliebigen Algorithmen feststellen kann?

Page 40: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

40 Intuitiver Algorithmusbegriff

Ein Algorithmus ist eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie auch von einer Maschine abgearbeitet werden kann.Ein Algorithmus ist

eindeutig,d. h.: die einzelnen Schritte und ihre Abfolge sind unmissverständlich beschrieben

ausführbar,d. h.: der "Prozessor" muss die Einzelschritte abarbeiten können

endlich,d. h.: seine Beschreibung besteht aus einem Text endlicher Länge

allgemein,d. h.: es wird nicht nur ein Problem, sondern eine ganze Klasse von Problemen gelöst Die oben aufgeführte Begriffsklärung ist keine präzise Definition im mathematischen Sinne. So ist z.B. nicht genau geklärt, was „von einer Maschine abgearbeitet werden kann“ nicht präzise festgelegt. Ziel ist es, die informelle Begriffsklärung durch eine präzise Definition im mathematischen Sinne zu ersetzen.

Page 41: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

41 Teil 3

Turingmaschine als Berechnungsmodell

Page 42: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

42 Ein erstes Berechnungsmodell

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

Ein erstes Berechnungsmodell wurde 1936 von A. Turing entwickelt - die sog. Turingmaschine.

Page 43: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

43 Turings Idee

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

"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. [...] The simple operations must therefore include: (a) Changes of the symbol on one of the observed squares. (b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares."aus: Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society

Page 44: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

44 Turings Idee

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

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

"We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one 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. [...] The simple operations must therefore include: (a) Changes of the symbol on one of the observed squares. (b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares."

"It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following: A. A possible change (a) of symbol together with a possible change of state of mind. B. A possible change (b) of observed squares, together with a possible change of state of mind." aus: Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society

Page 45: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

45 Turings Rechenmaschine

Wir benutzen das Programm TuringKara zur Simulation der von Turing entwickelten Rechenmaschine.

Aufgabe:

(a) Erzeuge zunächst die Ausgangssituation. Der Schreib-Lese-Kopf der Rechenmaschine soll so wie in der Abbildung zunächst auf dem Symbol "#" ganz rechts stehen.

Page 46: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

46 Turings Rechenmaschine

(b) Öffne jetzt mit der Schaltfläche [Programmieren] das Programmierfenster und lade das Steuerprogramm binaddition.kara.

Im Ausführfenster kannst du jetzt dieses Steuerprogramm ausführen. Beobachte genau, was passiert. Analysiere anschließend das Steuerprogramm. Welche Funktion haben die Zustände s0ü0, s1ü0, s0ü1, s1ü1, weiter, stopp? Wie sind die Zustandsübergänge hier festgelegt?

(c) Lies dir noch einmal die Ausführungen von Turing durch (s.o.) und erläutere die Entscheidungen von Turing anhand der durchgeführten Simulation (zur Addition von Dualzahlen).

Page 47: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

47 Turingmaschine – Binäre Addition

#

#

##

#

0

0

1 1 1

0Zustand

Zustandsübergang

Endzustand

Anfangszustand

GelesenesSymbol

Geschriebenes Symbol

Bewegung

Page 48: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

48 Turings Idee

“… 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." aus: Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society

Page 49: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

49 Aufgabe

Eine 0-1-Folge soll invertiert werden. Z.B. soll aus der Folge 10011 die Folge 01100 erzeugt werden. Löse dieses Problem in einer eindimensionalen „Turing-Welt“.

Page 50: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

50 Aufgabe

Eine Dualzahl soll um 1 erhöht werden. So soll aus der Dualzahl 1010 die neue Zahl 1011, aus der Dualzahl 10111 die neue Zahl 11000 erzeugt werden. Löse dieses Problem in einer eindimensionalen „Turing-Welt“.

Page 51: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

51 Turingmaschine – Invertieren

1

0 1

0

ZustandZustandsübergang EndzustandAnfangszustand

GelesenesSymbol

GeschriebenesSymbol

Bewegung

Page 52: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

0

52 Turingmaschine – Inkrementieren

1

1

0

1

0

ZustandZustandsübergang

EndzustandAnfangszustand

GelesenesSymbol

GeschriebenesSymbol

Bewegung

Symbol - Leeres Band

Symbol – leeres Band

Keine Bewegung

Page 53: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

53 Präzisierung der Turingmaschine

Eine (Ein-Band-) Turingmaschine verfügt über ein nach rechts und links unbegrenztes Band, das in einzelne Felder aufgeteilt ist. In diesen Felder können einzelne Symbole einer vorgegebenen Symbolmenge abgelegt werden. Die einzelnen Felder des Bandes können mit einem Lese-/Schreibkopf angesteuert werden. Dieser Lese-/Schreibkopf kann den Inhalt eines Feldes lesen und auch Symbole in die Felder schreiben. Zudem kann er sich jeweils einen Schritt nach rechts und nach links bewegen. Die Verarbeitungseinheit zur Steuerung des Lese-/Schreibkopfes befindet sich stets in einem bestimmten Zustand. Die Verarbeitung selbst wird über ein Steuerprogramm festgelegt.

0 1 01

Band mit Feldern

Zustandsbasierte Verarbeitungseinheit

Schreib-/Lese-Kopf

……

Page 54: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

54 Präzisierung der Turingmaschine

Die Arbeitsweise einer Turingmaschine soll anhand einer konkreten Verarbeitungsaufgabe erläutert werden: Die Turingmaschine befindet sich zunächst im Anfangszustand. Auf dem Band befinden sich die Symbole, die verarbeitet werden sollen. Im vorliegenden Beispiel sind das die Symbole "0" und "1". Der Lese-/Schreibkopf verarbeitet jetzt Schritt für Schritt die Symbole auf dem Band gemäß des Steuerprogramms (dargestellt durch ein Zustandsdiagramm).

1 0 1 0q0

q0

q1

qf

0 0 1 0q0

0 1 1 0q0 0 1 0 0q0 0 1 0 1q0 0 1 0 1q1 0 1 0 1q1 0 1 0 1q1 0 1 0 1q1 0 1 0 1q1 0 1 0 1qf

0; 1; R1; 0; R

□; □; L

0; 0; L1; 1; L

□; □; R

Zustandsdiagramm

Page 55: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

55 Präzisierung der Turingmaschine

Die Turingmaschine hat eine nichtleere endliche Menge Z von Zuständen. Im vorliegenden Fall ist das die Menge Z = {q0, q1, qf}. Der Zustand z0 ist hier als Anfangszustand ausgezeichnet, der Zustand zf als Endzustand.

Eine Verarbeitung wird durch einen Zustandsübergang (von einem Zustand in einen anderen, gegebenenfalls denselben Zustand) beschrieben. Ein Zustandsübergang erfolgt nur in Abhängigkeit vom gelesenen Symbol. Ein Zustandsübergang beschreibt zusätzlich, wie das gelesene Symbol überschrieben wird (ggf. durch dasselbe Symbol) und wie sich anschließend der Lese-Schreibkopf bewegt. R steht für einen Schritt nach rechts und L für einen Schritt nach links (und N für keine Bewegung – das erlauben wir nur für Übergänge in den Endzustand). Im Zustandsdiagramm werden diese Informationstripel in der Gestalt (gelesenes Symbol; geschriebenes Symbol, Bewegung) an die Übergangspfeile geschrieben.

Zustandsdiagramm

q0

q1

qf

0; 1; R1; 0; R

□; □; L

0; 0; L1; 1; L

□; □; R

GelesenesSymbol

GeschriebenesSymbol

Bewegung

Page 56: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

56 Präzisierung der Turingmaschine

Zustandsdiagramm

Eine (einfache) Turingmaschine ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:

eine nichtleere, endliche Menge von Zuständen

eine nichtleere, endliche Menge von Eingabesymbolen, die das Symbol □ (für ein leeres Feld) nicht enthält

eine nichtleere, endliche Menge von Bandsymbolen, die alle Eingabesymbole, gegebenenfalls weitere Hilfssymbole und das Symbol □ für ein leeres Feld enthält

eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einem gelesenen Symbol den Folgezustand zuordnet und zudem das zu schreibende Symbol und die Bewegung des Lese-Schreibkopfes festlegt.

einen ausgezeichneten Anfangszustand

einen ausgezeichneten Endzustand

q0

q1

qf

0; 1; R1; 0; R

□; □; L

0; 0; L1; 1; L

□; □; R

q0; 0; q0; 1; Rq0; 1; q0; 0; Rq0; □; q1; □; Lq1; 0; q1; 0; Lq1; 1; q1; 1; Lq1; □; qf; □; R Zustandstabelle

Page 57: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

57 Turingmaschinenvarianten

AZ: I I II

z0

q0

I ;II;RR

; ;LSq1

; ;RS

I ;I ;LS

q2

; ;SSq3

I ;II;RR2-Band-Turingmaschine

2-dimensionale Turingmaschine

Page 58: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

58 Turingmaschinenvarianten

Satz (über die Gleichmächtigkeit von Turingmaschinenvarianten)

Alle (hier betrachteten) Turingmaschinenvarianten sind im folgenden Sinn gleichmächtig: Ein Problem ist genau dann mit einer einfachen Turingmaschine lösbar, wenn es mit einer zweidimensionalen Turingmaschine lösbar ist, genau dann, wenn es mit einer ...-Turingmaschinenvariante lösbar ist.

q0

q1

qf

0; 1; R1; 0; R

□; □; L

0; 0; L1; 1; L

□; □; R

Page 59: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

59 Turingmaschinenvariante – 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.

Page 60: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

60 Kara´s Sicht der Welt

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!

Page 61: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

61 Problemlösen mit Kara

Kara steht auf dem ersten Kleeblatt einer Reihe von Kleeblättern. Kara soll ein Kleeblatt am Ende der Reihe hinzufügen und zurück zur Ausgangsposition laufen.

Page 62: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

62 Steuerung von Kara

Bedingung: Aktionen:Akt. Zustand: Neuer Zustand:

endeSuchen ja endeSuchen

endeSuchen nein anfangSuchen

anfangSuchen ja anfangSuchen

anfangSuchen nein stop

endeSuchen stop

Auf Blatt? ja / vorwärts

Auf Blatt? nein / hinlegen; ...

zurück

Auf Blatt? ja / vorwärts

Auf Blatt? nein / links; links

Page 63: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

63 Teil 4

Berechenbarkeit und Entscheidbarkeit mit einer Turingmaschine

Page 64: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

64

Berechnungen mit natürlichen Zahlen

Additionsproblem:

AZ:

ZZ:

Additionsfunktion:

f(m, n) = m+n

Subtraktionsproblem:

AZ:

ZZ:

Subtraktionsfunktion:

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

undefiniert ,falls m < n

4+2

6

2-4

undefiniert

TM hält nicht

Page 65: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

65 Turing-berechenbar

Eine k-stellige Funktion f: N,...,N -> N heißt Turing(maschinen)-berechenbar genau dann, wenn gilt: Es gibt eine Turingmaschine T mit der folgenden Eigenschaft:

Ausgangszustand: Auf dem Band befindet sich ein k-Tupel (n1, ..., nk) aus natürlichen Zahlen n1, ..., nk, die alle als Strichzahlen dargestellt sind und mit dem Symbol "#" verbunden sind. Die Turingmaschine befindet sich im Anfangszustand, der Lese-/Schreibkopf am Anfang der ersten Strichzahl.

Fall 1: f(n1, ..., nk) ist definiert.

Zielzustand: Die Turingmaschine T hält und hat f(n1, ..., nk) als Strichzahl auf dem Band erzeugt.

Fall 2: f(n1, ..., nk) ist nicht definiert.

Zielzustand: Die Turingmaschine T hält nicht.

Beachte: Rechenprobleme bei natürlichen Zahlen lassen sich mit Hilfe von (mehrstelligen) partiellen Funktionen beschreiben.

Page 66: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

66 Aufgaben

Zeige, dass die folgenden Rechenprobleme mit einer Turingmaschine lösbar sind bzw., dass die entsprechenden Funktionen Turing-berechnenbar sind:

(a) Additionsproblem: Das Symbol "#" wird als "plus" gedeutet. Das Rechenergebnis soll die Summe der beiden vorgegebenen Strichzahlen darstellen.

(b) Subtraktionsproblem: Das Symbol "#" wird als "minus" gedeutet. Das Rechenergebnis soll die Differenz der beiden vorgegebenen Strichzahlen darstellen. Wenn die erste Strichzahl kleiner als die zweite Strichzahl ist, dann soll die Turingmaschine nicht mehr klarkommen und in einer Endlosschleife irgendetwas machen.

(c) Verdopplungsproblem: Hier wird das Symbol "#" nicht benötigt. Das Rechenergebnis soll das Doppelte einer vorgegebenen Strichzahl darstellen.

(d) Multiplikationsproblem: Das Symbol "#" wird als "mal" gedeutet. Das Rechenergebnis soll das Produkt der beiden vorgegebenen Strichzahlen darstellen.

(e) Divisionsproblem: Das Symbol "#" wird als "durch" gedeutet. Das Rechenergebnis soll den ganzzahligen Quotienten (ohne Rest) der beiden vorgegebenen Strichzahlen darstellen. Wenn die zweite Strichzahl eine Null ist, dann soll die Turingmaschine nicht mehr klarkommen und in einer Endlosschleife irgendetwas machen.

Page 67: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

67 Codierte Rechenprobleme

Rechenprobleme kann man allgemein so charakterisieren, dass aus bestimmten natürlichen Zahlen eine neue natürliche Zahl bestimmt wird. Auf den ersten Blick scheint es so, dass Rechenprobleme eher spezielle, in der Mathematik auftretende Probleme sind. Es zeigt sich aber, dass man sehr viele Probleme als Rechenprobleme deuten kann. Es ist daher durchaus sinnvoll, sich auf das Lösen von Rechenproblemen zu konzentrieren.

Problem: Rechenproblem:

Codierung:

Verschlüsselung nach der Caesar-Methode

Bsp.: Verschlüsselung der Zeichenkette 'ALI' mit dem Schlüssel 3 liefert die Zeichenkette 'DOL'.

f: (n1, n2) -> nn1: Zeichen; n2: Zeichenkette; n: ja/nein

f: (11209, 3) -> 41512

A -> 01; B -> 02; C -> 03; ...

(011209, 3) -> 041512

Page 68: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

68 Verallgemeinerte Rechenprobleme

Problem: Rechenproblem:

Verschlüsselung nach der Caesar-Methode

Bsp.: Verschlüsselung der Zeichenkette 'ALI' mit dem Schlüssel 3 liefert die Zeichenkette 'DOL'.

f: (v) -> wv, w: Wörter über dem Alphabet {A, B, …, Z, #}f: (ALI#III) -> DOL

L IAq0

qe

# I I I

O LD

Man kann auch beliebige (partielle) Funktionen über Wortmengen als Rechenprobleme deuten.

Page 69: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

69 Turing-berechenbar

Eine partiell definierte Funktion f, die (bestimmten) Symbolfolgen über einer vorgegebenen Symbolmenge neue Symbolfolgen zuordnet, heißt Turing(maschinen)-berechenbar genau dann, wenn gilt: Es gibt eine Turingmaschine T mit der folgenden Eigenschaft:

Ausgangszustand: Auf dem Band befindet sich eine Symbolfolge w. Die Turingmaschine befindet sich im Anfangszustand, der Lese-/Schreibkopf am Anfang der Symbolfolge.

Fall 1: f(w) ist definiert.

Zielzustand: Die Turingmaschine T hält und hat f(w) auf dem Band erzeugt.

Fall 2: f(w) ist nicht definiert.

Zielzustand: Die Turingmaschine T hält nicht.

Page 70: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

70 Entscheidungsprobleme

Entscheidungsprobleme kann man in Rechenprobleme umwandeln. Bei der Entscheidung wird ein Wahrheitswert berechnet.

Problem: Rechenproblem:

Codierung:

Kommt ein Zeichen in einer Zeichenkette vor?

Bsp.: Kommt das Zeichen 'E' in der Zeichenkette 'TURING' vor?

f: (w1) -> w2

w1, w2 Zeichenketten

f: (E#TURING) -> f

A -> 01; B -> 02; C -> 03; ...

TURING -> 202118091407

ja ->1; nein -> 0

f: (n1, n2) -> nn1: Zahl; n2: Zahl; n: Zahl

f: (5, 202118091407) -> 0

Page 71: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

71 Beispiel - Spracherkennung

Die Sprache LMyXML soll vereinfachte XML-artige Ausdrücke beschreiben. Jedes zu dieser Sprache gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen. Anfangs- und Endtag sollen im Wesentlichen identisch sein. Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen. Der Text zwischen den Anfangs- und End-Tag soll nur aus den Buchstaben a, b und c bestehen. Zur Sprache LMyXML gehört beispielsweise das Wort <ab>acaa</ab>. Entscheidungsproblem: Gehört ein Wort w zur Sprache LMyXML?

Berechnungsproblem: Berechne die Funktion gehoertZuMyXML.

falls das Wort zur Sprache LMyXML gehört;

sonst

True

False

Wort über dem Alphabet

{a, b, <, >, /}

gehoertZuMyXML

gehoertZuMyXML

<ab>acaa</ab> True

Page 72: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

72

Turingmaschine zur Spracherkennung

Page 73: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

73 Teil 5

Universelle Turingmaschine

Page 74: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

74 Eine Zwischenbilanz

Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie tatsächlich die „Idee Computer“ adäquat repräsentieren kann. Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie tatsächlich die „Idee Computer“ adäquat repräsentieren kann.

Was sollte ein Berechnungsmodell leiste, das die „Idee Computer“ erfasst?

es kann Rechenoperationen ausführen (z. B. Addieren)

es kann Problemlösungen (in geeignet beschriebener Form) automatisiert ausführen (z. B. Texte verschlüsseln)

es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann

es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Was sollte ein Berechnungsmodell leiste, das die „Idee Computer“ erfasst?

es kann Rechenoperationen ausführen (z. B. Addieren)

es kann Problemlösungen (in geeignet beschriebener Form) automatisiert ausführen (z. B. Texte verschlüsseln)

es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann

es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Page 75: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

75 Spezielle Verarbeitungssysteme

Wir haben Turingmaschinen bisher als spezielle Verarbeitungssysteme benutzt: Für jedes Problem wurde hierzu eine spezielle Turingmachine entwickelt.

Page 76: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

76 Universelle Verarbeitungssysteme

Reale Computer sind programmierbare Systeme und somit universelle Verarbeitungssysteme: Sie sind in der Lage, beliebige vorgegebene Programme bei beliebig vorgegebenen Daten auszuführen. Sie sind also universell in dem Sinne, dass sie nicht nur für eine Aufgabe konzipiert sind, sondern zur Ausführung beliebiger Lösungsalgorithmen.

Page 77: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

77 Universelle Turingmaschine

universelle Turingmaschine

1 0 1 1 0 1 1 1 #

z1

1;0;R0;1;R

#;#;Sz0

0 1 0 0 1 0 0 0 #

Eingabeband

Eingabeband

Turingmaschine zum Invertieren einer 0-1-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. Die universelle Turingmaschine erzeugt dann die Daten, die die zu simulierende Turingmaschine bei der Verarbeitung der übergebenen Daten erzeugen würde.

Page 78: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

78 Simulation mit Turing-Kara

Kodierung der TM

Ein-/Ausgabeband

Vgl.: Turingkara – Aufgaben: Die universelle Turingmaschine

Aktueller Zustand

z1

1;0;R0;1;R

#;#;Sz0

1 0 1 0 1 0 1 0 1 #

Page 79: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

79 Aufgabe

Wenn man im Weltfenster von TuringKara die Schaltfläche [Aufgaben] anklickt, erhält man ein Auswahlmenu mit vielen Aufgaben, von leichten bis sehr schwierigen. Zu den sehr schwierigen gehört auch die Aufgabe "Die Universelle Turingmaschine".

(a) Wähle die Welt "Invertieren einer Zeichenkette" aus und führe das vorgegebene Steuerprogramm aus. Die Arbeitsweise dieser Turingmaschine ist zunächst etwas undurchsichtig. Aber mit etwas Geduld kann man doch einige Verhaltensmuster erkennen. Kannst du insbesondere nachvollziehen, in welcher Weise hier eine Zeichenkette invertiert wird?

(b) Lies dir jetzt auch die Hinweise unter "Codierung" durch. Hier erfährst du, wie eine (einfache) Turingmaschine auf dem zweidimensionalen Raster dargestellt wird.

(c) Wenn Du alles verstanden hast, dann solltest du in der Lage sein, eine (einfache) Turingmaschine zur Verdopplung einer Strichzahl mit der universellen Turingmaschine zu simulieren.

Wenn man im Weltfenster von TuringKara die Schaltfläche [Aufgaben] anklickt, erhält man ein Auswahlmenu mit vielen Aufgaben, von leichten bis sehr schwierigen. Zu den sehr schwierigen gehört auch die Aufgabe "Die Universelle Turingmaschine".

(a) Wähle die Welt "Invertieren einer Zeichenkette" aus und führe das vorgegebene Steuerprogramm aus. Die Arbeitsweise dieser Turingmaschine ist zunächst etwas undurchsichtig. Aber mit etwas Geduld kann man doch einige Verhaltensmuster erkennen. Kannst du insbesondere nachvollziehen, in welcher Weise hier eine Zeichenkette invertiert wird?

(b) Lies dir jetzt auch die Hinweise unter "Codierung" durch. Hier erfährst du, wie eine (einfache) Turingmaschine auf dem zweidimensionalen Raster dargestellt wird.

(c) Wenn Du alles verstanden hast, dann solltest du in der Lage sein, eine (einfache) Turingmaschine zur Verdopplung einer Strichzahl mit der universellen Turingmaschine zu simulieren.

Page 80: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

80

Existenz universeller Turingmaschinen

Band

einfache TM

Band

Die universelle Turingmaschine ist bisher als zweidimensionale Turingmaschine konzipiert. Um von einem universellen Berechnungsmodell sprechen zu können, müsste die universelle Turingmaschine vom selben Typ wie die zu simulierenden Turingmaschinen sein (also eine einfache Turingmaschine).

Mit dem Satz über die Gleichmächtigkeit von Turingmaschinenvarianten ergibt sich, dass es auch universelle Turingmaschinen als einfache Turingmaschinen gibt.

Zweidimensionale Turingmaschine

Page 81: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

81

Existenz universeller Turingmaschinen

Band

einfache TM

Bandeinfache

Turingmaschine

Satz (über die Existenz universeller Turingmaschinen)

Es gibt eine (einfache) Turingmaschine, die als universelle Turingmaschine jede andere (einfache) Turingmaschine simulieren kann.

Page 82: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

82 Eine neue Zwischenbilanz

Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie tatsächlich die „Idee Computer“ adäquat repräsentieren kann. Die Turingmaschine ist ein auf den ersten Blick sehr primitives Rechner-Modell. Zu klären ist, ob sie tatsächlich die „Idee Computer“ adäquat repräsentieren kann.

Was sollte ein Berechnungsmodell leiste, das die „Idee Computer“ erfasst?

es kann Rechenoperationen ausführen (z. B. Addieren)

es kann Problemlösungen (in geeignet beschriebener Form) automatisiert ausführen (z. B. Texte verschlüsseln)

es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann

es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Was sollte ein Berechnungsmodell leiste, das die „Idee Computer“ erfasst?

es kann Rechenoperationen ausführen (z. B. Addieren)

es kann Problemlösungen (in geeignet beschriebener Form) automatisiert ausführen (z. B. Texte verschlüsseln)

es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann

es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Page 83: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

83 Teil 6

Weitere Berechnungsmodelle

Page 84: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

84 Berechnungsmodelle

Die Turingmaschine ist letztlich eine mathematische Präzisierung des "Prozessors". Hier wird eine Art Modell-Maschine festgelegt, die die "Idee Computer" erfassen soll. Weitere Präzisierungsansätze sind möglich.

Die Turingmaschine ist letztlich eine mathematische Präzisierung des "Prozessors". Hier wird eine Art Modell-Maschine festgelegt, die die "Idee Computer" erfassen soll. Weitere Präzisierungsansätze sind möglich.

Maschinenorientierter Ansatz: Präzisierung des ProzessorsBeispiel: Turingmaschine, Registermaschine

Anweisungsorientierter Ansatz: Präzisierung der zulässigen AnweisungenBeispiel: While

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

“Prozessor”Verarbeitungsanweisungen

Eingaben

Ausgaben

Page 85: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

85 Registermaschine

Das Registermaschinenmodell orientiert sich stärker am Aufbau realer Computer.Das Registermaschinenmodell orientiert sich stärker am Aufbau realer Computer.

DatenProgramm

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

Eine Registermaschine ist eine Verarbeitungseinheit, die beliebig viele Register zur Speicherung von Daten hat und durch maschinennahe Programme gesteuert wird.

Page 86: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

86 Registermaschinen-berechenbar

Eine k-stellige Funktion f: N,...,N -> N heißt Registermaschinen-berechenbar genau dann, wenn gilt: Es gibt eine Registermaschine mit der folgenden Eigenschaft:

Ausgangszustand: In den Registern R1, ..., Rk befinden sich die zu verarbeitenden natürlichen Zahlen.

Fall 1: f(n1, ..., nk) ist definiert.

Zielzustand: Die Registermaschine hält und in R0 befindet sich der Funktionswert f(n1, ..., nk).

Fall 2: f(n1, ..., nk) ist nicht definiert.

Zielzustand: Die Registermaschine hält nicht.

Page 87: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

87 Aufgaben

Zeige, dass die folgenden Funktionen Registermaschinen-berechenbar sind. Suche dir ein Berechnungsproblem aus und entwickle ein geeignetes Registermaschinenprogramm.

(a) Subtraktionsproblem: Berechnet werden soll die Subtraktionsfunktion f: N, N -> N mit f(n1, n2) = n1 - n2, sofern n1 größer oder gleich n2 ist, bzw. f(n1, n2) ist nicht definiert, sofern n1 kleiner als n2 ist.

(b) Verdopplungsproblem: Berechnet werden soll die Verdopplungsfunktion f: N -> N mit f(n) = 2*n.

(c) Multiplikationsproblem: Berechnet werden soll die Multiplikationsfunktion f: N, N -> N mit f(n1, n2) = n1 * n2.

(d) Divisionsproblem: Berechnet werden soll die Divisionsfunktion f: N, N -> N mit f(n1, n2) = n1 // n2, sofern n2 ungleich 0 ist, bzw. f(n1, n2) ist nicht definiert, sofern n2 gleich 0 ist.

Page 88: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

88 Aufgaben

Zum Testen kannst du das Bonsai-Simulationsprogramm benutzen.

Page 89: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

89 While-Programme

Bestandteile von While-Programmen:Bestandteile von While-Programmen:

Variablen: x0, x1, x2, ...

Konstanten: 0, 1, 2 ...

Symbole: =, :, !=

Operatoren: + -

Schlüsselwörter: while, #while

Aufbau von While-Programmen:Aufbau von While-Programmen:

x0 = x1while x2 != 0: x0 = x0 + 1 x2 = x2 - 1#while

Zuweisungen: Jede Zuweisung mit dem folgenden Aufbau ist ein While-Programm:

variable = konstantevariable = variablevariable = variable + konstantevariable = variable - konstante

Sequenzen: Falls P1 und P2 While-Programme sind, dann ist auch die folgende Sequenz ein WHILE-Programm.

P1 P2

Wiederholungen: Falls P ein While-Programm ist und x eine Variable ist, dann ist auch

while x != 0: P #while

ein While-Programm.

Die Programmiersprache While ist eine sehr einfache Programmiersprache, die nur mit den oben genannten Programmierelementen auskommt.

Page 90: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

90 While-berechenbar

Eine (k-stellige) Funktion f: N, ..., N -> N heißt While-berechenbar genau dann, wenn gilt: Es gibt ein While-Programm mit der folgenden Eigenschaft:

Ausgangszustand: Die Variablen x1, ..., xk verwalten die zu verarbeitenden natürlichen Zahlen n1, ..., nk.

{x0 -> 0; x1 -> 7; x2 -> 3; ...}

Fall 1: f(n1, ..., nk) ist definiert.

Zielzustand: Die Variable x0 verwaltet den Funktionswert f(n1, ..., nk).

{x0 -> 10; x1 -> ...; x2 -> ...; ...}

Fall 2: f(n1, ..., nk) ist nicht definiert.

Zielzustand: Die Ausführung des While-Programms hält nicht.

Page 91: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

91 Aufgaben

Was leistet das gezeigte While-Programm? Stelle eine Vermutung auf. Überprüfen kannst du sie mit einem geeigneten Python-Programm.

x0 = x1while x2 != 0: x0 = x0 + 1 x2 = x2 - 1#while

# Initialisierung der Variablenx0 = 0x1 = 3x2 = 7

# Registermaschinenprogrammx0 = x1while x2 != 0: x0 = x0 + 1 x2 = x2 - 1#while

# Ausgabe der Variablenprint('x0: ', x0)print('x1: ', x1)print('x2: ', x2)

Page 92: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

92 Aufgaben

Zeige, dass die folgenden Funktionen While-berechenbar sind. Suche dir ein Berechnungsproblem aus und entwickle ein geeignetes While-Programm.

(a) Subtraktionsproblem: Berechnet werden soll die Subtraktionsfunktion f: N, N -> N mit f(n1, n2) = n1 - n2, sofern n1 größer oder gleich n2 ist, bzw. f(n1, n2) ist nicht definiert, sofern n1 kleiner als n2 ist.

(b) Verdopplungsproblem: Berechnet werden soll die Verdopplungsfunktion f: N -> N mit f(n) = 2*n.

(c) Multiplikationsproblem: Berechnet werden soll die Multiplikationsfunktion f: N, N -> N mit f(n1, n2) = n1 * n2.

(d) Divisionsproblem: Berechnet werden soll die Divisionsfunktion f: N, N -> N mit f(n1, n2) = n1 // n2, sofern n2 ungleich 0 ist, bzw. f(n1, n2) ist nicht definiert, sofern n2 gleich 0 ist.

Page 93: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

93 Äquivalenzsatz

Satz (über die Äquivalenz von Berechnungsmodellen)

Eine (k-stellige) Funktion f ist Turingmaschinen-berechenbar genau dann, wenn sie Registermaschinen-berechenbar ist bzw. genau dann, wenn sie While-berechenbar ist.

x0 = x1while x2 != 0: x0 = x0 + 1 x2 = x2 - 1#while

0 TST 11 JMP 32 JMP 63 DEC 14 INC 05 JMP 06 TST 27 JMP 98 JMP 119 DEC 210 INC 011 HLT

Page 94: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

94 Church-Turing-These

Church-Turing-These

Eine Funktion ist im intuitiven Sinn berechenbar genau dann, wenn sie Turingmaschinen-berechenbar ist bzw. genau dann, wenn sie Registermaschinen-berechenbar ist bzw. genau dann, wenn sie While-berechenbar ist bzw. genau dann, ...

Die Tatsache, dass alle Versuche, den Berechbarkeitsbegriff mathematisch zu präzisieren, zur gleichen Klasse berechenbarer Funktionen geführt hat, sehen viele als Bestätigung dafür, dass der intuitive Berechnebarkeitsbegriff durch die bisher entwickelten Berechnungsmodelle adäquat erfasst wird. Diese These wurde erstmals von Alonzo Church und Alan Turing - den Entwicklern der ersten Berechnungsmodelle - formuliert. Beachte, dass die Chuch-Turing-These keine mathematisch präzise Aussage ist, da hier der nicht präzisierte Begriff "im intuitiven Sinne berechenbar" vorkommt. Die Chuch-Turing-These drückt vielmehr die Erfahrung vieler Informatiker aus, die sich mit der Präzisierung des Algorithmusbegriffs beschäftigt haben. Was leistet das Berechnungsmodell "Turingmaschine" / "Python-programmierbar" / ...? es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Was leistet das Berechnungsmodell "Turingmaschine" / "Python-programmierbar" / ...? es kann Problemlösungen (in geeignet beschriebener Form) selbstständig ausführen (z. B. sortieren) es kann Rechenoperationen ausführen (z. B. Addieren) es ist universell programmierbar in dem Sinn, dass es beliebige Programme bei beliebigen Daten ausführen kann es ist so mächtig, dass es alle Algorithmen (in geeignet kodierter Form) ausführen kann

Page 95: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

95 Teil 7

Existenz nicht-berechenbarer Funktionen

Page 96: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

96 Vorbemerkungen

Um Aussagen über die Grenzen der Berchenbarkeit machen zu können, müssen wir ein präzise beschriebenes Berechnungsmodell verwenden. Nach dem Satz über die Äquivalenz von Berechnungsmodellen ist es dabei egal, welches Berechnungsmodell wir verwenden.

Hier soll im Folgenden die Turingmaschine als Berechnungsmodell benutzt werden. Dabei werden wir ausschließlich einfache Turingmaschinen betrachten. Wir setzen zudem voraus, dass auf dem Band außer dem speziellen Bandsymbol B für ein leeres Feld nur das Symbol I vorkommen soll - weiter unten wird auch noch das Symbol # hinzukommen. Schließlich setzen wir voraus, dass die betrachteten Turingmaschinen genau einen Endzustand stop haben.

Ziel ist es, einen Überblick über alle Turingmaschinen mit den eben formulierten Einschränkungen zu gewinnen. Wenn dieser Überblick vorliegt, können wir eventuell Aussagen über die mit diesen Turingmaschinen berechenbaren Funktionen treffen.

Page 97: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

97 Aufzählung von Turingmschinen

Wir betrachten zunächst nur Turingmaschinen mit nur einem Zustand (außer dem Endzustand stop). Wie dieser Zustand benannt wird, spielt dabei keine Rolle. Wir gehen von der Bezeichnung z0 aus. Dieser Zustand ist dann auch der Startzustand.

z0 B z0 B L; z0 I z0 B L;

z0 B z0 B L; z0 I z0 B R;

z0 B z0 B L; z0 I z0 I L;

z0 B z0 B L; z0 I z0 I R;

z0 B z0 B L; z0 I zS B L;

z0 B z0 B L; z0 I zS B R;

z0 B z0 B L; z0 I zS I L;

z0 B z0 B L; z0 I zS I R;

z0 B z0 B R; z0 I z0 B L;

...

z0 B zS I R; z0 I zS I R;

z0 B z0 B L; z0 I z0 B L;

Kurzschreibweise für Turingmaschinen:

Aufgabe:

(a) Kannst du die begonnene Aufzählung fortsetzen? Zur Kontrolle: Es gibt 64 verschiedene Möglichkeiten.

(b) Begründe, dass es 64 verschiedene Turingmaschinen (mit den gemachten Einschränkungen) mit genau einem Zustand (außer dem Endzustand) gibt.

Page 98: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

98 Aufzählung von Turingmschinen

Wir betrachten jetzt Turingmaschinen mit genau 2 Zuständen (außer dem Endzustand stop). Die Zustände sollen mit z0 und z1 bezeichnet werden. Der Zustand z0 soll auch hier der Startzustand sein.

z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L;

z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I R;

...

z0 B zS I R; z0 I zS I R; z1 B zS I R; z1 I zS I R;

Aufgabe:

(a) Kannst du die begonnene Aufzählung um einige wenige Turingmaschinen fortsetzen?

(b) Wie viele Turingmaschinen gibt es hier?

Page 99: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

99 Aufzählung von Turingmschinen

T0: z0 B z0 B L; z0 I z0 B L;

T1: z0 B z0 B L; z0 I z0 B R;

...

T64: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L;

T65: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I R;

...

T20800: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L; …

...

Satz (über die Aufzählbarkeit von Turingmaschinenvarianten)

Turingmaschinen mit einer fest vorgegebenen Symbolmenge (Eingabesymbole + Bandsymbole) kann man systematisch (algorithmisch) erzeugen.

T0, T1, T2, ...

Jede Turingmaschine kommt in dieser Auflistung vor. Man kann (mit einem geeigneten Algorithmus) zu jeder natürlichen Zahl n die zugehörige Turingmaschine Tn bestimmen. Umgekehrt kann man (mit einem geeigneten Algorithmus) zu jeder Turingmaschine T die Platznummer n in der Auflistung bestimmen.

Page 100: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

100 Problem

Ist jede Funktion f: N N (Turingmaschinen-) berechenbar? Wie kann man nachweisen, dass es Funktionen f: N N gibt, die nicht (Turingmaschinen-) berechenbar sind?

Menge der Funktionen von N nach N

Menge der berechenbaren Funktionen

von N nach N

?

?

n 2n

n s(n)

n prim(n)

Page 101: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

101 Abzählen unendlicher Mengen

Eine Menge M heißt abzählbar genau dann, wenn es eine Nummerierungsabbildung i von der Menge der natürlichen Zahlen in die Menge M gibt, bei der alle Elemente aus M als Bildelemente natürlicher Zahlen erfasst werden. Die Abbildung i ordnet in diesem Fall den Elementen von M ihre jeweiligen Nummern zu.

Eine Menge M heißt überabzählbar genau dann, wenn sie nicht abzählbar ist.

Beispiel: Die Menge der geraden Zahlen ist abzählbar. Die folgende Auflistung liefert implizit eine mögliche Nummerierung.

0, 2, 4, 6, ...

Beispiel: Die Menge der ganzen Zahlen ist abzählbar. Die folgende Auflistung liefert implizit eine mögliche Nummerierung.

0, 1, -1, 2, -2, 3, -3, ...

Beispiel: Die Menge der Wörter über dem Alphabet {a, b, c} ist abzählbar.

Beispiel: Die Menge der Turingmaschinen mit Eingabealphabet {I} und Bandlaphabet {I, B} ist abzählbar.

Page 102: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

102 Abzählen von Turingmaschinen

Satz (über die Abzählbarkeit von Turingmaschinen)

Die Menge aller Turingmaschinen über dem Eingabealphabet {I} und dem Bandlaphabet {I, B} ist abzählbar.

Beachte, dass im letzten Abschnitt sogar mehr gezeigt wurde. Es wurde dort gezeigt, dass die Zuordnung Turingmaschine - Nummer in beide Richtungen berechnet werden kann.

Satz (über die Abzählbarkeit von Turingmaschinen-berechenbaren Funktionen)

Die Menge aller Turingmaschinen-berechenbaren Funktionen von N nach N ist abzählbar.

Page 103: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

103 Abzählen von partiellen Funktionen

Angenommen, die Menge aller (partiellen) Funktionen von N nach N ist abzählbar.

Dann gibt es eine nummerierte Auflistung, mit der alle diese Funktionen erfasst werden:

f0, f1, f2, f3, f4, ...

Jeder dieser Funktionen ordnet allen natürlichen Zahlen eine natürliche Zahl oder den Wert u (für undefiniert) zu. Eine Zuordnungstabelle für alle Funktionen der Auflistung könnte z.B. so aussehen:

Satz (über die Überabzählbarkeit der Menge aller Funktionen)

Die Menge aller (partiellen) Funktionen von N nach N ist überabzählbar.

Page 104: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

104 Abzählen von partiellen Funktionen

Wir konstruieren jetzt eine weitere Funktion f von N nach N nach dem folgenden Schema:

Wir benutzen also die Funktionswerte in der Diagonalen der Ausgangstabelle und ändern sie alle systematisch ab.

Die Funktion f ist so definiert, dass sie sich an mindestens einer Stelle von jeder Funktion der Auflistung f0, f1, f2, f3, f4, ... unterscheidet.

Page 105: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

105 Abzählen von partiellen Funktionen

Angenommen, die Menge aller (partiellen) Funktionen von N nach N ist abzählbar.

Dann gibt es eine nummerierte Auflistung, mit der alle diese Funktionen erfasst werden:

f0, f1, f2, f3, f4, ...

...

Wir konstruieren jetzt eine weitere Funktion f von N nach N nach dem gezeigten Schema.

Die Funktion f ist so definiert, dass sie sich an mindestens einer Stelle von jeder Funktion der Auflistung f0, f1, f2, f3, f4, ... unterscheidet.

Argumentation:

Damit sind wir aber an einem Punkt angelangt, an dem wir uns in Widersprüche verwickeln. Wir sind von der Annahme ausgegangen, dass die Menge aller (partiellen) Funktionen von N nach N abzählbar ist. Aus einer möglichen Abzählung (in Form einer nummerierten Auflistung) haben wir eine Funktion f von N nach N konstruiert. Diese Funktion f muss Element der Menge M sein (da sie ja eine Funktion von N nach N ist) und gleichzeitig unterscheidet sie sich von allen Elementen von M (an mindestens einer Stelle). So etwas ist unmöglich. Die einzige Möglichkeit, aus diesem Dilemma herauszukommen, ist die Folgerung, dass wir von einer falschen Annahme ausgegangen sind.

Satz (über die Überabzählbarkeit der Menge aller Funktionen)

Die Menge aller (partiellen) Funktionen von N nach N ist überabzählbar.

Page 106: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

106

Existenz nicht-berechenb. Funktionen

Satz (über die Überabzählbarkeit der Menge aller Funktionen)

Die Menge aller (partiellen) Funktionen von N nach N ist überabzählbar.

Satz (über die Existenz nicht-berechenbarer Funktionen)

Es gibt (partielle) Funktionen von N nach N, die nicht Turingmaschinen-berechenbar sind.

Satz (über die Abzählbarkeit von Turingmaschinen-berechenbaren Funktionen)

Die Menge aller Turingmaschinen-berechenbaren Funktionen von N nach N ist abzählbar.

Menge der Funktionen von N nach N

Menge der berechenbaren Funktionen

von N nach N

?

?

n 2n

n s(n)

n prim(n)

es gibt nicht-berechenbare Funktionen

Analog kann man zeigen, dass es partielle Funktionen f: N, N -> N gibt, die nicht Turingmaschinen-berechenbar sind.

Page 107: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

107 Teil 8

Beispiel – Die Haltefunktion

Page 108: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

108 Die Haltefunktion für Python-Progr.

Gibt es ein Python-Programm (dargestellt als Python-Funktion), mit dessen Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann?

falls das Python-Programm bei der Verarbeitung der Daten hält,sonst

True

False

Python-Programm +

Daten

istHaltend

istHaltend

False

"""def primzahl(n): if n == 1: prim = False else: prim = True i = 2 while i < n: if n % i == 0: prim = False return prim"""

daten

quelltext

71

Page 109: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

109

Die Haltefunktion für Turingmaschinen

Gibt es eine Turingmaschine, mit deren Hilfe man feststellen kann, ob eine vorgegebene Turingmaschine bei der Verarbeitung natürlicher Zahlen hält oder nicht?

falls die TM bei der Verarbeitung der Zahl hält,sonst

True

False

Turingmaschine+

nat. Zahl

h

h

False

z0 B z0 B L; z0 I z0 B L;

Nat. Zahl

Turingmaschine

III

Page 110: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

110 Die Haltefunktion

T0: z0 B z0 B L; z0 I z0 B L;

T1: z0 B z0 B L; z0 I z0 B R;

T2: z0 B z0 B L; z0 I z0 I L;

T3: z0 B z0 B L; z0 I z0 I R;

T4: z0 B z0 B L; z0 I zS B L;

T5: z0 B z0 B L; z0 I zS B R;

...

Turingmaschinen: Zahlen:

w0:

w1: I

w2: II

w3: III

w4: IIII

w5: IIIII

...Im Folgenden wollen wir die Turingmschine Ti mit der zugehörigen Nummer i codieren. Die zu verarbeiten Daten sind (evtl. auch leere) Folgen des Symbols "I". Diese Folgen können als Codierungen natürlicher Zahlen aufgefasst werden.

Mit der Funktion h soll jetzt das Halterverhalten von Turingmaschinen bei der Verarbeitung natürlicher Zahlen beschrieben werden.

Page 111: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

111 Die Haltefunktion

T0: z0 B z0 B L; z0 I z0 B L;

T1: z0 B z0 B L; z0 I z0 B R;

T2: z0 B z0 B L; z0 I z0 I L;

T3: z0 B z0 B L; z0 I z0 I R;

T4: z0 B z0 B L; z0 I zS B L;

T5: z0 B z0 B L; z0 I zS B R;

...

Turingmaschinen:

Zahlen:

w0:

w1: I

w2: II

w3: III

w4: IIII

w5: IIIII

Aufgabe: In der Wertetabelle sind bereits einige Funktionswerte von h eingetragen. Dabei werden die beschriebenen Codierungen zu Grunde gelegt. Ergänze die fehlenden Funktionswerte.

Page 112: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

112 Berechnung der Haltefunktion

Annahme: Es gibt eine Turingmaschine Th, die die Funktion h berechnet.

Die Abbildung verdeutlicht das Verhalten von Th, wenn die übergebene Turingmschine bei dem übergebenen Wort hält.

Wenn die übergebene Turingmschine bei dem übergebenen Wort nicht hält, dann erzeugt Th ein leeres Band und geht in den Stop-Zustand über.

Page 113: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

113 Berechnung der Haltefunktion

Wir benutzen jetzt ein Diagonalisierungsverfahren, um aus Th eine neue Turingmaschine T zu konstruieren.

Die folgende Tabelle zeigt, wie das Halteverhalten aller möglichen Turingmaschinen bei bestimmten zu verarbeitenden Wörtern aussehen könnte.

Wenn der Eintrag in der Tabelle zu einer bestimmten Turingmaschine und einem bestimmten Datum ein "ja" ist, dann soll die betreffende Turingmaschine bei der Verarbeitung des betreffenden Datums halten, bei "nein" entsprechend nicht.

Ziel ist es, eine Turingmaschine T zu entwickeln, die das Halteverhalten der aufgelisteten Turingmaschinen in gewisser Weise umkehrt. T soll also genau dann bei der Verarbeitung des Wortes wi halten, wenn die Turingmaschine Ti bei der Verarbeitung des Wortes wi nicht hält.

Page 114: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

114 Berechnung der Haltefunktion

T gewinnen wir mit Hilfe von Th, indem wir zunächst das zu verarbeitende Wort duplizieren, anschließend die dargestellte Zahl (i, i) von Th verarbeiten lassen und abschließend den Übergang zum Stop-Zustand etwas abändern. Vorab wird geprüft, ob das gelesene Zeichen ein "I" ist. Wenn das der Fall ist, dann soll endlos ein "I" auf das Band geschrieben werden und eine Bewegung nach rechts erfolgen. Ist das gelesene Zeichen dagegen ein "B(lank)", dann soll ein Übergang in den Stop-Zustand erfolgen.

Page 115: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

115

Nicht-Berechenbarkeit der Haltefunktion

T entpuppt sich als höchst merkwürdige Turingmaschine: Einerseits muss T in der Auflistung aller Turingmaschinen vorkommen, also mit irgendeiner Turingmaschinen Ti der Auflistung übereinstimmen. Andererseits verhält sich T anders als jede der in der Auflistung vorkommenden Turingmaschinen. Es ergeben sich also zwei widersprüchliche Aussagen.

Die Annahme, dass es eine Turingmaschine Th gibt, die die Funktion h berechnet, führt also zu einem Widerspruch. Die Annahme muss folglich falsch sein.

Satz (über die Unlösbarkeit des Halteproblems bei Turingmaschinen)

Es gibt keine Turingmaschine, die die Haltefunktion h berechnet. Es gibt folglich keine Turingmaschine, mit der man das Halteverhalten beliebiger Turingmaschinen bei beliebigen zu verarbeitenden Daten entscheiden kann.

Page 116: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

116 Die Halte-Funktionen

Menge der Funktionen von N, N nach N

Menge der berechenbaren Funktionen

von N, N nach N?

f0, f1, f2, f3, ..., +, -, *, …

h

Halte-Funktion

Page 117: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

117 Teil 9

Beispiel – Die Rado´sche Σ-Funktion

Page 118: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

118 Die Rado´sche Funktionen

Menge der Funktionen von N nach N

Menge der berechenbaren Funktionen

von N nach N?

f0, f1, f2, f3, ...

Ziel ist es, eine weitere nicht-berechenbare Funktion konkret zu beschreiben.

Rado´sche -Funktion

Page 119: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

119 Biber-Turingmaschinen

Eine Biber-Turingmaschine ist eine (einfache) Turingmaschine, die in jedem Arbeitsschritt genau eine "Baumaktion" durchführt (Baumstamm hinlegen oder wegnehmen) und einen Schritt nach rechts oder links geht. Eine Biber-TM startet in einer leeren Welt, erzeugt „Baumstämme“ und hält nach endlich vielen Arbeitsschritten.

Vorher:

Nachher:

Biber-TM:

z0 B z1 I R;

z0 I zS I R;

z1 B z0 I L;

z1 I z0 I L;

Page 120: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

120 Aufgabe

Aufgabe 1: Biber-Turingmaschinen-Wettberwerb

Die gezeigte Biber-Turingmaschine mit 2 Zuständen (außer dem Stop-Zustand zS) sammelt genau 2 Baumstämme, bevor sie hält.

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

z0 B z1 I R;

z0 I zS I R;

z1 B z0 I L;

z1 I z0 I L;

Page 121: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

121 Aufgabe

Aufgabe 2: Biber-Turingmaschinen-Wettberwerb

Wer schafft die meisten Baumstämme? Gesucht ist eine Biber-Turingmaschine mit genau 3 bzw. 4 Zuständen (außer dem Stop-Zustand), die möglichst viele Baumstämme sammelt, bevor sie hält.

Page 122: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

122 Fleiß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:

Page 123: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

123 Rado´sche Funktion

Im Jahr 1962 hat der ungarische Mathematiker Tibor Rado ein bemerkenswerte Funktion definiert. Die Funktion Σ: N -> N ordnet jeder natürlichen Zahl n aus N nach der folgenden Berechnungsvorschrift eine natürliche Zahl zu:

Σ(n) beschreibt die maximale Anzahl von Baumstämmen, die eine Biber-Turingmaschine mit genau n Zuständen (außer dem Stop-Zustand) ausgehend von einem leeren Band sammeln kann.

n

0

1

2

3

4

5

6

(n)

0

1

4

6

13

...

...Aufgabe:

(a) Schätze erst einmal, wie groß die Funktionswerte Σ(5) und Σ(6) sind.

(b) Recherchiere anschließend, wie groß die Funktionswerte Σ(5) und Σ(6) sind. Wie gut waren deine Schätzungen?

Page 124: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

124

Nicht-Berechenbarkeit d. Rado-Funktion

Bemerkung:

Dass man die Funktionswerte der Σ-Funktion nicht so einfach berechnen kann, liegt nach dem oben angegebenen Satz an der Nicht-Berechenbarkeit der Funktion. Es gibt (nach der Chuch-Turing-These) kein algorithmisches Verfahren, mit dem man alle Funktionswerte der Σ-Funktion berechnen kann. Diese Tatsache schließt aber nicht aus, dass man einzelne Funktionswerte der Σ-Funktion bestimmen kann. Im Fall n = 2 kann man beispielsweise alle Turingmaschinen mit 2 Zuständen (außer dem Stop-Zustand) erzeugen und jede dieser endlichen vielen Turingmaschinen unsersuchen, ob sie hält und wie viele Baumstämme sie in diesem Fall erzeugt.

Satz (über die Nicht-Berechenbarkeit der Rado-Funktion)

Die Rado-Funktion Σ ist nicht Turingmaschinen-berechenbar.

Page 125: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

125 Satz von Rado

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 :

Satz (über die Nicht-Berechenbarkeit der Rado-Funktion)

Die Rado-Funktion Σ ist nicht Turingmaschinen-berechenbar.

Page 126: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

126 Satz von Rado

Man zeigt zunächst, dass es eine Turingmaschine Tn mit n Zuständen (außer dem Stop-Zustand) 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 6 Zuständen (außer dem Stop-Zustand) gibt, der eine gegebene, beliebig lange Baumstammreihe verdoppelt:

AZ:

ZZ: I I

z0TV:

II

I I

Page 127: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

127 Satz von Rado

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+6+k Zustände und erzeugt eine Baumstammreihe der Länge (2n).

Page 128: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

128 Satz von Rado

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

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

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

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

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

n+6+k = 2*(6+k) + (6+k) = 3*(6+k)

2n = 4*(6+k)

Hieraus folgt: n+6+k < 2n.

Aus der Monotonie von folgt: (n+7+6) < (2n).

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

Page 129: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

129 Teil 10

Ein Blick in die Geschichte

Page 130: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

130 David Hilbert

Page 131: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

131 Hilbert´s Rede

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.

[...]

Page 132: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

132 Hilbert´s Rede

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.

[...]Ein besonderes Anliegen war ihm, der Mathematik ein solides Fundament zu verleihen.

Page 133: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

133 Hilbert´sches Programm

Hilbert´sches Programm: Formalisierung der Mathematik

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 wahr oder falsch ist.

Das Hilbert´sche Entscheidungsproblem verlangt den Nachweis, dass es einen Algorithmus gibt, mit dessen Hilfe man die Wahrheit mathematischer Aussagen "berechnen" kann.

Page 134: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

134 Ergebnisse von Gödel

Gödelsche Unvollständigkeitssätze

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

(Vollständigkeit) (b) 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 logisch herleitbar sind.

Hilbert´sches 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 kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.

Gödel gelang es mit seinen Resultaten, auf eine grundlegende Schwäche der beweisenden Methode hinzuweisen. Mathematiker sind nicht in der Lage, fundamentale Eigenschaften der Mathematik nachzuweisen.

Page 135: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

135 Ergebnisse von Turing und Church

Hilbert´sches 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 kein Verfahren, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist.

Satz von Turing und Church

Es gibt kein algorithmisches Verfahren, mit dem man für jede beliebige mathematische Aussage in endlich vielen Schritten entscheiden kann, ob sie (aus den Grundannahmen) logisch herleitbar ist oder nicht.

Zur Klärung der Frage, ob es ein Verfahren gibt, mit dem man für jede beliebige Aussage in endlich vielen Schritten entscheiden kann, ob sie wahr oder falsch ist, sahen sich Turing und Church veranlasst, erst einmal zu präzisieren, was ein "Verfahren" ist. Turing entwickelte die nach ihm benannte Turingmaschine, Chuch ein alternatives Berechnungsmodell.

Page 136: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

136 Intellektuelle Leistungen im 20. Jhd. Informatik:

Methode: Ein Problem mit Hilfe eines Algorithmus lösen. Grenze der Methode: Das Entscheidungsproblem (... Halteproblem ...) ist

algorithmisch nicht lösbar. (Turing) Mathematik:

Methode: Einen Satz beweisen. Grenze der Methode: 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 beweisbar sind. (Gödel)

Physik: Methode: Eigenschaften eines Systems messen. Grenze der Methode: Man kann Ort und Impuls eines Teilchens nicht

gleichzeitig exakt bestimmen. (Heisenberg)

Page 137: Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

137 Literaturhinweise

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.