In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in \{0,1\}^*\}$. However, we proceeded to discuss when a language is recursively enumerable vs machines that are deciders etc, and then started discussing the halting problem.

My question is : given a Turing Machine $M$, is it undecidable to construct its Language $L(M)$, since theoretically there could be an input that never reaches a reject or accept state? (My intuition tells me this reduces to the halting problem).


If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts (see @d'alar'cop's comment)?

  • 1
    $\begingroup$ By constructing its language, you mean, given a machine $M$ and a string $s$, you want to see whether that machine accepts that string or not. Is it true that for answering such question, you must first determine whether that machine halts on that input or not? $\endgroup$
    – orezvani
    Sep 12, 2014 at 4:11
  • 1
    $\begingroup$ @emab I think he doesn't mean a particular string but rather to determine what language the machine accepts. $\endgroup$
    – d'alar'cop
    Sep 12, 2014 at 4:14
  • 1
    $\begingroup$ Please edit the question to define more precisely what you mean by "construct its language". At present it is not clear what you are asking. $\endgroup$
    – D.W.
    Sep 12, 2014 at 5:09
  • $\begingroup$ Your edit is not quite nough. How do you "list" an infinite set? $\endgroup$
    – Raphael
    Sep 12, 2014 at 14:47
  • $\begingroup$ It's still unclear what the question is asking. Decidability refers to decision problems: those with yes/no answers. What does it mean to ask if it is decidable to list something? Especially when that thing is potentially infinite. $\endgroup$ Sep 12, 2014 at 14:51

2 Answers 2


In answer to your edited question,

If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts?

The answer is yes, we can. In technical terms, this asks whether the language accepted by a TM is recursively enumerable.

Here's how to produce the strings that $M$ accepts. Define an enumerator TM, $E$ that acts as follows:

  1. Startup: decide on an enumeration of all possible input strings, $s_1, s_2, \dotsc$. For example, if the input alphabet was $\{0, 1\}$ the strings might be enumerated in order $\epsilon, 0, 1, 00, 01, 10, 11, \dotsc$. It's not hard to see how this could be accomplished. In particular, we could find, for every string $s_i$, the next string in order, $s_{i+1}$.
  2. Then use what's known as a dovetail construction in your enumerator TM $E$: $$\begin{align} &\text{repeat for } i = 1, 2, \dotsc \\ &\quad\text{for } k = 1, 2, \dotsc , i\\ &\quad\quad\text{simulate }M\text{ on } s_k\text{ for } i\text{ moves}\\ &\quad\quad\quad\text{if } M(s_k)\text{ accepts}\\ &\quad\quad\quad\quad\text{output } s_k \end{align}$$

It's not hard to see that every string $s_i$ accepted by $M$ will eventually be displayed (perhaps several times) by the enumerator TM $E$. In effect, we're running $M$ in (simulated) parallel on all possible strings $s_i$. Of course, the enumerator $E$ will run forever, but while it's running it will eventually produce any string in $L(M)$ in a finite time, which is just what you wanted.

  • $\begingroup$ I am not sure the OP is aware of the precise semantics of "accept" you are assuming, but your answer stands. $\endgroup$
    – Raphael
    Sep 15, 2014 at 9:05
  • $\begingroup$ you can also avoid repetitions by simulating computation "diagonally", i.e. advance step by step in a growing set of input strings, and display a string whenever its computation finishes and accepts. $\endgroup$
    – Denis
    Sep 16, 2014 at 13:24
  • $\begingroup$ @Raphael I assume a Turing machine accepts an input string by eventually transitioning an accept state $q_{accept}$ $\endgroup$
    – C.B.
    Sep 16, 2014 at 14:14

You can do this for many Turing machines, but not for any Turing machine.

For example you can make a Turing machine whose behaviour is exactly a finite-state machine, i.e. you can program a finite-state machine in a Turing machine. Then the problem for that given Turing machine is trivial.

For Turing machines in general this is undecidable, as it is equivalent to the Halting problem. In particular checking whether $w \in L(M)$ is exactly equal to checking whether $M$ halts for $w$.


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.