Vortrag 1 Grundbegri e der Berechenbarkeitstheorie · I Es gibt eine 1-st. partiell berechenbare...

Vortrag 1

Grundbegriffe der Berechenbarkeitstheorie

Seminar Theor. Informatik (WS 2010/11) Grundbegriffe der Berechenbarkeitstheorie 1 / 39

Ubersicht

In diesem einfuhrenden Vortrag werden Grundlagen aus derBerechenbarkeitstheorie kurz zusammengefasst, die bereits in derVorlesung “Einfuhrung in die Theoretische Informatik” ausfuhrlicherbehandelt wurden und die Grundlage fur die folgenden Vortrage sind.

1 Der intuitive Algorithmenbegriff und die Grundbegriffe derBerechenbarkeitstheorie (Berechenbarkeit, Entscheidbarkeit,Aufzahlbarkeit)

2 Formalisierung: Turingmaschinen und die Church-Turing-These

3 Universelle Maschinen und universelle Funktionen

4 Approximationen partiell berechenbarer Funktionen und aufzahlbarerMengen

5 Das Rekursionstheorem (Fixpunktsatz)


Teil 1:Grundbegriffe der Berechenbarkeitstheorie

Wir fuhren kurz die Begriffe der Berechenbarkeit, Entscheidbarkeitund Aufzahlbarkeit ein.

Dann betrachten wir die grundlegenden Beziehungen zwischen diesenKonzepten.


Algorithmen

Ein Algorithmus oder eine Rechenvorschrift ist ein effektives Verfahren

zur Transformation von DatenBestimme den grossten gemeinsamen Teiler von x und y !oder Berechne die Summe von x und y !

oder zur Uberprufung von Eigenschaften von DatenIst x eine Primzahl?

oder zur Generierung (moglicherweise unendlicher) DatenmengenZahle alle Primzahlen auf!

NB: Der Algorithmenbegriff ist kein formaler mathematischer Begriff. Einemogliche Formalisierung liefert der Begriff der Turingmaschine.


Daten und Zahlen

Hierbei sind Daten endliche Darstellungen mathematischer Objekte.

Im Rahmen des Seminars werden die betrachteten Daten naturlicheZahlen (oder endliche Tupel naturlicher Zahlen) sein.

Genauer: Nicht die Zahlen selbst sondern deren Unar-, oder Binar-oder Dezimaldarstellung.

Die Arbeitsweise von Algorithmen hangt namlich durchaus von dergewahlten Zahldarstellung ab (Beispiel: Addition).

Da es aber Algorithmen zur wechselseitigen Uberfuhrung derZahldarstellung gibt, spielt fur die Frage der im Folgendenbetrachteten Berechenbarkeit (Entscheidbarkeit, Aufzahlbarkeit) diegewahlte Zahldarstellung keine Rolle.


Berechenbarkeit, Entscheidbarkeit und Aufzahlbarkeit

Ein Berechnungsverfahren fur eine Funktion f : Nn → N ist ein AlgorithmusB, der bei Eingabe von ~x = (x1, . . . , xn) ∈ Nn den Wert f (~x) berechnet undausgibt.

f : Nn → N heisst berechenbar, wenn es ein Berechnungsverfahren fur f gibt.

Ein Entscheidungsverfahren fur eine (n-dim.) Menge A ⊆ Nn ist einAlgorithmus E , der bei Eingabe von ~x = (x1, . . . , xn) ∈ Nn feststellt, ob ~x inA liegt (und entsprechend JA oder NEIN ausgibt).

A ⊆ Nn heisst entscheidbar, wenn es eine Entscheidungsverfahren fur A gibt.

Ein Aufzahlungsverfahren fur eine (n-dim.) Menge A ⊆ Nn ist einAlgorithmus A, der (ohne Eingabe) die Elemente von A (in beliebigerReihenfolge) ausgibt.

A ⊆ Nn heisst aufzahlbar, wenn es ein Aufzahlungsverfahren fur A gibt.


Partielle Berechenbarkeit

Eine partielle (n-st.) Funktion ψ : Nn → N ist eine Funktion (nach N), derenDefinitionsbereich (domain) dom(ψ) eine (nicht notwendigerweise echte)Teilmenge von Nn ist.

Ist dom(ψ) = Nn, so ist ψ eine totale Funktion.

Notation:

I ψ, ϕ, etc.: partielle Funktionen; f , g , etc.: totale Funktionen.I ψ(~x) ↓ :⇔ ~x ∈ dom(ψ) (ψ(~x) definiert)ψ(~x) ↑ :⇔ ~x 6∈ dom(ψ) (ψ(~x) undefiniert)

Ein (partielles) Berechnungsverfahren fur eine partielle Funktion ψ : Nn → Nist ein Algorithmus B, der bei Eingabe ~x = (x1, . . . , xn) ∈ dom(ψ) den Wertψ(~x) berechnet und ausgibt. Fur ~x 6∈ dom(ψ) liefert B keine Ausgabe undterminiert moglicherweise nicht (d.h. lauft unendlich lange).

Eine partielle Funktion ψ : Nn → N ist partiell berechenbar, wenn es einepartielles Berechnungsverfahren fur ψ gibt.

NB Eine totale Funktion f is genau dann berechenbar, wenn f partiellberechenbar ist.


Beziehungen: Berechenbarkeit vs. Aufzahlbarkeit

Eine partielle Funktion ψ : Nn → N ist genau dann partiell berechenbar,wenn deren Graph

Graph(ψ) = {(~x , y) : ψ(~x) = y}

aufzahlbar ist.

NB Fur totales f , ist der Graph genau dann aufzahlbar, wenn erentscheidbar ist.

Fur totales f sind also folgende Aussagen aquivalent:

I f berechenbarI Graph(f ) aufzahlbarI Graph(f ) entscheidbar


Beziehungen: Entscheidbarkeit vs. Berechenbarkeit undAufzahlbarkeit

Eine Menge A ⊆ Nn ist genau dann entscheidbar, wenn derencharakteristische Funktion

cA(~x) =

{1 falls ~x ∈ A

0 sonst

berechenbar ist.

Eine Menge A ⊆ Nn ist genau dann entscheidbar, wenn die Menge A undderen Komplement A = Nn \ A aufzahlbar sind.

Insbesondere ist also jede entscheidbare Menge aufzahlbar. (Die Umkehrunggilt i.a. nicht! Siehe z.B. das in Vortrag 2 behandelte Halteproblem!)


Beziehungen: Entscheidbarkeit vs. Berechenbarkeit undAufzahlbarkeit (Forts.)

Eine Menge A ⊆ Nn ist genau dann entscheidbar, wenn A monotonaufzahlber ist.

Eine nichtleere Menge A ⊆ N ist genau dann entscheidbar, wenn A derWertebereich einer (1-st.) schwach monotonen berechenbaren Funktion ist.

Eine unendliche Menge A ⊆ N ist genau dann entscheidbar, wenn A derWertebereich einer (1-st.) streng monotonen berechenbaren Funktion ist.


Beziehungen: Aufzahlbarkeit vs. Berechenbarkeit

Fur eine Menge A ⊆ Nn sind folgende Aussagen aquivalent:

I A is aufzahlbar.

I Die partielle charakteristische Funktion χA von A

χA(~x) =

{1 falls ~x ∈ A

↑ sonst.

ist partiell berechenbar.

I A ist der Definitionsbereich einer partiell berechenbaren Funktion.


Beziehungen: Aufzahlbarkeit vs. Berechenbarkeit (Forts.)

Fur 1-dim. Mengen erhalten wir weitere Charakterisierungen der Aufzahlbarkeit:

Fur eine Menge A ⊆ N sind folgende Aussagen aquivalent:

I A is aufzahlbar.

I A ist der Wertebereich (range) einer (1-st.) partiell berechenbarenFunktion.

I Es gibt eine 1-st. partiell berechenbare Funktion ψ mitA = dom(ψ) = range(ψ).

I A = ∅ oder A ist der Wertebereich einer (1-st.) totalen berechenbarenFunktion.

I A ist endlich oder A ist der Wertebereich einer (1-st.) totaleninjektiven berechenbaren Funktion.


Beziehungen: Aufzahlbarkeit vs. Entscheidbarkeit

PROJEKTIONSLEMMA. Eine Menge A ⊆ Nn ist genau dann aufzahlbar, wenn Adie Projektion einer entscheidbaren Menge B ⊆ Nn+1 ist:

~x ∈ A ⇔ ∃ y [(~x , y) ∈ B]

(D.h. aufzahlbare Mengen sind gerade Suchprobleme mit entscheidbaremLosungsraum.)


Teil 2:Formalisierung des Berechenbarkeitsbegriffes:

Turingmaschinen und die Church-Turing-These

Wir rufen das Turingmaschinenmodell kurz in Erinnerung.

Hiermit wird der Berechenbarkeitsbegriff formalisiert.

Da sich Entscheidbarkeit und Aufzahlbarkeit auf die (partielle)Berechenbarkeit zuruckfuhren lassen, erhalten wir so auch Formalisierungendieser Begriffe.

Die Church-Turing-These besagt, dass die Formaliserungen adaquat sind.


Schematische Darstellung einer Turingmaschine


Intuitive Beschreibung der Komponenten einerTuringmaschine

SPEICHER (STRUKTUR, OPERATIONEN)• Nach beiden Seiten hin unendliches, in Felder aufgeteiltes Band.• Jedes Feld ist mit einem Buchstaben aus dem Bandalphabet Γ

beschrieben.(Leere Felder sind mit dem Blank b (Leerzeichen) beschriftet.)

• Der Zugriff auf die Daten erfolgt mit einem Lese/Schreibkopf,der auf einem Feld (dem Arbeitsfeld) sitzt und dessen Inschriftlesen und/oder uberschreiben kann.Danach kann der Kopf um ein Feld (nach links oder rechts)verlegt werden.

In einem Rechenschritt wird(1) die Inschrift des Arbeitsfeldes gelesen(2) die Inschrift des Arbeitsfeldes uberschrieben

(eventuell mit der alten Inschrift)(3) das Arbeitsfeld (um ein Feld nach links oder rechts) verlegt

(oder beibehalten)



EIN- UND AUSGABE

Ein- und Ausgabe sind Worter uber festgelegtem Eingabe- bzw.Ausgabealphabet. (Diese Alphabete sind Teil des Bandalphabets.)

EINGABE

• Die Eingabe wird rechts des Arbeitsfeldes auf das ansonstenleere Band geschrieben.(Dabei werden mehrere Eingaben durch Blanks getrennt.)

Da die Turingmaschine auf Wortern operiert, mussen Zahleingabendurch ihre Darstellungen ersetzt werden. Wir benutzen hierbei furdie Zahl n die Unardarstellung n = 1n.



AUSGABE

• Die Ausgabe wird dem Band rechts des Arbeitsfeldes entnommen.Genauer: Die Ausgabe ist das langste Wort uber dem Ausgabe-alphabet, das direkt rechts des Arbeitsfeldes steht.


Intuitive Beschreibung der Komponenten einerTuringmaschineSTEUERUNG (PROGRAMM)

• Die Maschine befindet sich zu jedem Zeitpunkt in einem vonendlich vielen moglichen (Programm-)Zustanden.Zu Beginn der Rechnung ist die Maschine in einemausgezeichneten Startzustand.• Die Rechenschritte der Maschine werden durch eine endliche Folge

von Instruktionen, dem Programm, festgelegt.• Eine Instruktion ist dabei eine bedingte Anweisung der folgenden Form:Falls die Maschine im Zustand z ist und der Buchstabe a auf demArbeitsfeld steht, so uberdrucke das Arbeitsfeld mit dem Buchstabena′, bewege den LS-Kopf nach links (oder rechts oder lasse ihn stehen)und gehe in den neuen Zustand z ′.• Zu jeder Bedingung (Paar aus Zustand und Inschrift des Arbeitsfeldes)

gibt es hochstens eine zutreffende Instruktion (→ Determinismus).Das Programm lasst sich daher auch als eine partielle Funktion

δ : Z × Γ→ Γ× Bew × Z

darstellen.

• Lasst sich keine Instruktion anwenden, ist die Rechnung beendet.Seminar Theor. Informatik (WS 2010/11) Grundbegriffe der Berechenbarkeitstheorie 19 / 39

Formale Spezifikation einer Turingmaschine

FORMALE SPEZIFIKATION EINER TURINGMASCHINE M = (Γ,Z , z0, δ)zur Berechnung einer (partiellen) Funktion ψ : Nm → N:

(Ein- und Ausgabealphabet sind {1}, da wir ja eine Zahl n durch n = 1n

darstellen.)

Γ ist ein (endliches) Alphabet, das zumindest die Zeichen 1 und b (Blank,Leerzeichen) enthalt, genannt das Bandalphabet von M.

Z ist eine endliche Menge, genannt die Zustandsmenge von M,

z0 ist ein Element aus Z , genannt der Startzustand,

δ ist eine partielle Funktion δ : Z × Γ→ Γ× Bew × Z , genannt dasProgramm oder die Ubergangsfunktion, wobei Bew = {L,S ,R} die Mengeder Bewegungen ist.


Arbeitsweise einer Turingmaschine

Die Turingmaschine M = (Γ,Z , z0, δ) zur Berechnung einer (partiellen) Funktionψ : Nm → N arbeitet in Schritten, wobei die aktuelle Gestalt der Maschine injedem Schritt durch eine Konfiguration beschrieben ist.Hierbei besteht jede Konfiguration aus dem aktuellen Zustand und dem aktuellenSpeicher (= Bandinschrift + Position des Arbeitsfeldes):

Startkonfiguration ist bei Eingabe ~x = (x0, . . . , xm) das Paar(z0, . . . b b 1x0 b . . . 1xm b b . . . )

Die Nachfolgekonfiguration einer Konfiguration wird durch das Programm δbestimmt (wie zuvor intuitiv beschrieben; wir verzichten auf die formaleDefinition).

Gibt es zu einer Konfiguration keine Nachfolgekonfiguration, so stoppt (halt,terminiert) die Maschine M und die Ausgabe der zuletzt erreichtenKonfiguration ist der Wert ψ(~x) der von M berechneten Funktion. (Wirdkeine Stoppkonfiguartion erreicht, so terminiert M nicht und ψ(~x) istundefiniert.)

Die von M berechnete (partielle) m-st. Funktion wird mit ϕ(m)M bezeichnet.


Turingberechenbarkeit

Eine (partielle) n-st. Funktion ψ : Nn → N heisst (partiell)Turing-berechenbar oder (partiell) rekursiv, wenn es eine Turingmaschine M

gibt, die ψ berechnet, d.h. fur die ψ = ϕ(m)M gilt.

Eine Menge A ⊆ Nn heisst Turing-entscheidbar oder rekursiv, wenn diecharakteristische Funktion von A Turing-berechenbar ist.

Eine Menge A ⊆ Nn heisst Turing-aufzahlbar oder rekursiv aufzahlbar (r.a.),wenn A der Definitionsbereich einer n-st. partiell Turing-berechenbarenFunktion ist.


Die Church-Turing These

Die Church-Turing-These besagt, dass eine Funktion genau dann im intuitivenSinne (partiell) berechenbar ist, wenn sie (im formalen, mathematischen Sinne)(partiell) Turing-berechenbar ist:

CHURCH-TURING-THESE. ψ ist genau dann (partiell) berechenbar, wenn ψ(partiell) Turing-berechenbar ist.

FOLGERUNG. A ist genau dann entscheidbar (aufzahlbar), wenn ATuring-entscheidbar (Turing-aufzahlbar) ist.

Im Folgenden werden wir die Church-Turing-These annehmen!


Teil 3:Universelle Maschinen und Funktionen

Wir normieren zunachst Turingmaschinen zur Berechnungzahlentheoretischer Funktionen und ordnen jeder derart normierten Maschineeine Godelnummer (Code) zu.

Eine universelle Turingmaschine simuliert dann alle normierten Maschinen.Die von ihr berechnete partielle Funktion ist universell fur die Klasse derpartiell berechenbaren Funktionen (gegebener Stelligkeit).


Normierung von Turingmaschinen

Zwei Turingmaschinen M und M ′ zur Berechnung zahlentheoretischerFunktionen heißen aquivalent, falls sie fur jede Stelligkeit m ≥ 1 dieselbe

partielle Funktion berechnen, d.h. falls ϕ(m)M = ϕ

(m)M′ fur alle m ≥ 1 gilt.

Zu einer gegebenen Turingmaschine M = (Γ,Z , z0, δ) kann mann leicht undeffektiv eine aquivalente Maschine M ′ = (Γ′,Z ′, z ′0, δ

′) konstruieren mit

I Γ′ = {0, 1, 2}, wobei 2 das Leerzeichen b ist.I Z ′ = {0, . . . , k} fur geeignetes k ≥ 0I z ′0 = 0

Weiter ist kein Zustand z ′ von M ′ uberflussig (d.h. zu z ′ gibt es a, a′, z ′′,Bmit δ′(z ′, a) = (a′,B, z ′′) oder δ′(z ′′, a) = (a′,B, z ′)).

Eine Turingmaschine diesen Typs heisst normiert.

Es genugt daher normierte Turingmaschinen zu betrachten.

Im Folgenden gehen wir stillschweigend davon aus, dass alleTuringmaschinen normiert sind.


Godelnummern (normierter) Turingmaschinen

Eine normierte Turingmaschine M ist durch ihre Programmfunktion

δ : {0, . . . , k} × {0, 1, 2} → {0, 1, 2} × Bew × {0, . . . , k}

bestimmt.

Ersetzt man die Bewegungen R, L,S durch die Zahlen 0, 1, 2, so kann manjede Programmzeile durch ein Zahltupel

(z , a, a′, b, z ′) ∈ {0, . . . , k} × {0, 1, 2} × {0, 1, 2} × {0, 1, 2} × {0, . . . , k}

oder durch das entsprechende Binarwort 1z+101a+101a′+101b+101z′+1

darstellen.

Die Programmfunktion insgesamt lasst sich dann durch die Binarzahl

δ := 1 0 0 δ0 0 0 δ1 0 0 . . . δp

beschreiben, wobei die Binarworter δ0, . . . , δp die Programmzeilen von δw.o. kodieren.

δ heisst Godelnummer von M.


Godelnummern von Turingmaschinen und Indizes partiellrekursiver Funktionen

Wir bezeichnen die (normierte) Turingmaschine mit Godelnummer e mit Me

(oder Pe) und wir bezeichnen die von Me berechnete partielle m-st.

Funktion ϕ(m)Me

kurz mit ϕ(m)e . (Weiter schreiben wir statt ϕ

(1)e kurz ϕe .)

Man beachte, dass man zu einer normierter Turingmaschine M dieGodelnummer e effektiv berechnen kann. Umgekehrt kann man fur einegegebene Zahl e entscheiden, ob diese Godelnummer einer Turingmaschineist und gegebenenfalls die zugehorige Turingmaschine Me effektiv angeben.

Ist e keine Godelnummer so identifizieren wir Me mit einer festenTuringmaschine M, die bei keiner Eingabe terminiert.

Es ist also {Me}e≥0 eine Aufzahlung aller (normierten) Turingmaschinen und

{ϕ(m)e }e≥0 eine Aufzahlung aller m-stelligen partiell rekursive Funktionen.

(Hierbei ist ϕ(m)e die nirgends definierte Funktion, falls e keine Godelnummer

ist.)


Universelle Turingmaschinen und universelle partiellrekursive Funktionen

SATZ UBER DIE EXISTENZ UNIVERSELLER TURINGMASCHINEN. Es gibteine Turingmaschine U die sich bei Eingabe (e,~x) wie die e-te TuringmaschineMe bei Eingabe ~x verhalt, d.h.

ϕ(m+1)U (e,~x) = ϕ

(m)Me

(~x) = ϕ(m)e (~x)

(fur alle m ≥ 0, e ≥ 0,~x ∈ Nm).

KOROLLAR (SATZ UBER DIE EXISTENZ UNIVERSELLER PART. REK.FUNKTIONEN oder AUFZAHLUNGSSATZ FUR DIE PARTIELL REKURSIVENFUNKTIONEN) Fur jedes m ≥ 1 gibt es eine (m + 1)-st. partiell rekursiveFunktion ϕ(m), deren Zweige gerade die m-st. partiell rekursiven Funktionen sind.Namlich

ϕ(m)(e,~x) = ϕe(~x) (fur alle (e,~x) ∈ Nm+1)

ist partiell rekursiv.


Universelle Turingmaschinen und universelle partiellrekursive Funktionen: Beweis

BEWEISIDEE. Verwendet man die Church-Turing These, so beweist manzunachst das Korollar indem man beobachtet, dass die Funktionϕ(m)(e,~x) := ϕe(~x) partiell berechenbar also auch part. rek. ist, und schliessthieraus (mit C-T-These) auf die Existenz einer Turingmaschine U, die ϕ(m)

berechnet.

Ohne Church-Turing These konstruiert man die Maschine U direkt, wobei U beiEingabe (e,~x) zunachst aus e die Binardarstellung von e konstruiert und mitderen Hilfe Me auf Eingabe ~x Schritt-fur-Schritt simuliert (s. VorlesungTheoretische Informatik).


Uniforme Rekursivitat

Eine Folge {ψe}e≥0 von partiell rekursive Funktionen (fester Stelligkeit) heisstuniform rekursiv, wenn die Funktion ψ, deren Zweige die Funktionen ψe sind (d.h.die Funktion ψ(e,~x) = ψe(~x)) partiell rekursiv ist.

Entsprechend heisst eine Menge Ψ von partiell partiell rekursiven Funktionen(fester Stelligkeit) uniform rekursiv, falls es eine partiell rekursive Funktion ψ mitΨ = {ψe : e ≥ 0} gibt.

Der Satz uber die Existenz universeller partiell rekursiver Funktionen besagtgerade, dass fur jedes m ≥ 1 die Klasse aller m-st. part. rek. Funktionen uniformrekursiv ist.

Auf der anderen Seite kann man durch ein einfaches Diagonalargument zeigen,dass die Klasse aller m-st. total rekursiven Funktionen nicht uniform rekursiv ist.


Teil 4:Approximationen partiell berechenbarer Funktionen


Approximationen partiell rekursiven Funktionen

Da Turingmaschinen effektiv und in Schritten arbeiten, kann man effektivfeststellen, ob eine Turingmaschine M bei Eingabe ~x innerhalb einer vorgegebenenSchrittzahl s stoppt und gegebenfalls den Wert von ϕM(x) effektiv bestimmen.

Wir benutzen folgende Notation (~x = (x0, . . . , xm−1))

ϕe,s(~x) = y :⇔ x0, . . . , xm−1, y , e < s & Me stoppt bei Eingabe~x in ≤ s Schritten und ϕe(~x) = y

Es gilt:

lims→∞ ϕe,s(~x) = ϕe(~x)

Das heisst, dass ϕe,s(~x) = ϕe(~x) fur alle hinreichend grossen s gilt.

Weiter gilt: ϕe,s(~x) = y ⇒ ∀ s ′ ≥ s [ϕe(~x) = ϕe,s′(~x) = y ]

Die Relationen {(e,~x , s) : ϕe,s(~x) ↓} und {(e,~x , y , s) : ϕe,s(~x) = y} sindentscheidbar. (Die Relationen {(e,~x) : ϕe(~x) ↓} und {(e,~x , y) : ϕe(~x) = y}sind dagegen nur aufzahlbar aber nicht entscheidbar; s. Vortrag 2.)


Teil 5:Das Rekursionstheorem (Fixpunktsatz)


Godelnummerierungen der partiell rekursiven Funktionen

DEFINITION. Eine Godelnummerierung oder Standardaufzahlung der m-st.partiell rekursiven Funktionen ist eine universelle Funktion ψ fur diese Klasse (d.h.eine (m + 1)-st. partiell rekursive Funktion ψ, deren Zweige gerade die m-st.partiell Funktionen sind) mit folgender Eigenschaft:Zu jeder (m + 1)-st. partiell rekursiven Funktion ψ gibt es eine total rekursiveFunktion h : N→ N mit ψe = ψh(e) fur alle e (h heisst Ubersetzungsfunktion von

ψ nach ψ).

SATZ. ϕ(m) ist eine Godelnummerierung der m-st. partiell rekursiven Funktionen.

BEWEISIDEE. Aus einer Turingmaschine M zur Berechnung von ψ kann maneffektiv Turingmaschinen M ′e angeben, die ψe berechnen. (Namlich M ′e schreibtzunachst 1e vor die gegebenen Eingaben und simuliert dann M.) Die Funktion hzur Berechnung des Index von M ′e ist daher berechenbar und damit nachC-T-These rekursiv. Nach Definition gilt aber ψe = ϕM′

e= ϕMh(e)

= ϕh(e).


Godelnummerierungen der partiell rekursiven Funktionen

Godelnummerierungen haben interessante Eigenschaften, die nicht alleuniversellen Funktionen haben. Z.B. gilt fur alle Godelnummerierungen:

Jede partiell rekursive Funktion besitzt unendlich viele Indizes.

Es gelten das s-m-n-Theorem und das Rekursionstheorem (Fixpunktsatz)

Ersteres gilt offensichtlich fur die aus der Godelisierung von Turing-Maschinenerhaltenen Godelnummerierung ϕ, da man zu der Programmfunktion einer(normierten) Turingmaschine M beliebig Programmzeilen hinzufugen kann, dienie ausgefuhrt werden, und so unendlich viele zu M aquivalente Turingmaschinenerhalt.

Das s-m-n-Theorem und Rekursionstheorem (Fixpunktsatz) formulieren wir aufden nachsten Folien fur die Godelnummerierung ϕ und skizzieren die Beweise.


s-m-n-Theorem

SATZ (s-m-n-Theorem). Fur alle m, n ≥ 1 gibt es eine rekursive Funktion Smn mit

(∗) ϕ(n)Smn (e,y1,...,ym)(x1, . . . , xn) = ϕ(m+n)

e (y1, . . . , ym, x1, . . . , xn).

BEWEISIDEE. Ein Berechnungsverfahren fur Smn sieht wie folgt aus:

Eingabe: e, y1, . . . , ym

Rekonstruiere zunachst aus e die Maschine Me .

Definiere hieraus eine Maschine M ′, die zunachst links des Arbeitsfeldes dieUnardarstellungen von y1, . . . , ym schreibt (also eine Eingabe (x1, . . . , xn) zu(y1, . . . , ym, x1, . . . , xn) erweitert) und dann wie Me arbeitet.

Es gilt also: ϕM′(x1, . . . , xn) = ϕ(m)e (y1, . . . , ym, x1, . . . , xn).

Berechne die Godelnummer gn(M ′) von M ′ und setzeSmn (e, y1, . . . , ym) := gn(M ′).

Offensichtlich ist Smn berechenbar - also nach C-T-These rekursiv - und erfullt (∗).


Rekursionstheorem (Fixpunktsatz)

SATZ (Fixpunktsatz, Rekursionstheorem). Zu jeder rekursiven Funktionf : N→ N gibt es einen Index k mit ϕf (k) = ϕk .

BEWEISIDEE: nachste Folie

Wegen der Uniformitat des Beweise erhalt man folgende allgemeinereparametrisierte Version des Fixpunktsatzes:

SATZ (Fixpunktsatz mit Parametern). Zu jeder rekursiven Funktionf : Nn+1 → N gibt es eine rekursive Funktion k : Nn → N mit

ϕf (k(~x),~x) = ϕk(~x).


Rekursionstheorem: Beweisidee

Wir zeigen zunachst, dass es eine rekursive Funktion h : N→ N gibt mit

(∗) ϕh(x) = ϕϕx (x)

(wobei fur x mit ϕx(x) ↑ die Funktion ϕϕx (x) die nirgends definierte Funktion sei).

Die Funktion ψ(x , y) = ϕϕx (x)(y) ist partiell berechenbar. Namlich, beiEingabe (x , y) berechne zunachst ϕx(x) und dann - falls ϕx(x) ↓ - ϕz(y)wobei z = ϕx(x).

Nach der C-T-These ist ψ also partiell rekursiv und es gibt einen Index e mit

ψ = ϕ(2)e .

Nach dem s-m-n-Theorem gilt daher fur die rekursive Funktion S11

ϕS11 (e,x)(y) = ϕ(2)

e (x , y) = ψ(x , y) = ϕϕx (x)(y)

Die durch h(x) := S11 (e, x) definierte rekursive Funktion h erfullt daher die

Bedingung (∗).


Rekursionstheorem: Beweisidee (Fortsetzung)

Sei h im Folgenden eine rekursive Funktion mit

(∗) ϕh(x) = ϕϕx (x)

Wegen der Rekursivitat von f ist dann auch f ◦ h rekursiv, und es gibt einenIndex e′ mit f ◦ h = ϕe′ , d.h. f (h(x)) = (f ◦ h)(x) = ϕe′(x).

Insbesondere gilt also (fur x = e′) f (h(e′)) = ϕe′(e′) und daher

(∗∗) ϕf (h(e′)) = ϕϕe′ (e′)

Es folgtϕf (h(e′)) = ϕϕe′ (e′) (wegen (∗∗))

= ϕh(e′) (wegen (∗))

Fur k := h(e′) gilt also ϕf (k) = ϕf (h(e′)) = ϕh(e′) = ϕk .

D.h. k ist der gesuchte Fixpunkt.


Date post:	18-Sep-2018
Category:	Documents
Upload:	donhi
View:	213 times
Download:	0 times

Vortrag 1 Grundbegri e der Berechenbarkeitstheorie · I Es gibt eine 1-st. partiell berechenbare...

Documents