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

Question

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

Answer 1

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.

Answer 2

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