1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Commented Jul 8, 2022 at 2:15
  • $\begingroup$ My instant bet is No. Let me check. $\endgroup$
    – John L.
    Commented Jul 8, 2022 at 2:20
  • $\begingroup$ @JoshuaLin Please check my update. $\endgroup$
    – John L.
    Commented Jul 8, 2022 at 3:20
  • $\begingroup$ 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 $\endgroup$ Commented Jul 8, 2022 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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