9

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?

2

2 Answers 2

8

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.

1

Alan turing wrote a paper describing an abstract conceptual implementation of a discrete automata (something that runs a sequence of commands over a number of discrete time blocks) specifically for use in computation. The Turing abstract model is that of a simple tape and a head that can read and write to that tape. You can issue commands to move the head back and forth (these commands can be also wrote and read from the same tape).

This is the 'Turing Machine'.

This simple abstract model (whether you think of it in the terms of 'tapes' and 'heads') turns out to be very powerful as functionality of modern computers can be described/modeled by this abstract representation.

On a side node, for fun and experiment some folks have created literal implementations close to the tape & head original description of the 'Turing machine' out of things as crazy like legos: https://www.youtube.com/watch?v=cYw2ewoO6c4 The interesting concept is that this insanely simple creation can do everything the best supercomputers can achieve (but might take a little more time and legos)

Your Answer

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

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