What are most programs like?

Separating computer program from computer memory makes both simpler to think about. When the program starts, its input is put into the computer's memory. Each instruction in the program changes the computer's memory. The program's answer is the value in the computer's memory when the program stops.

The change in the memory depends on which instruction is run and the current value in the memory. Following a program as it runs gives a sequence of instructions. These cause a precise one-to-one change in the value in the computer's memory (which we can lookup using the current value and the instruction). So by following the sequence of instructions and working out the memory's value after each one, we get exactly the output of the program.

This gives us the answer for one program. We can calculate mathematically the average answer of all computer programs. The maths shows that on average the answer given by computer programs does not change much as they get bigger (provided they are big enough to start with).

For more information see or.

W.B.Langdon . 11 Jan 2003