<p>The two books that come to mind are</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/113318779X" rel="nofollow"><em>Introduction to the Theory of Computation</em></a> by Sipser</p>

<p>and</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0262033844" rel="nofollow"><em>Introduction to Algorithms</em></a> by Cormen et al.</p>

<p>I agree with usul who said that theoretical computer science is a broad area and we could give better references if you were more specific about what you want to learn.</p>

CC BY-SA 3.0
2013-05-20T09:31:39.913Z
I wouldn't recommend the verbose *Introduction to Algorithms*. If one wishes to be introduced with the basic algorithmic techniques, I would recommend one of *Algorithms* by Dasgupta, Papadimitriou and Vazirani, *Algorithm Design* by Kleinberg and Tardos, or *The Design and Analysis of Algorithms* by Kozen. *Introduction to the Theory of Computation* by Sipser is an obviously great choice. I would also add some book on Computational Complexity (I find the ones by Papdimitriou, Arora and Barak, and Goldreich all excellent).
Bruno
CC BY-SA 3.0
2013-05-20T11:44:08.817Z
My personal preference is for Kozen's Theory of Computation (quite mathematical in style, and with a larger coverage of logic and computability) over Sipser (which is much closer in style to an applied computer science book).
András Salamon
CC BY-SA 3.0
2013-05-19T19:16:45.473Z
2013-05-19T19:16:45.473Z
Kevin A. Wortman
<p>You're essentially asking for resources that will let you turn your existing knowledge of logic, recursion theory, and category theory into knowledge about theoretical computer science.I would suggest looking at realizability theory, especially via its connections to topos theory and categorical proof theory. </p>

<p>Here are a handful of suggestions; my advice is to pick one and go into depth. With the exception of Taylor's book (which explains this), my suggestions assume you have been exposed to enough lambda calculus and category theory to have seen categorical interpretations of the simply-typed lambda calculus.</p>

<ul>
<li><p>Paul Taylor's book <em>Practical Foundations of Mathematics</em></p>

<p>IMO, this is probably the single best technical introduction to the relationship between logic, category theory and computation. It assumes almost no pre-requisites, but it gets into quite deep waters very quickly, and is sure to tax (and greatly improve) your mathematical maturity.  </p></li>
<li><p>Wesley Phoa's notes <a href="http://www.lfcs.inf.ed.ac.uk/reports/92/ECS-LFCS-92-208/ECS-LFCS-92-208.ps"><em>An Introduction to Fibrations, Topos Theory, the Effective Topos, and Modest Sets</em></a></p>

<p>These are some lecture notes that Wesley Phoa wrote up. If you are categorically fluent, then these notes offer a really fast path into understanding some of the most  important constructions in realizability and topos theory (namely, the construction of the effective topos).  </p></li>
<li><p>Bart Jacobs' book <em>Categorical Logic and Type Theory</em></p>

<p>This is one of the definitive references on the categorical semantics of type theory. It is also very large. </p></li>
</ul>

<p>At the same time you are reading one of these books, I would advise downloading and learn how to use the <a href="http://wiki.portal.chalmers.se/agda/pmwiki.php">Agda programming language</a>. This language implements the sophisticated type theories described above, and IMO it is incredibly helpful to see how the often quite subtle semantic constructions cash out in type theory. </p>

<p>Andrej Bauer can probably give you even better advice. Perhaps he can be persuaded to post. :) </p>

CC BY-SA 3.0
2013-05-17T19:47:13.720Z
2013-05-17T19:47:13.720Z
Neel Krishnaswami
<p><strong>Background</strong>:</p>

<p>I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g. recursion theory, lambda calculus, but the underlying CS is brushed under the rug. My main areas of interest - set theory and category theory - also have applications in computer science, but so far I've only studied them from the point of view of pure mathematics.</p>

<p><strong>Problem:</strong></p>

<p>My lack of any computer science background sometimes makes it difficult to see the motivation or intuition behind what is going on, or how it could be applied. I get by, but I feel like it would be healthier to branch out a little bit... it occurs to me that, for the benefit of my future research, I should learn some computer science.</p>

<p>Most CS books I've looked at haven't been very suitable for my purposes, either being too basic and untechnical, or presupposing the kind of CS background that I don't have. They seem to be aimed at people who are quite computer-savvy but who have little in the way in mathematical background - my situation is the opposite.</p>

<p><strong>Question:</strong></p>

<blockquote>
  <p>What books or other resources are there which could help a mathematician-turned-logician in their goal of gaining a working knowledge of (theoretical) computer science?</p>
</blockquote>

<p>I'm looking for something more wholesome than a few seminar talks and more in-depth than <em>The New Turing Omnibus</em>, but I don't have the time or resources to do another undergraduate degree. (It may be that I'm asking for something that doesn't exist.)</p>

<p>Sorry if the question is too vague or ill-posed. I felt it was more suitable here than on <a href="https://math.stackexchange.com/">MSE</a> but I'll be happy to migrate it if needs be.</p>

CC BY-SA 3.0
2013-05-17T16:44:23.927Z
Theoretical computer science makes a lot more sense if one is a good, or at least reasonable programmer, because in some sense, all (most) of TCS is a formalisation (and simplification) of what working programmers do. We had a thread about [related matters](http://cstheory.stackexchange.com/questions/8851/how-important-is-knowing-how-to-program-for-tcs/8889#8889)
Martin Berger
CC BY-SA 3.0
2013-05-17T17:07:25.487Z
this was answered on mathoverflow [computer science for mathematicians](http://mathoverflow.net/questions/51217/computer-science-for-mathematicians) but maybe there is room for a TCS.se version
vzn
CC BY-SA 3.0
2013-05-17T17:46:16.910Z
For computability and basic complexity theory, how about Sipser's Introduction to the Theory of Computation? I am puzzled you have not found mathematically oriented books, because there is plenty of them. For example, Arora and Barak, and Goldreich have recent complexity theory books available online, and I am sure there are plenty of math-y track-b theory books out there.
Sasho Nikolov
CC BY-SA 3.0
2013-05-18T12:42:26.933Z
Computer Science is quite big; can you narrow it down? It sounds like you are mainly interested in computability, type theory/programming languages, and perhaps complexity theory; does that sound right?
usul
CC BY-SA 3.0
2013-05-21T21:44:48.207Z
You might find the _Handbook of Logic in Computer Science_ useful for reference.
Radu GRIGore
CC BY-SA 3.0
2016-02-16T05:50:46.903Z
BTW, I know this is old -- but have you got any actual programming experience?
galois
<reference-request><soft-question>
Resources for mathematicians hoping to learn more computer science
Clive Newstead
# Resources for mathematicians hoping to learn more computer science

(Asked by: username_0 on 2013-05-17)

**Background**:

I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g. recursion theory, lambda calculus, but the underlying CS is brushed under the rug. My main areas of interest - set theory and category theory - also have applications in computer science, but so far I've only studied them from the point of view of pure mathematics.

**Problem:**

My lack of any computer science background sometimes makes it difficult to see the motivation or intuition behind what is going on, or how it could be applied. I get by, but I feel like it would be healthier to branch out a little bit... it occurs to me that, for the benefit of my future research, I should learn some computer science.

Most CS books I've looked at haven't been very suitable for my purposes, either being too basic and untechnical, or presupposing the kind of CS background that I don't have. They seem to be aimed at people who are quite computer-savvy but who have little in the way in mathematical background - my situation is the opposite.

**Question:**

> What books or other resources are there which could help a mathematician-turned-logician in their goal of gaining a working knowledge of (theoretical) computer science?

I'm looking for something more wholesome than a few seminar talks and more in-depth than *The New Turing Omnibus*, but I don't have the time or resources to do another undergraduate degree. (It may be that I'm asking for something that doesn't exist.)

Sorry if the question is too vague or ill-posed. I felt it was more suitable here than on [MSE](https://math.stackexchange.com/) but I'll be happy to migrate it if needs be.

**Tags:** reference-request, soft-question

> **Comments:**
> **username_1**: Theoretical computer science makes a lot more sense if one is a good, or at least reasonable programmer, because in some sense, all (most) of TCS is a formalisation (and simplification) of what working programmers do. We had a thread about [related matters](http://cstheory.stackexchange.com/questions/8851/how-important-is-knowing-how-to-program-for-tcs/8889#8889)  
> **username_2**: this was answered on mathoverflow [computer science for mathematicians](http://mathoverflow.net/questions/51217/computer-science-for-mathematicians) but maybe there is room for a TCS.se version  
> **username_3**: For computability and basic complexity theory, how about Sipser's Introduction to the Theory of Computation? I am puzzled you have not found mathematically oriented books, because there is plenty of them. For example, Arora and Barak, and Goldreich have recent complexity theory books available online, and I am sure there are plenty of math-y track-b theory books out there.  
> **username_4**: Computer Science is quite big; can you narrow it down? It sounds like you are mainly interested in computability, type theory/programming languages, and perhaps complexity theory; does that sound right?  
> **username_5**: You might find the _Handbook of Logic in Computer Science_ useful for reference.  
> **username_6**: BTW, I know this is old -- but have you got any actual programming experience?  

---

## 2 answers

### Answer by username_10 on 2013-05-17. Score: 12 | Accepted answer

You're essentially asking for resources that will let you turn your existing knowledge of logic, recursion theory, and category theory into knowledge about theoretical computer science.I would suggest looking at realizability theory, especially via its connections to topos theory and categorical proof theory.

Here are a handful of suggestions; my advice is to pick one and go into depth. With the exception of Taylor's book (which explains this), my suggestions assume you have been exposed to enough lambda calculus and category theory to have seen categorical interpretations of the simply-typed lambda calculus.

* Paul Taylor's book *Practical Foundations of Mathematics*

  IMO, this is probably the single best technical introduction to the relationship between logic, category theory and computation. It assumes almost no pre-requisites, but it gets into quite deep waters very quickly, and is sure to tax (and greatly improve) your mathematical maturity.
* Wesley Phoa's notes [*An Introduction to Fibrations, Topos Theory, the Effective Topos, and Modest Sets*](http://www.lfcs.inf.ed.ac.uk/reports/92/ECS-LFCS-92-208/ECS-LFCS-92-208.ps)

  These are some lecture notes that Wesley Phoa wrote up. If you are categorically fluent, then these notes offer a really fast path into understanding some of the most important constructions in realizability and topos theory (namely, the construction of the effective topos).
* Bart Jacobs' book *Categorical Logic and Type Theory*

  This is one of the definitive references on the categorical semantics of type theory. It is also very large.

At the same time you are reading one of these books, I would advise downloading and learn how to use the [Agda programming language](http://wiki.portal.chalmers.se/agda/pmwiki.php). This language implements the sophisticated type theories described above, and IMO it is incredibly helpful to see how the often quite subtle semantic constructions cash out in type theory.

Andrej Bauer can probably give you even better advice. Perhaps he can be persuaded to post. :)


---

### Answer by username_7 on 2013-05-19. Score: 4

The two books that come to mind are

[*Introduction to the Theory of Computation*](http://rads.stackoverflow.com/amzn/click/113318779X) by Sipser

and

[*Introduction to Algorithms*](http://rads.stackoverflow.com/amzn/click/0262033844) by Cormen et al.

I agree with username_4 who said that theoretical computer science is a broad area and we could give better references if you were more specific about what you want to learn.

> **Comments:**
> **username_8**: I wouldn't recommend the verbose *Introduction to Algorithms*. If one wishes to be introduced with the basic algorithmic techniques, I would recommend one of *Algorithms* by Dasgupta, Papadimitriou and Vazirani, *Algorithm Design* by Kleinberg and Tardos, or *The Design and Analysis of Algorithms* by Kozen. *Introduction to the Theory of Computation* by Sipser is an obviously great choice. I would also add some book on Computational Complexity (I find the ones by Papdimitriou, Arora and Barak, and Goldreich all excellent).  
> **username_9**: My personal preference is for Kozen's Theory of Computation (quite mathematical in style, and with a larger coverage of logic and computability) over Sipser (which is much closer in style to an applied computer science book).  

---

