# Nonexistance of collection of 'transformers' that 'trivially modify' Turing machines?

For a given recursive language $$L$$, let $$TL$$ be the language of turing machines that accept $$L$$, for some encoding of turing machines. $$TL$$ is countably infinite. Does there exist a set $$S = \{S_1,S_2,\cdots\}$$ of computable functions that take as input a turing machine and output a turing machine, such that if $$T$$ is in $$TL$$ then $$S_i(T)$$ is also in $$T_L$$, and that acting the $$S_i$$ on a given $$T$$ generates all of $$TL$$ eventually?

If there exists a set (which probably there isn't), does there exist a finite such set?

The motivation is that the $$S_i$$ can be thought of as transformations on the space of turing machines that don't change their behaviour, i.e. they are ways to 'rewrite' turing machines, and I wonder if there is a universal collection of such 'rewrite' algorithms. Examples include an $$S_i$$ that appends an additional, useless, calculation (states) to its input.

## 1 Answer

Call such a set "universal transformer".
Yes, there is a universal transformer.

Let $$\mathcal{ALL}$$ be the set of all Turing machines, that is, $$\mathcal{ALL}=\{\langle M\rangle\mid M\text{ is a Turing machine}\}$$, where $$\langle\cdot\rangle$$ is some fixed encoding scheme for Turing machines.

By abuse of notation, we will treat an element $$\langle M\rangle$$ in $$\mathcal{All}$$ either as a string or as the Turing machine $$M$$ that is encoded in that string.

Given two Turing machines $$M_1, M_2\in \mathcal{ALL}$$, let $$\delta_{M_1, M_2}: \mathcal{ALL}\to\mathcal{ALL}$$ be such that

• $$\delta_{M_1, M_2}(M)=M$$ for all $$M \not= M_1$$.
• if $$L(M_1)=L(M_2)$$, then $$\delta_{M_1, M_2}(M_1)=M_2$$. Otherwise $$\delta_{M_1, M_2}(M_1)=M_1$$.

Note that for all $$M$$, $$L(\delta_{M_1, M_2}(M))=L(M)$$. It is easy to check that $$\delta_{M_1, M_2}$$ is well-defined and computable.

Let $$S=\{\delta_{M_1,M_2} \mid M_1, M_2\in \mathcal{ALL}\}$$.

Suppose language $$L$$ is accepted by $$T\in\mathcal{ALL}$$.

• For any $$s\in S$$, $$s(T)\in TL$$.
• If $$L(T')=L(T)$$, then $$\delta_{T,T'}(T)=T'$$.

So, $$S$$ is a universal transformer.

Let $$L$$ be the empty language. $$TL$$ is the subset of $$\mathcal{ALL}$$ of all Turing machines that accept no strings.

There are infinitely many Turing machines that accept no strings. For example, the Turing machine $$E_i$$ that moves left forever after having moved to the right $$i$$ times.

So, a universal transformer cannot be a finite set.

As said above, $$S$$ is a universal transformer.

However, $$S$$ is not useful in the sense that $$S$$ is undecidable. That is, it is not decidable whether we can check a string $$s$$ is in $$S$$ or not, assuming that we represent each element in $$S$$ by some fixed encoding scheme. In fact, $$S$$ is not computably-enumerable nor co-computably-enumerable.

Call a set $$S$$ "weakly-universal transformer" if given a language $$L$$ and a Turing machine $$T$$ such that $$T$$ accepts $$L$$, for any Turing machine $$T'$$ such that $$T'$$ accepts $$L$$, there exists a sequence of elements in $$S$$, $$s_1, s_2, \cdots, s_n$$ such that $$s_n(s_{n-1}(\cdots(s_1(T))\cdots))=T'$$.

Claim: A weakly-universal transformer is not computably-enumerable.
Proof: For the sake of contradiction, suppose $$S$$ is a computably-enumerable weakly-universal transformer. Then the set of all finite sequences of elements in $$S$$, $$S^*=\{(s_1, s_2,\cdots, s_n)\mid n\text{ is a positive integer}, s_i\in S \}$$ is also computably-enumerable.

Let $$L$$ be the empty language. $$TL$$ is the subset of $$\mathcal{ALL}$$ of all Turing machines that accept no strings. Since $$S$$ is a weakly-universal transformer, $$TL=\{q\in S^*\mid q(E_0)\}$$, where $$E_0$$ is the Turing machine that keeps moving left. Since an element in $$S$$ is a computable function, $$TL$$ is computably-enumerable. However, we know that $$TL$$, the language of all Turing machines that accept no strings is not computably-enumerable. This is a contradiction. $$\quad\checkmark$$

Corollary: A weakly-universal transformer is not finite.

• Thank you for the answer! For your argument that universal transformer cannot be a finite set; I know that $TL$ is infinite, but I had actually meant in my question that repeated applications of the $S$ in the universal transformer generates all of $TL$ (in other words, if you label the $S$ as $S_1,S_2,\cdots$, then $S_i(T), S_i (S_j(T)), \cdots$ eventually covers all of $TL$. Is it possible that such a finite set exists? Commented Jul 8, 2022 at 2:15
• My instant bet is No. Let me check. Commented Jul 8, 2022 at 2:20
• @JoshuaLin Please check my update. Commented Jul 8, 2022 at 3:20
• Thank you! What I was missing is that $TL$ for $L$ empty language is not computably enumerable, which I guess comes from Rice's theorem Commented Jul 8, 2022 at 4:24