Bisakah fungsi yang dikomputasi menyatu dengan angka yang tidak dapat dihitung?

18

Apakah ada fungsi yang dapat dihitung sedemikian rupa sehingga:f:NQ

  • Untuk semuatN:0f(t)<X
  • limtf(t)=X

Di mana X 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.

cjnash
sumber
Saya yakin jawaban ini yang saya tulis tiga tahun lalu menjawab pertanyaan Anda: math.stackexchange.com/a/1267124/161559
kasperd
2
Angka-angka yang dapat diperoleh seperti batas X disebut real-ce real, jika Anda ingin mencari lebih banyak tentang propertinya.
Arno
mungkin juga math.stackexchange.com/a/462835/128985 yang memberikan fungsi seperti itu saya pikir (kecuali saya memiliki logika yang salah jalan)
Philip Oakley

Jawaban:

31

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=1ri=0R

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 diberikanMn<nn0.r1^...r2n1^ri^=1inri^=0nM(n)<R{M(n)}nNRϵ, Anda tidak dapat menghitung indeks sehingga di luar itu seri adalah -dekat dengan .ϵR

Ariel
sumber
The Anda sebutkan adalah setiap bilangan real atau itu bilangan real dihitung? (Apakah itu membuat perbedaan?)ϵ
Pedro A
1
Tidak ada masalah komputabilitas di sini, tetapi karena kita berbicara tentang input ke mesin Turing, itu harus memiliki beberapa representasi yang terbatas, sehingga kita dapat menganggap sebagai bilangan rasional kecil. ϵ
Ariel