## K. Velupillai

Print publication date: 2000

Print ISBN-13: 9780198295273

Published to Oxford Scholarship Online: November 2003

DOI: 10.1093/0198295278.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2015. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 30 September 2016

# (p.185) Appendix: A Child's Guide to Elementary Aspects of Computability

Source:
Computable Economics
Publisher:
Oxford University Press
DOI:10.1093/0198295278.005.0001

# Abstract and Keywords

In the appendix, a brief and introductory survey of selected, relevant results from classical recursion theory is given. The Turing Machine model of computability is made central, but a definition in terms of recursive functions is also discussed. That the two notions of computability and randomness provide the epistemological fulcra for computable economics is emphasized.

# A1 Preamble

And one might express what [Turing] says also in the form of games. And the interesting games would be such as brought one via certain rules to nonsensical instructions.

Wittgenstein (1980: s. 1096)

The following are the contents of a child's toy set, curiously called “Computable and Uncomputable Games.” The game in question is a game of solitaire, i.e. played by one person:
1. (a) a tinman with movable joints and sensory organs;

2. (b) a small box car, big enough for the tinman, on grooved wheels;

3. (c) a large supply of pieces of rails on which the grooves of the boxcar fit smoothly; each piece of rail is approximately long enough to hold the boxcar, but sliding wedges – like in Lego sets – make it possible to build long railroad lines in both directions;

4. (d) a long white board, on stands, that can be placed alongside the railroad lines – potentially extendable as far as the lines go; the tinman's vision is constrained, by artificial means, to view the contents of exactly one square of the white board per unit of time;

5. (e) colored chalks, cloth to wipe the board, and an extra boxcar; also instructions on how to order extra rail pieces and extensions for the white board.

The tinman in action is schematically illustrated in Figure A1.

Like all serious toy sets, this one includes a book of instructions and rules on how to “play” the game. The boxcar can move to the (p.186)

Fig. A1

right or left on the rails, one section of rail at a time; its movement is controlled by a lever which operates the wedges connecting adjacent pieces of rails. The tinman operates the lever. The operation is not unlike that which is done to shunt trains onto different tracks.

The tinman's functions are specified in the book of instructions as follows:

1. (i) to write any one symbol at a time in the square on the white board facing the boxcar in which the tinman stands; the instruction book specifies the allowable symbols (usually, 0, 1, and B (for blank, distinguishable from 0));

2. (ii) to erase the symbol, if any, that is in the square facing the boxcar;

3. (iii) to leave a square without altering its contents, if so wished.

The tinman's sensory organs are connected to a gearing mechanism which can operate at any one of a finite number of states (think of 16 speed gears on a bicycle, for example).

The rules, according to the instruction book, for allowable sequences of symbols with which the tinman can fill the squares are as follows:

1. (α) The person playing the game begins by filling a finite number of the squares on the white board with the allowable symbols.

2. (β) The boxcar is placed on the rail facing the leftmost of the squares that the player has filled, with the tinman in the boxcar.

3. (χ) When the tinman's sensory organs sense the scanned symbol – i.e. when the tinman “sees” the square on the white board facing the boxcar in which he is standing – they “instruct” his hand to:

• (i) erase the current symbol and replace it with another one; or,

(p.187)
• (ii) leave “as is”;

• (iii) shift gears to another level depending on the new symbol in the square;

• (iv) shift the lever to move the boxcar to the next rail on the left or right.

The above description exhausts the rules of the game as far as playing it is concerned. Games hang by their own bootstraps until some indication of a way to reach a “result” is specified. In “Computable and Uncomputable Games,” a play terminates when the gearing mechanism of the tinman's sensory organs reaches a specified position. The result of a game that terminates is a function of the string of symbols appearing on the white board at termination.

Surely, this is a game any child can play?

But, will every play of the game terminate? Does every game of Monopoly end conclusively in finite time? Of course not. In principle, the game of Monopoly can go on for ever. Similarly, in principle, the tinman can keep on working for ever – subject to availability of extension railtracks and white boards!

The above are the ingredients of a machine that can compute anything that is intuitively understood and accepted to be computable. But, the perceptive child will ask: “Whose intuition,” and what does “computable” mean? The second part is relatively easy to answer (cf. next section); the first part is more difficult.

It is in answering the first part of the child's query that one begins to enter the metaphysical zone of computable and uncomputable games. Let us agree, at least pro tempore, on the meaning to be attached to “computable” in the everyday sense of arithmetic at the grocery shop. The process of computing a sum, a product, a division, or a subtraction is not universal. The abacus, for example, is still dominant in everyday computing in Japan. But the abacus and the simple calculating machines come to the same answer, when given the same data and asked to perform one of the arithmetic operations. Are there fundamental irreducible processes hidden underneath superficially different activities? Turing answered this question by constructing his Turing machine, and its building‐blocks are almost exactly those in the above toy set.

We compute not only ordinary sums and the like; we also compute velocities, areas, and so on. Imagine another toy – let us call it “Recursive and Nonrecursive Games,” perhaps for slightly older (p.188) children – which claims to be able to compute all intuitively computable functions! How shall we decide whose intuition is superior? Fortunately, we are spared this difficult decision: it turns out that both games, in their plays, compute exactly the same class of functions. Evidence gathered over the years from different toy sets confirms that all of the games, even while allowing the plays to be different, compute the same class of functions. This “empirical fact” is called the Church–Turing thesis. Its origins lie in the deep recesses of mathematical epistemology. I have alluded to these issues, tangentially, in each chapter. A full discussion will appear in the companion book to this one.

But what does it mean “to compute a function”? Surely, any explication would require concepts and a maturity that would be beyond most children? Space and context do not allow me to go into a detailed answer refuting such skeptical thoughts, although an attempt – inadequate, no doubt – will be made in the next section. Suffice it to say that it is much easier to teach and motivate the meaning of a computation and the concomitant computable function than it is to teach much that is commonly taught as mathematics in high schools.

To conclude these elementary observations, consider the following questions posed by a perceptive child:

1. (1) Since the child learns, by playing, that the result of a terminated game is a function of the final sequence of symbols in the series of squares on the white board, it may wonder as follows: can I specify any pattern I like for the final configuration of a terminating game and ask you to give me the initial configuration that will lead to it? Like most “inverse problems,” this one gives a negative answer – unless the final configuration is trivial. This question, and the answer, contain much of the import of Rice's theorem.

2. (2) The child may also ask, after playing the game many times, if it is possible to “say” beforehand whether any given initial configuration will lead to a terminating game? This, too, leads to a negative answer and contains much of the substance of what I have referred to in the main text as the undecidability of the halting problem for Turing machines.

Why, the weary reader may wonder, should an economist try to seek theoretical foundations for economic theory in such simple games? I may happily deflect this reader to the perceptive admonition by (p.189) Arrow to economists to seek “more consistent assumptions of computability in the formulation of economic hypotheses” (cf. Chapter 3 above). I could even refer such readers all the way back to Petty's attempts to quantify economics, at its very origin.

But I may also answer by pointing out that it is the mathematization of economics that has caused the subject to become quantitative in a meaningful numerical and constructive sense. The epistemological constraints that mathematicians imposed on their own foundations led to a branch of mathematics that characterized the real number systems into a computable and an uncomputable part. If, therefore, economic entities are to be quantified, then it seems natural that they must be based on the computable numbers. These numbers are algorithmically generated by nothing other than “Computable and Uncomputable Games,” “Recursive and Non‐recursive Games,” and other games related to this by the Church–Turing thesis. It just so happens that these are almost as simple as children's games to play, and to understand. It is the algorithmic (rule‐based) generation that makes the game playable (cf. Chapter 7). If, as I have also argued, economics is also problem‐solving, then it may be necessary to leave out undecidable disjunctions, uncomputable numbers, and such noneffective methods. There again, the metaphor of the child's toy set is a good example: a toy set with noneffective instructions is useless. The same applies to any formalization. The beauty lies in the fact that a finitely specified effective game for children contains nonterminating plays!

# A2 Pseudo‐Theory

That we calculate with some concepts and with others do not, merely shews how different in kind conceptual tools are . . .

Wittgenstein (1980, s. 1095)

## A2.1 Description, Definitions, and Conventions

In preparing this section, I have used Boolos and Jeffrey (1989), Bridges (1994), Davis (1982), Hunter (1971), and Moret (1998) quite freely, and many of the standard classics of computability theory.

1. DESCRIPTION A.1. A Turing machine consists of the following interlinked parts:

(p.190)
• (i) a movable control mechanism which at any given point in time is in one of a finite number of possible states;

• (ii) a sensor, attached to the movable control mechanism, that can scan the symbols on an infinite tape, interpret the symbols, erase them, and also write symbols on the tape;

• (iii) the tape, infinite to the left and right, divided into (scannable) cells, in each one of which one symbol from a fixed alphabet can be written.

One of the many possible ways of depicting the essence of such a machine is shown in Figure A2.

Fig. A2

1. CONVENTION A1

2. (a) The sensor can scan exactly one cell at a time.

3. (b) Only a finite number of cells of the infinite tape are nonempty at any given point in time.

4. (c) The sensor is placed scanning the leftmost nonempty cell when it is initialized.

5. (d) The fixed alphabet consists of the three symbols ⟨ 0, 1, Ø⟩ (where Ø: denotes the symbol “blank” and is different from the numeral 0).

Denote by

1. Q: finite set of states;

2. q0 ∈ Q: a pre‐specified initial state;

3. qT ∈ Q: a pre‐specified terminal state;

4. δ: a partial function (i.e., not defined over the whole of its domain); i.e.,

5. δ: Q × ΛQ × Λ × {L, R, γ},

where Λ is the symbol set (alphabet): ⟨ 0, 1, Ø⟩ in our case; L is a left‐ward movement of the movable control; R is a rightward movement (p.191) of the movable control; γ represents no movement of the movable control; and where (q T, α) is not defined, ∀ α ∈ Λ; i.e., if the movable control is in, or reaches, the terminal state T, the actions of the Turing machine cease.

DEFINITION A1. TURING MACHINE. Given the fixed alphabet Λ, a Turing machine (TM) is a quadruple: TM ≡ ⟨ Q, δ, q 0, q T

Remark. Many elements of the description and the convention have been chosen with a view to making the definition seem “natural.” Not all of the elements are necessary. I have not sought a minimal set of elements for the description and the definition.

## A2.2 Examples of Computation

### (a) A General Example for the Turing Machine

1. (1) Assume that a finite portion of the infinite tape has written in the corresponding cells the following sequence of symbols: $1 0 0 1 ∅ 1 0 1 1 0 ∅ ,$with empty squares to the left of the leftmost 1 and to the right of the rightmost Ø.

2. (2) TM must be set to state q 0 and the sensor places against the leftmost 1.

3. (3) Then, in general, if the TM senses the symbol α in state q, it will compute δ(q, α) which may be equal to, say, δ(q′, α′, S).

4. (4) The TM sensors would write α′ in place of α, shift to state q′, and move one cell to the left (S = L), right (S = R), or not move at all (S = γ).

5. (5) If the TM ever reaches the state q T, it will stop its activities.

6. (6) The sequence of symbols remaining when the TM reaches q T is the output.

### (b) A Simple Example for TM, I.E. ⟨ Q, δ, Q 0, Q t⟩

Given Q = ⟨ q 0, q 1, q 2, q T⟩, Λ ≡ ⟨ 0, 1, Ø⟩ and the following tape input: the rules (= “programs”) for the activities of TM, i.e. the state transition function δ, can be given in a transition table (Table A1). (p.192)

Table A1

0

1

Ø

q 0

q 1,1,R⟩

q 2,Ø,R⟩

q T,Ø,L⟩

q 1

q 1,1,R⟩

q 1,0,R⟩

q T,Ø,L⟩

q 2

q 1,Ø,R⟩

q 2,1,γ⟩

q T,0,L⟩

q T

STOP

STOP

STOP

For example the instructions are read column‐by‐row; then TM, scanning 0 in state q 0, overwrites 0 with 1, enters state q 1, and shifts to scan the next cell on the right.

Hence, TM1's activities for the given input and transition table here, Table A1 will be as follows:

 Step 1: 0 Ø 1 1 0 0 Step 2: 1 Ø 1 1 0 0 Step 3: 1 Ø 1 1 0 0
This Turing machine's activity consists in replacing the leftmost 0 by a 1.

CONVENTION A2. The natural number nN is represented on a Turing machine tape by n + 1 symbols of the numeral 1. By courtesy, zero is represented by a single 1.

CONVENTION A3. The transition function δ is represented by a series of program cards, one card for each of the finite states of the relevant Turing machine, each of which specifies, for each symbol of the given alphabet, the computing activity of the machine.

### (C) A Computation Using Program Cards

Consider the 2‐state, 2‐symbol Turing machine, TM2 (Figure A3), whose activities are represented by two program cards (where state 1 corresponds to q 0). On each card we have:

1. (a) Column 1: scanned symbol

2. (b) Column 2: the new symbol to be inserted

3. (c) Column 3: shift left or right instruction

4. (d) Column 4: next state to enter

Example. Let us start TM2 on state 1 scanning a blank tape (see Figure A4): (p.193)

Fig. A3

1. (State 1) Step 1: scanning 0; overwrite 1; shift R; enter state 2

2. (State 2) Step 2: scanning 0; overwrite 1; shift L; enter state 1

3. (State 1) Step 3: scanning 1; overwrite 1; shift L; enter state 2

4. (State 2) Step 4: scanning 0; overwrite 1; shift L; enter state 1

5. (State 1) Step 5: scanning 0; overwrite 1; shift R; enter state 2

6. (State 2) Step 6: scanning 1; overwrite 1; shift L; stop

The activities of TM2, started off on a blank tape, can be summarized as follows:
1. (i) It writes four 1s on a blank tape.

2. (ii) It is a 2‐state machine that shifts 6 times.

DEFINITION A2. TURING MACHINE COMPUTABLE FUNCTIONS. A function f is Turing machine (TM) computable if there exists a Turing machine such that, whenever the TM is started in state 1 (= q 0), scanning the leftmost of x + 1 consecutive 1s, the TM eventually halts scanning at the leftmost of f(x) + 1 consecutive 1s.

### (d) An Example of a TM That Computes f(x) = 2

The 5‐state, 2 symbol TM depicted in Figure A5 computes f(x) = 2 under the above definition (i.e., start in state 1, etc).

Example of a noncomputable function: cf. Chapter 7.

## A2.3 Enumerability, Recursive Functions, and Sets: Some Definitions and Theorems

Consider the following four functions which can be accepted, unambiguously, as intuitively computable in the sense that it is easy to construct Turing machines to compute them: (p.194)

Fig. A4

1. (i) zero function: z(x) = 0, ∀ xN. This function assigns the same value, zero, to each natural number as argument; i.e. z(0) = z(1) = z(2) = . . . = 0;

2. (ii) identity function: Id(x) = (x), ∀ xN. This function assigns to each natural number as argument its own value as output; i.e., Id(0) = 0; Id(1) = 1; Id(2) = 2; . . . ; (p.195)

Fig. A5

3. (iii) successor function: S(x) = x + 1, ∀ xN;

4. (iv) projection function: $Pr i k : N k → N$, defined by “projecting” the ith coordinate of a k‐dimensioned domain as

$Display mathematics$

1. DEFINITION A3: THE BASIC FUNCTIONS. The collection of intuitively computable functions given by (i)–(iv) are the basic functions.

Next, consider the following two operations that are to be applied to given computable functions – again, in the sense that it is easy to construct Turing machines to perform them.

1. (α) Composition of computable functions. If f and g i (i = 1, 2, . . . , m) are computable functions of m and n arguments, respectively, then h is obtained by composition from f and g i (i = 1, 2, . . . , m) as follows:

$Display mathematics$

2. (β) Primitive recursion of computable functions. Given the computable functions

$Display mathematics$
the computable function Ψ: N nN is obtained from φ and θ by primitive recursion whenever
$Display mathematics$
and
$Display mathematics$

(p.196) DEFINITION A4: PRIMITIVE RECURSIVE FUNCTIONS. The set $𝓟$ of primitive recursive functions are those that are closed with respect to (finite applications of) composition and primitive recursion on the basic functions.

Unfortunately, this set does not exhaust the class of intuitively computable functions. The classic intuitively computable function from N × NN defined by Ackerman grows faster than any member of $𝓟$. Recall, from Chapter 7, that the construction of an intuitively uncomputable function used the same principle. Ackerman's famous function is:

$Display mathematics$
The same strategy as used for the Busy Beaver game can be used for the Ackerman function to show monstrous growth rates.

Now, since Ackerman's function is intuitively computable, the class $𝓟$ of primitive recursive functions will have to be enlarged. On what basis can this enlargement be executed so that exactly the intuitively computable functions are included in it? We have accepted that all the Turing machine computable functions are intuitively computable. Are there, conversely, intuitively computable functions that are not Turing machine computable? Answers to these questions are summarized, as mentioned in earlier sections and chapters, in the Church–Turing thesis. But to get to that, a few more definitions and details are necessary.

DEFINITION A5: PARTIAL FUNCTION AND TOTAL FUNCTION. A function f: XY but where f may not be defined on the entire domain X is called a partial function. Correspondingly, a total function is defined on its entire domain.

1. (γ) Minimalization of computable functions. The function h of n arguments is obtained by the following operation – called minimalization – from the computable total function f of n + 1 arguments:

$Display mathematics$
The qualifications “if any” and “for no y” introduce elements of effective undecidability to elementary computability (p.197) theory. We may keep on trying, in some definite order, different values of y until f(x 1, . . . , x n, y) = 0. There is no guarantee, except for trivial functions, that failure to find such a y after a billion or a trillion trials means that it will not be found in the next, say, 18 attempts. The same ambiguity applies to the activity of locating “the smallest y”. This operation of minimalization ties up recursive functions with the real activity of computation. A computer (i.e. a Turing machine) may fail to terminate for some inputs; a function h may be undefined.

DEFINITION A6: PARTIAL RECURSIVE FUNCTIONS. The set of functions PRC that are closed with respect to the (finitely applied) operations of composition, primitive recursion, and minimalization on the basic functions are the partial recursive functions.

CHURCH–TURING THESIS. A partial function is computable if and only if a Turing machine can be constructed to compute it.

Remark. This is a thesis and not a theorem. It is entirely possible that some future Alan Turing will find a way to tame the monstrous growth rates inherent in a Busy Beaver game. There are distinguished recursion theorists, philosophers, and mathematicians (Laszlo Kalmar, Ludwig Wittgenstein, and Steve Smale, respectively, come immediately to mind) who feel that there is more to be said on these issues.

DEFINITION A7: RECURSIVE SETS. A set XN of natural numbers is recursive if and only if there is a partial recursive function φ such that ∀ n, nX if and only if φ(n) = 0.

DEFINITION A8: DECIDABLE SETS. A set is decidable if and only if there is an effective (i.e. computable) method to characterize any member of the set.

Thus, since every partial recursive function is computable, every recursive set is decidable. In other words, there is an effective method – an algorithm — to decide whether or not an arbitrary n is a member of X.

DEFINITION A9: RECURSIVELY ENUMERABLE SETS. A set XN of natural numbers is recursively enumerable (r.e.) if and only if it is either empty or describes the range of a partial recursive function.

There is an open‐endedness in the definition of r.e. sets that is absent in the definition of recursive sets. The definition of r.e. sets (p.198) entails the existence of a partial recursive function (or, equivalently — by the Church–Turing thesis — a Turing machine) which can systematically output members of such sets. Thus, the openendedness comes from the fact that an arbitrary nn may not, say, till the billionth try be the output of a PRC; but it may well be the next output after the billionth try. We can only keep on trying, without any guarantee of a definite answer.

Some elementary and immediate implications of the above three definitions can now be stated.

PROPOSITION A1. If a set is recursive, then its complement is also recursive.

PROPOSITION A2. A recursive set is also recursively enumerable. (In other words, a decidable set is listable (enumerable).)

PROPOSITION A3. If a set and its complement are both recursively enumerable, then the two sets are also recursive.

THEOREM A.1: THE UNDECIDABILITY OF THE HALTING PROBLEM FOR TURING MACHINES. There is no algorithm to decide whether or not any given Turing machine enters the terminal state for arbitrary input configurations on the tape.

Remark. Any standard textbook on recursion theory will normally include a discussion of this theorem and, of course, complete proofs. The reason for stating the theorem at this particular juncture is as follows. According to this theorem, there is no effective method (i.e., again, there is no algorithm) to decide whether or not a Turing machine for an arbitrary program card will enter its terminal state. An immediately relevant question will be: can it be decided whether a Turing machine exhibits some particular input–output behavior? Armed with a knowledge of the undecidability of the halting problem, it will not be surprising that the answer is in the negative. Rice's theorem summarizes the result.

THEOREM A2: RICE'S THEOREM. Denote by φi: NN the partial recursive function computed by Turing machine TM. If XN is recursive, then there exists i, j such that iX and jNX, and φi = φj.

In other words, there are distinguishable Turing machines, TMi and TMj, that compute the same partial recursive functions. Thus, if D i is a decidable property possessed by TMi and not possessed by (p.199) TMj, then it is not possible to tell which is which simply by observing their input–output behavior. Another, and more succinct, way of stating the import of the theorem is as follows:

Any nontrivial input–output property of programs is undecidable.

This can be interpreted — exactly — to mean that only the properties of the empty set and the universal set are effectively decidable. Now, Rice's theorem characterizes recursive sets. The natural extension of Rice's theorem would be an analogous result for recursively enumerable sets. Such a result is encapsulated in the following theorem.
1. THEOREM A3: THE RICE–SHAPIRO THEOREM. Consider the set $𝓒$ of partial recursive functions such that

$Display mathematics$
Then, for any partial recursive function ψ,
$Display mathematics$

2. Now, every finite input–output configuration defines a recursive set. Going, therefore, from Rice's theorem to the Rice–Shapiro theorem would be akin to finding an extension of some finite input–output configuration to define recursively enumerable sets. Thus, according to the Rice–Shapiro theorem, a class of partial recursive functions is recursively enumerable if and only if each member of this class is defined by the extension of some finite input–output configuration in a recursively enumerable set of such configurations.

# A3 Partial Reflections

[T]he importance of the concept of general recursiveness (or Turing's computability) . . . is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., not one depending on the formalism chosen.

Gödel (1946/1965: 84)

Computability and randomness are the two basic epistemological notions I have used as building‐blocks to define computable economics. Both of these notions can be put to work to formalize (p.200) economic theory in effective ways. However, they can be made to work only on the basis of two theses: the Church–Turing thesis, and the Kolmogorov–Chaitin–Solomonoff thesis. Under these theses, we have definitions, independent of any chosen formalism, for computability and randomness.

In this appendix I have given an outline of elementary aspects of computability theory. The building‐blocks are simple, intuitively acceptable, and easy to assemble into vast, elegant, and useful structures. A similar outline could be given for the elementary parts of applied computability theory — i.e. algorithmic, computational, and diophantine complexity theories. For reasons of space, I must, reluctantly, refrain from attempting such an outline in this work.