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 is a UTP on the condition that HON never halts,
- 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?