Can Turing Machines solve non-decision problems?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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)$.

Answer 4

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.