Can Turing Machines solve non-decision problems?

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?

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.

StackExchange Computer Science Q#9574, answer score: 6