<p>There are two loanable copies at The National Library of Israel. </p>

<p>Here is a scanned <a href="https://www.cs.toronto.edu/~sacook/homepage/rabin_thesis.pdf">copy</a>.</p>

CC BY-SA 3.0
2016-04-03T22:21:54.777Z
Nice. Are these hard copies? Do they offer PDF version?
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-04-03T22:23:15.863Z
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...
Yuval Filmus
CC BY-SA 3.0
2016-04-03T22:26:16.460Z
Thanks Yuval. I hope someone has a scanned copy (considering that it is one of the founding references of the complexity theory).
Kaveh
CC BY-SA 3.0
2016-04-05T15:52:18.350Z
@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.
Joshua Grochow
CC BY-SA 3.0
2016-04-05T16:21:51.013Z
@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.
Kaveh
CC BY-SA 3.0
2016-04-03T22:18:13.163Z
2016-04-06T14:43:57.407Z
2016-04-06T14:43:57.407Z
Yuval Filmus
<p>I am looking for:</p>

<ul>
<li>Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960</li>
</ul>

<p>Summary:</p>

<blockquote>
  <p>“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.”</p>
</blockquote>

<p>I couldn't find a copy online or at our library.</p>

CC BY-SA 3.0
2016-04-03T21:33:46.477Z
The title is interesting and the thesis should give insights into the early development of notions that capture the hardness of computing functions.
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-04-03T21:56:13.063Z
I hope they keep a physical copy at the Hebrew University...
Yuval Filmus
CC BY-SA 3.0
2016-04-04T15:00:13.097Z
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.
Yixin Cao
CC BY-SA 3.0
2016-04-04T16:00:26.613Z
@YixinCao comments are not suitable for asking new tangential questions. You can post a question on [academia.se].
Kaveh
CC BY-SA 3.0
2016-04-06T14:50:15.020Z
ps: it turns out it is not Rabin's thesis. His thesis according to Wikipedia is "Recursive Unsolvability of Group Theoretic Problems", 1957.
Kaveh
<cc.complexity-theory><reference-request><ho.history-overview>
Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"
Kaveh
# Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

(Asked by: username_0 on 2016-04-03)

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.

**Tags:** cc.complexity-theory, reference-request, ho.history-overview
> **Comments:**
> **username_1**: The title is interesting and the thesis should give insights into the early development of notions that capture the hardness of computing functions.  
> **username_2**: I hope they keep a physical copy at the Hebrew University...  
> **username_3**: 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.  
> **username_0**: @YixinCao comments are not suitable for asking new tangential questions. You can post a question on [academia.se].  
> **username_0**: ps: it turns out it is not Rabin's thesis. His thesis according to Wikipedia is "Recursive Unsolvability of Group Theoretic Problems", 1957.  

---

## 1 answers

### Answer by username_2 on 2016-04-03. Score: 14 | Accepted answer

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

Here is a scanned [copy](https://www.cs.toronto.edu/~sacook/homepage/rabin_thesis.pdf).

> **Comments:**
> **username_1**: Nice. Are these hard copies? Do they offer PDF version?  
> **username_2**: 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...  
> **username_0**: Thanks Yuval. I hope someone has a scanned copy (considering that it is one of the founding references of the complexity theory).  
> **username_4**: @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.  
> **username_0**: @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.  

---

