13
$\begingroup$

I am looking for:

  • Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960

Summary:

“We attempt to measure the amount of work inherent in the task of computing a given computable (recursive) function. A notion of degree of difficulty of computing is introduced and studied. The notion is invariant in the sense that it is independent of the idealized computers (Turing Machines) used for computing the functions in question. Applications are made to the classification of solvable decision problems (recursive sets) according to relative difficulty.”

I couldn't find a copy online or at our library.

$\endgroup$
5
  • 1
    $\begingroup$ The title is interesting and the thesis should give insights into the early development of notions that capture the hardness of computing functions. $\endgroup$ – Mohammad Al-Turkistany Apr 3 '16 at 21:33
  • 2
    $\begingroup$ I hope they keep a physical copy at the Hebrew University... $\endgroup$ – Yuval Filmus Apr 3 '16 at 21:56
  • $\begingroup$ A comment not (directly) relevant to the OP: is that legal to collect a online repository of old (I don't know how long is qualified as old) theses/dissertations and allow free access? For many reasons, the newer ones are usually easy to get. $\endgroup$ – Yixin Cao Apr 4 '16 at 15:00
  • $\begingroup$ @YixinCao comments are not suitable for asking new tangential questions. You can post a question on Academia. $\endgroup$ – Kaveh Apr 4 '16 at 16:00
  • $\begingroup$ ps: it turns out it is not Rabin's thesis. His thesis according to Wikipedia is "Recursive Unsolvability of Group Theoretic Problems", 1957. $\endgroup$ – Kaveh Apr 6 '16 at 14:50
14
$\begingroup$

There are two loanable copies at The National Library of Israel.

Here is a scanned copy.

$\endgroup$
5
  • 1
    $\begingroup$ Nice. Are these hard copies? Do they offer PDF version? $\endgroup$ – Mohammad Al-Turkistany Apr 3 '16 at 22:21
  • 2
    $\begingroup$ Hard copies. But perhaps they will scan them on demand. I can probably get hold of a physical copy myself, though I'm not going to scan it all by myself... $\endgroup$ – Yuval Filmus Apr 3 '16 at 22:23
  • 3
    $\begingroup$ Thanks Yuval. I hope someone has a scanned copy (considering that it is one of the founding references of the complexity theory). $\endgroup$ – Kaveh Apr 3 '16 at 22:26
  • $\begingroup$ @Kaveh: Is it one of the founding references? I have never seen it cited... I have a scan of Rabin's "Mathematical Theory of Automata," which is one of the three papers often cited for having introduced the notion of P (and which I therefore do consider foundational). Let me know if you'd like it. $\endgroup$ – Joshua Grochow Apr 5 '16 at 15:52
  • $\begingroup$ @Josh, I have seen it cited together with Cobham's and Edmonds' and Hartmanis and Stearns's as first papers talking about what is now called computational complexity theory. Fortunately Steve has a copy of Rabin's thesis, he said he will scan and post it online. $\endgroup$ – Kaveh Apr 5 '16 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.