19
$\begingroup$

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

Improve this question
$\endgroup$
2

12 Answers 12

Reset to default
30
$\begingroup$

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

Improve this answer
$\endgroup$
1
16
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

Opening and doing a quick search in the (classic) Computational Complexity book of Arora and Barak (online draft here), 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").

Improve this answer
$\endgroup$
8
$\begingroup$

To complement some of the above answers, Avi Widgerson's recent book Mathematics and Computation 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.

Improve this answer
$\endgroup$
6
$\begingroup$

Here is another essay of a philosophical nature by Scott Aaronson. The Ghost in the Quantum Turing Machine

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

Avi Wigderson, in Knowledge, Creativity and P versus NP, argues that the philosophical question: Can creativity be automated? is equivalent to P = NP?.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

I highly recommend Pudlak's Logical Foundations of Mathematics and Computational Complexity.

Improve this answer
$\endgroup$
2
$\begingroup$

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, 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. 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:

  • In another unpublished manuscript of mine, 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 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 and Mathematics as Sign might be of interest.

  • Another area where computational complexity comes up sometimes is cognitive science. Two pointers come to mind:

    • This article by Pantsar connecting tractability and descriptive complexity to cognition.

    • This other paper 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!

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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