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

326 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13

Fig. 13-2

13.3Gödel Numbers

Recall (Section 11.5) that a positive integerp>1 is called a prime number if its only positive divisors are
1 andp. We letp 1 ,p 2 ,p 3 ,...denote the successive prime numbers. Thus

p 1 = 2 ,p 2 = 3 ,p 3 = 5 ,p 4 = 7 ,p 5 = 11 ,...

(By Theorem 11.12, there exists an infinite number of primes.) The Fundamental Theorem of Arithmetic
(Theorem 11.20) states that any positive integern>1 can be written uniquely (except for order) as a prod-
uct of prime numbers. The German logician Kurt Gödel used this result to code finite sequences of numbers and
also to code words over a finite or countable alphabet. Each sequence or word is assigned a positive integer called
itsGödel numberas follows.
The Gödel number of the sequences=(n 1 ,n 2 ,...,nk)of nonnegative integers is the positive integerc(s)
whereniis the exponent ofpiin the prime decomposition ofc(s), that is,

c(s)=pn 11 p 2 n^2 ...pnkk

For example,
s=( 3 , 1 , 2 , 0 , 2 ) is coded by c(s)= 23 · 3 · 52 · 70 · 112 =72 600

The Gödel number of a wordwon an alphabet{a 0 ,a 1 ,a 2 ,a 3 ,...}is the positive integerc(w)where the
subscript of theith letter ofwis the exponent ofpiin the prime decomposition ofc(w). For instance,

w=a 4 a 1 a 3 a 2 a 2 is coded by c(w)= 24 · 3 · 53 · 72 · 112

(Observe that both codes are essentially the same since we may view a wordwas the sequence of the subscripts
of its letters.)
The above coding is essentially the proof of the main result of this section:

Theorem 13.2: Suppose an alphabetAis countable. Then any languageLoverAis also countable.

Proof:The Gödel coding is a one-to-one mappingc:L→N. ThusLis countable.

13.4Turing Machines

There are a number of equivalent ways to formally define a “computable” function. We do it by means of a
Turing machineM. This section formally defines a Turing machineM, and the next section defines a computable
function.
Our definition of a Turing machine uses an infinite two-way tape, quintuples, and three halt states. Other
definitions use a one-way infinite tape and/or quadruples, and one halt state. However, all the definitions are
equivalent.