For the natural numbers Nat = {0, 1, 2, … } we use the unary representation, namely, n_Nat _ 0n1_{0,1}*. Since we will consider functions of several arguments, we will also need to encode tuples from Nat by concatenating the representations of the constituents, e.g.,
By the literal interpretation of Definition 8.1.7, Turing machines can compute only string-to-string functions. For functions on non string domains, Turing- computability is understood to be with respect to a “simple” representation of the domain in terms of strings.
| Previous slide | Next slide | Back to first slide | View graphic version |