Return to Answer

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

The algorithm in your answer, however, seems flawed to me, 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. That is, while you are checking a program that is itself UTP (and hence doesn't halt), your simulation could become inadertantly universal simply because of this. My algorithm prevents this problematic issue by means of the every-other-cell-zero simulation.

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

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.

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

The algorithm in your answer, however, seems flawed to me, 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. That is, while you are checking a program that is itself UTP (and hence doesn't halt), your simulation could become inadertantly universal simply because of this. My algorithm prevents this problematic issue by means of the every-other-cell-zero simulation.

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. But otherwise, we keep simulating $p$ in this every-other-cell manner.

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.

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.