theoretische Informatik: Berechenbarkeit

elise

hallo

habe ein Problem mit dem Begriff "Berechenbarkeit". Ich bin auf der Spur, aber es will sich da eine Aussage des Autors des Buches "Theoretische Informatik - kurzgefasst" nicht ganz in meinen Kopf einschleusen.
folgende Aussagen wende ich seit heute morgen hin und her:

1. die Funktion

f(n)= \left\{ \begin{array}{ll} 1 & , \textrm{falls n irgendwo in der Dezimalbruchentwicklung von PI }\\ & \textrm{vorkommt}\\ 0 & , \textrm{sonst} \\ \end{array} \right.

ist möglicherweise nicht berechenbar. Unser bisheriges Wissen über die Zahl PI reicht nicht aus, um eine Entscheidung über Berechenbarkeit oder Nicht-Berechenbarkeit zu treffen.

2. die Funktion

h(n)= \left\{ \begin{array}{ll} 1 & , \textrm{falls in der Dezimalbruchentwicklung von PI}\\ & \textrm{irgendwo mindestens n-mal hintereinander eine 7 vorkommt}\\ 0 & , \textrm{sonst} \\ \end{array} \right.

ist berechenbar. Der Autor meines aktuellen Buches geht davon aus, dass diese Funktion zwar ähnlich der ersten erscheint, und damit intuitiv ebenso als nicht berechenbar angesehen wird, dies jedoch ein Trugschluss ist. Er erklärt mir den Fakt der Berechenbarkeit dieser zweiten Funktion so:

Entweder kommen beliebig lange 7-er Folgen in PI vor, dann gilt: $$h(n)=1$$ für alle $$n$$. In diesem Fall ist $$h$$ sicher berechenbar.
Oder aber es gibt eine Zahl $$n_{0}$$, so dass es in PI 7-er Folgen bis zur Länge $$n_{0}$$, aber nicht $$n_{0}+1$$ gibt. Auch in diesem Fall ist $$h$$ einfach berechenbar: Es ist $$h(n)=1$$ , falls $$n \leq n_{0}$$ , und $$h(n)=0$$ sonst. In jedem dieser Fälle gibt es einen Algorithmus zur Berechnung von $$h$$ , und genau einer dieser Fälle muss vorliegen.

Gut, ich weiss, Berechenbar ist eine Funktion, wenn es eine Registermaschine gibt. Sprich: einen Algorithmus, der in endlichen Schritten die Funktion berechnet. Auch die partielle Berechenbarkeit ist mir einleuchtend.
Aus meinem Skript entnehme ich darüber hinaus, dass Berechenbarkeit eine Eigenschaft von Zahlenfunktionen ist und nicht von Funktionswerten. Also ist Berechenbarkeit keine lokale Eigenschaft einzelner Werte, sondern eine globale Eigenschaft der Funktion als Ganzes.

So ist mir klar, dass zum Beispiel $$x^{n}+y{n}=z^{n}$$ (nach Wiles gefundenem Beweis, dass keine Lösung existiert) -nun- berechenbar ist. Nämlich konstant 0. (Wenigstens so denke ich mir das).
Mit diesem Wissen versuche ich mir, obige Aussagen zu erschließen. Wo genau liegt nun der Unterschied zwischen Aussage 1 und Aussage 2?

Ist es konkret das $$n_{0}$$ , das mir diese Möglichkeit bietet? Sprich: dass ich eine Art "Unterfunktion" herstellen kann, die auf jeden Fall eine Lösung bringt, und ich damit nicht "in der Luft" schwebe?

Vielleicht kann mir jemand die obigen zwei Aussagen nochmal mit seinen/ihren Worten erläutern, um bei mir eine Erhellung zu erzeugen.

Danke.

\small elisefremd mal groß und kleinschreibung beachtet

SG1

elise schrieb:

So ist mir klar, dass zum Beispiel $$x^{n}+y{n}=z^{n}$$ (nach Wiles gefundenem Beweis, dass keine Lösung existiert) -nun- berechenbar ist.

Meinst Du die Funktion?

f(n)= \left\{ \begin{array}{ll} 1 & , \textrm{Es gibt x,y,z, so dass...} \\ 0 & , \textrm{sonst} \\ \end{array} \right.

Die war schon immer berechenbar - man wusste nur nicht wie. Inzwischen weiss man, wie man sie berechnet (eben fast konstant 0, ausser für n=0,1,2), und damit weiss man automatisch, dass sie berechenbar ist. Das ändert aber nichts daran, dass sie vorher auch schon berechenbar war. Berechenbarkeit ist eine Eigenschaft einer Funktion, nicht eine Eigenschaft des aktuellen Stands der Forschung!

elise

Man hätte aber vor Wiles Beweis für "hoch n" nicht sagen können, ob die Funktion berechenbar oder nicht berechenbar ist?

Folgende Definition habe ich für Berechenbar:

Eine (überall oder nur partiell definierte) Funktion f, die natürliche Zahlen auf natürliche Zahlen abbildet, heißt berechenbar, wenn es eine Rechenvorschrift gibt, die für jede natürliche Zahl n, für die die Funktion f definiert ist, in endlich vielen Schritten den Wert f(n) ausgibt, und die für jede natürliche Zahl n, für die die Funktion f nicht definiert ist, ewig weiterläuft.

Damit unterlege ich meine Idee zu Wiles Beweis. Vorher konnte man nicht wissen, ob die Funktion eine konstante Funktion (da keine Lösung) mit 0 ist (da es ja sein konnte, dass wir uns nicht in einer Endlosschleife befinden, sondern die Maschine noch arbeitet)

Zu meiner obigen Frage noch folgendes:
Die Funktion 1 erinnert mich an das Halteproblem:

Es gibt keinen allgemeinen Algorithmus, der Turings Halteproblem löst. Das bedeutet: Es gibt keinen Algorithmus, mit dem man für jedes beliebig vorgegebene Turingprogramm und für jeden beliebig vorgegebenen Eingabewert n entscheiden kann, ob das Turingprogramm für dieses n anhält oder nicht.

Wäre es klar, dass die Ziffernfolge irgendwann in PI vorkommt, wäre $$ g(n)=1$$ für alle n. Damit eine konstante Funktion und berechenbar.
So jedoch ist die Funktion 1 nicht berechenbar, da es keine "Endlosschleife" ist, wenn die oben genannte Turinmaschine nicht stoppt, sondern es kann eben eine Suche sein, die vielleicht irgendwann endet, vielleicht auch nicht.

Leider habe ich zur zweiten Funktion, die nach Lage des Autors berechenbar sei, zwar ein Gefühl, aber keine Worte, warum.

also suche ich noch weiter.

elise

ich denke, ich habe jetzt akzeptiert, daß es für h einen algorithmus gibt, auch wenn man ihn schwer formulieren kann, aber er existiert.
also ist h berechenbar.

für g findet man keinen. außer man formuliert die im dritten thread erdachte grundannahme.

erstmal schließe ich hier.

aber ganz schön elektrisierend, das thema.

Ponto

Für die zweite Funktion ist ein Algorithmus ganz einfach zu formulieren:

h(n) = n < n0 ? 1 : 0

Das einzige Problem ist, dass wir das n0 noch nicht kennen. Aber wir wissen $n0 \leq \omega$

Bei der ersten Funktion kann es sein, dass sie ganz einfach berechenbar ist, falls zum Beispiel jede natürliche Zahl mal in PI vorkommt. Und falls nicht alle vorkommen, kann es sein, dass man dies einfach entscheiden kann. Es kann aber auch passieren, dass dies nicht algorithmisch entscheidbar ist und dann ist diese Funktion nicht berechenbar.

Guten Morgen

f(h) = h falls ZFC wiederspruchsfrei ist
f(h) = 0 sonst

Ist berechenbar denn:
Wiederspruchsfrei(ZFC) => Es existiert ein Algo für f nämlich f(h) = h
not(Wiederspruchsfrei(ZFC)) => Es existiert ein Algo für f nämlich f(h) = 0

Wiederspruchsfrei(ZFC) oder not(Wiederspruchsfrei(ZFC))

Also gibt es einen Algorithmus. Er ist sogar sehr einfach. Trotzdem kannst du nicht entscheiden (in ZFC), welcher der beiden Algorithmen der gesuchte ist. Falls es unentscheidbar ist ob es beliebig lange 7-er Folgen in PI gibt, hast du das gleiche Problem!

Gruss
Tobias

Jester

Vielleicht noch ein schönes kleines Beispiel für Berechenbarkeit:

f(n) := { 1, falls am Ende des Semesters alle Studenten die Klausur zur Berechenbarkeitstheorie bestehen
          0 sonst

Diese Funktion ist berechenbar, sie ist nämlich entweder Konstant 1 oder Konstant 0. Das ist unabhängig davon, daß ich weiß wie's jetzt mit der Klausur aussieht. Den konkreten Wert der Funktion Funktion kann ich natürlich nicht berechnen. Aber die Funktion ist sicher berechenbar.

MfG Jester

elise

nettes beispiel *g*

erstmal thanks to all.

Hi elise.

Sieh es doch mal so, dass die Funktionen

$h(n) = n < n_0 ? 1 : 0$

für jedes beliebige n_0 berechenbar sind. Dass man hier nicht weiß welches n_0 evtl auf das Primzahlproblem zutrifft ist egal.

Es ist ganz hilfreich vom eigentlichen Problem abzusehen und einfach nur die Funktion ohne irgendeine Interpretation zu betrachten. h löst ja noch viele weitere Probleme.

Gruß, space