Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how can we cast the performance of mergesort as a decision problem?

share|improve this question
    
Wow, you have been given a very restricted "definition" of Turing machines. It is quite clear that it is not Turing-complete in the sense of the Church-Turing hypothesis. –  Raphael Feb 8 '13 at 8:36
    
The formal definition of Turing Machine in wikipedia does not suffer from this problem. Are you using the same source for your definition of TM as the person who asked this question? –  Peter Shor Feb 11 '13 at 5:30
add comment

migrated from cstheory.stackexchange.com Feb 7 '13 at 15:30

This question came from our site for theoretical computer scientists and researchers in related fields.

4 Answers

Usually, Turing machines are explained to calculate functions $f:A \rightarrow B$, of which decision problems are a special case where $B = \mathbb{B}$.

share|improve this answer
add comment

You can define two kinds of Turing Machines, transducers and acceptors. Acceptors have two final states (accept and reject) while transducers have only one final state and are used to calculate functions.

Let $\Sigma$ be the alphabet of the Turing Machine.

Transducers take an input $x \in \Sigma^*$ on an input tape and compute a function $f(x) \in \Sigma^*$ that is written on another tape (called output tape) when (and if) the machine halts.

The are various results that link together acceptors and transducers. For example:

Let $\Sigma=\{0, 1\}$. Given a language $L \subseteq \Sigma^*$ you can always define $f : L \to \{0,1\}$ to be the charateristic function of $L$ i.e. $$ f(x) = \begin{cases} 1 & \mbox{if $x \in L$} \\ 0 & \mbox{if $x \not\in L$} \end{cases} $$

In this case an acceptor machine for $L$ is essentially the same as a transducer machine for $f$ and vice versa.

For more details you can see Introduction to the Theory of Complexity by Crescenzi (download link at the bottom of the page). It is lincensed under Creative Commons.

share|improve this answer
    
You can have a TM which computes a function with just one tape. In my experience, people only worry about transducers when dealing with low-complexity classes like LOGSPACE. –  Peter Shor Feb 11 '13 at 5:32
add comment

We focus on studying the decision problems in undergrad complexity theory courses because they are simpler and also questions about many other kinds of computations problems can be reduced to questions about decision problems.

However there is nothing in the definition of Turing machine by itself that restricts it to dealing with decision problems. Take for example the number function computation problems: we want to compute some function $f:\{0,1\}^*\to\{0,1\}^*$. We say that a Turing machine compute this function if on every input $x$, the machine halts and what is left over the tape is equal to $f(x)$.

share|improve this answer
add comment
  1. It is easy to define what it means for a Turing Machine to compute a function: The input is written on the tape at the beginning, and the output is whatever is on the tape when the machine halts (if it halts).

  2. Most complexity classes we introduce initally, like $\mathsf{P}$, are defined for decision problems. However, there are also complexity classes for function problems, like $\mathsf{FP}$.

  3. We can convert between a decision problem and function problem pretty easily in most cases. In a function problem, you are given input $x$ and want to compute $f(x) = y$. In the equivalent decision problem, you are given input $(x,y)$, you want to decide whether $f(x) = y$ or not. (Or even whether $f(x) \leq y$, or so on.) Often it turns out that we can solve the first in polynomial time if and only if we can solve the second in polynomial time, so complexity-wise, the distinction is not very important.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.