|
|
|
|
Turing computable
|
(Definition)
|
|
|
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)$ .
Because of the fact that all types of Turing machines (deterministic, non-deterministic, 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.
|
"Turing computable" is owned by rspuzio. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
Cross-references: computer, operation, power, multiple, deterministic, types, maps, alphabet, Turing machine, function
There are 6 references to this entry.
This is version 5 of Turing computable, born on 2002-03-23, modified 2006-01-15.
Object id is 2800, canonical name is TuringComputable.
Accessed 5995 times total.
Classification:
| AMS MSC: | 68Q05 (Computer science :: Theory of computing :: Models of computation ) | | | 03D10 (Mathematical logic and foundations :: Computability and recursion theory :: Turing machines and related notions) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
