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 $\mathrm{\Sigma}$ be an alphabet and $f:{\mathrm{\Sigma}}^{*}\to {\mathrm{\Sigma}}^{*}$ on words over $\mathrm{\Sigma}$. Then $f$ is said to be Turingcomputable if there is a Turing machine $T$ over $\mathrm{\Sigma}$ (its input alphabet), as defined in this entry (http://planetmath.org/FormalDefinitionOfATuringMachine), such that for any $w\in {\mathrm{\Sigma}}^{*}$,
$$(s,{\tau}_{w},1){\to}^{*}(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.
It is not hard to find examples of Turing computable functions — because Turing machines provide an idealized model for the operation^{} of the digital computer, any function which can be evaluated by a computer provides an example.
Title  Turing computable 

Canonical name  TuringComputable 
Date of creation  20130322 12:33:16 
Last modified on  20130322 12:33:16 
Owner  rspuzio (6075) 
Last modified by  rspuzio (6075) 
Numerical id  9 
Author  rspuzio (6075) 
Entry type  Definition 
Classification  msc 03D10 
Classification  msc 68Q05 
Synonym  Turingcomputable 
Related topic  RecursivelyEnumerable 
Related topic  FormalDefinitionOfATuringMachine 