Apakah ada fungsi yang dapat dihitung sedemikian rupa sehingga:
- Untuk semua
Di mana adalah bilangan real yang tidak dapat dihitung.
Satu-satunya referensi untuk pertanyaan ini yang saya temukan adalah jawaban untuk pertanyaan ini : /math//a/1052579/168764 , di mana fungsinya tampaknya akan berlaku, tetapi saya tidak tahu bagaimana membuktikannya. batas fungsi ini adalah bilangan real yang tidak dapat dihitung.
computability
cjnash
sumber
sumber
Jawaban:
Pertimbangkan pengkodean bilangan real dari (hampir) masalah penghentian, yaitu mana jika mesin Turing ke-i (relatif terhadap urutan leksikografis) berhenti pada input kosong, dan sebaliknya. Mari kita menunjukkan angka ini dengan .r i = 1 r i = 0 R0. r1r2. . . rsaya= 1 rsaya=0 R
Sekarang, perhatikan mesin yang pada input mensimulasikan semua mesin Turing dengan panjang pada input kosong untuk langkah, dan mengembalikan mana jika 'th Turing perhentian mesin pada input kosong dalam waktu kurang dari langkah, dan sebaliknya. Jelas untuk semua itu menyatakan bahwa , dan tidak terlalu sulit untuk menunjukkan bahwa konvergen ke . Poin kuncinya adalah bahwa laju konvergensi tidak dapat dihitung, yang berarti diberikanM n <n n 0.r1^...r2n−1^ ri^=1 i n ri^=0 n M(n)<R {M(n)}n∈N R ϵ , Anda tidak dapat menghitung indeks sehingga di luar itu seri adalah -dekat dengan .ϵ R
sumber