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?

closed as unclear what you're asking by Henry Cohn, Stefan Kohl, Ryan Budney, Ricardo Andrade, Ramiro de la Vega Nov 18 '14 at 0:05

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    Your definition of what it means to be a UTP is not sufficiently precise to answer the question. If what it means to be a UTP is that the algorithm performs a certain precisely specified kind of algorithm (with no extra checks or other computation), then yes, this will be decidable, since we can inspect the code to see if it carries things out exactly like that. (The algorithm in your proposed counterexample does not follow the UTP template, since it also checks to see if a certain program halts, and then does something else.) But if your definition of what it means to be a UTP has to do... – Joel David Hamkins Nov 16 '14 at 12:54
  • 1
    ...with the behavior of the machine and whether externally we can view it as undertaking the UTP idea, then the kind of counterexample you propose would be a counterexample. So more precision in the question is needed in order to answer. – Joel David Hamkins Nov 16 '14 at 12:56
  • Your edit gives a more precise example of a UTP, but what I was asking for was: what counts as a UTP exactly? – Joel David Hamkins Nov 16 '14 at 13:44
  • 3
    That isn't the problem. The problem is that you are asking if a certain set is decidable, but you haven't really told us exactly what the set is. The answer to your question depends on this, since if the answer to "is $p$ a UTP?" depends only on syntactic things about how $p$ is designed to work, then it will be decidable; but if the answer depends on the behavior of $p$ as it proceeds, then it will not. – Joel David Hamkins Nov 16 '14 at 15:12
  • I'm sorry to say that I don't find it to be precise. Do the programs have inputs? What is the alphabet? You talk about a "largest non-interrupted" region, but I don't see how there could be a "largest" such region, if finite, unless you mean "largest" with respect to some other unstated criterion. Do you count any program that systematically writes every finite string on the tape to be a UTP? If so, then simulating the computations seems to have nothing to do with it, and you are just talking about a program whose tapes are universal in that sense. (I think this is a necessary condition.) – Joel David Hamkins Nov 16 '14 at 21:40
up vote 4 down vote accepted

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

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.

  • I don't think Rice's theorem applies directly here, since the algorithm he describes is not a decision algorithm, and indeed, it never halts on any input. – Joel David Hamkins Nov 16 '14 at 12:58
  • That is, Rice's theorem applies when one is separating programs by a criterion that is invariant if two programs compute the same function or accept/reject the same inputs. But my sense is that the OP's concept of UTP is not invariant in this sense, since I don't think he'll count as a UTP any program that never halt. Rather, he is interested in the ones that perform that universal task of simulating all programs. – Joel David Hamkins Nov 16 '14 at 13:41
  • @JoelDavidHamkins, you're right, I removed the statement about Rice's theorem. – usul Nov 16 '14 at 17:40
  • 2
    @usul "This a standard trick -- running all TMs in parallel -- but I don't know if it has a name." This is called dovetailing. – Benedict Eastaugh Nov 16 '14 at 17:43
  • 3
    Dovetailing is a more general term for interleaving any series of computations. Your question is a special case of dovetailing. But dovetailing does not imply that you run the machine indefinitely, or which computations it is that you're interleaving, so it is not by itself a term for the procedure you mention. Just wanted to be sure that's clear. – usul Nov 16 '14 at 22:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.