Apakah mungkin membuktikan suatu fungsi idempoten?

12

Apakah mungkin menggunakan tipe statis atau dependen untuk membuktikan fungsi idempoten?

Saya telah mencari Google dan berbagai tempat di StackOverflow / StackExchange untuk jawabannya tetapi tidak berhasil. Yang paling dekat yang saya temukan adalah percakapan tentang Idris ini: https://groups.google.com/forum/#!topic/idris-lang/yp7vrspChRg

Sayangnya, diskusi itu sedikit di luar kepala saya.

haskell bmaddy
sumber
3
Saya tidak memposting ini sebagai jawaban karena saya tidak 100% yakin, tapi saya percaya ini tidak mungkin karena Teorema Rice .
Gardenhead
4
Ini adalah pertanyaan yang menarik, dan intuisi saya menunjukkan ini harus dimungkinkan dalam bahasa yang terbatas, non-Turing-lengkap. Namun, Pemrogram fokus pada pertanyaan mengenai siklus hidup pengembangan perangkat lunak (lihat pusat bantuan untuk detail), sedangkan ini tampaknya menjadi pertanyaan ilmu komputer. Situs Ilmu Komputer mungkin lebih cocok dan mengarah ke jawaban yang lebih baik.
amon
2
Teorema @gardenhead Rice menyatakan bahwa diberikan properti apa pun yang bisa dimiliki oleh perilaku suatu program, terkadang tidak mungkin untuk menentukan apakah suatu program memiliki properti itu atau tidak. Ada perbedaan besar antara "ini kadang-kadang tidak mungkin" dan "ini tidak mungkin".
Tanner Swett
2
Komentar terakhir saya cukup samar. Bagaimanapun, inilah yang dikatakan teorema Rice: tidak ada algoritma yang dengan benar mengklasifikasikan semua fungsi sebagai idempoten atau bukan idempoten. Namun, masih ada algoritma yang berguna yang mengklasifikasikan beberapa fungsi sebagai idempoten atau tidak.
Tanner Swett
2
OP bertanya tentang membuktikan bahwa suatu fungsi idempoten, tidak memiliki algoritma yang mengklasifikasikan fungsi sebagai idemptoten atau tidak. Perbedaan utama adalah bahwa bukti dapat ditulis oleh seseorang. Sedangkan untuk kelengkapan Turing, memang bukan masalah .
gallais

Jawaban:

3

Untuk fungsi-fungsi tertentu. Terutama ketika Anda tahu fungsinya ;-)

Jika Anda maksud dengan pertanyaan Anda "apakah ada algoritma untuk memutuskan secara otomatis jika fungsi arbitrer idempoten atau tidak", jawabannya tidak, karena teorema yang telah disebutkan dalam komentar. Namun, untuk kelas fungsi tertentu, seseorang dapat - dalam teori - sangat mudah memutuskan apakah fungsi tersebut idempoten atau tidak. Misalnya, jika fungsinya murni (berarti: tanpa efek samping), dan orang tahu itu selalu mengembalikan nilai dalam jumlah waktu terbatas untuk setiap input yang diberikan, maka idempotensi dapat diputuskan hanya dengan mencoba jika f(f(x))=f(x)ada kemungkinan input xke fungsi. Bukannya ini akan sangat efisien, itu bisa berjalan sampai akhir jagat raya.

Jadi jika itu bukan jawaban yang Anda cari, tulis pertanyaan yang lebih baik, saat ini cukup tidak jelas apa sebenarnya yang sebenarnya Anda cari.

Doc Brown
sumber
Terima kasih atas jawabannya. Kemampuan untuk "memutuskan secara otomatis" adalah persis apa yang saya cari.
bmaddy
2
Untuk memperluas pernyataan 'untuk fungsi-fungsi tertentu itu adalah' : Idempotensi dapat dibuktikan untuk fungsi apa pun yang hanya menerima jumlah input yang terbatas (dengan mencoba semuanya), atau jenis input yang didefinisikan secara rekursif (seperti natural angka, atau daftar tertaut), yang berarti Anda hanya perlu membuktikan bahwa idempotensi benar untuk case dasar dan case recursive.
Qqwy