turing-machines

What is meant by the language of a Turing machine?


So I tried searching for the precise definition of language, but all articles assume that the definition is obvious to everyone. Apparently, to me it isn't.

What is the definition of a Turing machine's language?


Solution

  • When you run a TM, you give it as input a string. The TM will then either accept the string, reject the string, or loop on the machine. The language of a TM is defined as the set of all the strings it accepts.

    Not every language is the language of a Turing machine - that's one of the landmark results of theoretical computer science. The languages that are languages of Turing machines have lots of names - they're the Turing-recognizable languages, the semi-decidable languages, and the recursively enumerable languages. You'll see all these terms used depending on the context.