BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1340
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Undecidability in Macroeconomics (Preliminary Draft)
AUTHOR:: Chandra, Siddharth 
AUTHOR:: Chandra, Tushar Deepak
DATE:: April 1993
PAGES:: 36
ABSTRACT:: 
In this paper, we study the difficulty of solving problems in economics. For 
this purpose, we adopt the notion of undecidability from recursion theory. We 
show that certain problems in economics are undecidable, i.e., cannot be 
solved by a Turing Machine, a device that is at least as powerful as any 
computational device that can be constructed [2]. In particular, we prove 
that even in finite closed economies subject to a variable initial condition, 
in which a social planner knows the behavior of every agent in the economy, 
certain important social planning problems are undecidable. Thus, it may be 
impossible to make effective policy decisions.

Philosophically, this result formally brings into question the Rational 
Expectations Hypothesis, which assumes that each agent is able to determine 
what it should do if it wishes to maximize its utility. We show that even when 
an optimal rational forecast exists for each agent (based on the information 
currently available to it), agents may lack the ability to make these 
forecasts. For example, Lucas [7] describes economic models as ``mechanical, 
artificial world(s), populated by ... interacting robots''. Since any 
mechanical robot can be at most as computationally powerful as a Turing 
Machine, such economies are vulnerable to the phenomenon of undecidability.
END:: CORNELLCS//TR93-1340
BODY::
Undecidability in Macroeconomics
(Preliminary Draft)*
Siddharth Chandra**
Tushar Deepak Chandra***
TR 93-1340
April 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
Research supported by NSF grant CCR-91 02231, DARPA/NASA Ames grant NAG
2-593, grants from the IBM Endicott Programming Laboratory and Siemens Corp.
**Department of Economics, Uris HAll, Cornell University, Ithaca, NY 14853. This
author is also supported by a Cornell Sage fellowship.
***Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY
14853. This author is also supported by an IBM graduate fellowship.
Undecidability in Macroeconomics
(Preliminary Draft)*
Siddhartli Chandrat and Tushar Deepak Chandrat
April 28,1993
Abstract
In this paper we study the difficulty of solving problems in economics. For
this purpose, we adopt the notion of undecidability from recursion theory. We
show that certain problems in economics are undecidable, i.e., cannot be solved
by a Turing Machine, a device that is at least as powerful as any computational
device that can be constructed [2]. In particular, we prove that even in finite closed
economies subject to a variable initial condition, in which a social planner knows
the behavior of every agent in the economy, certain important social planning
problems are undecidable. Thus, it may be impossible to make effective policy
decisions.
Philosophically, this result formally brings into question the Rational Expec-
tations Hypothesis which assumes that each agent is able to determine what it
should do if it wishes to maximize its utility. We show that even when an optimal
rational forecast exists for each agent (based on the information currently available
to it), agents may lack the ability to make these forecasts. For example, Lucas [7]
describes economic models as "mechanical, artificial world(s), populated by .... in-
teracting robots". Since any mechanical robot can be at most as computationally
powerful as a Thring Machine, such economies are vulnerable to the phenomenon
of undecidability.
*Research supported by NSF grant CCR-9102231, DARPA/NASA Ames grant NAG-2-593, grants
from the IBM Endicott Programming Laboratory and Siemens Corp.
tDepartment of Economics, Uris Hall, Cornell University, Ithaca, NY 14853. This author is also
supported by a Cornell Sage fellowship.
tDepartment of Computer Science, Upson Hall, Cornell University, Ithaca, NY 14853. This author
is also supported by an IBM graduate fellowship.
Contents
1 Introduction
1.1 Rational Expectations: a limitation
2
3
ii
The Problem
2.1			Introduction. .			. .			. .			. .
2.2			Encoding the Thring Machine			.			. .			. .			.			. .
2.3			A Basic Economy
2.4			All Undecidable Economy . .			.			. .			. .			.
2.5			Correspondence between the Thring			Machine and the Economy
2.6			The Problem is Recursively Enumerable			.
2.7			Undecidability Proof . . .			.			. .			.			.
Applications and Limitations
3.1 Applications . .
3.2 Limitations
4 Conclusion
2
4
4
4
6
6
9
9
9
11
11
11
12
1 Introduction
In this paper we prove that there are fragments of macroeconomics about which it is
not possible to reason. In order to do so, we adopt techniques from recursion theory
that are new to the study of macroeconomics. There are two implications of this result.
First, agents in such economies cannot reason about potentially important facts. Sec-
ond, economists studying these economies cannot reason about them either. This result
prompts us to question the applicability of various traditional assumptions about knowl-
edge in economics. These include but are not restricted to the R?ational Expectations
Hypothesis and a variety of systems involving the formation of subjective or objective
probability priors. We emphasize that this result applies to closed finite economies. By
extension, we also provide an insight into what "...a formal theory of rational decision-
making in an open1 universe..." [1] might confront.
This result does not apply to the kinds of models macroeconomists are used to seeing
in journals. Those models have been designed to provide neat answers to a variety
of questions. An important feature that is almost invariably lacking in such models,
however, is a sense of separation of numerous heterogeneous agents or sectors. The result
of this paper might explain why economic models which mimic economies as distributed
systems of interacting agents or sectors are not very popular today: it is difficult and
sometimes impossible to reason about such economies.
Discrete decision processes are central to economic research. Examples of these
processes are the Overlapping Generations Model [10, 15] and the Townsend Turnpike
Model [10, 13]. It is natural to ask whether a systematic method solves such optimization
problems for economies with heterogeneous agents. This question is extremely difficult
to analyze. So we address the simpler question: given an arbitrary economy for which
there is a solution to a decision making problem, is it possible to find that solution? In
this paper, we show by example that this may not be possible even for a finite economy.
Thus the problem is "hard" because of its inherent complexity, and not because the
economy itself is intractably large. We present a problem that is specified in all respects
except for its initial condition and show that it is "hard" to solve.
To prove such a result we use the concept of a Turing Machine. A Turing Machine
is a computing device which is capable of executing any possible computing algorithm
including every possible learning algorithm and fine tuning mechanism. There is strong
evidence that a Thring Machine is at least as powerful as any computational device
that can be constructed [2]. A problem that cannot be solved by a Thring Machine
is said to be undecidable. We use techniques introduced by Reif et al [9] to develop a
methodology for showing that a variety of problems in economics are undecidable. We
apply this methodology to a simple problem for which a solution exists, and show that
the solution cannot be found using a Thring Machine. We thus demonstrate the degree
of difficulty that economists would encounter in characterizing a network economy in
terms of discrete interacting agents2 with limited choices.
1The italics are ours.
2These could be consumers, sectors, producers, trading partners etc.
2
A
c
INACCESSIBLE FACTS
ACCESSIBLE KNOWLEDGE
INFORMATION SET
Note: C implies A and B
Figure 1: We prove the existence of inaccessible facts.
This paper is divided into two parts. In the first part we present a discussion of
knowledge in economics and an example of an economy in which there are undecidable
problems. The second part consists of four appendices, the last two of which intro-
duce optimization and recursion theory to readers without any background in these
subjects. We strongly recommend that readers who are unfamiliar with the economic
or computational concepts used in the first part of the paper refer to these appendices.
Supplementary remedial readings are also suggested in each appendix.
1.1 Rational Expectations: a limitation
We use the exposition in Wan [16j to summarize rational expectations:
o Individuals form subjective probability distributions over future events.
o+ These distributions agree with the objective probability distribution of events based
on given information.
o+ This information includes past history, government policy and the set of relations
and functions that make up the general environment.
o+ Based on this information, a known outcome follows.
Thus, in order for rational expectations to hold, facts that follow from and only from
an agent's information must be available to the agent. In this paper, we show that there
exist facts that follow from and only from an agent's information that are not computable
by that agent even if (s)he knows the complete specification of the economy (see figure
1). Rational expectations as it is widely understood today shows no awareness of this
3
phenomenon. While this result is philosophical in nature, it should be of concern to a
variety of economists. In section 3 we outline a few examples in which undecidability is
a concern. The work of Spear [12] is related to this subject.
2 The Problem
2.1 Introduction
4
In this section, we will state a problem for a finite closed network economy and show
that it is undecidable. Intuitively, our construction will proceed as follows, Suppose
we are given a Thring Machine specification x and an input i. We will construct an
economy ?(x) with an agent ?, and an initial impulse 1(i) with the following property.
The impulse 1(i) reaches ? in S(x) if and only if ?? halts on i. In other words, we will
reduce the halting problem into a decision problem for a finite closed economy. By doing
so, we will have shown that the set of such problems is not recursive. This follows from
the fact that the halting problem is not recursive.
2.2 Encoding the Thring Machine
Suppose the given Turing Machine is T = (QT, F, 1, ?, 6T, q0, q?, q?? where F = fo, 11.?
We construct a new Thring Machine A4 that has exactly one halting state q? such that
M halts on exactly the same set of inputs as T.
The set of states of M is Q = Q?Ufq??. The state transition function of M, denoted
S, includes all the transitions of ?T and the following four additional transitions:
?(qa,O) =6(qa,1) = &(q?,O) =6(qr,1) = (q4,1,R)
The reader may verify that the resulting Thring Machine ?M halts on exactly the same
set of inputs as T. We will now construct an economy that mimics the behavior of M
and therefore mimics T.
Our economy consists of n agents, where n denotes the number of states in Q. Each
agent corresponds to a unique state of M. We represent the storage tape of A4 by using
two binary ftactions a3 and b3. Let go be the symbol which the tape head is currently
scanning.
Let g1,g2,g3,... be the successive symbols on the left of 9o, and h0, h1, ...... be the
successive symbols on the right of go. This is shown in figure 2. Then, we can represent
the storage tape by using two numbers a3 and b3:4
= li g,			(1)
i=0 3i+1
(2)
b3 =			___
3?+1
t--H--H0
Turing Machine moves can be divided into two cases, left moves and right moves.
Thus we consider two cases of ?:
3This assumption on F does Ilot reduce the computational power of the Thring Machine.
4We use 3 in the denominator of our expressions for a? and b8. [9] use 2 in the corresponding place.
5
Tape
...?			g2			g1			?			1)1			b4			?...
Read\Write Head
Finite
Control
Figure 2: Schematic diagram of a Turing Machine with alphabet ?0, 1?.
Note that 9j,hj ? fO,lJ.
Case 1: ?(q,c) =
Case 2: ?(q,c) =
Here, q is the current state of A4, q' is the next state of A4, c E fO, 1? is the symbol
below the tape head, and w ? (0,11 is the symbol which the tape head writes on the
tape L represents a left move, and R represents a right move. We now map the state
transition function 6 into the transition operation of an economy as follows:
Case 1: Left move 6(q, c) = (q', w, L). Let a6 and b6 be the values of a3 and b3 respectively
after this transition. Then, a6 and b6 can be written as:
a?=3Z g?			?3(a3???O)			(3)
i=1 3i+1			3
b6 =4+ _			=4+ ffis			(4)
3
Case 2: Right move 6(q, c) = (q', w, R). In this case a6 and b6 can be written as:
h0			w			1 ?			h0			w			a3--H
3			93 __ 3$1 =			+			+
a6 = --H + --H + --H			3			9			3			(5)
hj			h0
bb--H3?1 3i+1 --H3(bs --H 3)
6
(6)
In the next few sections we present agents who perform the very transformations
listed above, and then redirect the impulse to the agent corresponding to the new state
of M. Thus our economy will simulate the above Thring Machine.
2.3 A Basic Economy
Given the Thring Machine and its encoding, we can construct an economy as follows.
Each state of the Turing Machine's finite control is represented by a unique agent of the
economy. The computation of the Thring Machine is encoded as an impulse that flows
through the economy. At any instant this impulse will reside at exactly one agent. This
agent corresponds to the current state of the finite control of the Turing Machine.5 The
magnitude of the impulse represents the value of the tape of the Turing Machine.
When an agent receives an impulse, it optimizes its utility function and transmits
a new impulse to one of two6 neighbors (see figure 3). The choice of the neighbor to
whom the impulse is transmitted depends on the state transition function of the Turing
Machine as follows. A state transition from a to a' of the given Thring Machine is
encoded by an impulse transmitted by the agent corresponding to a towards the agent
corresponding to a'. The optimization function of each agent is designed to ensure that
the dynamics of the economy mimic the computation of the given Turing Machine.
Since the number of states of the given Thring Machine is finite, the number of agents
in the economy is also finite. The intensity of the received impulse plays an important
role in deciding with whom the receiving agent is going to interact. The process of
reoptimization may result in the absorption or magnification of some of the intensity of
the impulse.7
2.4 An Undecidable Economy
We consider the following economy: there are four consumer goods, a, b, c and d, and a
leisure good 1. The economy consists of a variety of agents who can consume any or all
of these goods, but can produce either one unit each of a and b, or one unit each of c
and d only. The goods in each production pair are referred to as related goods. Each
agent can buy goods from either a producer of a and b, or from a producer of c and cl.
Goods are bought by transforming leisure into labor, at the constant marginal cost of 1.
Figure 3 shows a section of the economy.
5This statement has a small technical flaw. In Appendix 3 we discuss this flaw and present a
specification for the economy which overcomes this flaw. We have avoided this technical discussion in
this section to make this paper easier to read.
6The problem can be generalized to a problem of choosing among many choices.
7This model is motivated by a discrete-choice making process which results from an impulse. An
example is an agent faced with a finite number of possible actions, of which he must choose one. His
action causes the agent he interacts with to adjust his behavior, and so on.
7
Endowment: (a,b)
Utility: U = Ui(a,b,c,d,l)
Endowment: (a,b)			3			Endowment: (c,d)
Utility: U = U2(a,b,c,d			Utility: U = U3(a,b,c,d,l)
Figure 3: A section of the economy
Following are the variables used in this analysis.
Zs = quantity of good i
z6 = quantity of good i
Zc = quantity of good i
sold to the preceding agent in a period
bought from the subsequent agent in a period
consumed in a period
where i is one of the four consumer goods. The utility function of agent j is of the
general form:
where
4
Uj = ZK,jic?21 +1
i--H--Hi
(7)
K,j = k(f?s?t4?i)			(8)
Thus the utility function is continuous and concave in a?, bc, Cc and dc. The parameter
Kij is a function of the quantity of produced goods sold by agent j. We motivate this
by an `information effect' on an agent's utility function.
Figure 10 in Appendix 2 shows the different values that Kt'j can take on for producers
of a and b. The corresponding values of Kq for producers of c and d are obtained by
replacing a? with Cs, bs with da, a6 with c6, etc.
The constant Kij for any good is a function of ?s, where i is the good itself or the
related good. The motivation for ?s entering K,j is as follows. An agent's marginal utility
for a good depends on how much of the good itself and the related good the agent sold.
We now emphasize some aspects of the economy. Note that all utility functions are
concave (weakly so in the case of leisure) and increasing in their arguments. The economy
has heterogeneous agents, i.e., different agents may have different utility functions. Thus
the economy is consistent with traditional assumptions of economic theory.
8
We now solve the optimization problem for one possible type of a and b producer.
See Appendix 2 for the solutions to the problems for all types of a and b producers. The
solution to the problem for the c and d producer is similar and is left to the reader.
The first case of Appendix 2 is solved below. This case corresponds to the following
transition in the Thring Machine simulation. The value in the tape cell below the tape
head of the Turing Machine is 1. The state transition function of M for the current
state requires the tape head to write a 1 and move to the left.
In this case, the agent chooses to buy a and b. The consumer's problem is:
subject to
1 I 4 --H 2bs ? 1
Max U = 2(2as)2ac2 + 0.1A + 2( )?2bc2 + 0.1dc2 + 1
3
ac			=			1 --H a? + ab
bc			=			1 --H bs + bb
Cc			=			Cb
dc			=			db
The first order conditions for an optimum are:
(2a			)21a?21			--H 1
4 --H 2b 1 1
3			8)2bc?2			= 1
O.O5Cc 2 = 1
O.O5dc 2 = 1
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
This condition will hold for the two goods which were bought: the agent will not be
willing to work for wages beyond this point, because leisure will be more valuable at the
margin. Because of the restriction on choice, the first order conditions will not hold for
the two goods which were not bought.
If a and b are bought, then ac = 2a? and ab = 3a? --H 1. Similarly, bc = ?32(2 --H bs) and
bb= -31(1+b5). Ifcand dwere to be bought, then Cc = Cb = 0J and dc= db = 021. It can
be checked that the utility from buying Cb and db is lower than the utility from buying
a6 and b6. Thus a and b are bought and:
a6 = 3a? --H 1			(18)
b6 = 1+bs			(19)
3
Recall that in this case the value of the tape cell below the tape head go is 1. It is
easy to verify the the impuise passed on to the next agent, i.e., (a6, b6) corresponds to
the case in which the tape head writes a 1 and then moves left (see Equations 3 and 4).
9
The optimization problem for the other types of a and b producer and for the c and
d producers can be solved in an analogous manner. A summary of the coefficients kij
for these cases appears in the figure in Appendix 2. Thus we have simulated a Thring
Machine using a simplistic economy consisting of producers and consumers who must
make discrete choices.
2.5 Correspondence between the Turing Machine and the Econ-
omy
In the introduction to this section the stated problem was whether an impulse 1(i) reaches
an agent 0. We can now relate these elements of the economy to the corresponding
elements of the given Thring Machine M.
o+ The agent 0 corresponds to g?, the halting state of M.
o+ The initial shock to the economy is determined as follows. Let i denote the initial
value of the tape of M. Then 1(i), the initial shock to the economy is (a?, bs) as
defined in Equations 1 and 2.
In summary, our construction mimics M as follows. M halts on input i if and only if
an initial shock 1(i) reaches 0 in ?(x).
2.6 The Problem is Recursively Enumerable
In our model economy, the path along which the impulse travels can be partitioned into
agent-to-agent subpaths. Since each subpath is an element of the solution to a simple
problem, the total path can be determined by a rational agent. Thus the problem is in
principle solvable, and a Thring Machine is capable of enumerating all the perturbations
which will ultimately affect a given agent. The problem is thus recursively enumerable.
In the next section we show that the problem is not recursive, i.e., a Turing Machine is
not capable of enumerating all the perturbations that neve? affect a given agent.
2.7 Undecidability Proof
We have shown our system and its relation to the Thring Machine. By simulating each
state as an agent and routing the impulse between the agents, we can simulate any
Thring Machine. Thus we have:
Theorem 1 The following language is undecidable:
t(I, ?, 0?j initial impulse I reaches agent 0 in economy SJ
Recall that the Universal Turing Machine can be used to simulate any Thring Machine
on any input. Let u denote the specification of any Universal Thring Machine and let
10
S(u) denote the economy that mimics u. Let o denote the agent in ?(u) corresponding
to the halting states of u. For any Turing Machine specification x and input i, ?? halts
on input i if and only if the initial shock I((x, ?`)) reaches ot in C(u). Thus there is a
particular finite economy ?(n) with a particular agent c for which we can show:
Theorem 2 The following language is undecidable:
?Ij initial impulse I reaches agent o in economy ?(u)1
We encourage the reader to contrast the statements of Theorems 1 and 2.
3 Applications and Limitations
3.1 Applications
11
In this section we mention a few areas in which the concept of undecidability is applicable.
The areas are trigger problems in macroeconomics, game theory and spectral analysis in
econometrics. For all of these examples, consider the kind of network economy presented
in section 3.
Trigger Problems in a Multi-Sector Economy8
Consider a node of an economy which releases a significant impulse `2 if it receives
an impulse li. If the question of whether impulse 1? ever passes through the node
is undecidable, then no economist or agent with rational expectations will know
whether the significant impulse 12 is ever going to be released. In this framework,
our modelling capability and rational expectations are compromised.
Game Theory --H a dynamic example
Consider a repeated dynamic game whose extensive form looks like the economy
?T Then each node in the tree represents a move by a player. The problem of
whether the game passes through a given node is undecidable.
Spectral Analysis in Time Series Econometrics
In the above economy, the question of whether or not an impulse passes through
a certain node of an economy is undecidable. Thus a time series econometrician
collecting data at that node can never be sure that (s)he has a complete set of
data, because (s)he will never know when to stop collecting data.
The above examples are a small subset of the conceivable range of undecidable prob-
lems.
3.2 Limitations
It is important to recognize the limitations of this result. A number of traditional
problems are decidable. Examples are certain problems involving homogeneous agents,
convergent infinite sequences and finite time horizons. These problems can be solved by
a suitably encoded Turing Machine. To the extent that economists are satisfied with the
realism of such problems, the issue of undecidability is not important. However, should
economists try to model the world as it actually is, in terms of a network of interacting
sectors or agents making discrete choices, the issue of undecidability must certainly play
a role in their concept of knowledge in economies.
8Models which attempt to closely mimic macroeconomic reality, such as Competitive General Equi
librium (CGE) models, are also the types of models which are most susceptible to the problem of
undecidability.
4 Conclusion
12
In this paper we have shown that certain problems in economics are undecidable. This
provides a formal basis for challenging the validity of the rational expectations hypothesis
in the context of such economies. The argument is that there are facts which follow from
and only from an agent's information which the agent cannot compute. Philosophically,
undecidability illuminates a problem for economists: there are fragments of economics
about which it may not be possible to reason.
Appendix 1
13
In section 2 we showed that the execution of any given Thring Machine can be mimicked
by the corresponding economy. In this appendix we illustrate a minor technical flaw in
our construction and show how it can be corrected. We first illustrate the flaw with an
example.
Suppose q, q0 and q1 are states of the given Turing Machine such that ?(q, 1) =
(q1, x, y? for some x and y, and &(q, 0) = (q0, x', ?? for some x' and ?. Then the economy
has three agents ?, ?i and ?o that correspond to the states q, q1 and q0 respectively.
Our construction requires ci to be a producer of a and b, and co to be a producer of c
and d.
Further suppose that q' is another state of the given Turing Machine such that
?(q', 0) = (q1, x, y? for some x and y. Our construction requires ci to be producer
of c and d. In this situation our construction fails. Figure 4 shows the flawed economy.
0			1
a,b or c,d?
D c,d
qi
Figure 4: A construction of the economy showing the technical flaw.
We overcome this problem by converting the Thring Machine
T = (Q,F,I,?,?q0,qa,qr?
into the modified Thring Machine
= (QI, , I, ?, ?, (q0, O\), (q?, 0), (q?, 0))
as follows:
o+ = Q x ?0, 1). In other words, every state q of M is represented by two states
of Al': (q,O) and (q,1).
14
? mimics ? as follows. Let q be any state of M. Suppose that M changes state
from q to q' upon reading i, i.e., ?(q, i) = x, ?? for some x and ?. Then
= 6:'((q,1?,i) =
o+ To correctly address the halting condition, we also add the following transitions:
= 6'((qa,1?,1) = ((qa,O?,1,R?
6'((q?, 1?, 0) = ?`((q?, 1?, 1) = ((q?, 0'), 1, R')
q
qi
Figure 5: A construction of the economy used to overcome the technical flaw.
Figure 5 is a visual representation of the above construction. It is easy to verify that
= L(M) and that our construction works correctly with M'. In summary, given
any arbitrary Thring Machine M, we first modify it into another Thring Machine M' as
described in this appendix and then convert M' into an economy using the techniques
of section 2.
15
Il ?			I ?
I I
0 ? ?+ ?
+
+ ?
0 0
.? l?l? ?A			+
I I I
I I
c? oo
o
__			--H 0000
+
o
0
0 0 0 ?
0
0
o I --HI --HI I --HI ?I
? Al Al Al Al V V V V
o
0
0 : 0			0			0
0 0 0 0
0
0
0
0
a
`4-
Co
a
0
`4-
a
0
a
a
a
Co
Co
Co
Ca
Co
a
Appendix 3
Optimization for the Recursion Theorist9
An Economy
16
An economy consists of a set of people or groups of people, referred to as agents, that
produce, trade and consume goods. The endowment of an agent at any time is the set
of goods produced or acquired by that agent prior to that time and currently within its
possession. For example, the endowment of a farmer today may be 100 tons of rice, the
endowment of an investor may be twenty shares in Imperial Chemical Industries etc.
Each agent in the economy consumes goods to satisfy its needs or to derive pleasure.
By consuming different mixes of goods, an agent derives different amounts of utility. For
example, consuming 1 apple and 1 orange might yield a different utility from consuming
2 apples and 1 banana. The utility of an agent is quantitatively captured by a utility
function. Each agent tries to mawimize its utility function. Note that (1) different agents
may have different utility functions and (2) the utility function of any given agent may
be affected by the past behavior of that agent and by the behavior of other agents.
Utility Maximization
In practice, economists assume that utility functions are concave.'0 This captures the
observation that in most cases, every additional unit of a good consumed gives less
additional pleasure.
In order to maximize their utility function, agents may trade a part of their endow-
ment with each other. For example, consider an economy in which there are two agents
A and 0. A is an apple farmer whose endowment is 10 apples and 0 is an orange farmer
whose endowment is 10 oranges. A's utility function UA is
and 0's utility function U0 is
U?(a,o) = 2a-2' +0-21
Uo(a, o) = 2a-21 + 30-21
If A and 0 do not trade, A's utility will be UA(10, 0) = 2? 6.3. Similarly, 0's
utility will be approximately 9.5. Suppose A and 0 agree to trade 1 apple for 1 orange,
A's utility will be UA(9, 1) = 7 and 0's utility will be U0(9, 1) = 11 both benefit from
the transaction. In fact, A would be even happier if (s)he could trade 2 apples for 2
oranges." In order to determine when A will be happiest, we need to solve the following
constrained optimization problem for a and 0:
?[11] provides a thorough treatment of this subject.
10This convenient assumption has never been proved, and is not always validated by observed behavior.
11To keep things simple in this example, we assume that 1 apple is always traded for exactly 1 orange.
MaxU?(a, o) = 2a21 + o?2'
a + 0			10,
a>O o>O
17
subject to
known as the budget constraint and
known as nonnegativity constraints.
Using the method of Lagrange, we derive
OU?(a,o) _ OU?(a,o)
Oo
known as the			condition.
The function 8a is referred to as the apple farmer's marginal utility of a and
referred to as the apple farmer's marginal utility of 0. In most cases,12 given a
8o
concave utility function f in n goods 91,92,... g?, the maximum utility can be determined
by equating all n marginal utilities of f (i.e., with respect to each of the n goods).
In this paper we consider a finite economy, i.e., one with a finite number of agents.
Each agent has a set of neighbors with whom it can perform transactions. This is indeed
the case in practice, since an agent can only interact with other agents that are "nearby".
In other words, if the physical or temporal distance between two agents is sufficiently
large, they cannot trade with each other.
We assume that time progresses in discrete units. In each time unit, an agent makes
a decision based on its endowment and its utility function, and may participate in a
transaction with one of its neighbors.
We subject this economy to an exogenous shock. An example of an exogenous shock
is an increase in the endowment of an agent. In practice, this may be achieved by reduced
taxation, low-interest loans, an outright grant etc. As economists, we wish to determine
what effect that this action will have on the economy. In particular, we wish to determine
whether an agent A will be affected if an agent B's endowment is increased. In practice,
this ability helps in policy decision making. For example, consider a government that
would like ensure that all its citizens receive at least a subsistence amount of food. One
possible way of achieving this goal would be to provide a subsidy to all farmers in the
economy and hope that some of the benefit in reduced food production "costs" is passed
on to the poor.
Thus the government wants to solve the following problem: if the endowment of the
farming sector is increased, will the poor benefit sufficiently? More generally, we can
study the following abstract problem: if the endowment of an agent A is increased, will
another agent B be affected?
12A common exception is a "corner" solution.
18
We show that in general, this problem is undecidable. Given an arbitrary Thring
Machine T, we show how to construct an economy ?T in which an agent B is affected
by the perturbation if and only if T halts on an empty tape. Technically, this result is
similar to showing that a ray tracing problem is undecidable [9j.
Appendix 4
Introducing Recursion Theory to Economists
Introduction
19
In this section, we go over some key concepts in recursion theory. An understanding of
these concepts is necessary for an understanding of the result of this paper. First, we
define some terms necessary for an understanding of recursion theory. Then, as a step
toward understanding the Thring Machine, we present a weaker and simpler computa-
tional device called the Deterministic Finite Automaton. The concept of a Deterministic
Finite Automaton also serves to emphasize the power of the Turing Machine. Finally,
we introduce the Turing Machine and state some fundamental theorems that we will use
to derive our result.
This section summarizes the exposition on Deterministic Finite Automata and Turing
Machines in [5, 6]: we make extensive use of the language and organization of [5, 6].
Basic Definitions
In this section we introduce the economist to R?ecursion Theory. We provide the defini-
tions of terms used in sections 4 and 4. A more detailed treatment of these concepts is
available in [5].
Definition 1 An alphabet is a finite set of symboTh.
For example consider the set of equations in elementary calculus. The alphabet for this
set, denoted ??, contains the following symbols:
1. The digits, 0, 1,... 9.
2. The decimal point, ".".
3. A finite set of connectives and operators, 4?, --H, X, +, , =, (, ), 0, d, f, lim, ?, sin,
cos, etc.
4. A finite set of variables x, y, etc.
5. A finite set of constants ir, e, etc.
Clearly, this set of symbols is finite. We use the symbol ? to denote an arbitrary alphabet.
Definition 2 A string over an alphabet ? is a finite list of symbols belonging to the set
For example,
dy + dx = x? + eA--Hx)
is a string over ?,, the alphabet for the set of equations in elementary calculus.
(20)
20
Definition 3 The concatenation of two strings x and y is denoted by xy.
Definition 4 ?? denotes the set of all strings over the alphabet ?.
Definition 5 The length of a string , denoted Ix is the number of symbols in x.
For example, the length of the string in Equation 20 is 16.
Clearly not all strings over ?? belong to the set of true equations in elementary
calculus. For example consider the following strings:
1. "x(" is not well-formed. It violates the rule that the number of open parentheses
ill an equation should equal the number of closed parentheses in an equation.
2. "1 = 2" while well-formed, is false.
Informally, the concept of a language is used to differentiate between "acceptable" and
"unacceptable" elements of ??. Thus the two unacceptable strings above do not belong
to the language of equations in elementary calculus.
Definition 6 A language over ? is a subset of ?*.
A decision problem is specified by a set A of all possible inputs and B c A of
"acceptable" instances. For example the following is a decision problem: is a specific
sector in an economy affected by a trade shock. The set of inputs is the set of all possible
trade shocks to the economy. The subset of "acceptable" instances is the set of all trade
shocks which affect the specified sector.
Definition 7 A decision problem over ? is a function from ?? that returns a "yes" or
no" answer.
Systems, States and Transitions
Intuitively, a system is a set of agents and relations connecting the agents. The state of
a system is a complete, instantaneous description of the system. In particular, the state
of a system provides all relevant information about each agent in the system and the
relations connecting them at the given instant.
Every system, is governed by a set of laws called the state transition function of that
system. The state transition function determines how the state of the system evolves
over time. For simplicity, we assume that the state transitions occur instantaneously.
As all example, we consider the following economy with n agents that trade in a
common market. Each agent a has a utility function Ua which it tries to maximize.
The endowment of a at time t is denoted by Ea(t). At the end of time period t, agent
a selects Xa units of one commodity Ca from its endowment and exchanges it for other
commodities from other agents. In exchange for Ca, agent a acquires a basket of goods,
ba.
The state of this system at time t is an n-tuple (Ea1 (t), Ea2 (t), ..., Fa (t)?. The state
transition function of this system is the solution of the utility maximization problem for
each agent. Thus if we are given each agent's utility function and the current state of
this system, then we can determine how the system will evolve over time.
21
The Deterministic Finite Automaton
In this section we briefly describe a simple class of computing devices known as Deter-
ministic Finite Automata. We use some of the notation of [5] and [6].
Definition 8 A Deterministic Finite Automaton is a 5-tuple
M =
where:
1. Q is the finite set of states of ?M.
2. ? is the finite alphabet of M.
3.			?: Q x ?			Q is the state transition function of A4.
4. q0 E Q is the initial state of A4.
5. A c Q is the set of accepting states of A4.
The Deterministic Finite Automaton M works as follows. It starts in its initial state,
q0. At each time period, it reads one symbol from its input and changes its state based
on its state transition function. We say that M accepts if at the end of its input it is in
an accepting state, i.e., a state in A. Otherwise, we say that Al rejects. Thus the set of
inputs on which Al accepts defines a language on ?.
Definition 9 If on input x, Al accepts, we say Al accepts x.
Definition 10 The language of a Deterministic Finite Automaton Al, denoted L(Al),
is [x ? ?*jAl accepts xi.
Definition 11 A set S C ?? is called regular if and only if there is a Deterministic
Finite Automaton Al such that L(Al) =
An Example
As an example consider Al, a Deterministic Finite Automaton that accepts [x E [a, b?*jx
does not contain the substring aba?. The set of states of Al is [q0, q1, q?, q3?. The
alphabet of Al is [a, bi. The initial state of Al is q0. The set of accepting states of Al is
[q0, q1, q2?. The state transition function of Al is given in figure 6. To illustrate how Al
functions, we show all the state transitions of Al when its input is aaabba. See figure 7.
When Al reads the last symbol of the input (i.e., a), Al enters the state q1. Al accepts
aaabba because q1 is an accepting state of Al.
As mentioned earlier, Deterministic Finite Automata have limited computing power.
This is illustrated by a theorem known as the pumping lemma. This theorem states that
there is no Deterministic Finite Automaton that accepts certain sets of strings that are
very simple to specify. We next explain the pumping lemma briefly and show that the
set [xlx = aThbfl for some nJ is not regular.
22
State			Input
a?b
q0			q1			q0
qi			q1			q2
q2			q3			q0
q3			q3			q3
Figure 6: State transition function for Deterministic Finite Automaton M
State Input Symbol Next State
q0			a			q1
q1			a			q1
a			q1
q1			b			q2
b			q0
q0			a			q1
Figure 7: Deterministic Finite Automaton M responding to aaabba
The Pumping Lemma
The intuition for the pumping lemma is the following. Consider a Deterministic Finite
Automaton A/I such that L(M) is infinite. Since A/I consists of a finite set of states, there
exists a sufficiently long string x C L(A/I) that will force the automaton to repeat at least
one state. Thus x is of the form abc where q, the state of A/I after scanning a, is the state
of A/I after scanning ab. Since A/I cannot tell the difference between two visitations of
the same state, the state of A/I after scanning abb must be q. Thus the substring between
the two visitations of the repeated state can be inserted into the string before the first
occurrence of the state and the newly constructed string will still be accepted.
This observation can be used to show that the set S = x is of the form a?b?1'3
is not regular, i.e., there is no Deterministic Finite Automaton that accepts precisely
this set. This is proven by contradiction: suppose there exists a Deterministic Finite
Automaton A/I such that L(A/I) = S. Take a string of the form an%brn such that m is
greater than the number of states in A/I. There must exist x and ?, x ? y ? m such that
the state of A/I after it scans aX, is the same as the state of A/I after it scans a?. We
leave it to the reader to verify that A/I must accept arn+3I?Xbrn, a string that is clearly
not in 5.
13a? denotes a string of n consecutive a's. a* denotes a string of any number of consecutive a's.
Thring Machines, Computability and Undecidability
Introduction
23
The Thring Machine was invented in 1936 by Alan Thring [14]. It was conceived at a time
when mathematicians were trying to define the concept of computability of functions.
Examples of such efforts are Church's A-calculus [2], Post's Post systems [8], Godel's
?-recursive functions [3], etc. Later mathematicians showed that all of these systems are
computationally equivalent, leading Church to declare that each system captured the
intuitive notion of "computable". This declaration is known as Church's Thesis. Church's
Thesis is widely accepted by Recursion Theorists, and there is no known computable
function that cannot be programmed by a Thring Machine. Recursion Theorists use
the Thring Machine to define computability. Informally, a language L is said to be
computable if and only if there is a Thring Machine that accepts L.
An Informal Description of Thring Machines
In this section, we provide an informal description of Thring Machines. Essentially, a
Turing Machine is a Deterministic Finite Automaton (see page 21) augmented with a
one-way infinite 1 - dimensional tape on which it may read and write values (see figure
8). The tape of the Turing Machine is divided into an infinite number of tape cells, each
of which contains a symbol in F, an alphabet that contains ? and a blank symbol I ?
The Thring Machine accesses the tape via a single tape head. The Thring Machine may
read, write or overwrite a symbol on the tape cell beneath the tape head. A state
transition for a Turing Machine consists of a change in the state of the Deterministic
Finite Automaton associated with the Thring Machine, a command to write a symbol
in the cell below the tape head, and a command to move the tape head one cell to the
left or right. The input to the Turing Machine is a finite string from ?? and is initially
written on the tape in contiguous tape cells (see figure 8). The infinitely many cells on
either side of the input are assigned the blank symbol I.
The Turing Machine starts in its initial state q0 with its head scanning the leftmost
symbol of the input. In each step the Thring Machine reads the symbol on the tape cell
beneath its tape head, and depending on that symbol and the current state of the Thring
Machine, it writes a new symbol on that tape cell, moves its tape head either one cell
left or right and enters some new state. The action taken by the Thring Machine in each
situation is determined by its state transition function ?. It accepts its input by entering
a special accept state q? and rejects its input by entering a special reject state q?. The
Turing Machine is said to halt on input x if it either accepts x or rejects x. Note that it
may do neither, by running infinitely on input x without ever accepting or rejecting.
A Formal Description of Turing Machines
Definition 12 A Turing Machine [5] is a 8-tuple
M = (Q,F,I,?,?q0,qa,qr?
24
Tape
a			b			a			b			a
Read\Write Head
Finite
Control
Figure 8: Schematic diagram of a Thring Machine with ? = fa, bJ.
where:
1. Q is the finite set of states of M.
2. F is the set of allowable tape symbols of A4.
3. I is the blank symbol of M.
4. ? is the set of input symbols of M. Note that ? C F --H ?IJ.14
5. ?: Q x F H Q x F x fL, R) is the state transition function of M.
6. q0 Ei Q is the initial state of M.
7. q? E Q is the accepting state of M.
8. q? E Q is the rejecting state of M.
Figure 8 is a schematic diagram of a Thring Machine. Q and q0 for a Thring Machine are
the same as Q and qo for the Deterministic Finite Automaton of the Thring Machine.
The input to the Thring Machine is in ?? for some alphabet ?. Each tape cell contains
one symbol from a set F, a superset of ? that contains I, the special blank symbol. The
state transition function of the Turing Machine now returns a triple rather than just the
14In some cases, ? is a proper subset of F --H ?I?. In our example in figure 9, P = ? U ?I, ??.
25
state of the Deterministic Finite Automaton of the Turing Machine. As before, &(q, a)
describes the actions of the Turing Machine when it is in state q and the tape cell below
its tape head contains the value a. If 6(q, a) = (q', a', d?, then the operation of the Turing
Machine is as follows.
1. The Turing Machine writes a' on the tape cell below its head,
2. The Turing Machine moves the tape head in direction d (either left, denoted L or
right, denoted R).
3. The Turing Machine enters state q'
In addition, once the machine enters the accept q? or the reject state q?, its execution
halts. If it halts in q?, we say that it accepts. If it halts in q?, we say that it rejects.
Definition 13 If on input x, M accepts, we say M accepts x.
Definition 14 If on input x, M rejects, we say M rejects x.
Definition 15 The language of a Turing Machine M, denoted L(M), is fx E ?*jM
accepts x?.
An Example
As an example, consider M, a Turing Machine that accepts the set ?a?b?c?in > o?. ?,
the set of input symbols of M is ?a, b, ci. The blank symbol of M is I. Apart from 1
and the symbols in ?, F contains the symbol ? called the erased symbol. Thus the set
of allowable tape symbols of M is fa, b, c, I, ??.
Informally, M repeats the following procedure as often as possible:
1. If there does not exist at least one each of a, b and c, then M stops and decides.
2. If there exists at least one each of a, b and c, the head goes from left to right over
the input, erasing the first a, the first b and the first c.
3. The head goes back to the beginning of the input.
At the end, if there is any symbol in ?a, b, ci left, then clearly the string is not of the
form aflbflcU. Also note that care is taken to avoid strings of the form abaccb, i.e., strings
with an equal number of a's, b's and c's but not of the form a* b*c*. The state transition
function of M is given in figure 9.
Note that the above set is not regular. That is, we can use the pumping lemma to show
that there is no Deterministic Finite Automaton that will accept this set. The reader is
encouraged to verify that M actually accepts a?b?c? by trying out a few examples.
26
iState			a			T			b			g			c T			T			7
q0			(q1, ?, R?			(q6, b, R?			(q6, c, R)			(q5, ?, R?			(q0, ?, R?
q1			(q1, a, R?			(q2, ?, R)			(q6, c, R?			(g6, ?, R?			(q1, ?, R?
q2			(q6, a, R?			(q?, b, R?			(q3, ?, R?			(q6, I, R?			(q2, ?, R?
q3			(q6, a, R?			(q6, b, R?			(q3, c, R?			(q4, m, L?			(q3, ?, R?
q4			(q4, a, L?			(q?, b, L?			(q4, c, L?			(q0, I, R?			(q4, ?, L?
q5 This is the accept			state
q6 This is the reject			state
Figure 9: State transition function for Thring Machine M
Decision Problems and Recursive Functions
In the previous sections, we saw Thring Machines that check whether a given string is in
a language. A Thring Machine can also be used to compute a function as follows. The
tape of the Turing Machine is initialized to contain the parameters of the function; the
tape head initially scans the leftmost symbol of the input. The output of the function
is taken to be the value written on the tape when the Thring Machine goes into its
accepting state.
Definition 16 A function f is recursive if and only if there is a Turnng Machine M
such that on eve?y input x in the domain off, M eventually wrntes f(x) on its tape and
enters its accepting state.
Given a Thring Machine Al that computes a function f and a Thring Machine Al' that
solves a decision problem, we can "concatenate" Al and Al' as follows. We can construct
a Thring Machine Al+ that first runs Al. When Al enters its accepting state, Al+ runs
Al'. Thus Al+ accepts txlf(x) ? L(Al')1. More precisely, given
and
Al = (Q,F,,?,?q0,qa,qr?
Al' = (Qt,F,1,?,?t,q0t,q?t,q?t?
Assuming for simplicity that Q and Q' are disjoint, we can construct
Al+= (Q+,F,I,?,?,q0+,q?+,q?+?
where
1. Q+ = Q uQ' --H tqa,qr)
6'(q, a)
(q0,, a', d?
if q C Q'
if ?(q, a) = (q',a',d? and q' # q?
if 6(q, a) = (q',a',d? and q' =
2. ?+(?a)=
3. q0+ = q0
4. q?+ = q?' and q?+ =
Me M' denotes the concatenation of M and M'
27
Decidability and Undecidability
Definition 17 A set S c ?? is called recursively enumerable (abbreviated r.e.) if and
only if there is a Turing Machine M such that L(M) = 5.
Definition 18 A set 5 C ?? is called recursive if both 5 and S are recursively enumer-
able 15
A property is decidable if there exists a Turing Machine that accepts all strings with that
property and rejects all strings without that property.
Definition 19 A property is decidable if and only if the set of all elements having that
property is recursive.
A property is undecidable if there is no Thring Machine that can determine whether an
arbitrary given string has that property.
Certain properties are undecidable. For example, there is no mechanical procedure
that can be used to tell whether or not a string causes a Turing Machine to halt. In par-
ticular, there is no finite set of axioms and inference rules that can be used to determine
which strings and Turing Machines have this property and which do not.
Note that the terms "recursive" and "recursively enumerable" apply to sets. The
terms "decidable" and "undecidable" apply to properties of elements of sets. By a
slight abuse of terminology, we say that a language is undecidable if there is no Turing
Machine that can determine whether an arbitrary given string belongs to that language.
[4] contains a good intuitive description of the above concepts.
Universal Turing Machines
As we saw earlier, a Turing Machine is specified by an 8-tuple (Q, F, 1, ?, 6, g0, q?, q??.
It is easy to encode this specification so that the only symbols that occur in it are "0"
and "1". Thus the specification of the Turing Machine can be given as a string over the
alphabet [0, 1?.
With this encoding technique in mind, we can view the set of specifications of all
Turing Machines as a language over [0, 11. That is, each specification of a Thring
Machine corresponds to a tinique binary number. The Thring Machine specification
corresponding to the number x is denoted ?.
Note that ?? is not defined for all x since some numbers do not correspond to a Turing
Machine specification. This is notationally inconvenient. Thus if x does not correspond
15S is used to denote the complement of the set S.
28
to a Thring Machine specification, ? is defined (by default) to be the Thring Machine
that accepts ?.
A Universal Turing Machine is a Thring Machine whose language is the set of pairs of
Thring Machines M and strings x such that x ? L(M). Intuitively, the Universal Thring
Machine is capable of simulating every Thring Machine. More precisely, the alphabet of
a Universal Turing Machine is [0, lJ. The Universal Thring Machine accepts the string
(x, y? if and only if ?? accepts y. To see the construction of a Universal Thring Machine,
the reader is referred to [5].
Since the Universal Turing Machine is capable of simulating every Turing Machine,
it is capable of simulating itself. The property by which a Thring Machine can simulate
itself is called self reference. This allows us to use a proof technique called diagonalization
to prove that some problems are undecidable.
Diagonalization
We first illustrate the method of diagonalization with what is perhaps its simplest ex-
ample.
Theorem 3 There is an English sentence that is neither true nor false.
PROOF: Consider the sentence:
"This sentence is false."
Let us assume for contradiction that this sentence is either true or false. There are two
cases to consider:
1. The sentence is true. In this case, the sentence is false--Ha contradiction.
2. The sentence is false. In this case, it is false that the sentence is false, i.e., the
sentence is true a contradiction.
Note that the above sentence refers to itself.
The technique of diagonalization was first used by Cantor [4] at the end of the last
century to show that there does not exist a one-to-one correspondence between the
natural numbers N and 2N, the power set of N, which is defined as follows.
Definition 20 The power set of a set A, denoted 2A, is the set of all the subsets of A.
Cantor's argument is as follows: Suppose for a contradiction that there is a one-to-one
and onto function
f: N H 2N
29
123456789
f(1)			1			0			0			1			0			0			1			0			0
f(2)			1			0			0			1			1			1			0			0			1
f(3)			0			0			0			0			1			1			0			0			1
f(4)			0			0			0			0			1			1			1			0			0
f(5)			1			1			1			1			1			1			1			0			0
f(6)			0			1			1			1			1			0			1			0			1
f(7)			0			1			0			1			0			1			0			1			0
f(8)			1			0			1			0			1			0			1			0			1
f(9)			1			0			1			0			0			1			1			0			1
Figure 10: An example of M showing the relationship between N and 2N,
We can build the following infinite two-dimensional matrix, M:
Mt,j			o1 i??? ? f(i)
? f(i)
In other words, each row of M represents a different function. The 1st row denotes f(1),
the second row denotes f(2), and so on. For example, figure 10 represents one possible
matrix M. f(1) =[1,4,7,.. .?, f(2) = [1,4,5,6,9,...), and soon. By our assumption
that f is onto, every subset of N appears as a row of the matrix.
Now we will use diagonalization to derive a contradiction. Construct the complement
of the infinite string down the main diagonal of the matrix by switching the 1's in it to
0's and the 0's to 1's. In other words, construct S c N as follows:
The set S for the matrix M in figure 10
onto and S c N, there must be a number z
consider:
i ? s if and only if Mj,j = 0 (i.e., i ?
is [2, 3, 4,6, 7, 8,...). Since f is one-to-one
such that f(i) = S. There are two cases to
1. i e f(i). In this case, Mj,j = 1. Hence z ? S. Since f(i) = S, we have a
contradiction.
2. i ? f(i). In this case, Mj,? = 0. Hence ? ? 5. Since f(i) = 5, we have a
contradiction.
Note that this argument can applied to a wide variety of sets other than N. A similar
argument was also used in "Russell's paradox" [4].
Undecidability of the Halting Problem
30
Cantor's simple cardinality argument allows us to prove the existence of undecidable
decision problems. Informally, the proof is as follows: there are uncountably many
languages over [0,11* but only countably many Turing Machines. Thus there must exist
many languages that are not accepted by any Thring Machine.
In this section, we prove the undecidability of one such problem, known as the Halting
Problem and denoted H [5]. Informally, H is stated as follows: given a Turing Machine
specification i and a string x, does ? halt on x? More formally H is the language defined
as follows:
H = [(i,x?I?i(x) haltsl
Theorem 4 The halting problem is undecidable.
PROOF: Suppose for a contradiction that there is a Thring Machine specification h such
that ?h accepts (i, x? if ? halts on x and ?h rejects (i, x? otherwise. ?h can be represented
as the following infinite two-dimensional matrix:
accepts if ? halts on j
?h(i, j)			?jects if ? does not halt on j
Now we will use diagonalization to derive a contradiction. Consider the following
function dbl defined as follows:
dbl(x) =
dbl is a recursive function. Let h' = (Q, F, I, ?, ?, q0, q?, q?? represent the specification
of the Thring Machine dbl. ?h Then ?h' behaves as follows:
accepts if ?? halts on i
rejects if ? does not halt on i
Note that ?h' corresponds to the diagonal of the two-dimensional matrix representing
?h ?7e can construct a Thring Machine specification h+ based on the specification h' as
follows. Add a new state q? and replace all transitions to q? with transitions to q?. Thus
?h' and ?h+ behave identically except when ?h' enters ?a, ?h+ enters q?. More formally,
we construct h+ = (Q+, F, ffi, ?, ?+, q0, q?, q?\) as follows:
1. Q+ = Quq?, where q? is anew state not in Q
(qI,at,?),ql # q? and q # q?
2.			?+(?a) =			(qa,a',d? and q # q?
(q',a',d?			if 6(q, a) =
(q?,a',d?			if ?(q, a) =
(q?,a,R?			ifq=q?
It is easy to verify the following facts:
31
o+ h+ is the specification of a Thring Machine that does not accept any strings. In
other words, L(?h+) =
o+ If bh' rejects string x, then bh+ also rejects x.
o+ If bh' accepts string x, then bh+ does not halt on x. In fact bh+ enters state q? and
never leaves that state.
Intuitively ?h+ halts on x if and only if ? does not halt on x. Let us now consider what
happens when we run ?h+ with h+ as input. There are two cases to consider:
1. ?h+ halts on h+. In this case, ?h+ does not halt on h+ a contradiction.
2. ?h+ does not halt on h+. In this case, ?h+ halts on h+--Ha contradiction.
We conclude from the above argument that H is not recursive.
In other words, there does not exist a Thring Machine that can determine in a finite
amount of time whether any given Thring Machine M halts on an arbitrary given input
Reducibility: A Tool to Prove Undecidability
In this section we introduce reducibility, a relation that allows us to compare degrees
of difficulty of solving problems. Using reducibility, it is possible to show that many
problems are at least as hard to solve as the Halting Problem. Since we know that the
Halting Problem is undecidable, it follows that all these problems are also undecidable.
We now define reducibility.
Definition 21 Let L1 and L2 be any two languages over some finite alphabet ?. We
say that L1 is Turing reducible to L2, written L1 <T L2 if and only if there is a recursive
function F : ?? that maps elements of L1 to elements of L2 and elements of L1 to
elements of L2
In other words, there is a Thring Machine M with the following properties. If the input
to M is an element of L1, M writes an element of L2 on its tape before halting. If the
input to M is an element of L1, M writes an element of L2 on its tape before halting.
Note that several types of reducibility have been studied in the literature. For this paper,
however, we will only be concerned with Turing reducibility. For the rest of this paper,
we use the term "reducibility" to denote Turing reducibility. We can prove the following
theorem about the halting problem H:
Theorem 5 For any language , if H ?T , then  is not recursive.
PROOF: Suppose for a contradiction that  is recursive; there must be a Thring Machine
M that halts on every input, such that L(M) = ?. Further, since H is reducible to ,
there is a Turing Machine M' with the following properties. If the input to M' is an
32
element of H, M' eventually writes an element of  on its tape and halts. If the input
to M' is an element of H, ?M' eventually writes an element of  on its tape and halts.
Consider the Thring Machine M+ = o+ M. We will show that M+ halts on every
input and L(M+) = H. Since the halting problem is undecidable, this immediately gives
us a contradiction. There are two cases to consider:
1.
2.
The input to M+ is an element of H. In this case, M+ works as follows. First M'
runs until completion. Since the input to M' is an element of H, ?4' writes x, an
element of fl on its tape and halts. Next M runs until completion. Since x, the
input to M, is an element of fl and L(M) = ?, M accepts. Thus A4+ accepts.
The input to M+ is an element of H. In this case, M+ works as follows. First
runs until completion. Since the input to A4' is an element of H, M' writes
x, an element of  on its tape and halts. Next M runs until completion. Since x,
the input to M, is an element of  and M halts on every input, M rejects. Thus
A4+ rejects.
We have shown that M' halts on every input and that L(M') = H, giving the desired
contradiction.
In section 2 we will define a problem ? in a finite economy and show that the Halting
Problem is reducible to?. F'rom Theorem 5, it follows that ? is undecidable.
On the Robustness of the Turing Machine model
Even though the Thring Machine model appears to be simple, it is very powerful. In
this subsection we mention a few of the enhancements of the Thring Machine model that
do not increase its power. We hope that this gives the reader some intuition for the
robustness of the Thring Machine model:
Two-way infinite tapes: The Thring Machine model presented in this paper assumes
that the tape is infinite in only one direction. With this enhancement, we allow
the tape to be infinite in both directions.
Multiple tapes: With this enhancement, the Thring Machine is allowed to have sev-
eral tapes, each of which has its own tape head. Each tape can be controlled
independently.
Multiple tape heads: With this enhancement, the Thring Machine is allowed to have
many tape heads on each tape. This allows the Thring Machine to read different
cells of the tape simultaneously. Each tape head can be controlled independently.
Multi-dimensional tapes: The Thring Machine model presented in this paper assumes
that the tape is i-dimensional. With this enhancement, we allow the tape to be
multi-dimensional and infinite in all dimensions.
33
By introducing non-determinism: The Thring Machine model presented in this pa-
per is completely deterministic, i.e., based on the current state of a Thring Machine
and its state transition function, it is possible to determine the next state of the
Turing Machine. There are several ways to bypass this restriction. One obvious
way is to allow the Thring Machine to toss a coin at each step and make its tran-
sition based on (1) its current state, (2) the value in the tape cell below its tape
head and (3) the result of the coin toss. Other ways of eliminating determinism
such as non-determinism and alternation have also been considered. For a detailed
description, the reader is referred to [5].
None of the enhancements mentioned above increase the power of the Thring Machine
model. Furthermore, even if we apply a combination of these enhancements, the com-
puting power of the Thring Machine model remains unchanged. More precisely, given
any Thring Machine M that uses some or all of the enhancements mentioned above,
there exists a Thring Machine A4' without any enhancements such that (a) M' accepts
if and only if M accepts, (b) M' rejects if and only if M rejects and (c) M' neither
accepts nor rejects if and only if M neither accepts nor rejects. The proof of this fact is
beyond the scope of this paper: for this, the reader is referred to [5].
Acknowledgments
34
We would like to thank Karl Shell for his valuable advice and comments on the result.
We would like to thank Mike Reiter, Sonal Deshpande and Nish Shah for their useful
comments on previous drafts of this paper and James Grosjean for his thorough read-
ing and revealing comments. Siddharth thanks John Curran, Mark Fisher and James
Grosjean for expanding the bounds of his rationality.
35
References
[1] Ken Binmore. Debayesing game theory, June 1991. Lecture for the International
Conference on Game Theory, Florence,
[2] A. Church. An unsolvable problem of elementary number theory. American Journal
of Mathematics, 58:345--H363, 1936.
[3] Kurt G5del. On Formally Undecidable Propositions. Basic Books, New York, NY,
1962.
[4] Douglas R. Hofstadter. Gjdel, Escher, Bach: An Eternal Golden Braid. Random
House, Inc., New York, NY, 1989.
[5] J. Hopcroft and J. Uliman. Introduction to Automata Theory, Languages, and
Computation. Addison-Wesley, Reading, 1979.
[6] Dexter Kozen. Lecture notes for introduction to theory of computation. Lecture
notes for Cornell University course CS381, 1992.
[7] Robert E. Lucas Jr. On the mechanics of economic development. Journal of Mon-
etary Economics, 22,1988.
[8] E. Post. Finite combinatory processes --H formulation, I. Journal of Symbolic Logic,
1, 1936.
[9]
John H. Reif, J.D. Tygar, and Akitoshi Yoshida. The computability and complexity
of optical beam tracing. In Proceedings of the Thirty-first Symposium on Founda-
tions of Computer Science, pages 106--H114, June 1990.
[10] Thomas J. Sargent. Dynamic Macroeconomic Theory. Harvard University Press,
Cambridge MA, 1987.
[11] Eugene Silberberg. The structure of economics: a mathematical analysis. McGraw-
Hill, 1978.
[12] Stephen E. Spear. Learning rational expectations under computability constraints.
Econometrica, 57(4):889--H910, 1989.
[13]
Robert Townsend. Models of money with spatially separated agents. In J.H. Kareken
and Neil Wallace, editors, Models of Monetary Economies, pages 265--H304. Federal
Reserve Bank of Minneapolis, Minneapolis, 1980.
[14] A.M. Thring. On computable numbers with an application to the Entscheidungs-
problem. Proceedings of the London Math. Society, 2,1936.
[15] Neil Wallace. Models of Overlapping Generations: An Exposition. University of
Minnesota, Minneapolis MN, 1978.
36
Henry Y. Wan (Jr.). The new classical economics--Ha game-theoretic critique. In
George R Feiwel, editor, Issues in contemporary macroeconomics and distribution,
page 237. State University of New York Press, Albany, 1985.
[16]
