Kardinalitas himpunan algoritma

Seseorang dalam sebuah diskusi mengemukakan bahwa (dia menganggap) setidaknya ada sejumlah kontinum strategi untuk mendekati masalah tertentu. Masalah spesifiknya adalah strategi perdagangan (bukan algoritma tetapi strategi) tapi saya pikir itulah inti pertanyaan saya.

Ini membuat saya berpikir tentang kardinalitas himpunan algoritma. Saya telah mencari-cari sedikit tetapi tidak menemukan apa-apa. Saya telah berpikir bahwa, karena mesin turing beroperasi dengan seperangkat alfabet yang terbatas dan pita harus dapat diindeks sehingga dapat dihitung, tidak mungkin untuk memiliki jumlah algoritma yang tidak terhitung. Teori himpunan saya memang berkarat jadi saya tidak yakin sama sekali alasan saya valid dan saya mungkin tidak akan bisa membuktikannya, tapi itu pemikiran yang menarik.

Apa kardinalitas himpunan algoritma?

Algoritma secara informal dijelaskan sebagai urutan terbatas dari instruksi tertulis untuk menyelesaikan beberapa tugas. Secara lebih formal, mereka diidentifikasi sebagai mesin Turing, meskipun Anda juga dapat menggambarkannya sebagai program komputer.

Formalisme tepat yang Anda gunakan tidak banyak masalah tetapi titik mendasar adalah bahwa setiap algoritma dapat ditulis sebagai urutan karakter yang terbatas, di mana karakter dipilih dari beberapa set yang terbatas, misalnya, huruf romawi, ASCII atau nol dan nol. Untuk mempermudah, mari kita asumsikan angka nol dan satu. Setiap urutan nol dan satu hanyalah bilangan alami yang ditulis dalam biner. Itu berarti ada paling banyak tak terhitung algoritma, karena setiap algoritma dapat direpresentasikan sebagai bilangan alami.

Untuk kredit penuh, Anda harus khawatir bahwa beberapa bilangan asli mungkin tidak kode program yang valid, sehingga mungkin ada lebih sedikit algoritma daripada angka alami. (Untuk kredit bonus, Anda mungkin juga bertanya-tanya apakah itu mungkin bahwa dua bilangan yang berbeda mewakili algoritma yang sama.) Namun, print 1, print 2, print 3dan sebagainya semua algoritma dan semua berbeda, jadi ada setidaknya countably tak terhingga banyaknya algoritma.

Jadi kami menyimpulkan bahwa himpunan algoritma ini terhitung tak terbatas.

Himpunan algoritma ini sangat tak terbatas. Ini karena setiap algoritma memiliki deskripsi yang terbatas, katakan sebagai mesin Turing.

Fakta bahwa suatu algoritma memiliki deskripsi yang terbatas memungkinkan kita untuk memasukkan satu algoritma ke yang lain, dan ini adalah dasar dari teori komputabilitas. Ini memungkinkan kita untuk merumuskan masalah penghentian, misalnya.

setidaknya sejumlah strategi untuk mendekati masalah tertentu

"Continuum" mungkin seharusnya berarti bilangan real ... menggunakan "setidaknya" bersama dengan kata itu tidak masuk akal di atas. Menjadi sedikit dari mulut ke mulut: tak terhingga tak terhingga cukup besar, tetapi tak terhingga tak terbatas ... lebih besar dari besar. Lebih dari itu. Tak terduga.

Jadi mari kita buang itu ke luar jendela. Untuk melihat infinity seperti apa yang sedang kita hadapi adalah mati sederhana (dan intuitif, bahkan jika teman Anda belum pernah mendengar ilmu komputer teoritis apa pun):

• Algoritma apa pun dapat diimplementasikan dengan bahasa turing-complete; pilih racun favorit Anda dari bahasa dunia nyata (Java, C, ...) untuk menghilangkan sedikit kebingungan ini. Semua ini setara dengan set algoritma teoritis yang dapat dibuat oleh siapa pun. Perhatikan bahwa setiap algoritma itu sendiri terbatas, yaitu, tidak ada algoritma yang akan mengambil banyak simbol untuk dituliskan.
• Jangan berpikir tentang Mesin Turing yang rumit. Bahasa pilihan Anda menggunakan file sederhana untuk menyimpan kode sumbernya. Setiap file adalah kumpulan angka kecil (alias, byte). Yang penting adalah bahwa angka-angka ini paling jelas bilangan bulat, bukan kontinu. (Jika Anda seorang purist dan ingin tetap berada dalam rezim teoritis, ganti kata "byte" dengan "simbol", itu tidak mengubah apa pun.) Jika Anda takut tentang program besar yang didistribusikan di beberapa file (dan perpustakaan) , dan hal-hal lain), kemudian cukup zip menjadi satu arsip terkompresi (yaitu, satu file).
• Sekarang, Anda dapat menetapkan nomor integer tunggal untuk setiap file di luar sana, secara objektif. Kami hanya menulis seluruh kekacauan bit / byte file satu demi satu, dan berakhir dengan jumlah yang sangat besar yang dinyatakan dalam biner. Di masa lalu yang jauh, orang-orang benar-benar melakukan itu: mereka mencetak program biner yang dikompilasi sebagai daftar panjang nomor hex di majalah; Anda akan mengetiknya, tetapi tidak pernah melihatnya sebagai apa pun selain angka (sering dikelompokkan dengan mudah dalam 8 atau 16 digit set untuk memudahkan pengetikan).
• Jadi: setiap program dapat diwakili oleh angka integer, meskipun jumlahnya besar. Cara sebaliknya juga bekerja - setiap bilangan bulat dapat segera dan sepele ditransfer ke file dan dilemparkan ke kompiler (jelas, hanya sebagian kecil dari itu akan menjadi program yang valid, tetapi itu tidak masalah bagi kami sekarang).
• Pada akhirnya, program, dan dengan demikian algoritma, adalah bagian dari bilangan bulat; karenanya, hanya banyak yang dapat eksis.
• NB, fakta bahwa ada banyak implementasi berbeda dari algoritma tunggal yang menguntungkan kami, yaitu, banyak dari bilangan bulat tersebut terkondensasi menjadi (representasi berbeda dari) algoritma yang sama. Jadi jika infinity yang dihitung bukan jenis infinity terkecil, kita harus khawatir tentang jumlah algoritma yang lebih kecil, tetapi tentu saja tidak lebih besar (yaitu, terhitung).

Masalah khusus adalah strategi perdagangan (bukan algoritma tetapi strategi)

Saya tidak tahu apa yang dimaksud teman Anda dengan "strategi"; Saya berasumsi dia berarti sesuatu yang seperti algoritma, tetapi tidak dirumuskan secara cukup rinci untuk meretasnya ke komputer? Atau yang entah bagaimana tergantung pada "intuisi" manusia selama eksekusi? Jika demikian, maka ini hanyalah detail yang tidak relevan. Umat ​​manusia belum menemukan deskripsi proses apa pun yang lebih kuat atau lebih besar dari "algoritma" dalam arti yang kami gunakan dalam CS.

Lihat Penomoran Nomor , itu adalah fakta dasar dalam ilmu komputer bahwa algoritma dapat dihitung, seperti halnya dengan ekstensi set enumerable rekursif.

Algoritma dapat dihitung, mudah untuk menunjukkan bahwa tidak ada algoritma untuk memverifikasi setiap set dalam sistem formal (tetapkan nilai kebenaran untuk suatu masalah). Ini akan setara dengan menetapkan algoritma untuk setiap fungsi memetakan set masalah ke nilai boolean. Namun, himpunan fungsi-fungsi ini tak terhitung (sepele kardinalitas yang sama dengan himpunan daya himpunan masalah, oleh karena itu tak terhitung).

Saya harap ini memberikan beberapa intuisi mengapa algoritma harus "kurang kuat" daripada fungsi apa pun, yang dapat dihitung (mari kita abaikan hipotesis kontinum di sini).

Jika seseorang tidak memulai dengan persyaratan bahwa suatu strategi perlu diimplementasikan dengan suatu algoritma, dan mengabaikan efek diskritisasi kehidupan nyata, misalnya seseorang dapat menerima hal-hal berikut sebagai strategi perdagangan yang diparameterisasi:

$a$$b$$a$$b$

$a$$b$

Jika kita memahami algoritma sebagai program komputer yang ditulis dalam biner *, maka jumlah algoritma adalah jumlah (bilangan bulat) angka biner. Jadi kardinalitas algoritma adalah kardinalitas bilangan bulat.

* Bukti bahwa mesin turing dapat menjalankan semua algoritma, dan bahwa komputer dapat menjalankan mesin program turing, akan membuat jawaban ini terlalu lama. Yang pertama mungkin tergantung pada definisi algoritma, tetapi saya tidak berpikir Anda menggunakan strategi perdagangan yang tidak dapat dihitung.

Jawaban lain telah menjelaskan bahwa dalam model komputasi standar (mesin Turing, kalkulus lambda, dll.) Sekumpulan algoritme sangat tak terhingga.

Namun, ada model teoretis lain dari komputasi di mana himpunan algoritma tak terhingga jumlahnya. Sebagai contoh, mesin Blum – Shub – Smale memiliki set instruksi ^{1 yang} tak terhingga jumlahnya , sehingga algoritma mereka juga tak terhingga jumlahnya.

karena mesin turing beroperasi dengan seperangkat alfabet yang terbatas dan pita harus dapat diindeks sehingga dapat dihitung

Diberikan ukuran tertentu, ada banyak mesin Turing, dan ada banyak ukuran. Satu set angka yang dapat dihitung, selama terbatas, dapat dihitung. Ukuran alfabet merupakan faktor dalam jumlah mesin Turing, tetapi ukuran kasetnya tidak. Jika alfabet diizinkan memiliki banyak karakter, maka akan ada banyak mesin yang tak terhitung jumlahnya (setiap bilangan real dapat dikodekan sebagai urutan simbol).

Jika "algoritma" yang Anda maksudkan hanyalah korespondensi antara input dan output, dan bukan mesin Turing atau sesuatu yang merupakan arti normal dari "perhitungan", maka jelas jika ada banyak input yang berbeda, maka ada banyak algoritma: untuk setiap bilangan real, kita bisa mendefinisikan "algoritma" yang mengambil bilangan alami sebagai input, dan output tempat desimal itu. Misalnya, memberikan input "3" ke menu$\sqrt{.5}$Algoritma akan memberikan output "7". (Perhatikan bahwa meskipun mungkin untuk merancang mesin Turing yang memberikan digit ke-n$\sqrt{.5}$, tidak mungkin untuk melakukannya untuk semua bilangan real; hanya banyak bilangan real yang dapat dihitung).