close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

19 Wie kann man den Berechnungsbegriff noch charak- terisieren ?

EinbettenHerunterladen
19 Wie kann man den Berechnungsbegriff noch charakterisieren ?
Ausgehend vom Begriff “(Formale) Sprache” sind wir zum “Grammatik”-Begriff gekommen,
mit dem wir die Möglichkeit geschaffen haben, die Wörter einer Sprache zu generieren. Als
Pendant zum Grammatik-Begriff führten wir die “Akzeptoren” ein, d.h. die Automaten-Typen,
die die jeweiligen Sprachklassen akzeptieren/erkennen können.
Im Rahmen der Behandlung von Turing-Maschinen
sahen wir aber auch, dass das Akzeptieren
✁
der Zeichenketten einer Sprache L
✁ * interpretiert werden kann als “Berechnung” der charakteristischen Funktion von L relativ zu *.
Es wurde bereits erwähnt, dass man die Paare (Eingabe, Ausgabe/Ergebnis) als Sprache
auffassen und wieder die Frage des Akzeptierens dieser Sprache stellen kann. In diesem Zusammenhang spricht man eher von “Entscheiden”. Auf damit verbundene Probleme wird an
späterer Stelle noch genauer eingegangen.
Der Versuch, den intuitiven Berechnungsbegriff oder, gleichbedeutend, den “Algorithmus”Begriff zu präzisieren (und nicht das Akzeptieren von Sprachen), war der historische Ausgangspunkt der Überlegungen zu den TM. Weil sich in der Informatik alles um diese Begriffe dreht,
wollen wir sie im Folgenden durch weitere Konzepte beleuchten, die näher an der Erfahrung und
Sprechweise mit Programmiersprachen liegen, insbesondere durch die LOOP-, WHILE- und
GOTO-Berechenbarkeit. Auch hier wird gelten, dass - bis auf LOOP-Berechenbarkeit - die
Konzepte untereinander und zu den TM mit allen Varianten äquivalent sind.
Sei n,m ✂ ✄ . Eine Turing-Maschine M berechnet eine partielle Funktion f : (☎ *)n ✆ (☎ *)+ mit
f( ✝ 1, ✝ 2, ..., ✝ n) = ( ✞ 1, ✞ 2, ..., ✞ m), gdw. M nach endlich vielen Schritten anhält, sich dabei in einem
Endzustand befindet und ( ✞ 1, ✞ 2, ..., ✞ m) auf dem Band steht. Hält M nicht an für die Eingabe ( ✝ 1,
✝ 2, ..., ✝ n) oder hält M in einem Nichtendezustand, weil keine Folgekonfiguration mittels ✟ definiert ist, dann ist f für diese Eingabe undefiniert (deshalb “partiell”).
✁
✁
Sei f eine evtl. partielle Funktion f : ( *)n ✆ ( *)+, also eine Funktion, die an manchen Stellen
nicht definiert sein muss. Genau dann ist f Turing-berechenbar, wenn es eine Turing-Maschine
gibt, die f berechnet.
Ist f total und Turing-berechenbar, dann nennt man f auchtotal rekursiv oder nur rekursiv. (Das
bedeutet, dass die zugehörige Turing-Maschine bei jeder Eingabe stoppt!)
Wegen der o.a. Äquivalenz können wir die folgenden These aufstellen:
Church/Turing-These:
Die von TM und ihren Varianten bzw. durch WHILE- sowie GOTO-Berechenbarkeit erfasste
Klasse von Funktionen stimmt genau mit der Klasse der Funktionen überein, die im intuitiven
Sinn berechenbar sind.
✠
145
LOOP-Berechenbarkeit
19.1
Wir beginnen mit der einfachen Programmiersprache LOOP mit folgender Syntax. Zunächst gibt
es
Variablen:
Konstanten:
Trennsymbole:
Operationszeichen:
Schlüsselwörter:
x, y, z, ..., x0, x1, x2, x3, ...
0, 1, 2 , ...
Wertzuweisung := und Anweisungstrennsymbol ;
+, LOOP, DO, END
Wir verzichten auf “syntaktischen Zucker” wie READ und WRITE. Die weitere Syntax wird so
definiert, wobei c eine Konstante ist:
Jede Wertzuweisung
xi := xj + c
und
xi := xj - c
ist ein LOOP-Programm.
Sind P, P1 und P2 LOOP-Programme, dann auch
P1 ; P 2
und
LOOP xi DO P END
Die Semantik soll nur informell erklärt werden und ist mit einem programmiersprachlichen
Vorverständnis unmittelbar einsichtig:
Soll ein LOOP-Programm eine k-stellige Funktion berechnen, stehen die k Eingabeparameter
in den Variablen x1, x2, ..., xk. Alle anderen haben den Wert 0. Die Variable x0 ist für das Resultat
reserviert. Die Wertzuweisungen werden wie üblich interpretiert. Die Subtraktion xj - c wird so
modifiziert, dass keine negativen Werte auftreten, also ist xj < c bekommt xj den Wert 0.
P1 ; P2 ist die übliche Hintereinanderausführung.
Die Laufschleife LOOP x DO P END ist so zu interpretieren, dass P genau x-mal ausgeführt
wird, auch wenn ggf. x innerhalb von P verändert wird.
146
Definition:
k ✂ ✄ . Eine Funktion f : ✄ k ✆✡✄ heißt LOOP-berechenbar, wenn es ein LOOP-Programm P so
gibt, dass P, gestartet mit den Variablen x1, x2, ..., xk (und alle anderen gleich 0 gesetzt), stoppt
und f(x1, x2, ..., xk) = x0.
Beispiele:
Addition:
Multiplikation:
✠
Anmerkungen:
>
Für xi := xj + 0 kann man auch xi := xj schreiben.
>
Für xi := xj + c mit xj = 0 kann man auch xi := c schreiben.
>
Man kann LOOP um den “Makro-Befehl”
IF x = 0 THEN P END
erweitern, denn dazu gleichwertig ist
y := 1;
LOOP x DO y:= 0 END;
LOOP y DO P END
Die Variable y darf sonst im Programm nicht benutzt werden.
>
LOOP-Programme haben keine Endlosschleifen. Sie terminieren immer, sind also total.
>
Die meisten arithmetischen Funktionen sind LOOP-berechenbar.
>
Zu jedem LOOP-Programm gibt es eine äquivalente TM, die dieselbe Funktion berechnet.
Das Umgekehrte gilt nicht! Also, es gibt Funktionen, die nicht LOOP-berechenbar sind.
Die LOOP-berechenbaren Funktionen sind eine echte Teilmenge der Turing-berechenbaren Funktionen
147
Die Ackermann-Funktion (1928) als Beispiel für eine nicht LOOP-berechenbare Funktion:
ack(0, y) = y+1
ack(x, 0) = ack(x-1, 1)
ack(x, y) = ack(x-1, ack(x, y-1))
148
(Diese Seite ist absichtlich leer.)
149
WHILE-Berechenbarkeit
19.2
Die Programmiersprache LOOP wird durch ein Konstrukt WHILE erweitert, das syntaktisch
wie folgt definiert ist und die übliche Semantik besitzt:
WHILE x ☛ 0 DO P END
P wird solange ausgeführt, bis x = 0 ist. Die Variable x darf in P benutzt und insbesondere
verändert werden.
So kommen wir zur Programmiersprache WHILE.
Definition:
Sei k ✂ ✄ . Eine Funktion f : ✄ k ✆✡✄ heißt WHILE-berechenbar, wenn es ein WHILE-Programm
P so gibt, dass P, gestartet mit den Variablen x 1, x2, ..., xk (und alle anderen gleich 0 gesetzt),
✠
stoppt und f(x1, x2, ..., xk) = x0.
Anmerkungen:
>
Die Ackermannfunktion ist WHILE-berechenbar.
>
Weil
y := x;
WHILE y > 0 DO P; y := y - 1; END
äquivalent ist zu
LOOP x DO P END
kann man auf das LOOP-Konstrukt verzichten.
>
Zu jedem WHILE-Programm, das eine Funktion f berechnet, gibt es eine äquivalente TM,
die f berechnet. Das Umgekehrte gilt ebenfalls.
150
19.3
GOTO-Berechenbarkeit
Programme der GOTO-Programmiersprache
Anweisungen”
15
bestehen aus einer Folge von “markierten
M1 : A1 ;
M2 : A2 ;
....... ;
Mk : Ak ;
wobei für Ai Folgendes zugelassen ist:
Wertzuweisungen
unbedingte Sprünge
bedingte Sprünge
Stopp-Anweisung
xi := xj + c und xi := xj - c
GOTO Mj mit 1 ☞ j ☞ k
IF x = c GOTO Mj mit 1 ☞ j ☞ k
HALT
Wenn Marken nie angesprungen werden, kann man sie auch weglassen. Es würde genügen, nur
den Test auf x = 0 zuzulassen.
Die Semantik von GOTO-Programmen ist wie gewohnt definiert.
Durch rückwärts gerichtete Sprünge kann man die WHILE-Anweisung simulieren, was zu tun
normalerweise verpönt ist:
M1 :
M2 :
IF x = 0 THEN GOTO M2 ;
P;
GOTO M1 ;
.....
So ist klar, dass man jedes WHILE-Programm in ein GOTO-Programm überführen kann.
Auch die Umkehrung gilt (wenn auch etwas umständlicher zu beweisen): Jedes GOTOProgramm kann man durch ein WHILE-Programm simulieren. Man kann beweisen (“Kleenesche
Normalform”), dass man jedes Programm so umformen kann, dass nur eine einzige WHILEAnweisung vonnöten ist.
Da die Äquivalenz zwischen Turing-Berechenbarkeit und WHILE-Berechenbarkeit schon
erwähnt wurde, gilt - wie zu erwarten - dass auch GOTO-Berechenbarkeit und Turing-Berechenbarkeit die gleiche Menge von Funktionen umfasst.
15
Zur Zeit der hitzigen Diskussionen in den 1970-ern über Strukturiertes Programmieren hätte man
sie wohl als PFUI-Programmiersprache bezeichnet.
151
(Die Seite ist absichtlich leer.)
152
Weitere Berechenbarkeit-Kalküle
19.4
Die Suche nach einer Formalisierung des Berechenbarkeit/Algorithmus-Begriffs hat noch
weiter Kalküle gebracht, so die
>
primitiv rekursiven Funktionen, die mit der Klasse der LOOP-berechenbaren Funktionen
übereinstimmen
>
✌ -rekursiven Funktionen, eine Erweiterung der primitiv rekursiven Funktionen um den
>
✍ -Kalkül, die Basis der Programmiersprache Lisp
>
.......
✌ -Operator, der ein Pendant zur WHILE-Anweisung ist
Wieder gilt: Die Klasse der ✎ -rekursiven Funktionen, der durch den ✏ -Kalkül beschreibbaren
Funktionen, der WHILE-, GOTO- und Turing-berechenbaren Funktionen sind identisch. Oder
anders ausgedrückt: Eine Funktion ist genau dann ✎ -rekursiv, wenn sie WHILE-berechenbar oder
Turing-berechenbar oder ✏ -berechenbar oder GOTO-berechenbar ist.
Wegen der Äquivalenz derartig unterschiedlicher Ansätze ist die Church/Turing-These gerechtfertigt. Allerdings übertragen sich die “Entscheidbarkeitsprobleme” im einen Kalkül in analoger
Weise auf die anderen.
Es gibt dabei u.a. so hübsche Theoreme wie: Man kann entweder entscheiden, ob bei einer
Programmiersprache P die Programme eine Endlosschleife haben, oder man kann in P den
Compiler für P schreiben. Beides zusammen ist nicht möglich.
153
Document
Kategorie
Sport
Seitenansichten
9
Dateigröße
58 KB
Tags
1/--Seiten
melden