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

  • 1
    $\begingroup$ The term is decision problems. "Classification" is a term more associated with machine learning. $\endgroup$ – Raphael Mar 26 '16 at 10:41

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.

  • $\begingroup$ For those looking to find a nontrivial example of a model of computation that is apparently different from a Turing machine: look up "process networks". $\endgroup$ – Mehrdad Mar 26 '16 at 0:39

Turing machines are commonly used to model computation of functions like addition and subtraction. The machine finds its input on the tape when it starts running, and it leaves its output on the tape when it terminates. In this way you can model functions directly.

You can also model functions through decision problems (what you call classification problems). Taking as an example addition, consider the decision problem whose Yes instances are triple $\langle x,y,i \rangle$ such that the $i$th bit of $x+y$ is $1$. If you can solve this decision problem, you can add numbers (and vice versa).

Real life computers are interactive — then send and receive information from the outside world. This can be modelled using Turing machine with special tapes which can be used to send messages or to receive them, similar to oracle tapes which you will learn about later on.


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.