Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set?

Question

Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set, and only programs in that set?

I know there exist programs which compute every other program, by diagonalizing on the library of all possible programs. So there are infinite sets of programs such that every program in that set computes every other program in that set. But what about the second condition, that they compute only programs from that set?

This is not a homework question; I am writing a philosophy term paper and would like to cite this fact as evidence for something.

Answer 1

If I understand your question correctly (and perhaps I don't), then yes it's true.

If every program in a set $\cal P$ of programs "computes every other program in that set", I take this to mean that all the programs in the set compute the same partial mathematical function. Specifically, for a program $P$, let $f_P$ be the function computed by $P$, $D_P$ its domain (the set of integers, say, on which $P$ halts). Then I take your condition to mean: for all $P, Q\in \cal P$, $f_P = f_Q$ (and so of course $D_P=D_Q$).

For every program $P$ (or Turing machine $M$, or computable function $\varphi_e$, ... pick your favorite formal system of computation), there are infinitely many other programs $Q$ which compute the same partial mathematical function as $p$ does: $f_P = f_Q$. Some of them actually implement different algorithms, while others arise by "padding" — adding useless instructions. In particular this holds for programs that don't halt on some inputs, those that halt on no inputs, as well as those that halt on all inputs (which compute total functions).

As for your mention of diagonalization in the question and in a comment, I don't see how this applies. To judge from your comment, I think you mean enumeration. Nor do I see how there are really two parts to the question: unless you means something different than what I imagine, the answer to the first implies the second. In your comment you mention the following "computation":

Execute the first step of that program. Then go to the second program on the list, and execute the first step of that. Then go back to the first program, and execute the next step. Then go back to the second program... by continuing in this way, diagonally, the program can execute all the steps of all the programs.

This is not a (halting) computation, as you know — computations have finitely many steps.

I see another way to interpret your question. Perhaps you intend a notion like $$\text{line $i$ in program $P$ simulates line $j$ in program $Q$ at step $t$ on input $x$,}$$ and you're asking whether there's an infinite set of programs $\cal P$ such that for all $P\in\cal P$, $P$ run on input $x$ has this property — that is, for every $Q\in\cal P$, every line $j$ in $Q$, there is a line $i$ of $P$ which at some step $t$ simulates line $j$ of $Q$ run on $x$. In this case, the "second part" of your question really is distinct: no $P\in\cal P$ should simulate all the lines of any program not in $\cal P$ on any input.

The answer to that ought to be No, but the details are relative to the particular formalism involved, which are required to make the definition of "simulates" precise.

Answer 2

I think a more natural (and, more to the point, more likely to be close to the OP's intention) interpretation of the question goes as follows:

Is there a set $A\subseteq 2^{<\omega}$ such that for every $e\in A$, the collection of functions $f_t(x)=\varphi_e(tx)$, $t\in 2^{<\omega}$, is exactly $\{\varphi_s :s\in A\}$?

I suspect the "non-halting" in the OP was caused by a misunderstanding how universal functions generate all programs (it's not by doing this successively, but by varying the input); of course, I could be wrong.

I've used strings rather than integers as inputs, which seems more convenient here.