Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT formula. Therefore there are infinitely many 3SAT assignment finder Turing Machines. Could we enumerate all of them? Intuitively, I would expect to be able to find a function that maps natural numbers to 3SAT assignment finders as 3SAT assignment finders is just a subset of all Turing Machines, and the set of all Turing Machines is countable. However, could we compute this function that enumerates the problem solvers? Intuitively it feels like this should not be possible, but I am not sure.


1 Answer 1


Your question is, given a TM $M$, where $L(M) = L$, is it possible to create an enumerator $E_L$ that enumerates every $TM \ M'$, such that $L(M') = L$

The answer to this interesting question is actually no, we prove this by contradiction

First consider the language $ATM = \{<M, w>| M \ is \ a \ TM \ and \ M \ accepts \ w\}$, which we know is undecidable

Our proof will show that if we can construct $E_L$, then $A_{TM}$ is decidable, hence a contradiction

Assume given $TM, M$, where $L(M) = L$ we can construct enumerator $E_L$ enumerating every $TM \ M'$ such that $L(M') = L$

Now we will have two subroutines that we will run in parallel $A$ and $B$

Given $<M,w>$, $A$ halts if $w \in L(M)$, $B$ halts if $w \notin L(M)$, either one of them is the case, so eventually one halts and gives us the answer

First lets explain how $A$ works, given $M,w$, $A$ constructs a new machine $M_w$ which recognises the language $L(M) \cup \{w\}$, $M_w$ just checks if the input is $w$ if so it accepts, otherwise it simulates $M$, now we construct the enumerator $E_{L_{M_w}}$ which enumerates every $TM$ recognising $L(M) \cup \{w\}$, now if $M$ already accepts $w$, then $L(M) \cup \{w\} = L(M)$, and so $E_{L_{M_w}}$ eventually prints the description of $M$ and hence we halt and accept

Next lets go with $B$, given $M,w$, $B$ constructs an new machine $M_{\bar w}$ which recognises the language $L(M) - \{w\}$, so $M_{\bar w}$ just checks if the input is $w$, if so it rejects otherwise it simulates $M$, now we construct the enumerator $E_{L_{M_{\bar w}}}$ which enumerates every $TM$ recognising $L(M) - \{w\}$, if $w \notin L(M)$, then $L(M) - \{w\} = L(M)$ and hence $E_{L_{M_{\bar w}}}$ eventually prints the description of $M$ and hence we halt and reject

Again its important that we run both enumerators $E_{L_{M_{w}}}$ and $E_{L_{M_{\bar w}}}$ from $A$ and $B$ respectively in parallel to guarantee that we don't loop

Using this construction, we can show that $A_{TM}$ is decidable yielding a contradiction, and hence we cannot construct such an Enumerator


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.