Contoh Dijkstra tentang program yang ambigu

Salam Dijkstra menulis bahwa bahkan beberapa baris kode yang kelihatannya sederhana dapat menjadi sangat membingungkan. Setidaknya dalam satu karya, yang saya tidak dapat menemukan sekarang untuk menyelamatkan hidup saya, dia memberikan sedikit contoh program untuk menunjukkan ambiguitas ini. Adakah yang bisa mengarahkan saya ke makalahnya di mana ia memasukkan salah satu contoh ini?

ambiguity Dijkstra Reader
sumber

Jawaban:

Baca ini:

http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions

http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ memiliki jangkauan yang bagus; mencari "masalah terputus-putus"

Ada beberapa bentuk kontradiksi penghentian penting.

def halts( code_block ):
    # Some magical code

def whistler():
    while halts(whistler): 
        sys.whistle( 1 )

Apakah "siulan" bersiul nol, sekali atau jumlah yang tak terbatas?

Jika halts()fungsi menentukan bahwa fungsi tersebut whistlertampaknya berhenti, fungsi whistlertersebut tidak dapat berhenti.

Jika halts()fungsi menentukan bahwa fungsi whistlertidak muncul berhenti, fungsi whistlerberhenti.

Karena itu, halts()fungsinya tidak bisa ada.

S.Lott
sumber

Anda lupa opsi ketiga, di mana ia kembali FILE_NOT_FOUND;)

FrustratedWithFormsDesigner

Terima kasih! Apa yang Dijkstra gambarkan di koran yang saya baca bukanlah masalah yang berhenti. Itu hanya beberapa baris kode sederhana, tetapi Anda tidak bisa mengatakan apa artinya. Konteksnya adalah bahwa Dijkstra berbicara tentang metode yang ia gunakan untuk menunjukkan kepada audiens bahwa pemrograman itu sulit, oleh karena itu programmer harus rendah hati. Perhatikan bahwa makalahnya tidak, saya sedih mengatakan, "Programmer Humble." :)

Dijkstra Reader

Apakah Anda berbicara tentang cs.utexas.edu/users/EWD/transcription/EWD06xx/EWD658.html ?

S.Lott

Terima kasih lagi. Sedih untuk dikatakan, bukan itu yang salah. Dalam makalah yang saya maksudkan, Dijkstra secara khusus mengatakan pemrograman itu sulit, bahkan untuk orang pintar, kita harus menghargai itu, "Misalnya, apa yang dilakukan program kecil berikut?"

Dijkstra Reader

Mungkin bukan cs.utexas.edu/~EWD/transcription/EWD03xx/EWD340.html . Tapi saya mengangkatnya sebagai kutipan umum tentang betapa sulitnya pemrograman.

S.Lott

Apakah Anda yakin makalah itu ditulis oleh Dijkstra? Refleksi Kepercayaan Kepercayaan oleh Ken Thompson sepertinya bisa jadi apa yang Anda pikirkan. Ini menunjukkan bagaimana program yang benar-benar sederhana, langsung, dan benar dapat berakhir dengan melakukan sesuatu yang benar-benar tidak terduga yang sama sekali tidak terlihat di sumbernya. Bahkan jika itu bukan apa yang Anda pikirkan, itu adalah makalah yang bermanfaat untuk dibaca.

Pergi ke arah yang berbeda, jika Anda menginginkan contoh program pendek yang bagus dengan perilaku yang mengejutkan, kontes C yang curang itu bagus. Contohnya lihat pemenang 2008 . Tantangannya adalah untuk menulis program baris perintah untuk mengosongkan bagian dari gambar, sedemikian rupa sehingga gambar secara visual dihilangkan dengan sempurna, tetapi file tersebut mempertahankan beberapa informasi tentang bagian gambar yang telah dihapus. DAN sedemikian rupa sehingga kode Anda dapat lulus tinjauan kode. (Anda dapat memilih format penyimpanan gambar.)

btilly
sumber

Terima kasih! Ya, ini jelas makalah dari Dijkstra yang saya maksudkan.

Dijkstra Reader