Skip to main content
6 of 7
Added the alphabet of the program.

Can an algorithm decide whether a program computes all programs?

Problem

It is possible that a program computes every possible program in parallel on a single-taped Universal Turing Machine (UTM). For example, we can order all the programs and also all the instructions of all the programs. For every instruction of a program that has to be executed, the read-write head of the UTM goes to the reserved place on the tape for that program, expands that place with one cell by replacing the rest of what has already been computed with one cell, then executes the instruction, and then goes back to the main program for deciding which instruction of which program has to be executed next and where that is. There are infinitely many programs of this type.

What I wonder in the first place is whether this kind of program has a name in the literature? I know of a specific instance of this program, called FAST by Jürgen Schmidhuber (The Fastest Way of Computing All Universes. In H. Zenil, ed., A Computable Universe. World Scientific, 2012), but I would be interested in other references. I am writing a paper in which I call such a program a Universal Turing Program (UTP) for now. Would that name capture the meaning?

Formal definition

Mathematical language seems to prefer Turing machines, inputs and outputs, rather than 'programs'. The UTM mentioned above can be considered as a computer with infinite memory, plus an operating system and a Turing complete language installed on it. The alphabet may be just binary: 1 and 0. The input of the UTM is the binary software code of the program, and the output is what is written and rewritten in the RAM memory when the program is executed. This is an essentially 2-dimensional output that can be reduced to a 1-dimensional output by sticking the state of the RAM of each time t in a row. After considering the answer of professor Hamkins below, I must conclude that the shortest and best definition of a UTP is that it is a program for which it is possible to find every possible finite binary string in the output.

Proof of undecidability of UTP-ness

I am also interested in the matter whether an algorithm can decide which programs are a UTP. I believe not, because you can easily convert each possible program HON (Halt Or Not?) to a converted program CP such that:

  1. CP is a UTP on the condition that HON never halts,
  2. CP is not a UTP on the condition that HON halts.

CP consists of running HON plus running a UTP, plus running code that checks whether HON is still running. Just execute the next instruction of the UTP in CP as long as HON is still running. Halt CP when HON halts. If it would be possible to decide UTP-ness for each program, then we could also decide the halting problem for each HON in this way, which is known to be impossible. Is this proof correct?

Additional question

Is it correct that the computation of all the decimal places of an irrational number like $\pi$ is a UTP? For this I assume that all the symbols of the UTM are used in the digits of the computed number, and that the number appears as an ever-expanding, non-interrupted region on the memory tape.