Ist eine Funktion, die nach Teilsequenzen von Ziffern von

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

f (n) = {\begin{cases} 1 & if \bar{n} occurs in the decimal representation of π \\ 0 & otherwise \end{cases}

$f(n) = \begin{cases} 1 & \text{if $\bar n$ occurs in the decimal representation of $\pi$} \\ 0 & \text{otherwise} \\ \end{cases}$

Dabei ist die Dezimaldarstellung von ohne führende Nullen. $\bar n$ $n$

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

computability real-numbers 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

π

$\pi$

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.

π

$\pi$

Raphael

@Kaveh: Wir hätten auch nach

suchen können, ohne die Antwort zu ändern.

(01)^{n}

$(01)^n$

Raphael

@ 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:

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

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 konstant ist oder nicht. Zum Beispiel können Sie erstellen , das berechenbar ist, aber so, dass die Konstanz von der Goldbach-Vermutung entspricht . $f$ $f$ $g$ $g$

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

auf der Ebene der Berechenbarkeitstheorie 101 berechenbar sein kann oder nicht?

f

$f$

f

$f$

Gilles 'SO - hör auf böse zu sein'

Nun, ich wollte die Frage beantworten: "Bedeutet

angesichts der Tatsache, dass

eine schwierige Frage ist

, dass

?" und meine Antwort ist „Warum nicht? Mindestens

bedeutet nicht , dass

ist eine triviale Frage

“

[f ? = 1

$[f?=1$

]

$]$

f \neq 1

$f≠1$

P (f)

$P(f)$

\neg P (f)

$¬P(f)$

[f ? = 1

$[f?=1$

]

$]$

Jmad