[P&N] Chapter 8: The Limits of Software

Citation: Edward A. Lee, 2017: Plato and the Nerd - the creative partnership of humans and technology. MIT Press, Cambridge, MA

Happy New Year!

Universal Machines

In short, although we can do an extraordinary amount with software, it’s nothing compared with what is possible if we do not limit ourselves to this smallest of infinite sets.

A universal Turing machine is simply a programmable Turing machine where the program can encode any other Turing machine. Any modern computer is a universal Turing machine, except that it may run out of memory.

The notion of an algorithm is central to computer science, but it is important to recognize that an algorithm is a model of what a machine does. … An algorithm is an abstraction that ignores the messy continuous-world details of the computer. In this abstraction, a step does not take time, and there is no notion of being halfway through a step. A step occurs atomically.

The definition of algorithm:

1. Step by step.
2. It reaches a conclusion.

Is an operating system also an algorithm?

Maybe not. Consider a CPS (Cyber-Physical System) first, if an interactive program is interacting with the physical world, then the timing of the actions of the program will surely affect the overall behavior of the system. Hence, the timing of the program’s actions must be considered as part of its outputs. But an algorithm does not have a notion of timing. In this sense, such interactive program is definitely not an algorithm.

Undecidability

A decision function takes a finite binary integer as input, such as 011101, and produces a binary result, 0 or 1.

Decision functions that cannot be realized by software on a computer are said to be “undecidable”.

In fact, almost all decision functions are undecidable, or equivalently, almost all decision functions are not effectively computable.

Proof by coming up with one contrarian function:

Assumptions:

1. We have a modern computer with an unbounded amount of memory.
2. We have a list of all the possible inputs to our decision functions.

From here, we can draw the following conclusions step by step:

1. Every possible input, every possible finite bit sequence, will be somewhere on this list.
2. Every program for any modern computer is represented as a sequence of 0s and 1s. So every program will be somewhere on the list.
3. Hence, every decision programs is on the list.

For the sake of argument, let’s call the first decision program on the list \( P_1 \), the second \( P_2 \), and so on.

Then we can come up with a contrarian function \( C \). It yields the following decision for each input:

Now, \( C \) is different from any of the decision programs on the list while itself is a decision function.

Again, Map and Territory

A very important thought professor Lee trying to convey throughout this book is that we should always keep in mind that maps and territories are two different objects. Any “explanations” of the physical world or of what a computer does is a map. They are models, and models are incomplete, in the sense that there are properties of the physical world that are not represented in the model.

A computer works for the electrons sloshing around in those circuits, it exists in the physical world while the programs are models of computers. They can never fully explain the thing they are modeling. Always be aware of this subtlety.

Cardinality

The term cardinality denotes the size of a set.

In cantor’s notion of the size of infinite sets, two infinite sets \( A \) and \( B \) are said to have the same size if we can define a one-to-one correspondence between the elements of the sets. For example, the set \( (0, 1) \) and set \( \mathbb{R} \) have the same size because we can use a \( tan(x) \) to build such a correspondence.

Cantor denoted the size of the set \( \mathbb{N} \) by the symbol \( \aleph_0 \), where \( \aleph \) is the first letter of the Hebrew alphabet. The subscript 0 indicates that this is the size of the smallest known infinite sets.

We can easily have the following conclusions:

1. The set of binary sequences, say \( \mathbb{B} = {0, 1, 00, 01, 10, 11, 000 …} \), also has size \( \aleph_0 \).

2. The set of all computer programs, say \( \mathbb{P} \), has size \( \aleph_0 \) for any computer program can be represented using one of the sequences listed in \( \mathbb{B} \).

3. The set of all rational numbers has size \( \aleph_0^2 \), but \( \aleph_0^2 = \aleph_0 \).

A set with size \( \aleph_0 \) is called a “countably infinite set.” The sets considered above are all countable sets, in fact, there are many uncountable sets besides \( \mathbb{R} \), for example, the set of decision functions is uncountable, it has the same size as \( \mathbb{R} \).

From the above we can know:

1. Any power of \( \aleph_0 \) is still \( \aleph_0 \).

2. \( \mathbb{P} \)’s size is \( \aleph_0 \), it’s vastly smaller than the size of \( \mathbb{R} \).

3. There are vastly more decision functions cannot be realized than can be realized by a computer program, leave alone all the interesting functions.

The above conclusion is only invalid is digital physics is true, but I agree with professor Lee, holding the belief that the chance is extraordinarily tiny.

But even though digital physics is false, it is still valuable to to have computational models of this world. The model built to predict the whether is an perfect example.

As engineers in 21st century, we must know the bottleneck of the thing we devote our whole lives to, only then can we move on.

Fortunately, we are not limited to only softwares, cyberphysical systems form a partnership between software and other non-software physical systems. These combined machines offer a vast and largely unexplored landscape for creative designers and inventors.