Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why classification represents all computations?

, , No Comments
Problem Detail: 

I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me if I'm wrong) Turing machine could do any computation that is possible to compute. But for all examples in computing, what my instructor takes are classification (deciding whether the input has a certain characteristic or not) problems.

Does being able to classify anything mean you can do any computation? For example, addition subtraction etc? What is the connection between classification and computation in general?

I referred few books but I couldn't find an answer. Please help.

Thank you, PPG

Asked By : user5393678

Answered By : Rick Decker

First, you're not entirely correct when you say that a "Turing machine could do any computation that is possible to compute". What you're referring to is known as the Church-Turing thesis and it's not a statement of fact, but more like a statement of confidence. A better way of stating it would be "Any task that we would agree would be described as 'computation' can be accomplished by a TM". This wouldn't be true or false until we could somehow formalize the part "... we would agree would be described as computation ...".

One reason that we have for being confident in the C-T thesis is that people have come up with many apparently different ways of modeling what we call computation and in every case it has turned out to be the case that anything that these models can do can also be done by a TM.

Take, for instance, addition. While your instructor may not have shown you, it's not difficult to build a TM that when given two (binary, say) representations of integers, produces on its tape a representation of the number that is the sum of the two original inputs. Any text I know of includes examples of such computations and there are literally hundreds of online examples of TMs that can add, subtract, multiply, compare numbers, and do other tasks that we'd call computation.

In a sense, you can do these computational tasks without explicitly showing how as long as you can decide whether an input string was in a language, which is what you mean by "classification". The classification problems you've seen take the form, I suspect, of "Given a language $L$, make a TM that determines whether of not an input string is in the language". These decision problems are just disguised forms of what you've described as "computation".

Here's an example: Suppose you had a language, $A$, consisting of all triples, $(x,y,z)$ where $x,y,z$ were binary representations of integers such that $x+y=z$ and you had a TM, $M$, that when given any such triple, could decide whether or not that triple was in $A$ or not. From this TM, you could make another, $M'$, that would do addition. All it would have to do to add $x$ and $y$ would be to try all possible strings $z$ and for each one use $M$ to decide whether $(x,y,z)$ was in the language $A$. Sure, it would take a long time to come up with an answer, but once you hit upon the right $z$, all that $M'$ would have to do would be to write the $z$ it found on its tape.

That equivalence, between classification and computation, gives some justification for the apparent approach your instructor has adopted (though a weak justification, in my opinion). My advice to you would be to search out some examples of computation, like addition, that would give you an idea about the tasks TMs can do.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback