3
$\begingroup$

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).

EDIT

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)?

|cite|improve this question
$\endgroup$
  • 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 '14 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 '14 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 '14 at 5:09
  • $\begingroup$ Your edit is not quite nough. How do you "list" an infinite set? $\endgroup$ – Raphael♦ Sep 12 '14 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$ – David Richerby Sep 12 '14 at 14:51
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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 '14 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 '14 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 '14 at 14:14
3
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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