Apakah ada gagasan tentang komputabilitas pada set selain bilangan asli?

Apakah ada gagasan tentang komputabilitas pada set selain bilangan asli? Demi argumen, katakanlah pada set $S$ yang biject dengan $\mathbb{N}$ .

Sangat menggoda untuk mengatakan "ya, mereka adalah fungsi-fungsi dari bentuk $g \circ f \circ g^{-1}$ mana $g$ adalah setiap penambangan $\mathbb{N} \to S$ dan $f$ adalah setiap fungsi yang dapat dihitung $\mathbb{N} \to \mathbb{N}$ ". Saya berhati-hati dengan definisi ini karena dua alasan.

1. Ini hak istimewa $\mathbb{N}$ atas set dihitung lainnya. Mengapa $\mathbb{N}$ istimewa dalam mendefinisikan komputasi? Saya ingin definisi komputabilitas yang "bebas koordinat" tanpa referensi ke set privileged dengan cara yang sama saya mungkin ingin definisi "bebas koordinat" dari konsep aljabar linier tanpa referensi ke dasar istimewa.

2. Ini menimbulkan pertanyaan tentang pilihan $g$ . Saya curiga ada kemungkinan untuk menemukan kontradiksi dengan pilihan patologis $S$ dan $g$ . Sebagai contoh jika saya memilih $S = \mathbb{N}$ dan $g$ beberapa non-computable bijection itu benar-benar terjadi bahwa $g \circ f \circ g^{-1}$ adalah computable untuk semua computable $f$ ?

   Sangat menggoda untuk meminta dalam definisi bahwa $g$ dapat dihitung tetapi sayangnya itu menimbulkan pertanyaan.

Apakah ada cara umum untuk menggambarkan komputabilitas pada set yang dapat dihitung selain $\mathbb{N}$ ?

Pertanyaan ini bukan tingkat penelitian, tetapi karena menerima jawaban, saya ingin menawarkan jawaban yang mungkin sedikit memperjelas, dan memberikan referensi.

Ada seluruh bidang ilmu komputer teoretis yang mempelajari kemampuan komputasi dalam analisis, aljabar dan topologi. Yang paling penting adalah gagasan kemampuan komputasi untuk bilangan real. Sebenarnya kertas asli Turing pada mesin Turing dimulai dengan kalimat berikut:

Angka "yang dapat dihitung" dapat digambarkan secara singkat sebagai bilangan real yang ekspresinya sebagai desimal dapat dihitung dengan cara terbatas.

Terkadang membayar untuk kembali ke sumber.

Ada beberapa cara untuk mengatur komputasi pada set umum, yang salah satu yang paling umum adalah teori realizability . Gagasan teori realizability kembali ke makalah Kleene Pada Interpretation of Intuitionistic Number Theory dari 1945, tetapi sejak itu digeneralisasi dan dikembangkan menjadi mini-cabang komputabilitas, dengan campuran yang baik dari teori kategori, lihat misalnya buku Jaap van Oosten "Realisasi: pengantar sisi kategorikal" (Studi Logika dan Yayasan Matematika, vol. 152, Elsevier, 2008).

$\lambda$$\mathbb{N}$$\lambda$

$X$$\Vdash_X$$\mathbb{N}$$X$$x \in X$$n \in \mathbb{N}$$n \Vdash_X x$$n$$x \in X$

Mengingat dua majelis dan , peta adalah menyadari (atau "dihitung") jika ada Turing mesin , sehingga, setiap kali maka berakhir dan . Sekali lagi, ini adalah transliterasi langsung dari apa artinya secara informal untuk "memprogram" fungsi abstrak : mesin Turing yang sesuai melakukan untuk merepresentasikan data apa pun yang dilakukan terhadap elemen yang sesuai.$(X, {\Vdash_X})$$(Y, {\Vdash_Y})$$f : X \to Y$$T$$n \Vdash_X x$$T(n)$$T(n) \Vdash_Y f(x)$$f$$f$

Majelis dapat diperluas ke topos realisasi . Topos adalah model matematika intuitionistic tingkat tinggi. Ini memberitahu kita bahwa setiap topos realisasi (ada satu untuk setiap model perhitungan) berisi banyak objek menarik. Misalnya, ini berisi objek bilangan real, yang dengan demikian memberi kita kemampuan untuk menghitung pada real. Tapi itu juga mengandung banyak objek lain, seperti ruang Hilbert, ruang Banach, ruang peta halus, dll. Anda meminta beberapa struktur yang dapat dihitung, tetapi Anda mendapatkan sesuatu yang lebih baik: seluruh dunia komputabilitas matematika.

Karena teori kategori dan toposa bisa menakutkan dan memerlukan sejumlah kecakapan teknis dalam teori komputabilitas, teori kategori, dan logika, kita juga bisa bekerja hanya dalam satu topos beton, tetapi kami mengekspresikan semuanya dengan cara konkret non-abstrak. Dunia komputasi yang sangat baik muncul dari realisasi fungsi Kleene , dan menggunakan analisis komputabel .

Izinkan saya mengomentari persyaratan "bebas berkoordinasi":

• Beralih di antara model komputasi memberikan berbagai jenis dunia yang dapat dihitung. Ini agak seperti beralih antara bidang yang berbeda memberikan berbagai jenis aljabar linier.

• Himpunan dapat dilengkapi dengan banyak struktur komputabilitas , sama seperti seperangkat vektor memiliki banyak basis. Namun, meskipun semua pangkalan adalah setara, tidak semua struktur komputabilitas pada setara secara komputatif.$X$$\Vdash_X$$X$

• Jika kita bekerja secara konkret dengan struktur komputabilitas , itu seperti bekerja dengan matriks dalam aljabar linier. Ini bisa sangat berguna, tetapi tidak abstrak.$(X, {\Vdash_X})$

• Untuk bekerja dengan cara "bebas koordinat", kami bekerja dalam topos yang dapat diwujudkan dan memanfaatkan kekuatan teori kategori (ya, itu klise tetapi berhasil).

• Kita bahkan dapat bekerja dengan cara "bebas-dunia": mengembangkan matematika dalam logika intuitionistic, dan kemudian menginterpretasikan hasil dalam topos yang dapat diwujudkan.

Dua makalah di bawah ini mengembangkan gagasan komputabilitas untuk set arbitrer. Menariknya bahkan gagasan teori kompleksitas dapat didefinisikan untuk model perhitungan ini.

Fungsi Kumpulan Rekursif Cobham dan Teori Kumpulan Lemah Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Rekursi Subset-Bounded dan Model Sirkuit untuk Fungsi Set Rekursif Cobham Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Ada konsep kompleksitas dan perhitungan atas real. Buku teks yang akan saya tujukan adalah: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Saya tahu satu lab yang mempelajari ini secara khusus: https://complexity.kaist.ac.kr/

Ini mirip dengan bagaimana kami mendefinisikan komputabilitas dalam hal mesin Turing dan kemudian segera melupakan mesin Turing. Karena ternyata mesin Turing adalah definisi yang sama baiknya dengan yang lain, kami menggunakannya sebagai jangkar untuk seluruh kelas model ekuivalensi, dan kami berakhir dengan kelas yang sama tidak peduli dari mana elemen yang kami hasilkan. Pada dasarnya ini adalah tesis Church-Turing dan mendefinisikan serangkaian string bit yang dapat dihitung.

Demikian pula, untuk menentukan computability pada set yang berbeda , kami jangkar dengan fungsi parsial tertentu dari bit string untuk . Sebenarnya tidak masalah jika fungsi ini adalah penambangan atau injeksi atau jenis fungsi lainnya (untuk kasus di mana kita tidak benar-benar ingin itu menjadi suntikan, pertimbangkan grup yang ditentukan oleh presentasinya di mana kita tidak memiliki representasi unik untuk elemen-elemennya). Bahkan tidak harus menjadi kejutan jika kami mengizinkan bahwa set singleton dapat dihitung. Dengan menyusun fungsi ini dengan sembarang penghitungan yang dapat dihitung dari string bit ke string bit (sebuah konsep yang sudah didefinisikan), kita mendapatkan definisi kemampuan komputasi untuk$S$$S$$S$itu tidak tetap sehubungan dengan fungsi yang awalnya kami pilih (selama kami memilih sesuatu yang masuk akal). Artinya, CT tesis untuk kami set . Tetapi jika kita tidak memilih fungsi yang masuk akal, kita mendapatkan definisi komputabilitas yang berbeda.$S$

Fungsi ini juga berfungsi untuk menentukan computability fungsi lainnya dengan domain atau kisaran sama untuk . Dengan mengubah rentang , menjaga domain sebagai , kami juga mendapatkan definisi -invariant kompleksitas Kolmogorov untuk . Dan akhirnya kita dapat mengatakan bahwa fungsi yang kita pilih sendiri dapat dihitung.$S$$S$$\{0,1\}^*$$O(1)$$S$

Jadi saya pikir jawaban untuk pertanyaan Anda adalah TIDAK. Kita harus mendefinisikan komputabilitas untuk setiap set yang ingin kita bicarakan, karena ada definisi yang tidak setara. Selain dari diskusi yang sangat teknis atau pedagogis itu tidak perlu, karena orang yang masuk akal dapat membayangkan definisi yang masuk akal secara mandiri.

Tapi tunggu, biar jadi set yang tak terhingga jumlahnya, dan hanya itu. Apa definisi masuk akal kami tentang komputasi untuk ? Mengetahui bahwa rangkaian bijections antara dan tidak kosong tidak memberi tahu kita mana yang masuk akal. Kami kurang beruntung tanpa rincian lebih lanjut.$S$$S$$S$$\{0,1\}^*$

Dan kita mungkin menemukan beberapa alternatif yang tidak setara tetapi sama-sama masuk akal. Misalkan setiap pohon memiliki sejumlah daun merah dan sejumlah daun hijau, dan untuk setiap ada persis satu pohon dengan daun merah, dan untuk setiap ada persis satu pohon dengan daun hijau. Kedua bijections masuk akal dalam arti bahwa kita dapat menghitung daun dan membedakan warna, dan kita dapat berjalan tanpa tujuan di sekitar hutan menghitung daun di pohon sampai kita menemukan pohon dengan tepat daun hijau, atau satu dengan$r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$daun merah. Tidak jelas apakah akan mengidentifikasi pohon menggunakan jumlah daun merah atau jumlah daun hijau karena pilihan ini mengarah pada definisi yang tidak setara dari kemampuan komputasi untuk set pohon. Jika sebaliknya kita membuat definisi dengan menggabungkan penghitungan dengan fungsi pasangan berpasangan yang dapat dihitung dari ke (memiliki kemampuan komputasi yang didefinisikan dengan tepat pada ), yang juga secara unik mengidentifikasi masing-masing pohon, tetapi situasinya bahkan lebih buruk karena ini bukan penambangan antara pohon dan , sekarang mungkin semua set pohon yang dapat dihitung terbatas!$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Jadi untuk menghindari seluruh diskusi harus dipahami tidak hanya bahwa ada definisi yang masuk akal dari komputabilitas pada set yang dipertanyakan, tetapi juga bahwa ada satu kelas definisi yang masuk akal.

Saya pikir situasinya menjadi jauh lebih menarik jika kita membawa kompleksitas waktu ke dalam gambar. Bahkan ketika hanya mempertimbangkan bilangan bulat, pilihan kita lebih penting. Sebagai contoh, bagaimana jika kita ingin mewakili setiap angka sebagai jumlah empat kotak? Kita dapat menemukan representasi seperti itu, mulai dari representasi basis, dalam waktu kuadratik yang diharapkan dengan akses ke keacakan. Atau sebagai gantinya, sebagai daftar faktor prima, yang mungkin atau tidak mungkin dihitung dalam waktu polinomial. Sejauh kami mengizinkan representasi keras, kami kehilangan presisi dalam kompleksitas waktu. Sebagai contoh, kita tidak dapat mengatakan secara bermakna bahwa beberapa fungsi dapat dihitung dalam waktu kuadratik jika kita memiliki representasi dari$F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$yang mungkin memerlukan lebih dari waktu kuadrat untuk mengkonversi ke atau dari representasi basis. Saya pikir perspektif ini mengungkapkan bahwa representasi basis adalah standar yang agak arbitrer. (Standar dalam arti bahwa representasi dasar adalah apa yang ada dalam pikiran setiap orang ketika mereka mengatakan sesuatu seperti " dapat dihitung dalam waktu kuadratik", jika model yang mendasarinya adalah yang menghitung bit string dari bit string dan kita seharusnya menyimpulkan artinya.)$F:\mathbb{N} \rightarrow \mathbb{N}$