Automata Theory is a subject where we mathematically model a computing device and study the theory behind it. Here we group the computing devices based on the number of languages they can accept. Based on that we say :

Finite Automata's Power < Push Down Automata's Power < Linear Bounded Automata's Power < Turing Machine's Power

and hence forward it is a widely known fact that Turing Machine is the most powerful machine.

But my question is why do we say machine A is more powerful than machine B based only on its language accepting capability? I mean there are lots of other things that a general machine can do. Why not base the concept of power on those other things? In that sense a TM can do nothing more than accept a language!! Can a TM wash clothes? No. Because it has no capability of accepting the input (i.e clothes) on its tape. Can it produce heat energy? No. Because its output is fixed on pencil and paper.

At max, a Turing Machine can do all the possible mathematical problems. Leave alone the other ones like Finite Automata or the Linear Bounded Automata.

So what effectively do we gain by classifying the machines based on this particular property of expressive power excluding all the other properties?

  • $\begingroup$ Could you show these other properties? I am not sure what do you expect as the answer and what are "those other things" that a general machine can do. $\endgroup$ – Evil Dec 1 '16 at 3:43
  • $\begingroup$ By "Other properties ", I mean toasting a bread, cutting iron, washing clothes and various other forms of converting energy into a intended goal action. That is precisely the definition of machine: "A machine is a tool containing one or more parts that uses energy to perform an intended action. " Why are you only considering the "computational properties" of a machine? $\endgroup$ – Sounak Bhattacharya Dec 1 '16 at 3:46
  • 1
    $\begingroup$ @SounakBhattacharya If you go outside of formal models, how can you expect to be able to prove things? Note that there are other models than language acceptance, but they are typically not taught in introductory causes. $\endgroup$ – Raphael Dec 1 '16 at 5:56
  • $\begingroup$ None of the models of computation that we study can toast bread, cut iron or wash clothes. So adding those things into our measure of computing power wouldn't make any new distinctions. $\endgroup$ – David Richerby Dec 1 '16 at 8:58
  • $\begingroup$ "a Turing Machine can do all the possible mathematical problems" -- nope! Undecidable problems exist, like the halting problem. $\endgroup$ – chi Dec 1 '16 at 10:42

The main reason we base our judgements of an abstract machine's "power" on the languages it accepts is that a lot of computational tasks can be equally well expressed in terms of language recognition.

Here's an example: a perfectly reasonable computational task is, "Given an integer $n$ (say in decimal representation), is $n$ a prime number? We could translate that into an exactly equivalent language recognition problem by saying "Is an integer $n$ in the language $\{2,3,5,7,11,13,17,\dotsc\}$?" In general terms, any computational task that requires only a "yes" or "no" answer is equivalent to the problem of determining whether the related language is decidable. We can do similar correspondences for other problems like, "How many primes are there less than $N$?"

By the way, it's not quite correct to say "a Turing Machine can do all the possible mathematical problems". That's roughly the Church-Turing Thesis (look it up), a statement of confidence which can't be either true or false until you can rigorously specify what "all possible mathematical problems" means.

| cite | improve this answer | |
  • $\begingroup$ How can it be said that every computational problem can be translated into a problem of language acceptance? Can you please provide some formal proof? $\endgroup$ – Sounak Bhattacharya Dec 1 '16 at 4:05
  • $\begingroup$ @SounakBhattacharya You can not prove such statements. You just observe that many models you can come up with reduce to languages. $\endgroup$ – Raphael Dec 1 '16 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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