Kapan kita dapat mengatakan bahwa dua program berbeda?

Q1. Kapan kita dapat mengatakan bahwa dua program (ditulis dalam beberapa bahasa pemrograman seperti C ++) berbeda?

Ekstrem pertama adalah untuk mengatakan bahwa dua program adalah setara jika mereka identik. Ekstrem lainnya adalah dengan mengatakan dua program setara jika mereka menghitung fungsi yang sama (atau menunjukkan perilaku yang dapat diamati sama di lingkungan yang sama). Tapi ini tidak baik: tidak semua program memeriksa keaslian adalah sama. Kami dapat menambahkan baris kode tanpa efek pada hasilnya dan kami masih akan menganggapnya sebagai program yang sama.

Q2. Apakah program dan algoritma adalah jenis objek yang sama? Jika tidak, apa definisi dari suatu algoritma dan bagaimana perbedaannya dari definisi suatu program? Kapan kita bisa mengatakan dua algoritma setara?

pl.programming-languages semantics equivalence Anonim
sumber

Masalah program isomorfisme? Tidak bisakah seseorang bertanya "apakah program ini isomorfis terhadap program yang selalu terhenti?" dan pulihkan Masalah Penghentian? Jika kita membatasi diri pada Masalah Program Berhenti Terikat bukankah ini hanya grafik isomorfisme?

user834

Kapan dua algoritma itu sama? arxiv.org/abs/0811.0811

sdcvvc

Bukankah itu tergantung sepenuhnya pada konteksnya? Menjadi sedikit filosofis di sini, tetapi kursi yang dibaut dan kursi yang dibaut yang terbalik adalah hal yang sama secara fisik tetapi tidak sama dalam hal gagasan kursi.

Rei Miyasaka

Agak di luar topik, tetapi, karena buktinya adalah program ... gowers.wordpress.com/2007/10/04/…

Radu GRIGore

Artikel berikut ini sangat terkait. Saya hanya membaca sekilas beberapa waktu lalu, tetapi Blass dan Gurevic biasanya menulis dengan sangat baik (saya hanya tidak ingat pernah membaca yang lain oleh Dershowitz, tidak mengatakan itu biasanya tidak terlalu mudah dibaca). research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf KAPAN DUA ALGORITMA SAMA? ANDREAS BLASS, NACHUM DERSHOWITZ, DAN YURI GUREVICH

kasterma

Jawaban:

T1: Ada banyak gagasan tentang kesetaraan program (jejak kesetaraan, kesetaraan kontekstual, kesetaraan pengamatan, bisimilaritas) yang mungkin atau mungkin tidak mempertimbangkan hal-hal seperti waktu, penggunaan sumber daya, nondeterminisme, penghentian. Banyak pekerjaan telah dilakukan untuk menemukan konsep kesetaraan program yang dapat digunakan. Sebagai contoh: Teori Kesetaraan Program Berbasis Operasional oleh Andy Pitts . Tapi ini nyaris tidak menggores permukaan. Ini harus bermanfaat bahkan jika Anda tertarik ketika dua program tidak setara. Orang bahkan dapat beralasan tentang program yang tidak berhenti (menggunakan bisimulasi dan koinduksi).

T2: Satu jawaban yang mungkin untuk bagian dari pertanyaan ini adalah bahwa program interaktif bukan algoritma (dengan asumsi bahwa seseorang menganggap algoritma untuk mengambil semua inputnya sekaligus, tetapi definisi sempit ini tidak termasuk algoritma online). Suatu program dapat berupa kumpulan proses yang berinteraksi yang juga berinteraksi dengan lingkungannya. Ini tentu saja tidak sesuai dengan gagasan teori Turing-machine / Recursion tentang algoritma.

Dave Clarke
sumber

IO dan efek samping secara umum tidak tercakup oleh gagasan algoritma klasik sama sekali.

Raphael

Ekstrem lainnya adalah dengan mengatakan dua program setara jika mereka menghitung fungsi yang sama (atau menunjukkan perilaku yang dapat diamati sama di lingkungan yang sama). Tapi ini tidak baik: tidak semua program memeriksa keaslian adalah sama. Kami dapat menambahkan baris kode tanpa efek pada hasilnya dan kami masih akan menganggapnya sebagai program yang sama.

Ini bukan ekstrem: kesetaraan program harus didefinisikan relatif terhadap gagasan pengamatan.

Definisi paling umum dalam penelitian PL adalah kesetaraan kontekstual. Dalam kesetaraan kontekstual, idenya adalah bahwa kita mengamati program dengan menggunakannya sebagai komponen program yang lebih besar (konteks). Jadi jika dua program menghitung nilai akhir yang sama untuk semua konteks, maka keduanya dinilai sama. Karena definisi ini mengkuantifikasi semua konteks program yang mungkin, sulit untuk dikerjakan secara langsung. Jadi program penelitian tipikal dalam PL adalah menemukan prinsip-prinsip penalaran komposisi yang menyiratkan kesetaraan kontekstual.

Namun, ini bukan satu-satunya gagasan pengamatan yang mungkin. Sebagai contoh, kita dapat dengan mudah mengatakan bahwa memori, waktu, atau perilaku kekuatan suatu program dapat diamati. Dalam hal ini, lebih sedikit kesetaraan program berlaku, karena kita dapat membedakan lebih banyak program (misalnya, mergesort sekarang dapat dibedakan dari quicksort). Jika Anda ingin (mengatakan) merancang bahasa yang kebal terhadap serangan saluran waktu, atau merancang bahasa pemrograman terbatas ruang, maka ini adalah hal yang harus Anda lakukan.

Selain itu, kami dapat memilih untuk menilai beberapa kondisi perantara dari suatu komputasi yang dapat diamati. Ini selalu terjadi untuk bahasa yang berbarengan, karena kemungkinan gangguan. Tetapi Anda mungkin ingin mengambil tampilan ini bahkan untuk bahasa berurutan --- misalnya, jika Anda ingin memastikan bahwa tidak ada perhitungan yang menyimpan data yang tidak terenkripsi di memori utama, maka Anda harus menganggap penulisan ke memori utama sebagai yang dapat diamati.

Pada dasarnya, tidak ada gagasan tunggal tentang kesetaraan program; itu selalu relatif terhadap gagasan pengamatan yang Anda pilih, dan itu tergantung pada aplikasi yang ada dalam pikiran Anda.

Neel Krishnaswami
sumber

Perlu ditunjukkan bahwa tidak ada gagasan unik tentang kesetaraan kontekstual (atau kesesuaian kontekstual), misalnya jika bahasa pemrograman yang dimaksud adalah interaktif (yaitu tidak menghasilkan nilai).

Martin Berger

α

$\alpha$

α

$\alpha$

α

$\alpha$

@ SamTobin-Hochstadt. Ok, mari kita lupakan "biasa". Perasaan yang saya dapatkan adalah bahwa Anda mengatakan hal yang sama dengan yang dikatakan Neel, yang menurut saya cukup baik. Gagasan Anda, yang masih samar bagi saya, dapat diformalkan dalam kerangka kerja Neel dengan memilih jenis pengamatan yang tepat dan konteks program yang tepat.

Uday Reddy

λ

$\lambda$

λ x . x

$\lambda x.x$

λ y . y

$\lambda y.y$

T2: Saya pikir definisi teoritis yang biasa tidak benar-benar membedakan antara algoritma dan program, tetapi "algoritma" seperti yang biasa digunakan lebih seperti kelas program. Bagi saya suatu algoritma adalah semacam program dengan beberapa subrutin yang tersisa tidak sepenuhnya ditentukan (yaitu perilaku yang diinginkan mereka didefinisikan tetapi tidak implementasi mereka). Sebagai contoh, algoritma eliminasi Gaussian tidak benar-benar menentukan bagaimana perkalian bilangan bulat harus dilakukan.

Saya minta maaf jika ini naif. Saya tidak melakukan riset PL.

Sasho Nikolov
sumber

Idenya mungkin adalah bahwa ada beberapa implementasi untuk subrutin tersebut dan Anda tidak peduli yang dipilih selama berkinerja sesuai dengan spesifikasi Anda.

Raphael