A sorting algorithm with non-exponential computational complexity
Our universe is analog. Digital computers discretize (limit) time and information to a series of predetermined values. However, digital computers are also analog machines. Their peculiarity is that we interpret their behavior digitally.
This happens up to the quantum level, where space (position), time and matter / energy / information could be discrete / digital phenomena.
In short, we have:
- Analog Machines: They use physical variables such as voltage, length or position to represent data as accurately as the physical device allows. Examples: slide rules, mercury thermometers, thermostats.
- Digital Machines: They are analog machines whose behavior we interpret digitally, discretely. They represent data in the form of discrete numbers, so that each variable can only take one value from a predefined and limited set of possible values.
We can forget that digital is not the only thing that exists. How to sort a series of numbers with an analog computer?
It turns out that there is an analog sorting algorithm with linear computational complexity.
The algorithm is as follows: just cut sticks of a length proportional to each number you want to sort. Then you arrange them in the form of a vertical bundle. You hit the table with them. You lower your hand and the first one that sticks out will be the largest. You remove it and so on.
Why does this algorithm work? Because it uses properties of the physical world that digital computers ignore.
***
We had this fascinating conversation at the Immune Technology Institute.
2 Comments