<p>Quantum Computing Since Democritus by Scott Aaronson is the closest match I can think of. I don't think there is a single book completely devoted to philosophical implications of TCS.</p>

CC BY-SA 3.0
2017-12-08T23:53:57.607Z
2017-12-08T23:53:57.607Z
Gustav Nordh
<p>To complement some of the above answers, Avi Widgerson's recent book <a href="https://www.math.ias.edu/files/mathandcomp.pdf#page=1" rel="noreferrer">Mathematics and Computation</a> briefly discusses philosophical interplays between computer science and philosophy in section 20.5. More broadly, the entire book contains a lot of material of philosophical interest, as it focuses mainly on the interplay between seemingly different fields, and does so by explaining the underlying structure and meaning of various concepts of ToC (randomness, knowledge, interaction, evolution, induction, learning... Among many others). While not a book about philosophy in itself, it makes the reader wonder about the new light shed by ToC on all these concepts. And it significantly departs from standard schoolbooks (indeed, that's not what this book is), as it contains no proofs. I highly recommend it.</p>

CC BY-SA 3.0
2017-12-12T23:05:56.340Z
2017-12-12T23:05:56.340Z
Geoffroy Couteau
<p>Opening and doing a quick search in the (classic) <em>Computational Complexity</em> book of Arora and Barak (<a href="http://theory.cs.princeton.edu/complexity/" rel="noreferrer">online draft here</a>), there are 19 occurrences of the word "philosophical", including such subsections as</p>

<ul>
<li><p>"On the philosophical importance of $\mathrm{P}$"</p></li>
<li><p>"The philosophical importance of $\mathrm{NP}$"</p></li>
<li><p>a discussion of randomness in Chapter 16 ("Derandomization, Expanders and Extractors").</p></li>
</ul>

CC BY-SA 3.0
2017-12-09T01:39:48.613Z
2017-12-09T01:39:48.613Z
Clement C.
<p>Here is another essay of a philosophical nature by Scott Aaronson. <a href="https://www.scottaaronson.com/papers/giqtm3.pdf" rel="noreferrer">The Ghost in the Quantum Turing Machine</a></p>

CC BY-SA 3.0
2017-12-10T15:32:24.460Z
2017-12-10T15:32:24.460Z
Abhishek Shetty
<p>John Searle in his book "<em>The Rediscovery of the Mind</em>" among other things raises the question what a computation is. In particular he states that "being computational" is not a property inherent to any process. Rather, there must be some observer attributing the "meaning" to the process. </p>

<p>This influential hypothesis has created quite some literature though mostly in the form of articles, not books, I think.  </p>

CC BY-SA 3.0
2017-12-12T15:49:19.917Z
2017-12-12T15:49:19.917Z
Peter Leupold
<p>Avi Wigderson, in <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf" rel="nofollow noreferrer">Knowledge, Creativity and P versus NP</a>, argues that the philosophical question: Can creativity be automated? is equivalent to P = NP?.</p>

CC BY-SA 3.0
2017-12-11T14:00:19.047Z
2017-12-11T14:00:19.047Z
Mohammad Al-Turkistany
<p>As far as I know, there is no book dedicated exclusively to philosophical <em>implications</em> of theoretical computer science. However, there is some philosophical work done around complexity theory and related topics, mostly in the context of philosophy of mathematics. That is, more about philosophical <em>applications</em>. Keep in mind that, due to the way theoretical computer science has historically developed (in computer science departments rather than in math of logic departments), philosophers have not paid much attention to it and have instead remained on the more mathematical logic side of things. As a result, the existing literature is scattered and not necessarily linked so precise results.</p>
<p>Nevertheless, the following are some pointers that come to mind (on top of the ones other users have suggested):</p>
<ul>
<li><p>Walter Dean, who is perhaps the contemporary analytic philosopher who was written the most about this, <a href="https://academic.oup.com/philmat/article-abstract/27/3/381/5613215?redirectedFrom=PDF&amp;casa_token=qbqNONrDZSoAAAAA:bqCLNM3H8m-mMttLMq4NkvsuHDjfXvduvPgawbJrJ5IQduqNgQT9AWBHajeGJTJ-IS3ENutD0nN6Pyk" rel="nofollow noreferrer">has a nice survey about computational complexity published on Philosophia Mathematica</a>, but this is more for philosophers who don't know about complexity theory</p>
</li>
<li><p>Dean is also the author of the <a href="https://plato.stanford.edu/entries/computational-complexity/" rel="nofollow noreferrer">Standford Encyclopedia of Philosophy entry on this same topic</a>. Section 4 contains references to some nice philosophical considerations.</p>
</li>
<li><p>The main philosophical connection between philosophy of mathematics and complexity theory is perhaps through issues related to ultrafinitism and proof complexity. Dean's SEP entry above outlines some of this, but if you want to go into more detail, the following might be relevant:</p>
<ul>
<li><p><a href="https://www.cambridge.org/core/journals/review-of-symbolic-logic/article/abs/strict-finitism-feasibility-and-the-sorites/F5886AF91E88F838AFEA1CB81184479B" rel="nofollow noreferrer">Dean's paper on how computational complexity brings light into the sorites paradox</a></p>
</li>
<li><p>I have myself written about this in the past. This is from a 2020 <a href="https://narteche.github.io/files/manuscripts/Strict%20Finitism%27s%20Unrequited%20Love%20for%20Computational%20Complexity%20%5BNoel%20Arteche%5D.pdf" rel="nofollow noreferrer">unpublished manuscript of mine</a> on the relation between complexity theory, philosophy of mathematics and strict finitism.</p>
</li>
</ul>
</li>
<li><p>In <a href="https://narteche.github.io/files/manuscripts/Between%20Invention%20and%20Discovery:%20What%20Video%20Game%20Speedrunning%20Can%20Teach%20Us%20about%20Mathematical%20Practice%20%5BNoel%20Arteche%5D.pdf" rel="nofollow noreferrer">another unpublished manuscript of mine</a>, amongst other things, I make some unorthodox philosophical remarks on the quest for faster matrix multiplication algorithms in the context of the philosophy of mathematical practice (see Section 3.2).</p>
</li>
<li><p>Thomas Tymoczko's <a href="https://press.princeton.edu/books/paperback/9780691034980/new-directions-in-the-philosophy-of-mathematics" rel="nofollow noreferrer">New Directions in the Philosophy of Mathematics</a> is a volume of collected works on alternative approaches to the philosophy of mathematics, some of which are inspired by issues involving tractability and computers. All of the essays there are really interesting, but in particular the ones by Lipton and Chaitin might the closest ones to TCS topics.</p>
</li>
<li><p>In a less analytic tradition (though not strictly continental, in case you are allergic to that), and also concerned with issues of strict finitism, computational complexity can be hinted at in some works by philosopher Brian Rotman. In particular, his books <a href="https://www.sup.org/books/title/?id=3034" rel="nofollow noreferrer">Ad Infinitum</a> and <a href="https://www.sup.org/books/title/?id=415" rel="nofollow noreferrer">Mathematics as Sign</a> might be of interest.</p>
</li>
<li><p>Another area where computational complexity comes up sometimes is cognitive science. Two pointers come to mind:</p>
<ul>
<li><p>This <a href="https://link.springer.com/article/10.1007/s11023-020-09545-4" rel="nofollow noreferrer">article by Pantsar</a> connecting tractability and descriptive complexity to cognition.</p>
</li>
<li><p><a href="https://psyarxiv.com/k79nv/" rel="nofollow noreferrer">This other paper</a> by Patricia Rich, Ronald de Haan, Todd Wareham and Iris van Rooij suggested looking at computational complexity and parameterized complexity in cognitive science. This in particular addresses the common concern some of us have that computational complexity is too idealistic and precise to be used to model real-world phenomena.</p>
</li>
</ul>
</li>
</ul>
<p>Hope this helps a bit!</p>

CC BY-SA 4.0
2023-01-16T18:52:17.280Z
2023-01-16T18:52:17.280Z
Noel Arteche
<p>I highly recommend Pudlak's <a href="https://link.springer.com/book/10.1007/978-3-319-00119-7" rel="nofollow noreferrer"><em>Logical Foundations of Mathematics and Computational Complexity</em></a>.</p>

CC BY-SA 4.0
2023-01-13T22:44:38.680Z
2023-01-13T22:44:38.680Z
Jim Hefferon
<p>The Philosophy of Computer Science, in the Stanford Encyclopedia of Philosophy: <a href="https://plato.stanford.edu/entries/computer-science/" rel="nofollow noreferrer">https://plato.stanford.edu/entries/computer-science/</a> with an interesting bibliography.</p>

CC BY-SA 4.0
2023-01-09T10:31:07.327Z
2023-01-09T10:31:07.327Z
Martin Berger
<p>I haven't done much reading myself but i find the book &quot;Structure and Interpretation of Computer Programs&quot; very eye opening.</p>
<p>Gerry Sussman has done an amazing work with that book.</p>
<p>It's worth a read. :-)</p>
<p><a href="https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book.html" rel="nofollow noreferrer">Full Book Here</a></p>

CC BY-SA 4.0
2017-12-10T06:51:22.643Z
2023-01-09T09:55:30.863Z
2023-01-09T09:55:30.863Z
sohom154
<p>lance fortnow "the golden ticket" , it deals with the consequences of what happens in case P=NP and other issues in a very lighter manner.</p>

CC BY-SA 3.0
2017-12-11T07:43:54.343Z
2017-12-11T07:43:54.343Z
thecomplexitytheorist
<p>Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" <a href="https://arxiv.org/abs/1108.1791" rel="noreferrer">https://arxiv.org/abs/1108.1791</a></p>

CC BY-SA 3.0
2017-12-10T01:46:11.170Z
It's apparently not on that essay, but Aaronson tends to quip that [computer science should be called quantitative epistemology](https://www.scottaaronson.com/democritus/lec13.html), which brings it closer to philosophical grounds.
E.P.
CC BY-SA 3.0
2017-12-09T00:20:25.030Z
2017-12-09T00:20:25.030Z
Ryan Williams
<p>I find some books about computers, but all of them are about technology. I want something more linked to theory.</p>

CC BY-SA 3.0
2017-12-09T12:22:34.190Z
[Gödel, Escher, Bach](https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach) comes to mind, but I'm not sure whether that's the kind of stuff you're looking for.
Martin Ender
CC BY-SA 3.0
2017-12-10T01:54:29.613Z
Is [Impagliazzo's Five Worlds](https://www.researchgate.net/publication/3653458_Personal_view_of_average-case_complexity) the kind of thing you're looking for?
E.P.
<reference-request><soft-question><philosophy>
Is there any book on the philosophical implications of Theoretical Computer Science?
Raphael Augusto
# Is there any book on the philosophical implications of Theoretical Computer Science?

(Asked by: username_0 on 2017-12-08)

I find some books about computers, but all of them are about technology. I want something more linked to theory.

**Tags:** reference-request, soft-question, philosophy
> **Comments:**
> **username_1**: [Gödel, Escher, Bach](https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach) comes to mind, but I'm not sure whether that's the kind of stuff you're looking for.  
> **username_2**: Is [Impagliazzo's Five Worlds](https://www.researchgate.net/publication/3653458_Personal_view_of_average-case_complexity) the kind of thing you're looking for?  

---

## 12 answers

### Answer by username_14 on 2017-12-09. Score: 30 | Accepted answer

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" <https://arxiv.org/abs/1108.1791>

> **Comments:**
> **username_2**: It's apparently not on that essay, but Aaronson tends to quip that [computer science should be called quantitative epistemology](https://www.scottaaronson.com/democritus/lec13.html), which brings it closer to philosophical grounds.  

---

### Answer by username_3 on 2017-12-08. Score: 16

Quantum Computing Since Democritus by Scott Aaronson is the closest match I can think of. I don't think there is a single book completely devoted to philosophical implications of TCS.


---

### Answer by username_4 on 2017-12-12. Score: 8

To complement some of the above answers, Avi Widgerson's recent book [Mathematics and Computation](https://www.math.ias.edu/files/mathandcomp.pdf#page=1) briefly discusses philosophical interplays between computer science and philosophy in section 20.5. More broadly, the entire book contains a lot of material of philosophical interest, as it focuses mainly on the interplay between seemingly different fields, and does so by explaining the underlying structure and meaning of various concepts of ToC (randomness, knowledge, interaction, evolution, induction, learning... Among many others). While not a book about philosophy in itself, it makes the reader wonder about the new light shed by ToC on all these concepts. And it significantly departs from standard schoolbooks (indeed, that's not what this book is), as it contains no proofs. I highly recommend it.


---

### Answer by username_5 on 2017-12-09. Score: 8

Opening and doing a quick search in the (classic) *Computational Complexity* book of Arora and Barak ([online draft here](http://theory.cs.princeton.edu/complexity/)), there are 19 occurrences of the word "philosophical", including such subsections as

* "On the philosophical importance of $\mathrm{P}$"
* "The philosophical importance of $\mathrm{NP}$"
* a discussion of randomness in Chapter 16 ("Derandomization, Expanders and Extractors").


---

### Answer by username_6 on 2017-12-10. Score: 6

Here is another essay of a philosophical nature by Scott Aaronson. [The Ghost in the Quantum Turing Machine](https://www.scottaaronson.com/papers/giqtm3.pdf)


---

### Answer by username_7 on 2017-12-12. Score: 4

John Searle in his book "*The Rediscovery of the Mind*" among other things raises the question what a computation is. In particular he states that "being computational" is not a property inherent to any process. Rather, there must be some observer attributing the "meaning" to the process.

This influential hypothesis has created quite some literature though mostly in the form of articles, not books, I think.


---

### Answer by username_8 on 2017-12-11. Score: 3

Avi Wigderson, in [Knowledge, Creativity and P versus NP](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf), argues that the philosophical question: Can creativity be automated? is equivalent to P = NP?.


---

### Answer by username_9 on 2023-01-16. Score: 2

As far as I know, there is no book dedicated exclusively to philosophical *implications* of theoretical computer science. However, there is some philosophical work done around complexity theory and related topics, mostly in the context of philosophy of mathematics. That is, more about philosophical *applications*. Keep in mind that, due to the way theoretical computer science has historically developed (in computer science departments rather than in math of logic departments), philosophers have not paid much attention to it and have instead remained on the more mathematical logic side of things. As a result, the existing literature is scattered and not necessarily linked so precise results.

Nevertheless, the following are some pointers that come to mind (on top of the ones other users have suggested):

* Walter Dean, who is perhaps the contemporary analytic philosopher who was written the most about this, [has a nice survey about computational complexity published on Philosophia Mathematica](https://academic.oup.com/philmat/article-abstract/27/3/381/5613215?redirectedFrom=PDF&casa_token=qbqNONrDZSoAAAAA:bqCLNM3H8m-mMttLMq4NkvsuHDjfXvduvPgawbJrJ5IQduqNgQT9AWBHajeGJTJ-IS3ENutD0nN6Pyk), but this is more for philosophers who don't know about complexity theory
* Dean is also the author of the [Standford Encyclopedia of Philosophy entry on this same topic](https://plato.stanford.edu/entries/computational-complexity/). Section 4 contains references to some nice philosophical considerations.
* The main philosophical connection between philosophy of mathematics and complexity theory is perhaps through issues related to ultrafinitism and proof complexity. Dean's SEP entry above outlines some of this, but if you want to go into more detail, the following might be relevant:

  + [Dean's paper on how computational complexity brings light into the sorites paradox](https://www.cambridge.org/core/journals/review-of-symbolic-logic/article/abs/strict-finitism-feasibility-and-the-sorites/F5886AF91E88F838AFEA1CB81184479B)
  + I have myself written about this in the past. This is from a 2020 [unpublished manuscript of mine](https://narteche.github.io/files/manuscripts/Strict%20Finitism%27s%20Unrequited%20Love%20for%20Computational%20Complexity%20%5BNoel%20Arteche%5D.pdf) on the relation between complexity theory, philosophy of mathematics and strict finitism.
* In [another unpublished manuscript of mine](https://narteche.github.io/files/manuscripts/Between%20Invention%20and%20Discovery:%20What%20Video%20Game%20Speedrunning%20Can%20Teach%20Us%20about%20Mathematical%20Practice%20%5BNoel%20Arteche%5D.pdf), amongst other things, I make some unorthodox philosophical remarks on the quest for faster matrix multiplication algorithms in the context of the philosophy of mathematical practice (see Section 3.2).
* Thomas Tymoczko's [New Directions in the Philosophy of Mathematics](https://press.princeton.edu/books/paperback/9780691034980/new-directions-in-the-philosophy-of-mathematics) is a volume of collected works on alternative approaches to the philosophy of mathematics, some of which are inspired by issues involving tractability and computers. All of the essays there are really interesting, but in particular the ones by Lipton and Chaitin might the closest ones to TCS topics.
* In a less analytic tradition (though not strictly continental, in case you are allergic to that), and also concerned with issues of strict finitism, computational complexity can be hinted at in some works by philosopher Brian Rotman. In particular, his books [Ad Infinitum](https://www.sup.org/books/title/?id=3034) and [Mathematics as Sign](https://www.sup.org/books/title/?id=415) might be of interest.
* Another area where computational complexity comes up sometimes is cognitive science. Two pointers come to mind:

  + This [article by Pantsar](https://link.springer.com/article/10.1007/s11023-020-09545-4) connecting tractability and descriptive complexity to cognition.
  + [This other paper](https://psyarxiv.com/k79nv/) by Patricia Rich, Ronald de Haan, Todd Wareham and Iris van Rooij suggested looking at computational complexity and parameterized complexity in cognitive science. This in particular addresses the common concern some of us have that computational complexity is too idealistic and precise to be used to model real-world phenomena.

Hope this helps a bit!


---

### Answer by username_10 on 2023-01-13. Score: 2

I highly recommend Pudlak's [*Logical Foundations of Mathematics and Computational Complexity*](https://link.springer.com/book/10.1007/978-3-319-00119-7).


---

### Answer by username_11 on 2023-01-09. Score: 2

The Philosophy of Computer Science, in the Stanford Encyclopedia of Philosophy: <https://plato.stanford.edu/entries/computer-science/> with an interesting bibliography.


---

### Answer by username_12 on 2017-12-10. Score: 1

I haven't done much reading myself but i find the book "Structure and Interpretation of Computer Programs" very eye opening.

Gerry Sussman has done an amazing work with that book.

It's worth a read. :-)

[Full Book Here](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book.html)


---

### Answer by username_13 on 2017-12-11. Score: 1

lance fortnow "the golden ticket" , it deals with the consequences of what happens in case P=NP and other issues in a very lighter manner.


---

