Definition 8.1.7: a partial function is called (partial) Turing-computable if there exists a Turing transducer that computes exactly that (partial) function; for a total function, if there exists a Turing transducer that computes that function and halts for every element of the domain, the function is said to be total Turing-computable.
By a Turing transducer we simply mean an ordinaryTuring machine where we take notice of thecorrespondence between the initial input sequencefrom _* and the content of the tape from _* (normallyignoring rightmost blanks) when the machine halts (if ever).
Previous slide | Next slide | Back to first slide | View graphic version |