You are here
HomeTuring computable
Primary tabs
Turing computable
A function is Turing computable if the function’s value can be computed with a Turing machine.
More specifically, let $D$ be a set of words in a given alphabet and let $f$ be a function which maps elements of $D$ to words on the same alphabet. We say that $f$ is Turing computable if there exists a Turing machine such that

If one starts the Turing machine with a word $w\in D$ as the initial content of the tape, the computation will halt.

When the computation halts, the tape will read $f(w)$.
Formally, let $\Sigma$ be an alphabet and $f:\Sigma^{*}\to\Sigma^{*}$ on words over $\Sigma$. Then $f$ is said to be Turingcomputable if there is a Turing machine $T$ over $\Sigma$ (its input alphabet), as defined in this entry, such that for any $w\in\Sigma^{*}$,
$(s,\tau_{w},1)\rightarrow^{*}(h,\tau_{{f(w)}},m)$ 
for some $m$. Here, $h$ is a halt state (either an accept or a reject state), and $\tau_{w}$ for any word $w$ is defined as the tape description such that the content of the $i$th square is the $i$th letter of $w$, and blank everywhere else.
Because of the fact that all types of Turing machines (deterministic, nondeterministic, single head, multiple head, etc.) all have the same computational power, it does not matter which type of Turing machine one uses in the definition.
Mathematics Subject Classification
03D10 no label found68Q05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
aka ``recursive''
``Turing computable'' functions are also called ``recursive'' functions. (The confusion stems from the preChurchTuring days, when the concept of recursive function was defined by adding minimization to primitive recursive functions, and it was not clear that Turing machines had exactly the same power).
Could this synonym be added?
Re: aka ``recursive''
I've changed the entry to mention that recursive means basically the same thing, but I'm not making it a formal synonym. This is because I think there should be a separate ``recursive function'' entry with that synonym, which should recieve the linking.
Alternatively this entry could be greatly expanded so that it covers recursive function theory, but I'm not the guy to write that (I'll orphan the entry if you want it though.)
apk