Questions about Turing Machine

Question

Below I will list a concrete example and the confusion it causes.

Let's first say we have a decision problem, which is:

"Is X <= 400?"

We define the alphabet as the set of natural numbers.

The language formed by this problem is $L = \{ w | w <= 400 \}$

We define a Turing machine, M, over the alphabet, that halts in an accepting state on any word that is in L. Ie the Turing machine recognises L.

$L(M) = \{ w |$ M halts in an accepting state on input w$\}$

• Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?

• Since this is a decision problem, the language realised from it, will always b finite?

• Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.

• How would the Language be for the problem: "Is X <= Y?"

• For a decision problem, the elements in the Language realised are the solutions?

  • I left out the notion of an algorithm, in my explanation, Is it not needed as it is implicit in the Turing machine halting on any input of L? Which means it implements some algorithm that can solve the problem?

Answer 1

We define the alphabet as the set of natural numbers.

No you don't. The alphabet must be finite.

Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?

If all you know is that the TM recognizes the language then you're correct: it could loop forever on some inputs.

Since this is a decision problem, the language realised from it, will always b finite?

That doesn't follow from being a decision problem. This language is finite because there are only finitely many natural numbers less than 400. But, for example, the language of even numbers is infinite, but it's still a decision problem.

Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.

Yes, you could produce a Turing machine that decides the language $\{x,y\mid x,y\leq 400\}$.

How would the Language be for the problem: "Is X <= Y?"

It would be the set of all strings with that property.

For a decision problem, the elements in the Language realised are the solutions?

I'm not sure what you mean by "realised". (You wrote it before but the exact meaning wasn't so important, then.) A decision problem is any problem of the form "Does the input string have property X?" and it's naturally associated with the language of strings that do have that property.

Answer 2

Let me start with a small but important point. You need to distinguish between $X$ which is a natural number and $w$ which is a string representing a natural number. So the string $11$ could represent the number $2$ in unary, the number $3$ in binary, the number $11$ in decimal, the number $17$ in hexadecimal etc. The language

$L=\{w|w \text{ represents a natural number } X \le 400\}$

will depend on how you want to represent numbers.

Second point - we can create a finite state automata $F(L)$ that recognises $L$. For example, if we are using the unary number system then $L$ consists of all strings of $1$s with length no greater than $400$, so a $402$ state DFA with $400$ accepting states will recognise $L$.

There will be many different Turing machines $M(L)$ that accept $L$. And it is certainly possible to design a convoluted and highly obfuscated such $M(L)$ for which it is impossible to determine whether it halts for certain inputs.

But since we know there is a finite state automata $F(L)$ that accepts $L$, the most straightforward approach is to implement this automata as a Turing machine $M(F(L))$. And with this approach, we can be sure that $M(F(L))$ will always halt on any given input $w$ because $F(L)$ will go through at most $|w|$ state transitions.

To capture the decision problem "Is $X \le Y$" as a language, you simply need to devise a scheme for representing two natural numbers $X$ and $Y$ in a single word. A simple way to do this is to introduce a symbol $\#$ that is used solely for separating numbers (or, strictly speaking, representations of numbers). Then you can then define the language

$L' = \{x\#y| (x \text{ represents a natural number } X) \land (y \text{ represents a natural number } Y) \land (X \le Y)\}$