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, this 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


The algorithm in your answer seems flawed, because it could be that during your checking procedure of whether the given program halted or not, your computation became inadvertantly universal, even though you didn't want or intend it to. My algorithm prevents this problematic issue by means of the every-other-cell-zero simulation.