Apakah fungsi mencari digit selanjutnya dari

Bagaimana bisa diputuskan apakah memiliki beberapa urutan digit? $\pi$ mengilhami saya untuk bertanya apakah variasi yang tampak tidak bersalah berikut ini dapat dihitung:

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

di mana adalah representasi desimal dari tanpa nol nol di depan. $\bar n$ $n$

Jika ekspansi desimal berisi semua urutan digit hingga (sebut saja ini angka universal (dalam basis 10)), maka adalah konstanta . Tetapi ini adalah pertanyaan matematika terbuka. Jika tidak universal, apakah ini berarti bahwa tidak dapat dihitung? $\pi$ $f$ $1$ $\pi$ $f$

computability real-numbers Gilles 'SANGAT berhenti menjadi jahat'
sumber

Trik untuk masalah lain berfungsi karena unary, trik itu tidak akan berfungsi untuk memeriksa string biner. Tetapi itu tidak berarti bahwa itu tidak mungkin dengan cara lain.

Kaveh

@ Kaveh Apa yang Anda maksud dengan "unary"? Pertanyaan yang ditautkan dianggap sebagai representasi desimal dari

π

$\pi$

Raphael

Ini adalah salah satu cara untuk merender

-contoh yang tidak dapat dihitung. Cara lainnya adalah dengan memberikan bilangan real sebagai input. Saya tidak punya bukti yang berguna.

π

$\pi$

Raphael

@ Kaveh: Kami juga bisa memeriksa

tanpa mengubah jawabannya.

(01)^{n}

$(01)^n$

Raphael

@ Raphael, Anda bisa menganggapnya sebagai dasarnya juga unary. (Yang penting adalah struktur string yang mungkin untuk memeriksa hubungan awalan wrt.)

Kaveh

Jawaban:

Perhatikan bahwa dapat menjadi konstanta walaupun bukan angka normal. (Dalam bahasa Prancis kita katakan jika adalah konstan maka adalah semesta nombre . Saya tidak tahu istilah yang sesuai dalam bahasa Inggris) $f$ $1$ $\pi$ $f$ $\pi$

Untuk apa nilainya: bisa jadi , dengan cara berikut:

Membuktikan dapat dihitung tidak harus menyiratkan resolusi dari pertanyaan terbuka apakah konstan atau tidak. Misalnya Anda dapat membangun yang dapat dihitung tetapi sedemikian rupa sehingga konstanta setara dengan dugaan Goldbach . $f$ $f$ $g$ $g$

Tentu saja itu bahkan tidak mulai menjawab pertanyaan Anda, tetapi kemungkinan terbuka untuk saya.

jmad
sumber

Benar, sebenarnya yang saya maksud adalah nombre univers . Jadi

dapat dihitung tanpa menjadi konstan. Saya cukup yakin ada cara sederhana untuk menunjukkan ini. Bisakah Anda menjelaskan sedikit lebih bagaimana

mungkin atau tidak mungkin dihitung, pada tingkat computability teori 101?

f

$f$

f

$f$

Gilles 'SANGAT berhenti menjadi jahat'

[f ? = 1

$[f?=1$

]

$]$

f \neq 1

$f≠1$

P (f)

$P(f)$

\neg P (f)

$¬P(f)$

[f ? = 1

$[f?=1$

]

$]$