Home » Reading clubs » Classic » Limits of Complexity

Limits of Complexity

[written by William K. Larsen]

We read two papers. Both were review articles from the journal Nature.

Summary of: Ultimate physical limits to computation(2000), by Seth Lloyd

The article is written for the general scientifically literate audience and is mostly easily digestible. A description of the concept of an AND-gate is given, which is rather elementary.The paper covers advanced topics as well.

Lloyd defines the Ultimate physical laptop as a “computer” with mass of 1 kg and volume of 1 liter.

2 main arguments are made concerning the ultimate physical laptop:

  1. Energy limits the speed of computation – which leads to a limit of approximately 1050 computations pr. second (1041 GHz).
  2. Entropy limits memory space – which leads to a limit of approximately 1031 bits (1021 GB)

Overall, the paper makes you think of a computer as a physical object with energy, mass and volume, rather than the idealized model often used in computer science. It gives a taste of a number physical concepts and ideas along the way.

Our discussion:

The limits presented in the paper are very large upper bounds. One could theoretically fill an empty jar with colored sand and consider the very large number of possible configurations as being representative of the information stored. The problem is that the jar of sand cannot be utilized for work in the same way that a computer can.

This paper was written before the death of Moore’s law and thus the limits may have seemed more like a important perspective than a fun thought experiment.


Brief summary of: Limits on fundamental limits to computation(2014), by Igor L. Markov

The aim of this paper is to get a perspective on the different possible barriers for the development of computers.

The other paper considered the problem of Fundamental limits to computation by looking at Energy, Space and Information.

This corresponds to only 3 of 25 cells in the following table from the paper:

limits of computation.PNG

Markov considers different cells in this table and makes some concluding remarks.

Our discussion of the paper:

The paper is really hard on the quantum computer – claiming that quantum computers can only find use when simulating quantum-chemical phenomena and that this is also uncertain.

Markov generally does not go into too much depth with anything, but the references seem very useful. Especially 8 of them have been highlighted and given a small description (out of 99)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: