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:


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?



Can an algorithm decide whether a program computes all strings?
The answer seems to be no, this is not decidable.


You seem to have a concept in mind of what it means for a program
$p$ to be UTP, and it involves the idea that pieces of any given
computation history of any other program (on some fixed input)
appear on the tape during the computation of $p$ on the trivial
input.


Although I am not clear on the details of your definition, it
seems to me that nevertheless to follow from what you've said that
if a program $p$ counts as UTP, then in particular, for any given
finite string $s$, it must be that $s$ appears on the tape during
the computation of program $p$ on the trivial input. The reason is
that there is another program that definitely writes $s$ on the
tape, and this computation will be one of the computations that
you are "simulating", and so $s$ must appear in a block during the
computation of $p$, in order for it to count as UTP in your sense.


My next observation is that, conversely, the converse is also
true. Namely, if program $p$ has the property that the computation
of program $p$ on trivial input leads to every single finite
string $s$ appearing at some point on the tape during the
computation, then indeed any "simulated copy" of any given
computation will also appear, since this is just a particular
finite string.


So it seems to me that your concept of UTP is simply the set of
programs that lead to computations on which every finite string
eventually appears on the tape. We can call these the *universal*
programs, since their computation histories constitute a universal
string, in the sense that it contains every finite string as a
substring.


In this case, UTP is not decidable, for essentially the reasons
you said. It is easy enough to have a computation that eventually
writes out every finite string. For example, in the usual decimal
alphabet, we could arrange that the machine simply count, writing
out 0123456789101112131415... and so on, and this sequence of
symbols contains all finite strings in that alphabet. (One could
gradually write this string on the tape, with the scratch work
taking place further and further out, eventually overwritten.)


Now, design a program q as follows: on input $p$, first run a
simultated version of $p$ on input $0$, but in such a way so as to
use only every other cell, so that we have all zeros on the even
cells. If it eventually halts, then we go into a mode as above
where we write every finite string, using all the cells. But otherwise, we keep
simulating $p$ in this every-other-cell manner, and this will not be universal because it has zeros on all the even cells.


For any given $p$, the program $q\_p$ which works like program $q$
on input $p$ (but $q\_p$ takes trivial input) will have the
property that $q\_p$ is universal just in case $p$ halts on input
$p$.


Thus, we have reduced the halting problem to the question of
whether a given program is universal, and so UTP is not decidable.
QED


