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.

Improve this question
$\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, 2016 at 21:33
  • 2
    $\begingroup$ I hope they keep a physical copy at the Hebrew University... $\endgroup$
    – Yuval Filmus
    Apr 3, 2016 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, 2016 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, 2016 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, 2016 at 14:50

1 Answer 1

Reset to default
14
$\begingroup$

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

Here is a scanned copy.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Nice. Are these hard copies? Do they offer PDF version? $\endgroup$
    – Mohammad Al-Turkistany
    Apr 3, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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.