Czy funkcja szukająca podciągów cyfr

Jak można rozstrzygać, czy ma pewną sekwencję cyfr? $\pi$ zainspirowało mnie do pytania, czy można obliczyć następującą niewinnie wyglądającą odmianę:

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}$

gdzie jest dziesiętną reprezentacją bez zer wiodących. $\bar n$ $n$

Jeśli rozwinięcie dziesiętne zawiera wszystkie ciągi cyfr skończonych (nazwijmy to liczbą uniwersalną (w podstawie 10)), to jest stałą . Ale to otwarte pytanie matematyczne. Jeśli nie jest uniwersalne, czy to oznacza, że jest nieobliczalne? $\pi$ $f$ $1$ $\pi$ $f$

computability real-numbers Gilles „SO- przestań być zły”
źródło

sztuczka dla drugiego problemu działa, ponieważ jest jednoargumentowa, ta sztuczka nie zadziała do sprawdzania ciągów binarnych. Ale to nie znaczy, że nie jest to możliwe w inny sposób.

Kaveh

@Kaveh Co rozumiesz przez „unary”? Połączone pytanie dotyczyło dziesiętnej reprezentacji .

π

$\pi$

Raphael

Jest to jeden ze sposobów, aby uczynić -example nieobliczalnym. Innym sposobem jest podanie liczby rzeczywistej jako danych wejściowych. Jednak nie mam pod ręką dowodu.

π

$\pi$

Raphael

@Kaveh: Moglibyśmy również sprawdzić bez zmiany odpowiedzi.

(01)^{n}

$(01)^n$

Raphael

@ Rafael, możesz myśleć o tym również jako zasadniczo jednoargumentowy. (Ważną rzeczą jest struktura możliwych ciągów do sprawdzania relacji prefiksu wrt.)

Kaveh

Odpowiedzi:

Zauważ, że może być stałą nawet jeśli nie jest liczbą normalną. (W języku francuskim mówimy, że jeśli jest stałe, że jest uniwersalnym uniwersytetem . Nie znam odpowiedniego terminu w języku angielskim) $f$ $1$ $\pi$ $f$ $\pi$

Za to, co jest warte: może być w następujący sposób:

Udowodnienie, że jest obliczalne, niekoniecznie oznaczałoby rozstrzygnięcie otwartego pytania, czy jest stałe, czy nie. Na przykład możesz zbudować który jest obliczalny, ale taki, że stałość jest równoważna hipotezie Goldbacha . $f$ $f$ $g$ $g$

Oczywiście to nawet nie zaczyna odpowiadać na twoje pytanie, ale prawdopodobnie jest dla mnie otwarte.

jmad
źródło

Racja, właściwie miałem na myśli nombre univers . Więc

może być obliczalne bez bycia stałym. Jestem prawie pewien, że istnieje prostszy sposób, aby to pokazać. Czy możesz wyjaśnić nieco więcej, w jaki sposób

może, ale nie musi być obliczalny, na poziomie teorii obliczalności 101?

f

$f$

f

$f$

Gilles „SO- przestań być zły”

[f ? = 1

$[f?=1$

]

$]$

f \neq 1

$f≠1$

P (f)

$P(f)$

\neg P (f)

$¬P(f)$

[f ? = 1

$[f?=1$

]

$]$