Wie kann entschieden werden, ob eine Ziffernfolge hat?

130

Wir erhielten die folgende Übung.

Lassen

f(n)={10n occurs in the decimal representation of π0else

Beweisen Sie, dass berechenbar ist.f

Wie ist das möglich? Soweit ich weiß, wissen wir nicht, ob jede Ziffernfolge enthält (oder welche), und ein Algorithmus kann mit Sicherheit nicht entscheiden, dass eine bestimmte Folge nicht auftritt. Deshalb denke ich, dass nicht berechenbar ist, weil das zugrunde liegende Problem nur halbentscheidbar ist.fπf

Raphael
quelle
32
Verzeihen Sie mir, dass ich völlig ignorant bin. Mir fehlt offensichtlich ein grundlegender Punkt der Frage, aber ist 0 ^ n nicht immer 0? Wenn pi die 32. Dezimalstelle 0 ist, würde das dann nicht bedeuten, dass f (n) immer 1 zurückgibt?
Cory Klein
68
@ CoryKlein: Dies ist eine formale Sprachnotation . hochgestelltes bedeutet hier fache Verkettung, dh . ist hier nur ein Symbol, keine Zahl. n a 5 = a a a a ein 0nna5=aaaaa0
Raphael

Antworten:

133

Es gibt nur zwei Möglichkeiten zu prüfen.

  • Für jede positive ganze Zahl erscheint die Zeichenfolge in der Dezimaldarstellung von . In diesem Fall ist der Algorithmus, der immer 1 zurückgibt, immer korrekt.n0nπ

  • Es gibt eine größte Ganzzahl , sodass in der Dezimaldarstellung von . In diesem Fall ist der folgende Algorithmus (mit dem Wert fest codiert) immer korrekt:N0NπN

    Zeros-in-pi(n):
     if (n > N) then return 0 else return 1
    

Wir haben keine Ahnung, welche dieser Möglichkeiten richtig ist oder welcher Wert von im zweiten Fall der richtige ist. Trotzdem ist garantiert, dass einer dieser Algorithmen korrekt ist. Somit gibt es einen Algorithmus, um zu entscheiden, ob eine Folge von Nullen in ; Das Problem ist entscheidbar.Nnπ


Beachten Sie den subtilen Unterschied zu der folgenden von gallais vorgeschlagenen Beweisskizze :

  1. Nimm eine zufällige Turingmaschine und eine zufällige Eingabe.
  2. Entweder wird die Berechnung für immer fortgesetzt oder sie wird irgendwann beendet und es gibt eine (konstante) berechenbare Funktion, die jedes dieser Verhalten beschreibt.
  3. ???
  4. Profitieren!

Alex ten Brink erklärt:

Achten Sie darauf, was der Halting-Satz besagt: Es gibt kein einzelnes Programm, das entscheiden kann, ob ein bestimmtes Programm anhält. Sie können problemlos zwei Programme so erstellen, dass entweder eines berechnet, ob ein bestimmtes Programm anhält: Das erste sagt immer "es hält an", das zweite "es hält nicht an" - ein Programm ist immer richtig, wir können nur nicht berechnen, welches von ihnen ist!

sepp2k fügt hinzu:

Im Beispiel von Alex liefert keiner der Algorithmen das richtige Ergebnis für alle Eingaben. Im Falle dieser Frage wird einer von ihnen. Sie können behaupten, dass das Problem entscheidend ist, da Sie wissen, dass es einen Algorithmus gibt, der für alle Eingaben das richtige Ergebnis liefert. Es ist egal, ob Sie wissen, welcher dieser Algorithmus ist. 10

JeffE
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Gilles
12
Was würde passieren, wenn jemand nachweisen würde, dass die Aussage "Für jede positive ganze Zahl n erscheint die Zeichenfolge 0 ^ n in der Dezimaldarstellung von π" nicht beweisbar ist? Würden wir immer noch sagen, dass dieses Problem entscheidbar ist, obwohl kein korrekter Algorithmus jemals konstruiert werden konnte?
Andere
4
@Others Ja, wir würden.
JeffE
1
@ JeffE Okay. Ist ein Beweis in der intuitionistischen Logik möglich? Oder ist hier das Gesetz der ausgeschlossenen Mitte notwendig?
Andere
@Sonstiges Wenn ich das richtig verstanden habe, lautet die Idee: Wenn wir für jedes die Turingmaschine wie im ersten Teil der Antwort definieren, dann wissen wir, dass eine von ihnen diese Funktion berechnet. Wir wissen nicht welche (und wenn Ihre Aussage bewiesen wäre, würden wir sogar wissen, dass es unmöglich ist zu wissen, welche), aber wir wissen immer noch, dass es eine solche Turing-Maschine gibt , sodass die Funktion berechenbar ist. M NNMN
JiK
14

Posten Sie einfach eine kurze Erläuterung der Antwort von JeffE.

Wir wissen, dass zwei Funktionen / Fälle existieren, die die Funktion f (n) berechnen können:

  1. Eine Funktion, die immer true zurückgibt (für alle n gibt es n aufeinanderfolgende Nullen)
  2. Eine Funktion, die true zurückgibt, wenn n kleiner als eine Ganzzahl N ist, wobei N als die maximale Länge aufeinanderfolgender Nullen definiert ist, die in der angegebenen irrationalen Zahl existieren (andernfalls wird false zurückgegeben).

Eine und nur eine dieser Funktionen kann korrekt sein. Wir wissen nicht welche, aber wir wissen mit Sicherheit, dass es eine Antwort gibt. Die Berechenbarkeit setzt voraus, dass eine Funktion vorhanden ist, die die Antwort innerhalb einer begrenzten Anzahl von Schritten bestimmen kann.

Die Anzahl der Schritte in Fall 1 ist trivial an die Rückgabe von 1 gebunden.

In Fall 2 ist auch die Anzahl der Schritte endlich. Für jede ganze Zahl wir eine Turing-Maschine konstruieren , die akzeptiert, wenn und andernfalls in endlicher Zeit ablehnt. Es spielt also keine Rolle , eine obere Schranke für . Für jedes gibt es eine Turing-Maschine, nämlich , die korrekt berechnet, ob (wir wissen nicht, welche davon korrekt sind, aber es spielt keine Rolle, es gibt eine).T N ( n ) n < N N N T N ( n ) n < NNTN(n)n<NNNTN(n)n<N

Obwohl es möglicherweise nicht möglich ist, zwischen den beiden Fällen zu wählen (obwohl einer wahrscheinlicher ist als der andere), wissen wir, dass genau einer der Fälle korrekt sein muss.

Als Randnotiz: Unsere Lösung geht davon aus, dass wir zwar nicht bestimmen können, welche Funktion einen korrekten Wert hervorruft, das Wesen der Berechenbarkeit jedoch nicht von der Konstruierbarkeit des Beweises abhängt. Reine Existenz ist ausreichend.

JC
quelle
9
Nicht alle Mathematiker akzeptieren dies - z. B. Intuitionisten nicht.
Reinierpost
Sie machen im Grunde ein langes Beispiel für das Gesetz der ausgeschlossenen Mitte, , lol. In der intuitionistischen Logik oder einem typentheoretischen Logiksystem wird dieser Beweis abgelehnt. P¬P
Kaa1el,
5

Schritt 5 des folgenden Beweisversuchs ist nicht gerechtfertigt und in der Tat falsch - ein Gegenbeispiel finden Sie hier . (Danke, Yuval; es fühlte sich wie der skizzenhafteste Teil der Skizze an). Ich habe die Antwort hier gelassen, da ich denke, dass der Fehler aufschlussreich ist.


Zunächst einmal: JeffEs Antwortpaar ist ausreichend; f ist so oder so berechenbar.

Ein kurzer Umweg über den Versuch, einen Beweis durch Induktion zu skizzieren:
Prämisse R : wiederholt sich nicht. 1. Sehen Sie sich in base 2 an. Dies dient hauptsächlich dazu, die Anzahl der Fälle zu verringern. 2. Egal wie weit Sie gehen, Sie werden immer irgendwo eine weitere 1 finden : Die Alternative sind alle Nullen, was bedeuten würde, dass anfängt, sich zu wiederholen, was gegen R geht . 3. Gleiches gilt für das Durchgehen und Finden von 0 . 4. Erweitern Sie auf zweistellige Sequenzen: Sie können weder 01 noch 10 (d. H. Stellen, an denen umgeschaltet wird) finden, da dies sonst der Fall istπ π π ππ
π
π

π würde beginnen, sich bei 1 oder 0 zu wiederholen . Ebenso können Sie nicht aufhören zu finden , 11 oder 00 , denn sonst beginnt es zu wiederholen 1010101 ...
5. Der induktive Schritt: jede endliche Folge eine unendliche Anzahl von Zeiten erscheinen muss, denn die Alternative ist , dass auf startet Wiederholung eine der kürzeren Sequenzen, die R widerspricht .π

Stephen Voris
quelle
10
Zunächst wissen wir, dass sich die binäre Erweiterung von nicht wiederholt, da irrational ist. Zweitens gibt es irrationale Zahlen, die weder 000 noch 111 in ihrer binären Erweiterung enthalten, zum Beispiel diejenige, die der Thue-Morse-Sequenz entspricht: 0.0110100110010110 ...πππ
Yuval Filmus
1
Ah, die Gefahren von Induktionssprüngen: P Guter Fang, danke.
Stephen Voris
1
Im Übrigen, wenn die Schlussfolgerung falsch ist, ist es für mich sinnvoller, sie zu löschen oder zu verlassen und durch Bearbeiten zu bestätigen, dass sie falsch ist?
Stephen Voris
4
πbb
2
@DavidRicherby Großes offenes Problem, sagst du? Ja, das ist gut zu wissen. Ich halte dies für einen einigermaßen lehrreichen Fehler, denn es zeigt, wie schwierig das Problem ist, auf das sich die Frage des OP stützt. Angesichts der Ablehnung könnte ich natürlich auch darin falsch liegen.
Stephen Voris