I am interested in learning about the fundamental limits of computation and in particular would like to read textbooks on the subject if they exist. My background is in maths and computer science - I am certainly not looking for books on complexity theory.

Example questions I am looking to answer/be able to interpret:

  1. What is the amount of energy required (as a fundamental limit) to divide two numbers?
  2. What is the smallest volume of space which can retrievably store $n$ bits of data?
  3. What is the fundamentally shortest running time of an algorithm with $n$ steps? (where steps are suitably defined by some fundamental physical definition of a computer)

I have heard of quantum-information theory, but I'm not sure that's precisely what I'm looking for.

  • $\begingroup$ Computational complexity. $\endgroup$ – Lewis Miller May 30 '19 at 17:28
  • $\begingroup$ I don't see these questions well-formulated to have a single answer. For example, for question 1 you can have several devices from abacus to digital computers passing by analogic computers. $\endgroup$ – nicoguaro May 30 '19 at 17:29
  • $\begingroup$ My question explicitly states I'm not looking for books on complexity theory, I am interested in fundamental physical limits. As for varying devices, that is why the question is about fundamental limits. $\endgroup$ – campbellC May 30 '19 at 17:53
  • 1
    $\begingroup$ Something like this? $\endgroup$ – Jahan Claes May 30 '19 at 18:42
  • $\begingroup$ Computational complexity and Complexity theory are not the same. $\endgroup$ – Lewis Miller May 30 '19 at 19:01

Although not the name of a field, Bremermann's limit is an example of the type of thing I'm looking for. This is the number of calculations of bits per second per kilogram of mass in a computer and is a fundamental limit derived from the laws of physics rather than an abstract computational model. Similarly the Bekenstein bound is the amount of information you can store in a finite region of space with finite entropy. Thank you Jahan Claes for the link. I will follow links until I find a good text book.


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.