[Solved]: Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

Problem Detail: 

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

Asked By : C.B.

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29923

3.2K people like this

 Download Related Notes/Documents