"Tingkat kesulitan Rabin dalam menghitung suatu fungsi, dan urutan parsial set rekursif"

Saya mencari:

Michael O. Rabin, "Tingkat kesulitan menghitung fungsi, dan urutan parsial set rekursif", Universitas Ibrani, Yerusalem, 1960

Ringkasan:

“Kami berupaya mengukur jumlah pekerjaan yang melekat dalam tugas menghitung fungsi komputasi (rekursif) yang diberikan. Konsep tingkat kesulitan komputasi diperkenalkan dan dipelajari. Gagasan ini invarian dalam arti bahwa itu tidak tergantung pada komputer ideal (Turing Machines) yang digunakan untuk menghitung fungsi yang dimaksud. Aplikasi dibuat untuk klasifikasi masalah keputusan yang dapat dipecahkan (set rekursif) sesuai dengan kesulitan relatif. "

Saya tidak dapat menemukan salinannya di internet atau di perpustakaan kami.

cc.complexity-theory reference-request ho.history-overview Kaveh
sumber

Judul ini menarik dan tesis harus memberikan wawasan tentang perkembangan awal gagasan yang menangkap kekerasan fungsi komputasi.

Mohammad Al-Turkistany

Saya harap mereka menyimpan salinan fisik di Universitas Ibrani ...

Yuval Filmus

Sebuah komentar yang tidak (secara langsung) relevan dengan OP: apakah itu sah untuk mengumpulkan repositori online lama (saya tidak tahu berapa lama memenuhi syarat sebagai tua) tesis / disertasi dan memungkinkan akses gratis? Karena banyak alasan, yang baru biasanya mudah didapat.

Yixin Cao

Komentar @YixinCao tidak cocok untuk mengajukan pertanyaan tangensial baru. Anda dapat memposting pertanyaan di Academia .

Kaveh

ps: ternyata itu bukan tesis Rabin. Tesisnya menurut Wikipedia adalah "Unsurvabilitas Berulang dari Masalah Teori Kelompok", 1957.

Kaveh

Jawaban:

Ada dua salinan pinjaman di Perpustakaan Nasional Israel.

Ini salinan yang dipindai .

Yuval Filmus
sumber

Bagus. Apakah ini hard copy? Apakah mereka menawarkan versi PDF?

Mohammad Al-Turkistany

Salinan keras. Tapi mungkin mereka akan memindai sesuai permintaan. Saya mungkin bisa mendapatkan salinan fisik sendiri, meskipun saya tidak akan memindai semuanya sendiri ...

Yuval Filmus

Yuval terima kasih. Saya harap seseorang memiliki salinan yang dipindai (mengingat bahwa itu adalah salah satu referensi pendiri teori kompleksitas).

Kaveh

@ Kaveh: Apakah itu salah satu referensi pendiri? Aku belum pernah melihat itu dikutip ... Saya memiliki scan Rabin "matematika Teori Automata," yang merupakan salah satu dari tiga makalah sering dikutip karena telah memperkenalkan konsep P (dan yang karena itu saya lakukan mempertimbangkan dasar). Beri tahu saya jika Anda menyukainya.

Joshua Grochow

@Josh, saya telah melihatnya dikutip bersama dengan Cobham dan Edmonds dan Hartmanis dan Stearns sebagai makalah pertama yang berbicara tentang apa yang sekarang disebut teori kompleksitas komputasi. Untungnya Steve memiliki salinan tesis Rabin, dia bilang dia akan memindai dan mempostingnya secara online.

Kaveh