# In automata theory, why is a machine classified based on the languages it recognises?

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?

• 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. – Evil Dec 1 '16 at 3:43
• 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? – Sounak Bhattacharya Dec 1 '16 at 3:46
• @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. – Raphael Dec 1 '16 at 5:56
• 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. – David Richerby Dec 1 '16 at 8:58
• "a Turing Machine can do all the possible mathematical problems" -- nope! Undecidable problems exist, like the halting problem. – chi Dec 1 '16 at 10:42

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$?"