4
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?
7
Usually, Turing machines are explained to calculate functions $f:A \rightarrow B$, of which decision problems are a special case where $B = \mathbb{B}$.
6
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.
Steven
Posted 2013-02-07T10:46:15.323
Reputation: 12 921
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 – 2013-02-11T05:32:25.163
4
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)$.
Kaveh
Posted 2013-02-07T10:46:15.323
Reputation: 20 985
2
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).
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}$.
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.
usul
Posted 2013-02-07T10:46:15.323
Reputation: 3 920
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 – 2013-02-08T08:36:57.703
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 – 2013-02-11T05:30:55.803