Ist eine Funktion, die nach Teilsequenzen von Ziffern von

11

Wie kann entschieden werden, ob eine Ziffernfolge hat? πhat mich dazu inspiriert zu fragen, ob die folgende unschuldig aussehende Variante berechenbar ist:

f(n)={1if n¯ occurs in the decimal representation of π0otherwise

Dabei ist die Dezimaldarstellung von n ohne führende Nullen.n¯n

Wenn die Dezimalerweiterung von alle endlichen Ziffernfolgen enthält (nennen wir dies eine universelle Zahl (in Basis 10)), dann ist f die Konstante 1 . Dies ist jedoch eine offene mathematische Frage. Wenn π nicht universell ist, bedeutet dies, dass f nicht berechenbar ist?πf1πf

Gilles 'SO - hör auf böse zu sein'
quelle
Der Trick für das andere Problem funktioniert, da es unär ist. Dieser Trick funktioniert nicht zum Überprüfen von Binärzeichenfolgen. Das heißt aber nicht, dass es auf andere Weise nicht möglich ist.
Kaveh
@Kaveh Was meinst du mit "unär"? Die verknüpfte Frage berücksichtigte die Dezimaldarstellung von . π
Raphael
Dies ist eine Möglichkeit, das Beispiel nicht berechenbar zu machen . Die andere Möglichkeit besteht darin, eine reelle Zahl als Eingabe anzugeben. Ich habe jedoch keinen Beweis zur Hand. π
Raphael
1
@Kaveh: Wir hätten auch nach suchen können, ohne die Antwort zu ändern. (01)n
Raphael
1
@ Raphael, man kann es sich auch als im Wesentlichen unär vorstellen. (Das Wichtigste ist die Struktur möglicher Zeichenfolgen, um die Beziehung zwischen den Präfixen zu überprüfen.)
Kaveh,

Antworten:

3

Beachten Sie, dass die Konstante 1 sein kann, auch wenn π keine normale Zahl ist. (Auf Französisch sagen wir, wenn f konstant ist, dass π ein Nombre-Universum ist . Ich kenne den entsprechenden Begriff auf Englisch nicht.)f1πfπ

Für das, was es wert ist: Es könnte folgendermaßen sein:

Der Beweis, dass berechenbar ist, würde nicht notwendigerweise die Lösung der offenen Frage bedeuten, ob f konstant ist oder nicht. Zum Beispiel können Sie g erstellen , das berechenbar ist, aber so, dass die Konstanz von g der Goldbach-Vermutung entspricht .ffgg

Natürlich beginnt das nicht einmal, Ihre Frage zu beantworten, aber es steht mir wahrscheinlich offen.

jmad
quelle
Richtig, ich meinte tatsächlich Nombre Univers . So könnte ohne konstant berechenbar sein. Ich bin mir ziemlich sicher, dass es einen einfacheren Weg gibt, dies zu zeigen. Können Sie etwas näher erläutern, wie f auf der Ebene der Berechenbarkeitstheorie 101 berechenbar sein kann oder nicht? ff
Gilles 'SO - hör auf böse zu sein'
Nun, ich wollte die Frage beantworten: "Bedeutet f 1 angesichts der Tatsache, dass eine schwierige Frage ist ] , dass P ( f ) ?" und meine Antwort ist „Warum nicht? Mindestens ¬ P ( f ) bedeutet nicht , dass [ f ? = 1 ist eine triviale Frage ][f?=1]f1P(f)¬P(f)[f?=1]
Jmad