I would like to define a Turing machine as follows.

Let Z be an alphabet, and let L be the set of all sentences of this alphabet. For instance, Z={0,1}, then L is the set of all binary sentences.

A Turing machine is a function which takes a (binary) input and produces a (binary) output:

$$ TM: L \to L $$

However, it is also possible that it doesn't halt. In this case, it is not from $L\to L $.

Initially, I was thinking of mapping $TM: L \to L \cup \nexists$. And claim if it doesn't halt, it maps to $\nexists$.

BUT, here are my concerns:

  1. If TM never halts because it keeps printing symbols forever, then it does map to a sentence of L. It is just that the sentence is infinite.

  2. If TM never halts because it gets stuck somewhere (after n symbols are printed), then it did produce a sentence of L, its just that it is stuck.

So I all cases it maps from L to L.

So is the right answer simply to claim from L to L (where sentences can contain infinitely many symbol) and just claim TM is either computable or non computable?


1 Answer 1


This is not the definition of a Turing machine. "Turing machine" is a term of art with a standard, accepted definition. The right answer is "none of the above" - the premise is faulty, as Turing machine already has a definition that is different from what you've written.

You seem to be attempting to come up with a way to represent the externally visible behavior of a Turing machine. And you have correctly identified reasons why your approach does not work. (It's not correct that in case 1 it does map to a sentence of $L$, because an infinite sequence is not in $L$; $L$ consists of only finite sequences.) No, your final question is not the correct approach either. A TM cannot be "computable" or "not computable"; computability is a property of a language, not a Turing machine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.