0
$\begingroup$

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?
|cite|improve this question
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "It would be the set of all strings with that property." Is this a tuple or do we use the # separator? $\endgroup$ – WeCanBeFriends Jun 19 '19 at 16:04
  • $\begingroup$ No, it's a set of strings. I suggest you look up the basic definitions as these things are all different. $\endgroup$ – David Richerby Jun 19 '19 at 16:04
  • $\begingroup$ Got it, would the set of strings then have the separator, for example; 2#3, would be in the set $\endgroup$ – WeCanBeFriends Jun 19 '19 at 16:06
  • $\begingroup$ Regarding my last question: If I say a Turing machine M, accepts a language L. Then I would not need to make mention of the algorithm? $\endgroup$ – WeCanBeFriends Jun 19 '19 at 16:08
  • 1
    $\begingroup$ @WeCanBeFriends Yes, 2#3 would be in the set. Yes, you can say that a Turing machine does something (e.g., accepts some language) without having to say how it does that (i.e., what algorithm it implements). $\endgroup$ – David Richerby Jun 19 '19 at 16:11
1
$\begingroup$

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)\}$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why did you introduce a Finite State Automota? Is it not possible to answer the question without introducing it? $\endgroup$ – WeCanBeFriends Jun 19 '19 at 16:00
  • $\begingroup$ Can the language not accept two words? Instead of using #? $\endgroup$ – WeCanBeFriends Jun 19 '19 at 16:01
  • $\begingroup$ @WeCanBeFriends A language is a set of strings, not sets of pairs of strings. If you want the strings to represent pairs of things, you have to do that by encoding pairs as strings somehow. A separator character such as # is the usual way of doing that. $\endgroup$ – David Richerby Jun 19 '19 at 16:04
  • $\begingroup$ I introduced the FSA to show that for this particular problem you don't need the full capability of a Turing machine. You can solve this problem with a Turing machine that doesn't even change the symbols on its tape. You could design a much more complicated Turing machine that accepts the same language, but you don't need to. $\endgroup$ – gandalf61 Jun 19 '19 at 16:26

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.