Mengapa kita dapat menganggap suatu algoritma dapat direpresentasikan sebagai string bit?

17

Saya mulai membaca buku tentang Kompleksitas Komputasi dan Mesin Turing. Berikut ini kutipannya:

Algoritma (yaitu, mesin) dapat direpresentasikan sebagai string bit setelah kami memutuskan beberapa pengkodean kanonik.

Pernyataan ini diberikan sebagai fakta sederhana, tetapi saya tidak bisa memahaminya.

Misalnya, jika saya memiliki algoritma yang mengambil sebagai input dan menghitung atau:( x + 1 ) 2x(x+1)2

int function (int x){
   x = x + 1; 
   return x**2; 
}

Bagaimana ini dapat direpresentasikan sebagai string menggunakan alfabet ?{0,1}∗

algorithms turing-machines computability computation-models Kenenbek Arzymatov
sumber
38
Anda tidak tahu pengetahuan minimum mutlak yang diperlukan untuk memahami bagaimana teks dikodekan. Hari ini adalah hari yang menyenangkan untuk belajar! joelonsoftware.com/2003/10/08/...
Eric Lippert
1
Saya pikir OP mungkin datang pada ini dari sudut pandang yang berbeda berdasarkan pada ambiguitas dalam teks yang dikutip. Saya kira OP berarti 'bagaimana seluruh mesin dan algoritma dapat dibangun sebagai string bit,' bukan input ke mesin Turing itu sendiri. Teks yang dikutip menyiratkan bahwa keseluruhan algoritma dapat dieksekusi sendiri, tetapi sedikit bahasa c yang dikodekan tidak mengatakan apa-apa tentang bagaimana mesin benar-benar akan bertindak pada string itu.
Sentinel
3
... Saya pikir semua orang di sini salah memahami sumber dan mengambil lelucon terlalu jauh, dengan mengorbankan pengalaman Roma. Sebagian besar komentar dan jawaban ini berbicara tentang penyandian teks untuk transmisi sewenang-wenang, sementara kutipan berbicara tentang penyandian algoritma untuk konsumsi oleh mesin turing. Jawaban (saat ini) diterima, setidaknya menyentuh di dalam kalimat kedua.
Izkata
2
@Izkata Saya tidak yakin apakah Anda sadar bahwa, karena universalitas, kedua pernyataan ini setara.
Konrad Rudolph
15
Yang lucu adalah bahwa dalam rangka bagi saya untuk dapat membaca algoritma Anda kode itu tentu harus berubah menjadi urutan bit segera setelah Anda mengetik. Itu tidak pernah diwakili secara berbeda - jauh dari keyboard Anda ke monitor saya. Itu memiliki representasi non-biner hanya dalam pikiran kita; dan pada tingkat fisiologis, ketika Anda melihat sinapsis, bahkan itu masih bisa diperdebatkan.
Peter - Reinstate Monica

Jawaban:

45

Jawaban yang paling naif dan sederhana untuk pertanyaan Anda adalah bahwa kode yang disediakan (dan kode mesin yang dikompilasi) sebenarnya direpresentasikan sebagai string sintaksis dari {0,1} *. Selain itu, karena Anda berbicara tentang mesin turing, program yang mereka jalankan adalah daftar linier operasi / instruksi, tidak ada alasan ini tidak dapat direpresentasikan sebagai bit / byte.

Daniel F
sumber
Bagaimana tepatnya Anda mewakili mesin Turing sebagai daftar instruksi? Definisi yang biasa adalah sesuatu seperti ini .
svick
@ svick Seperti yang disebutkan dalam jawaban saya di bawah ini, Anda menggunakan TM universal, yang mengambil deskripsi TM sebagai input (dikodekan dengan cara yang sesuai)
dseuss
@ svick Bahasa pemrograman dengan instruksi sederhana untuk memindahkan pointer ke tape? Saya percaya contoh seperti itu bisa menjadi bahasa pemrograman esoterik Brainfuck . Kode contoh
LukStorms
@LukStorms Saya tidak berpikir Anda bisa menyebutnya "mesin Turing" lagi.
svick
52

Anda sudah memiliki representasi fungsi itu sebagai teks. Konversi setiap karakter ke nilai satu byte menggunakan pengkodean ASCII. Maka hasilnya adalah urutan byte, yaitu urutan bit, yaitu string di atas alfabet . Itu salah satu contoh pengkodean.{0,1}∗

DW
sumber
Persis. Dan seperti yang saya katakan di atas, itu terjadi ketika Roma menulisnya. Bahkan mesin terbang yang saya lihat di monitor saya adalah piksel b & w, yaitu informasi biner, yang dikirim melalui koneksi data biner dari memori biner yang terhubung ke jaringan biner melalui pengontrol biner. Apakah mungkin untuk merepresentasikan setiap algoritma sebagai string bit? Lebih dari itu: tidak dapat dihindari kecuali Anda membatasi diri Anda pada media analog dan komunikasi tatap muka.
Peter - Reinstate Monica
@ PeterA.Schneider Menggunakan media analog atau tatap muka tidak selalu menyiratkan bahwa tidak ada penyandian diskrit tertanam. Menggunakan bahasa alami tidak jauh dari menggunakan pengkodean diskrit, bukan?
Jean-Baptiste Yunès
32

Saya tidak bisa menahan ...

⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂
⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀
⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀
⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀
⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆
⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

⢱⠀
⢸⠁
⠊

(Titik-titik di atas mewakili yang, nol kosong).

leftaroundabout
sumber
5
Lucu (+1) tetapi berfungsi untuk menggarisbawahi sifat dasarnya sewenang-wenang dari pengkodean.
John Coleman
4
Bersenang-senang menulis compiler untuk ini :)
Barmar
Mengingatkan saya pada stackoverflow.com/questions/5508110/…
MSalters
1
@Barmar Kedengarannya seperti tantangan bagi codegolf.stackexchange.com
IMSoP
1
@RomaKarageorgievich inilah fungsi yang melakukan rendering ke karakter Braille. Inilah pembungkus sederhana yang memungkinkan Anda memanggilnya dari baris perintah.
leftaroundabout
13

Komputer Anda menyimpan semuanya sebagai urutan 0dan 1, termasuk pertanyaan yang Anda ketikkan untuk menanyakan bagaimana melakukannya. Sebagai contoh, setiap huruf dan simbol diwakili oleh 8-bit (saya berbicara tentang bagaimana hal-hal yang dulu, saat ini 16-bit, dan lebih rumit). Anda bisa melihatnya di sini . Yah, mereka tidak menunjukkan bit, melainkan kode heksadesimal dan oktal. Apakah Anda tahu cara mengonversi angka ke representasi digitalnya?

Andrej Bauer
sumber
6
Ini 16 byte hanya pada Windows dan di beberapa perpustakaan seperti Qt atau ICU, yang menggunakan UTF-16. Dan bahkan tidak semua huruf menggunakan unit kode tunggal secara umum, bahkan dalam UTF-32, sehingga mungkin lebih lama. Jadi saya pikir lebih baik tetap berpegang pada ASCII dalam diskusi ini, membawa Unicode ke sini akan menimbulkan cukup banyak kesulitan.
Ruslan
8

Hipotesis mendasar di balik konsep ini adalah tesis Church-Turing . Mungkin sulit untuk melihat bahwa algoritma apa pun dapat direpresentasikan sebagai string bit, karena istilah "algoritma" dapat dianggap dalam istilah yang sangat informal. Dalam tesis Church-Turing, mereka menggunakan konsep yang sangat ketat tentang apa itu algoritma (dan bahkan kemudian ada beberapa pertanyaan tentang kata-kata). Namun, terminologi mereka telah mendapat begitu banyak bergoyang bahwa itu kadang-kadang berpendapat bahwa definisi ini untuk kata-kata seperti "algoritma" sangat efektif bahwa kita hanya menerima mereka sebagai yang definisi.

Church-Turing menyatakan bahwa setiap algoritma dapat diimplementasikan sebagai perhitungan pada Mesin Turing. Mengingat bahwa deskripsi Mesin Turing adalah himpunan nilai hingga, sepele untuk melihat bagaimana memetakan deskripsi ini ke dalam urutan angka, dan kemudian ke dalam urutan 0 dan 1.

Seperti jawaban lain yang disebutkan, itu sepele untuk mewakili contoh algoritma Anda dengan menggunakan pengkodean ASCII atau pengkodean lainnya.

Saya pikir alasan mengapa buku Anda memberikan pernyataan ini sebagai fakta berasal dari fakta bahwa banyak orang menggunakan tesis Church-Turing sebagai dasar untuk definisi algoritma. Jika Anda menggunakan definisi seperti itu, jelas fakta bahwa "5 adalah angka" karena pada dasarnya Anda mendefinisikannya.

Cort Ammon - Pulihkan Monica
sumber
9
Tesis Church-Turing bukan teorema dan tidak melibatkan definisi apa pun untuk konsep algoritma, yang merupakan konsep informal. Saya juga tidak melihat perlunya memohon tesis Church-Turing untuk ini. Alasan "mendalam" mengapa beberapa objek dapat direpresentasikan sebagai string hingga dan beberapa tidak bisa adalah karena beberapa set dapat dihitung dan beberapa tidak.
quicksort
Saya melihat "suatu algoritma dapat dikodekan sebagai string jika kita menentukan injeksi antara komponen spesifikasi mesin dan set string dalam bahasa." OP melakukan ini dalam contohnya, mengambil mesin yang diwakili oleh " $ (x + 1) ^ 2 $ " dan merepresentasikannya sebagai string dalam bahasa fungsi C (atau BCPL, C ++, et al.) Yang terbentuk dengan baik .
Eric Towers
1
@EricTowers Yang memang membutuhkan tesis Church-Turing. Kalau tidak, kita tidak dapat memastikan bahwa ada spesifikasi mesin dari suatu algoritma untuk semua algoritma.
Cort Ammon - Reinstate Monica
1
Saya menyatakan bahwa "algoritma [yang] membutuhkan jumlah simbol yang tak terhingga jumlahnya untuk diekspresikan" tidak dapat diungkapkan. Ungkapan seperti itu harus menggunakan banyak simbol yang tak terhitung banyaknya, jika tidak, ia dapat diekspresikan dalam bahasa kecil. Lebih jauh, setiap ekspresi (non-konyol) atas alfabet tak terbatas memiliki jumlah entropi yang tak terbatas di hampir semua simbolnya, sehingga menentang ekspresi (yaitu, tidak dapat benar-benar berkomunikasi dengan penerima). Semua logika keuangan menolak untuk beroperasi pada string tak terbatas seperti itu dan saya tidak mengetahui logika tak terbatas yang akan memungkinkan bekerja pada string tak terhitung.
Eric Towers
1
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
DW
4

Pernyataan ini didasarkan pada keberadaan TM universal . Ini pada dasarnya adalah TM yang dapat diprogram yang dapat mensimulasikan TM lainnya dengan paling banyak poli overhead. Karena itu, program Anda hanyalah bagian dari input yang dikodekan sebagai nol dan satu.

dseuss
sumber
1
@ Discretelizard, saya tidak mengikuti Anda. Algoritma apa pun dapat diekspresikan sebagai input ke TM universal. Bahasa dapat dihitung atau tidak dapat dihitung; Saya tidak terbiasa dengan gagasan standar tentang kemampuan komputasi untuk algoritma, jadi saya tidak yakin apa yang Anda maksud. Apa artinya memiliki algoritma yang tidak dapat dihitung? Mungkin Anda memikirkan algoritme yang belum tentu berakhir? Tetapi TM universal masih dapat menjalankan algoritma tersebut.
DW
@ Discretelizard saya juga tidak mengikuti Anda. Menjadi runnable pada mesin Turing pada dasarnya adalah definisi suatu algoritma. Saya kira Anda dapat berbicara tentang "algoritma" untuk, katakanlah, mesin Turing dengan oracle untuk masalah penghentian tetapi, biasanya, "algoritma" berarti "hal yang dapat Anda lakukan pada mesin Turing."
David Richerby
@ DavidvidRicherby Benar, definisi sebenarnya dari algoritma lebih ketat, saya kira. Tetapi pertanyaan ini adalah tentang mengapa kita menerapkan batasan yang jauh lebih lunak dan mengatakan bahwa ada batasan yang bahkan lebih kuat tidak terlalu instruktif, menurut pendapat saya.
Kadal diskrit
4

Baiklah, mari kita bicara tentang algoritma yang tidak dapat direpresentasikan sebagai bit-string yang terbatas untuk segala jenis pengkodean.

Biarkan saya mengetikkan algoritma seperti itu untuk Anda ... Ah, tetapi jika saya melakukan itu, saya dapat mewakili algoritma itu dengan pengkodean teks yang saya ketik.

Bagaimana kalau mewakili algoritme saya menggunakan beberapa 'sarana analog', katakan dengan posisi beberapa koin di meja saya. Meskipun posisi koin-koin itu dapat dimodelkan dengan beberapa bilangan real (yang dalam beberapa pengkodean tidak mungkin untuk diwakili secara tepat), seluruh uraian ini dapat kembali dianggap sebagai representasi dari algoritma saya dan dapat dikodekan ke bit-string lagi!

Saya harap contoh-contoh ini memperjelas bahwa jika beberapa algoritma tidak dapat diwakili oleh bit-string yang terbatas kita tidak memiliki cara untuk menggambarkan algoritma ini sama sekali!

Jadi, mengapa kita mempertimbangkan keberadaan sesuatu yang tidak dapat kita bicarakan? Mungkin menarik untuk filsafat, tetapi tidak untuk sains. Oleh karena itu, kami mendefinisikan gagasan tentang algoritma sehingga dapat diwakili oleh bit-string, karena dengan demikian kita setidaknya tahu bahwa kita dapat berbicara tentang semua algoritma.

Meskipun jawaban di atas pertanyaan yang diajukan, saya pikir kebingungan tentang contoh yang diberikan sebagian besar disebabkan oleh fakta bahwa representasi hanya perlu secara unik mewakili beberapa algoritma. Cara representasi tidak perlu melibatkan perhitungan aktual yang dilakukan oleh algoritma! Ini sangat berguna, karena itu berarti kami juga dapat mewakili algoritma yang tidak dapat dihitung !

Kadal diskrit
sumber
rSEBUAHr
1
SEBUAHrR
1
Iya! Menyenangkan! Wittgenstein! "Wovon man nicht sprechen kann, darüber muss man schweigen."
Peter - Reinstate Monica
r
@ Raphael Ya, dan? Seharusnya tidak mengherankan bahwa menuliskan sejumlah algoritma yang tidak terhitung tidak mungkin. Dan lagi, Anda mengklaim bahwa Anda "mengungkapkan" beberapa algoritma yang tidak dapat ditulis. Saya tidak mengerti apa yang Anda maksud dengan "mengekspresikan", tetapi tampaknya setidaknya menyiratkan representasi. Karena klaim saya dimulai dengan asumsi bahwa suatu algoritma tidak terwakili, saya gagal melihat bagaimana hal ini bertentangan dengan klaim saya.
Kadal diskrit
2

Cara lain untuk melihatnya adalah melalui teori informasi. Semua penyandian informasi / pertanyaan yang bermakna / berguna dapat dibuat menjadi 'urutan' biner.

Sebagian besar bidang menjawab pertanyaan, "apa cara untuk mengajukan pertanyaan dengan jumlah rata-rata paling sedikit untuk mengomunikasikan informasi yang bermakna?" Dalam praktiknya, ini sama dengan "apa pendekatan optimal untuk mengajukan paling sedikit pertanyaan ya / tidak untuk memahami apa yang dikomunikasikan atau dikatakan?"

eSurfsnake
sumber