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?