Apakah fungsi mencari digit selanjutnya dari

11

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

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

di mana adalah representasi desimal dari n tanpa nol nol di depan.n¯n

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

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 . π
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. π
Raphael
1
@ Kaveh: Kami juga bisa memeriksa tanpa mengubah jawabannya. (01)n
Raphael
1
@ Raphael, Anda bisa menganggapnya sebagai dasarnya juga unary. (Yang penting adalah struktur string yang mungkin untuk memeriksa hubungan awalan wrt.)
Kaveh

Jawaban:

3

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

Untuk apa nilainya: bisa jadi , dengan cara berikut:

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

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 f mungkin atau tidak mungkin dihitung, pada tingkat computability teori 101? ff
Gilles 'SANGAT berhenti menjadi jahat'
[f?=1]f1P(f)¬P(f)[f?=1]