Ausgewählte Kapitel Diskreter Mathematik mit Anwendungen

Lektion 5: Berechenbarkeit
Wahlpflichtfach Bachelor Informatik 4. Semester
Ausgewählte Kapitel Diskreter Mathematik
mit Anwendungen
Lektion 5: Berechenbarkeit
Kurt-Ulrich Witt
Sommersemester 2011
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
1/13
Lektion 5: Berechenbarkeit
Inhaltsverzeichnis
Churchsche These
Ackermannfunktion
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
2/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Weitere Berechenbarkeitskonzepte und deren Äquivalenz
Turingmaschinen
λ-Kalkül
Markov-Algorithmen
URM-Programme
Goto-Programme
While-Programme
...
Es gilt: Sei
X ∈ { Turingmaschinen, λ-Kalkül, Markov-Algorithmen, URM-Programme,
Goto-Programme, While-Programme, . . . }
dann ist
µR = { f : Nk0 → N0 | k ≥ 0, f ist X -berechenbar }
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
3/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Churchsche These; Definition von P und R
Die Klasse µR der µ-rekursiven Funktionen ist genau die
Klasse der im intuitiven Sinne berechenbaren Funktionen.
Wir bezeichnen mit
P = { f | f : Nk0 → N0 , k ≥ 0, f ist im intuitiven Sinn berechenbar }
die Klasse der partiell berechenbaren Funktionen. Die
Churchsche These besagt, dass µR = P ist.
Wir bezeichnen mit
R = { f | f : Nk0 → N0 , k ≥ 0, f ∈ P und f ist total }
die Klasse der total berechenbaren Funktionen.
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
4/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Zusammenhang der Klassen PR, R und P
Wir wissen:
PR ⊆ R ⊂ P
Frage: Gilt auch R ⊆ PR und damit PR = R?
Antwort: Nein!
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
5/13
Churchsche These
Ackermannfunktion
Lektion 5: Berechenbarkeit
Idee
Folge stark anwachsender Funktionen ϕi (a, b), i ≥ 0:
b
b + 1, a + b, a · b, a , . . .
Diese Folge hat die Eigenschaft, dass bei jedem Glied die Operation des vorherigen Gliedes (b − 1)-mal auf a
angewandt wird. So bedeutet a + b, dass (b − 1)-mal 1 zu a + 1 addiert wird:
a + b = a + 1 +1 + 1 + . . . + 1
{z
}
|
(b−1)-mal
a · b bedeutet, dass (b − 1)-mal a zu a addiert wird:
a · b = a +a + a + . . . + a
|
{z
}
(b−1)-mal
b
Und a bedeutet, dass (b − 1)-mal a mit a multipliziert wird:
b
a = a ·a · a · . . . · a
|
{z
}
(b−1)-mal
Für das nächste Folgenglied gibt es keine gängige mathematische Notation. Deshalb ist in (??) an der Stelle . . .
angegeben. Dieses Folgendglied ergibt sich, indem (b − 1)-mal a mit sich selbst fortgesetzt potenziert wird:
a
Kurt-Ulrich Witt
a·
··
a
Diskrete Mathematik • Lektion 5
6/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Definition (Rózsa Péter)


x =0
 y + 1,
A(x, y ) = A(x − 1, 1),
x=
6 0∧y =0


A(x − 1, A(x, y − 1)), sonst
Es gilt z.B. für alle n ≥ 0:
A(1, n) = n + 2
A(2, n) = 2n + 3
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
7/13
Churchsche These
Ackermannfunktion
Lektion 5: Berechenbarkeit
Definition der Funktion ack
Familie { Ai }i≥0 von Funktionen Ai : N0


 1,
A0 (x) = 2,


x + 2,
→ N0 :
x =0
x =1
sonst
An+1 (x) = Axn (1)
= An (An (. . . An (1) . . .))
{z
}
|
x -mal
sowie
ack : N0 → N0
mit
ack (x) = Ax (x)
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
8/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Beispiele
ack (0) = A0 (0) = 1
ack (1) = A1 (1) = A10 (1) = 2
ack (2) = A2 (2) = A21 (1) = A1 (A1 (1)) = A1 (2)
= A20 (1) = A0 (A0 (1)) = A0 (2) = 2 + 2 = 4
ack (3) = A3 (3) = A32 (1) = A2 (A2 (A2 (1))) = A2 (A2 (2)) = A2 (4)
= A41 (1) = A1 (A1 (A1 (A1 (1)))) = A1 (A1 (A1 (2))) = A1 (A1 (4))
= A1 (A1 (4)) = A1 (A40 (1)) = A1 (A0 (A0 (A0 (A0 (1)))))
= A1 (A0 (A0 (A0 (2)))) = A1 (A0 (A0 (4))) = A1 (A0 (6))
= A1 (8) = . . .
..
.
= 16
ack (4) = . . .
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
9/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Beispiele
Es gilt A2 (x) = 2x für alle x ∈ N0 .
Übung: Beweis!
x-mal iterierte Zweierpotenz iter 2 : N0 → N0 definiert durch
iter 2 (n + 1) = 2iter 2 (n) , n ≥ 1
iter 2 (0) = 1
iter 2 (1) =
iter 2 (2) =
iter 2 (3) =
iter 2 (4) =
2iter 2 (0) =
iter 2 (1)
2
iter 2 (2)
2
=
=
2iter 2 (3) =
21 =
2
2
2 =
22
2
22
22
4
4
=
2 =
16
=
216 =
65 536
Es gilt A3 (x) = iter 2 (x) für alle x ∈ N0 .
Übung: Beweis!
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
10/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
Beispiele
ack (4) = A4 (4) = A43 (1) = A33 (A3 (1))
= A33 (2) = A23 (A3 (2))
= A23 (4)) = A3 (A3 (4))
= A3 (65536) = iter 2 (65536)
22
=2
.2
..
(65536-mal iterierte Zweierpotenz)
>> 2350 ≈ Anzahl der Atome im „bekannten“ Universum
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
11/13
Lektion 5: Berechenbarkeit
Churchsche These
Ackermannfunktion
PR ⊂ R
Satz: Zu jeder primitv-rekursiven Funktion f : N0 → N0
existiert ein xf ∈ N0 , so dass ack (x) > f (x) für alle x ≥ xf ist.
Folgerung: a) Es ist ack ∈ R − PR.
b) Es gilt PR ⊂ R sowie
c) PR ⊂ R ⊂ P
Kurt-Ulrich Witt
Diskrete Mathematik • Lektion 5
12/13
Lektion 5: Berechenbarkeit
Kurt-Ulrich Witt
Churchsche These
Ackermannfunktion
Diskrete Mathematik • Lektion 5
13/13

Download Report