Grundlagen der Informatik

Kapitel 19

Harald Krottmaier

Sven Havemann

WS2007 2

Agenda

• Begriffe

• Turingmaschine – Beispiele

• Berechenbarkeit – Hilfsmittel

– Beispiele

WS2007 3

Motivation

• Sind Computer „allmächtig“?

• Präziser: Ist alles von einem

Computer berechenbar?

WS2007 4

1937…

• Alan Turing – Engl. Mathematiker, Gigant!

• Berechnung von Funktionen:

• Partielle Funktion: Nur eine Teilmenge aller möglichen Eingaben wird akzeptiert:

WS2007 5

Berechenbare Funktion

• “Eine Funktion heißt berechenbar,

wenn ein Algorithmus gefunden

werden kann, der die Funktion

berechnet.”

– Eine Funktion ist eine Abbildung

– Ein Algorithmus ist eine endliche

Berechnungsvorschrift

WS2007 6

Bsp. Berechenbare Funktion

• f(n) = 2n

• g(n) = (4n) * 0.5

• f und g sind gleiche Funktionen,

aber mit unterschiedlichen

Berechnungsvorschriften

• h(n)=100/(n-1) ist partielle

Funktion, undefiniert für n=1

Eine nicht berechenbare

Funktion

• Sei f(i,j) eine Funktion, die alle

möglichen Folgen natürlicher Zahlen

enthält, also f(i,j) { 0,..,9 }

– Eigentlich Liste von Ziffernfolgen!

• f(i): i-te Folge, entspricht den

nichtabbrechenden Dezimalzahlen

zwischen 0.0 und unter 1.0

– 0 . 9 1 3 9 1 3 0 1 3 2 9 7 2 3 2 3 4 …

WS2007 7

Eine nicht berechenbare

Funktion

• Konstruiere nun eine neue Funktion

die sich von jeder Funktion in der

Liste unterscheidet:

– g(j) sei 0 wenn f(j,j) 0

– g(j) sei 1 wenn f(j,j) = 0

• g unterscheidet sich von allen

Funktionen in der Liste!

• Also enthält f nicht alle Folgen! WS2007 8

WS2007 9

Nicht berechenbare

Funktionen

• Diagonalverfahren nach Cantor (1873)

• Georg Cantor: Begründer der

Mengenlehre

– Gigant!

WS2007 10

Bsp.: Diagonalverfahren

WS2007 11

Nicht durch Algorithmus

berechenbare Funktionen

• Potenzmenge P(IN) – Das ist die Menge aller möglichen

Teilmengen von IN

– Es gibt mehr Teilmengen als es Elemente von IN gibt

• P(IN) ist überabzählbar

• Die Menge aller Funktionen f: IN IN ist auch überabzählbar

WS2007 12

Wieviele Algorithmen gibt es?

• Ein Algorithmus besteht aus einem

endlichen Wort aus ∑*

• Es gibt nur abzählbar viele Algorithmen!

– Wirklich? Wie zählt man sie ab??

• Es gibt daher auch nur abzählbar viele

berechenbare Funktionen!

• Es gibt also sehr viele Funktionen, die

nicht durch einen Algorithmus berechnet

werden können!

WS2007 13

Die Church'sche These

• "Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen."

• Die Church´sche These ist nicht beweisbar – Problem: "intuitiv berechenbar.."

• Satz: "Die Menge der berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turingmaschine berechnen lassen."

WS2007 14

Berechenbarkeitskonzepte

WS2007 15

Die Turingmaschine

• Alan Turing: allgemeines Konzept einer „rechnenden Maschine" – unbegrenztes Arbeitsband, in Felder unterteilt

– Lese-/Schreib-Kopf an aktueller Position

– Maschine selbst hat endlich viele Zustände

– Maschine kann Zeichen in Arbeitsfeld lesen und abhängig vom aktuellen Zustand

• Neues Zeichen in Arbeitsfeld schreiben

• Nach rechts oder links gehen und dann

• In einen neuen Zustand übergehen

WS2007 16

Die Turingmaschine formal

7-Tupel:

WS2007 17

Wichtiger Satz in der

Informatik:

• Jedes Problem, das überhaupt

maschinell lösbar ist, kann auch von

einer Turingmaschine gelöst werden

• Problem nur im Einzelfall: Finde die

richtige Überführungsfunktion….

– (schreibe das richtige C-Programm)

WS2007 18

Bsp Turingmaschine:

Paritätsprüfung

• Ungerade Anzahl von Strichen (I, III,

IIIII, ...) akzeptieren, sonst nicht!

– Leere Bandfelder enthalten ein #

• Zustandsgraph:

WS2007 19

Tätigkeit der Turingmaschine:

• Liste von 5-Tupeln: – Aktueller Zustand aus Z

– Eingabezeichen aus Σ Γ

– Ausgabezeichen aus Γ

– Kopfbewegung aus {L,N,R}

– Folgezustand aus Z

• Praktischerweise als Tabelle

angeben, „Turingtabelle“

WS2007 20

Für Paritätsprüfungsbeispiel:

• Braucht drei 5-Tupel, Schreibweise:

– 1I#R2 „liest die Maschine in Zustand 1 ein I, so schreibt

sie ein #, geht nach rechts und geht in Zustand 2“

– 2I#R1

– 2##N3

• Zustand 1: gerade, 2: ungerade Anz

• Zustand 3: Maschine hat ungerade

Anzahl von "I" gelesen.

WS2007 21

WS2007 22

Bsp.: Duale Addition von 1

• z.B.

– Eingabe: #1100#

– Ausgabe: #1101#

• oder:

– Eingabe: #11011#

– Ausgabe: #11100#

Turingmaschine: Binärinkrement

WS2007 23

WS2007 24

Bsp.: Erkennen einer Sprache

• Wörter aus der formalen Sprache

L={anbncn | n≥0} werden akzeptiert

– abc

– aabbcc

– aaabbbccc

– aaaabbbbcccc

– ...

L={anbncn | n≥0}

WS2007 25

„Finde den Fehler“

Weitere Ideen…

• Verdopplungsmaschine:

Aus n Strichen mache 2n Striche

• Multipliziermaschine:

aus III#IIII mache xxx#IIII#IIIIIIIIIIII

– Mit x-en mitzählen, wie oft schon addiert

worden ist

• Unterprogramme: Sub-Tabellen…

– Sequenzielle Ausführung von TMs

WS2007 26

WS2007 27

Viele Varianten von TMs...

• Varianten von Turingmaschinen:

– mehrere Eingabebänder

– einseitig begrenztes Band

– Grosses Eingabealphabet

– …

• Aber: Alle TMs sind gleichwertig!

– jedes Alphabet lässt sich beispielsweise

auf {#, 0, 1} reduzieren

WS2007 28

Turing-berechenbare Funktionen

• Partielle Funktion f: INk IN berechnen – Argumente (n1, n2, ..., nk) auf Band kodieren

z.B. als #n1# n2# ... #nk#

– L/S-Kopf ganz links, dann starte TM

• Wenn TM anhält: – Ergebnis ist ab dem Zeichen unter dem L/S-

Kopf ablesbar

– Wird Eingabe akzeptiert, ist das Ergebnis f (n1, n2, ..., nk), sonst:

• TM hält nicht an oder

• unter L/S-Kopf ist keine Zahl

Registermaschine

• Speicher

– Datenspeicher

– Programmspeicher

• Prozessor

– Akkumulator

– Befehlsregister

– Befehlszähler

• Ein/Ausgabe-Einheit WS2007 29

Registermaschine

WS2007 30

WS2007 31

Registermaschine

• Einfaches, abstrahiertes Modell

eines von-Neumann-Rechners

• RM kann alles berechnen, was auch

ein realer Rechner berechnen kann.

• RM kann TM simulieren!

• TM kann RM simulieren!

• Äquivalente Berechnungsmodelle

WS2007 32

Modell-Sprachen

• Einfache modellhafte Sprachen:

– GOTO-Sprache

– WHILE-Sprache

– LOOP-Sprache

• Satz: Jede Turing-berechenbare

Funktion ist auch GOTO und

WHILE-berechenbar

– LOOP ist schwächer…

WS2007 33

GOTO-Programmiersprache

• Wie RM, aber statt Registern Variablennamen, und einfache Syntax:

• Jede numerierte Zeile enthält entweder – Zuweisung eines berechneten Terms an eine

Variable

• x := 2*a + 4*b

– Bedingten oder unbedingten Sprungbefehl

• IF bedingung GOTO zeile

• GOTO zeile

WS2007 34

GOTO: Addition

• Addition zweier natürlicher Zahlen

x = a + b wenn Prozessor nur succ

und nicht + beherrscht:

WS2007 35

WHILE-Programmiersprache

• Programm besteht aus einem von:

– Zuweisung

– bedingte Anweisung

– WHILE-Schleife

– Sequenz von

Programmen

WS2007 36

WHILE-Sprache: Addition

• x = a + b

WS2007 37

WHILE-Sprache: Multiplikation

• e = a * b

WS2007 38

WHILE durch GOTO

• WHILE-Schleife wird durch

bedingten Sprung nachgebildet

GOTO durch WHILE

WS2007 39

WS2007 40

Kleene'sches Theorem

• Äquivalent: Jedes GOTO-Programm

lässt sich in ein WHILE-Programm

umwandeln und umgekehrt

• Kleene'sches

Normalformentheorem:

"Jede berechenbare Funktion kann

mit einer einzigen WHILE-Schleife

programmiert werden."

WS2007 41

LOOP-Programme

• auch FOR-Programme genannt…

• WHILE-Schleife durch FOR-Schleife

ersetzt, aber: Durchlaufanzahl fest!

WS2007 42

Eigenschaften LOOP-Prog.

• Endlicher Durchlauf aller Schleifen

– Schleifenvariable i darf im Body der

Schleife nicht geändert werden!

• Konsequenz:

– LOOP-Programme terminieren immer!

– Start-/Endwert ist immer angegeben

• LOOP nicht so mächtig wie WHILE

– Kein TM-Simulator mit LOOP möglich

WS2007 43

Primitive Rekursion

• Funktion durch Rekursion berechnet,

kommt ohne Zuweisung/Schleifen aus

– z.B. in funktionalen Programmiersprachen

• Definition Primitive Rekursion:

WS2007 44

Primitive Rekursion

• Erlaubt sind dazu noch:

– Funktions-Komposition

– Vertauschen von Argumentpositionen

– Projektion

• Eine Funktion heisst primitiv rekursiv,

wenn sie aus 0, succ() und den

Projektionen von Verkettung und

primitiver Rekursion gebildet werden

kann

WS2007 45

Primitive Rekursion

• Projektion: pk,i : INk → IN

ist definiert durch pk,i(x1,…, xk) = xi

• Verkettung: Ist f n-stellige und g1,…, gn

k-stellige Funktion, so ist die Verkettung f ◦ (g1,…, gn) : IN

k → IN definiert durch:

(f ◦ (g1,…, gn))(x1,…, xk) = f (g1(x1,…, xk),…, gn(x1,…, xk))

Bsp.: Primitive Rekursion

WS2007 46

Bsp. LOOP-Programm

WS2007 47

WS2007 48

Primitive Rekursion als

LOOP-Programm

• Satz: Jede primitiv-rekursive Funktion ist

LOOP-berechenbar

• Jede „vernünftig“ total berechenbare

Funktion ist primitiv rekursiv, wobei

„vernünftig“ bedeutet, dass man die

maximal möglichen Schleifendurchläufe

vorab bestimmen kann.

• Das ist weniger als TM-Berechenbarkeit!

WS2007 49

µ-Rekursion

• Es gibt Probleme, die sich nicht

mehr primitiv-rekursiv lösen lassen

• z.B. Suchprobleme: Suche für (k+1)-

stellige Funktion f das kleinste z, für

das f(z, x1, ..., xk) = true ist

• Argument wird beim rekursiven

Aufruf nicht kleiner, sondern größer!

µ-Rekursion

• Mögliches Problem: Suche bricht

niemals ab – z.B. wenn es kein z

gibt, für das f true liefert

WS2007 50

WS2007 51

µ-Rekursion versus

WHILE-berechenbar

• Beide Klassen stimmen überein:

• Alle µ-rekursiven Funktionen sind

WHILE-berechenbar (und damit auch

GOTO- und Turing-berechenbar)

• Nach Kleene kommt man mit einer

einzigen WHILE-Schleife aus!

• Also gilt:

Jede berechenbare Funktion lässt sich

als µ-rekursive Funktion schreiben

WS2007 52

µ-Rekursion durch WHILE

• Ziemlich offensichtlich:

WS2007 53

Bisher:

• Jede LOOP-berechenbare Funktion ist

total (d.h., terminiert immer!)

• Jede total berechenbare Funktion, für die

mit LOOP-Programmen eine

Abschätzung der max. möglichen

Schleifendurchläufe möglich ist, ist auch

LOOP-berechenbar.

• LOOP-berechenbare Funktion sind

genau die primitiv rekursiven Funktionen.

WS2007 54

Frage:

• Ist jede total berechenbare Funktion

immer durch ein LOOP-Programm

berechenbar?

WS2007 55

Ackermann-Funktion

• totale, berechenbare Funktion

• nicht primitiv rekursiv!

• [Ackermann-Péter]

• = m+1 wenn n=0

a(m,n) = a(n-1,1) wenn m=0

= a(n-1,a(n,m-1)) sonst

Ackermann-Funktion

• Wächst sehr stark an

• Kann von keiner primitiv rekursiven

Funktion nach oben beschränkt

werden

WS2007 56

Ackermann-Funktion

• Verallgemeinerung der

Grundrechenarten:

– a(0,y) = y+1

– a(1,y) = y+2

– a(2,y) = 2y + 3

– a(3,y) = 2y+3-3

– a(4,y) = 2X-3 wobei X=2^…^2 mit

„Turmhöhe“ y+2

WS2007 57

Unlösbare Probleme

WS2007 59

Prinzipiell unlösbare Probleme

• Ein Algorithmus kann angegeben

werden, aber ein Computer kann

das Problem nicht lösen.

• Probleme, die niemals durch

menschliche Erfindungskraft und

technisch-wissenschaftlichen

Fortschritt zu lösen sein werden

WS2007 60

Entscheidbare Menge

• „Eine Menge M heißt rekursiv

entscheidbar oder entscheidbar,

wenn es einen Algorithmus gibt, der

nach endlicher Zeit terminiert und

entscheidet, ob die Eingabe zur

Menge gehört oder nicht."

WS2007 61

Bsp: Entscheidbare Menge:

Goldbach-Vermutung

• "Jede gerade Zahl größer als 2 kann

als Summe zweier Primzahlen

geschrieben werden.„

– Nun als „Goldbach-Eigenschaft“

• [für alle Zahlen bis 1018 überprüft...]

• [Satz von Euklid: es gibt unendlich

viele Primzahlen...]

WS2007 62

Semi-entscheidbare Menge

• Frage: Element in Menge?

– Ja

– Nein

• Eine der beiden Antworten muss in

endlicher Zeit gegeben werden

– Die andere darf unendlich dauern…

WS2007 63

Bsp. (3n+1)-Problem

• „Collatz-Folge“

• Startzahl heißt "wundersam", wenn Folge mit Zahl 1 endet

• Startzahl 6: Folge 3, 10, 5, 16, 8, 4, 2, 1

• Folge kann sehr, sehr lang werden!

• Wundersamkeit ist semi-entscheidbar!

WS2007 64

Bsp. "Game of Life"

• Drei Regeln:

– Geburt: Tote Zelle wird lebendig, wenn

3 der 8 Nachbarn leben

– Überbevölkerung: Zelle stirbt, wenn 4

oder mehr Nachbarn leben

– Vereinsamung: Zelle stirbt, wenn sie

weniger als 2 lebende Nachbarn hat

• Semi-entscheidbar?

WS2007 65

Das Halteproblem

• "Gibt es ein Programm, das als

Eingabe den Quelltext eines zweiten

Programms sowie dessen

Eingabewerte erhält, und dann

entscheiden kann, ob das zweite

Programm terminiert, d.h. nicht

endlos weiterläuft?"

WS2007 66

Halteproblem

• Angenommen, es gibt so eine Fkt:

WS2007 67

Halteproblem

• Dann kann man ein fiese Funktion

test() bauen, die nur dann nicht

terminiert, wenn haltetest JA gibt:

Halteproblem

• Wende nun test auf sich selber an,

also berechne test(test)

– haltetest(test,test) liefert JA weil

test(test) terminiert: Aber dann kann das

WHILE in test() nicht terminieren! –

Widerspruch.

– haltetest(test,test) liefert NEIN: Dann

terminiert das WHILE sofort –

Widerspruch.

WS2007 68

WS2007 69

Halteproblem

• Beide Fälle führen zum Widerspruch,

es gibt aber nur die beiden Fälle, also

kann es die Funktion haltetest nicht

geben!

• Halteproblem semi-entscheidbar:

TM simulieren und JA ausgeben,

wenn sie anhält.

Konsequenzen des

Halteproblems

• „In jedem System, das Turing-

mächtig ist, lassen sich Aussagen

formulieren, die weder bewiesen

noch widerlegt werden können.

Solche Systeme sind grundsätzlich

unvollständig“

• Die Arithmetik ist solch ein System.

WS2007 70

Konsequenzen des

Halteproblems

• Auswirkung auf die

Software-Entwicklung:

• Es kann kein Computerprogramm

geben, das generell überprüft, ob

andere Computerprogramme für alle

Eingaben das korrekte Ergebnis

liefern

WS2007 71

WS2007 72

Zusammenfassung

• Turingmaschine

– Simulator ausprobieren!

• GOTO, WHILE, LOOP

• Unlösbare Probleme

WS2007 73

Organisatorisches...

• Prüfung

– Termine

– Prüfungsfragen

WS2007 74

Quellen

• "Grundlagen der Informatik", Herold,

Lurz, Wohlrab; Pearson Studium

• Wikipedia