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:

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.

I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ appears in the output. I am writing a paper in which I call such a program a Universal Turing Program (UTP). There are infinitely many UTPs. I have two questions:

1. 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. Would the name Universal Turing Program capture the meaning?

2. 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:

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?

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. Then the input of that UTM is the 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 string of symbols 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.

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.

I only gave an example of a UTP, and a more precise definition of a UTP, and of what it means for a program to be computed by another program, might be appropriate here:

Computing

At each time $t$, a program $p$ maps to a finite, largest non-interrupted 2-dimensional region $R_{p,t}$ of non-blank symbols. One dimension is the cellular dimension of the tape memory, the other is the temporal dimension of the computation. A program $x$ is computed by a program $y$ if, for each time $t_1$ in the computation of $x$ and for some time $t_2$ in the computation of $y$, $R_{x,t_1}$ is a part of $R_{y,t_2}$.

UTP

A UTP is any program for which it holds that every other program is computed by it. It also follows that a program that computes a UTP is itself a UTP. The definition of a UTP is therefore based on how it behaves internally. It may not be clearly apparent from the programming code that a program is a UTP.

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. Then the input of that UTM is the 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 string of symbols in the output.