Search This Blog

Computer Programs as Mathematical Objects

Computer Programs as Mathematical Objects

First let's define a "computer program" as follows..

A finite list of instructions (picked from a finite instructions set).
A finite way to specify the initial starting condition.
An output stream that can be finite or infinite (infinite just means the program never stops.)

Notice that the above definition is quite general. It's independent of programming language, instruction set and hardware.

The case of finite output is trivial because the output could be used as an initial starting condition for a simple read/write program. So the only "non-trivial" programs are those with infinite output. An example is a recursive program such as a fractal generator.

Recursive programs use their output as input. They are an interesting subset of programs. They can have very few instructions, but produce complex infinite output.

Now, with the the above definition, let P be the set of all computer programs. Then we can ask questions about P that directly relate to mathematics and number theory, such as..

Can we define a binary operation on P?
Does P contain a member who's output is the list of prime numbers?
Does P contain a member who's output is the digits of pi?

I think most mathematicians would answer these questions with a definite "no". But can this be proved? And what does a proof look like? Of course, if the answer is "yes" then we have a very interesting situation!

Content written and posted by Ken Abbott