gotchaMajor
Why does a Turing machine recognise exactly one language?
Viewed 0 times
whyrecogniselanguageonedoesmachineturingexactly
Problem
I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
Solution
The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.
Context
StackExchange Computer Science Q#42367, answer score: 30
Revisions (0)
No revisions yet.