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
© Copyright 2025 ExpyDoc