Turing computable
A function is Turing computable if the function’s value can becomputed with a Turing machine.
More specifically, let be a set of words in a given alphabet andlet be a function which maps elements of to words on thesame alphabet. We say that is Turing computable if thereexists a Turing machine such that
- •
If one starts the Turing machine with a word as theinitial content of the tape, the computation will halt.
- •
When the computation halts, the tape will read .
Formally, let be an alphabet and on words over . Then is said to be Turing-computable if there is a Turing machine over (its input alphabet), as defined in this entry (http://planetmath.org/FormalDefinitionOfATuringMachine), such that for any ,
for some . Here, is a halt state (either an accept or a reject state), and for any word is defined as the tape description such that the content of the -th square is the -th letter of , and blank everywhere else.
Because of the fact that all types of Turing machines (deterministic,non-deterministic, single head, multiple head, etc.) all have the samecomputational power, it does not matter which type of Turing machineone uses in the definition.
It is not hard to find examples of Turing computable functions —because Turing machines provide an idealized model for the operationof the digital computer, any function which can be evaluated by acomputer provides an example.