Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

330 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

13.5Computable Functions

Computable functions are defined on the set of nonnegative integers. Some texts useNto denote this set. We
useNto denote the set of positive integers, so we will use the notation

N 0 ={ 0 , 1 , 2 , 3 ,...}

Throughoutthissection,thetermsnumber,integer,andnonnegativeintegerareusedsynonymously.Thepreceding
section described the way a Turing machineMmanipulates and recognizes character data. Here we show how
Mmanipulates numerical data. First, however, we need to be able to represent our numbers by our tape setA.
We will write 1 for the tape symbola 1 and 1nfor 111...1, where 1 occursntimes.

Definition 13.12: Each numbernwill be represented by the tape expression〈n〉where〈n〉= 1 n+^1. Thus:

〈 4 〉= 11111 = 15 , 〈 0 〉= 1 , 〈 2 〉= 111 = 13.

Definition 13.13: LetEbe an expression. Then [E] will denote the number of times 1 occurs inE. Thus

[ 11 Bs 2 a 3111 Ba 4 ]= 5 , [a 4 s 2 Ba 2 ]= 0 , [〈n〉] =n+ 1.

Definition 13.14: A functionf:N 0 →N 0 is computable if there exists a Turing machineMsuch that, for every
integern,Mhalts on〈n〉and

f (n)=[term(α(〈n〉)]

We then say thatMcomputesf.
That is, given a functionfand an integern, we input〈n〉and applyM.IfMalways halts on〈n〉and the
number of 1’s in the final picture is equal tof (n), thenfis a computable function and we say thatMcomputesf.

EXAMPLE 13.4 The functionf (n)=n+3 is computable. The input isW= 1 n+^1. Thus we need only add
two 1’s to the input. A Turing machineMwhich computesffollows:

M={q 1 ,q 2 ,q 3 }={s 01 s 0 L, s 0 B 1 s 1 L, s 1 B 1 sHL}

Observe that:

(1)q 1 moves the machineMto the left.

(2)q 2 writes 1 in the blank squareB, and movesMto the left.

(3)q 3 writes 1 in the blank squareB, and haltsM.

Accordingly, for any positive integern,

s 01 n+^1 →s 0 B 1 n+^1 →s 1 B 1 n+^2 →sHB 1 n+^3

ThusMcomputesf (n)=n+3. It is clear that, for any positive integerk, the functionf (n)=n+kis
computable.

The following theorem applies.

Theorem 13.4: Supposef:N 0 →N 0 andg:N 0 →N 0 are computable. Then the composition function
h=g◦fis computable.
We indicate the proof of this theorem here. SupposeMfandMgare the Turing machines which compute
fandg, respectively. Given the input〈n〉, we applyMfto〈n〉to finally obtain an expressionEwith[E]=f (n).
We then arrange thatE=s 01 f (n). We next add 1 toEto obtainE′=s 011 f (n)and applyMgtoE′. This yields
E′′where[E′′]=g(f (n))=(g◦f )(n), as required.