Can an algorithm decide whether a program computes all strings? [closed]

Question

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?

Answer 1

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

Answer 2

This might be more comment than answer, but --

This a standard trick -- running all TMs in parallel -- but I don't know if it has a name. You can probably find it used in introductory complexity textbooks like Sipser, somewhere. One keyword is "Godel numbering", which refers to the ordering of programs that you mention (we assign each program to a natural number). I guess UTP is a fine name, you just want to distinguish it from Universal Turing Machine (UTM), which is a TM that, given the description of a program and an input, simulates that program on that input.

Your proof of undecidability is correct.

Sidenote, questions like this might fit better at cs.stackexchange.com.