Economic methodology and computability implications for the evaluation of econometric forec

Page 1

Economic Methodology and Computability:

Implications for The Evaluation of Econometric Forecasts

Scott Moss and Bruce Edmonds1

1Introduction

The purpose of this paper is to bring standard propositions of economics together withcomputability theory in order to assess the use of econometric forecasting in policy analy-sis. Our criterion for the applicability of econometric forecasting will be in terms of therelative accuracies of alternative forecasts as a result of improved model specification,estimation and/or data collection and processing techniques. We will justify this criterionby demonstrating that standard economic methodology going back to Friedman (1953)implies that elementary welfare considerations impose a duty on forecasters to identify theconditions in which their forecasts are the best available.

This approach gives our arguments particular importance when forecasts are used forpolicy analysis by rational decision-makers and their advisors. It also removes from usany requirement to specify correctly what is in the heads of econometricians. Nonetheless,we note that econometricians often write and speak as if they view econometric forecast-ing as a progressive science in which the reasons for specific forecasting failures are rec-ognized, understood and corrected. Consequently, revised models will be more accurate inthe sense of making correct forecasts should the circumstances of the last forecasting fail-ure recur. The arguments of this paper apply equally to the possibility that econometricforecasting can be a progressive science in this sense.

We formulate the question of whether it is possible for forecasters to execute their dutyto choose the best available model or for econometric forecasting to be a progressive sci-ence so that it can be answered by an appeal to computability theory. We find that in someconditions individual forecasting procedures can be compared for systematic differencesin accuracy. However, there are no general procedures which can be used to makea prioricomparisons of forecasting model goodness.

1This paper follows on from previous work by Moss, Michael Artis and Paul Ormerod

funded by the ESRC under contract R000232821. The authors wish to express their grati-tude to Michael Artis of the University of Manchester and European University Institutefor extended discussions about previous draughts of this paper. He does not bear anyresponsibility and does not necessarily agree with our arguments.

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

2The Methodological Issues2

Page 2

Our concern with forecasting in particular together with the importance of forecastingin the formulation of economic and business policies leads us naturally to associate the useof forecasting models and methods with policy analysis. For the present, we simplyassume that econometric models should be assessed according to the accuracy of theirforecasts. We also recognize that many econometric modellers would not accept that fore-casting accuracy is an appropriate test of their models. For this reason, we return to theissue in section 4.

In line with the foregoing remarks, we will take it for granted that a forecastingmodel should be used for policy prescription only when that application maximizes thepolicy analyst's subjective expectation of policy benefit. In effect, a standard cost-benefitapproach is applied to methodological issues.

Define a policy as a set of individual actsP. We suppose the set of acts to be supportedby a forecasting model whenever all of the conditions in which that model is the bestavailable model are satisfied. This will mean that the model is specified in some appropri-ate way, that the estimation techniques yield the best possible estimates of the “true”parameters of the model, that the observed data either conform to the definitions of thevariables of the model or the model has been specified to take account of the differencesbetween the true and the observed data.

Suppose that there is some set of conditions in which the model specification and esti-mation, the data and the computational procedures are all appropriate to the determinationof some optimal set of policy decisions. That is, there is some forecasting model which,when applied to the current data set implies some policy.

A particular policy is implied by a forecasting model whenever that model is the bestavailable and, at least, is no worse than any previous or alternative current forecastingmodel. Let us suppose that there is some set of conditionsCwhich gives us confidencethat the conditions of application of a forecasting model are satisfied (and, therefore, wehave confidence in the policies supported by that model). Let there ben such conditions.Each condition is tagged with the variableCi∈{true,false}. Thus,C implies thatCi=true(i=1...n).

2The arguments of this section closely follows the argument in Moss (1993).

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 3

LetB be the image of the mapping[PC→ℜ], the value of the benefits expectedfrom the set of policy actionsP.

The “observation tag” for theith condition isφi∈{true,false} which takes the valuetrue if it is intended to observe theith condition andfalse otherwise. The intention of theforecaster to observe conditions of application is captured by the setΦ={φi(i=1…n)}∩true. In addition, we denote byC(Φ) the cost of observing allof the conditionsφi∈Φ.

To complete our notation we require some means of representing degrees of priorbelief in the satisfaction of the conditions of application which it is intended to observe.The standard representation is in terms of subjective probabilities. For this reason, weadopt the mappingΨ(Φ)→[0,1] which we interpret as the subjective probability thatall conditions of application which it is intended to observe will be satisfied.

By hypothesis, if all of the conditions of application of the theory are true, then theacts inP will imply some expected benefit,E(BC). Otherwise some different benefit,E(B¬C), will result. Thus, the prior expected benefit ofP when the set of conditions tobe observed is empty is(1)

E(BΦ=∅)=E(BC)⋅E(C)+E(B¬C)⋅(1–E(¬C))

More generally, the expected benefit given any arbitrary set of conditions to beobserved will be(2)

E(BΦ)=Ψ(Φ)⋅{E(CΨ(Φ))⋅E(BC)

+[1–E(CΨ(Φ))]⋅E(B¬C)–c(Φ)}–[(1–Ψ(Φ))⋅c(Φ)]

where c(Φ) is the cost of observing the conditions of application inΦ. Expanding and sim-plifying equation (2), we get(3)

E(BΦ)=E(CΨ(Φ))⋅Ψ(Φ)⋅E(BC)

+[1–E(CΨ(Φ))]⋅E(B¬C)

–c(Φ)

SinceE(CΨ(Φ))⋅Ψ(Φ)=E(Ψ(Φ)C)⋅E(C) and, from the definition ofC,E(Ψ(Φ)C)=1, equation (3) can be written(4)

E(BΦ)=E(BC)⋅E(C)+(1–E(C))⋅E(B¬C)

–(1–Ψ(Φ))⋅E(B¬C)–c(Φ)

Substituting into equation (4) from equation (1), we have

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

(5)

E(BΦ)=E(BΦ=0)–(1–Ψ(Φ))⋅E(B¬C)+c(Φ)

Page 4

For the regime in which no conditions of application are observed to entail rationality,it must be the case that the negative term on the right side of equation (5) is non-negative.That is, to adopt a policy based on some forecasting model without a prior assessment ofthe extent to which the conditions of application of that model are satisfied is efficient ifand only if(6)

(1–Ψ(Φ))⋅E(B¬C)+c(Φ)>0

for every possible setΦ - i.e. for every possible combination of conditions of applicationof the model.

For example, presuming that there is some cost to observing conditions of application,equation (6) will always be satisfied if (1-Ψ(Φ))=0. This would be the case if the policyanalyst were convinced that all of the conditions of application of the forecasting modelwere always satisfied. As a result, any subset of those conditions will also always be satis-fied.

Another forecaster might believe that the policies implied by the model and forecastyield substantial and positive benefits even when the conditions of application are vio-lated. Formally, E(B|¬C) is so high that allowing for the probability of ¬C, the benefitwhen conditions of application are known not to be fulfilled swamp the cost of observa-tion. Presumably, some theory supports that belief.

The more general possibility is that, even if conditions of application might be violatedand, if they are, negative benefits might result from the implied policies, the cost ofobserving the conditions of application could in principle be so great that they exceed theexpected opportunity costs associated with the inapplicability of the forecast. This possi-bility seems reasonable when observation requires detailed and expensive investigationswhich themselves yield no collateral benefits. But is it never sufficiently cheap and errornever sufficiently costly and is the world never sufficiently risky as to make it worthwhilea priori to investigate the validity of anyconditions of application of any forecastingmodel? If it is possible that equation (6) will not be satisfied in non-trivial cases, then the-conditions of application of forecasting models become a serious and important issue..3

3Compare this position with that in Friedman’s (1953) classic essay on methodology

where conditions of application are never the descriptive accuracy of the theory though,implicitly, different models would apply to different problems. The particular model to beused for a particular problem “will doubtless be recognized before the event.” (p. 36)

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

3Arbitrary Models and Computability Theory

Page 5

The argument of the previous section suggests that elementary welfare considerationsrequire forecasters to define and assess the conditions of alternative forecasting modelsbefore choosing any of them for policy prescription. In this section we show that suchcomparisons are not in general computablea priori. Obviously, we can makea postioricomparisons of finite forecasts and reject models that fail the test. This is not sufficienteither to justify the use of particular forecasting models in policy analysis or to sustain thegeneral proposition that econometric forecasting is or can be a progressive science. Wecan either try to identify the conditions in which particular models yield relatively accu-rate forecasts or we can adopt an approach to policy formation which does not rely on theaccuracy of any particular forecasting model or set of models.We begin with some definitions.

Computable model: a model for which all of its variable values can be computed givenunlimited computational resources.

Switch: an endogenous means of selecting variable values or equations which is not itselfan equation. Rules, dummy variables and programming code are examples of switches.Standard model: a computable, linear econometric model over discrete time with switchesand at least one time lag.

Correct model: a standard model that generates empirically correct values of observablevariables to within some predetermined accuracy. Since any finite sequence of numberscan be generated by some algorithmic process, there must always be at least one correctmodel.

The basic result of this section is the proof that there is no general algorithmic means ofknowing if an arbitrarystandard trial model will ultimately converge to acorrect modelWe first show that the class of economic models is identical to that of the well knownclass of computable functions. As a corollary of this we deduce that it is undecidablewhether such standard models will actually converge. This has further consequences forthe possibility that sequences of such models will converge on the correct model.There are many ways to characterize the class of processes that can be mechanicallycomputed. The first such characterisation was by Turing (1936). This was followed by ahost of other such formalisations (e.g. Gödel-Kleene (1936), Church (1941), Post (1943),Markov(1951)). All of these turned out to be equivalent. Since then many processes haveturned out to be equivalent, some of them quite surprising like solving diophantine equa-

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 6

tions and tiling the plane. This has lead to the Church’s famous thesis thatallmechanicalprocesses are thus equivalent. It should not, therefore, surprise us that the class of econo-metric forecasts should also be equivalent.4

The field of Computability (also know as Recursive Function) Theory has now becomea well-established field of mathematics. Some of its most important results show thatmany important questionsabout computable functions arethemselves not computable. Inparticular, there is no computable means of settling the question of whether a computableprocess will ever halt and come to an answer.

While there has been substantial and important work on the implications of computa-bility for economic games5 and choice functions6, we are not aware of any applications toeconometric forecasting.

We will use here a formalisation of computable functions called an Unlimited RegisterMachine (URM) formulated by Sheperdson and Sturgis (1963). This is a much easier for-malism to deal with than Turing’s original machine. Like other such formalisations it isfunctionally equivalent to that of Turing’s.

AURM is a computer with an unlimited number of memory locations, called “regis-ters”, available to it. Each of these registers can hold a natural number (0, 1, 2,...). Callthese registersr1, r2, r3,....

Each URM also has a program consisting of a sequence of four kinds of instruction:- Make register numbern zero.

- Increase register number n by one.

- Copy the contents of register numbern to register numberm, erasingits previous contents.

J(n,m,q)- If the contents of register numbern are the same as register numberm,

then jump to instruction numberq.

The URM executes the program starting at instruction1 and progressing to the nextunless it meets an instruction of type J(n,m,q) where the condition holds, in which case itcontinues execution at stepq.

The starting state of the registers represents the input to this machine. The program ter-minates whenq becomes zero. In this case the output is the end state of the registers.

Z(n)S(n)M(n,m)

4A good but mathematical introductory text is Cutland (1980) where all of the standard

computability results on which we rely are found. An introduction to applications of com-putability theory to economics is Anderlini (1992).5

e.g. Prasad, (1991).

6 Binmore (1987); Rustem & Velupillai, (1990).

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

An Alternative Version of the URM (AURM)

Page 7

We will be using an altered version of this standard type that is equivalent to the stand-ard version in that any program for the standard URM can be simulated on the altered ver-sion and vice-versa.

This version is identical to the standard URM, except that it has only two types ofinstruction available:

S(n)DJZ(n,q)Assumptions

Assume that there is a correct but unknown model of some economic process. We willconsider the case where we are trying to construct trial models that will converge to thecorrect model after an initial “settling-down” period. We will restrict ourselves tostandardmodels of the above type.

It should be noted that most questions about processes with known bounds upon theircomputation timeare computable. Trivially you can run the process and see. Similarly anyfinite sequence of numbers can be generated by some algorithmic process by copying theoutput from an internal table as required. Thus there must always be at least one correctmodel for such finite sequences. This does not mean that this model is known (or evenknowable) by us. For the sake of the arguments below we are assuming that there is a cor-rect model which isuniversally valid7.

Lemma 1: AURM machines can simulate any URM Machine

For any URM there is a AURM machine that is equivalent to it, such that it alwaysgives the same output for every input and it only terminates if the URM terminates (seeAppendix A for a detailed proof).

Lemma 2: URM machines can simulate any AURM Machine

Likewise for any AURM there is a URM machine that is similarly equivalent to it, suchthat it always gives the same output for every input and it only terminates if the URM ter-minates (see Appendix A for a detailed proof).

- Increase register numbern by one.

- Decrease the contents of register numbern if it is greater than zero. Ifthe result is zero continue execution of the program from stepq.

7Note that if you have a series of models and known criteria for swapping between them

(e.g. at certain times) then this can be combined to form a single universal model.

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Lemma 3: AURM machines can be simulated by a“Standard”Model

Page 8

We now show that an arbitrary AURM machine can be simulated by an linear switchedmodel on a number with one time lag.

Proof:

Let the maximum register referred to by the AURM bemax.

Consider a AURM machine with registers:r1, r2, r3,...,rmaxwith initial values:a1, a2,a3,..., amax. and a program with instructions:i1, i2, i3,...,imax.

Each registerr1, r2, r3,...,rmax will be simulated by the variables:X1, X2, X3,..., Xmax.The starting value of the model (X1(0), X2(0),... Xmax(0)) will be the input values of theAURM registersr1, r2, r3,...,rmaxbefore the program starts.Pc will start at1 as doesRt.Let the model have three sections (as above).

Let the first and third sections be initially empty and the second section as follows:Inc := 0

If Pc(T-1)>0 Then Inc := 1Pc(T) := Pc(T-1) + IncRt := Rt + Inc

For each instruction in the program add equations to the model as follows (consideringthejthinstruction):

If thejth instruction is a S(n) instruction add a block of equations of the form:Ps := 0

If Pc(T) = j Then Ps = 1Xn(T) := Xn(T-1) + Ps

to the first section of the model.

If thejth instruction is a DJZ(n,q) instruction add a block of equations of the form:Ps := 0

If Pc = j And Xn(T-1)>0 Then Ps = 1Xn(T) := Xn(T-1) - Ps

to the first section and a switch of the form:If Pc(T)=j and Xn(T)=0 Then Pc :=qto the third section.

Now we have a model which simulates the AURM. Each time step simulates oneinstruction of the AURM being executed. The variablePc keeps track of which instructionis to be executed next.

The model will converge to settled values for all the variables (includingPc andRt) ifPc is set to zero (i.e. the AURM terminates).

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

This model simulates the arbitrary AURM (see Appendix A for detailed proof).Lemma 4: An AURM can simulate anystandard model

Page 9

As we have shown above that the AURM is equivalent to the URM as a definition ofcomputability, it can compute anycomputablefunction. We thus appeal to the Church-Turing Thesis to show this.

Main Theorem: The class of functions that are computable by a standard model are identi-cal to those computable by a Turing Machine.

Proof

As the class of functions computable by a standard model and those computable by anAURM is identical and that class is identical to those computable by an URM, that classmust be the commonly recognised class ofcomputable functions.This URM is a well-known equivalent of a Turing Machine8.

Corollary 1:There Is No Algorithmic Means Of Knowing If An Arbitrary Standard ModelConverges

If there were an algorithm to predict whether all linear models with switches and atleast one time lag would converge to fixed values then that algorithm would predictwhether a model of the above type would converge. We would thus have an algorithm todecide if the AURM it simulated terminated; this would give us a general algorithm fordetermining whenever the corresponding URM halted - this is impossible.Hence there is no such algorithm.

Corollary 2: Convergence by an arbitrary such linear switched model to a computable“correct” model is undecidable.

The question of whether an arbitrary linear switched model converges to the “correct”model is equivalent to the question of whether the difference between the two models onany important variable is sufficiently small after a certain time.

The difference of such models is just another linear switched model with at least onetime lag as the two sets of equations and switches could be collected together (renamingany variables which occur in both) and adding an extra series of equations calculating thedifferences as new variables. Thus the problem of convergence of the trial model to thecorrect one is equivalent to the convergence of another standard model to the zero func-tion (we will call this functionψ).

8 See Cutland (1980)

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 10

We will now use Rice’s Theorem. This states that ifφ1,φ2,φ3,... is any (effective) enu-meration of computable functions andℑ is any non-trivial class of computable functions(i.e.ℑ≠∅and∃φ∉ℑ)then the problem ‘φx∈ℑ’ is undecidable.

If we call the correct modelψ and the trial modelφe then the problem can be expressedas∃T∀t>T(|φe(t)-ψ(t)|<ε), i.e. is there a time after which the trial model and the correctmodel differ by less thanε. Letℜ={φ |∃T∀t>T(|φ(t)-ψ(t)|<ε)}. Then the problem can beexpressed as ‘φx∈ℜ’. Now, by definitionΧ∈ℜ and(ψ+x)∉ℜ,thus the problem ‘φx∈ℜ’ isundecidable by Rice’s Theorem.

Thus you can not, in general tell whether such an arbitrary standard model converges toa similarcorrect model.

Corollary 3: There is no general algorithm for determining the existence of a method forimproving arbitrary models so that it will converge to the “correct” one.

Call the arbitrary trial modelφe and the correct modelψ. Let I={f |∃N∀n>N∃T∀t>T(|φfn(e)(t)-ψ(t)|<ε)}, i.e. this is the set of computable functions such thatafter a certain number of them to this arbitrary trial model, it is suitably close to the correctmodel (in the same sense as above). Now, sinceψ∈Cthen there is a natural number k suchthatψ=φk in an enumeration ofC, then the constant functionk(x)=k is in I (so I≠∅) and ift is the index of the function(ψ+x) (i.e.φt=(ψ+x)) then the constant functiont(x)=t is notin I (sot∉I). Thus by Rice’s Theorem the problem ‘φx∈Ι’ is undecidable. In other wordsthere is no effective means of decidinga priori whether an algorithmic process willimprove a model so that it converges to a correct model.

This does not stop any improvements of a trial model as, at least, some trivial methodsof improvement are possible: e.g. taking one point at a time in the series and fixing them tothe desired values. It does show that you can not assume that there is a method for uni-formly improving forecasts.

Corollary 4: There is no general algorithm for determining which of several alternativestandard models will converge most closely to a “correct” model.

If there were a general algorithm for determining which of several model convergesmost closely to a “correct” model then this algorithm would also determine whether agiven algorithm improved a trial model as much as the perfect constant function (k in theabove). Thus we would have a positive procedure for deciding whether an algorithmimproved the trial model perfectly. This we showed was impossible in the last corollary.

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 11

Thus we have shown that there is no general algorithmic means for determiningwhether a standard model converges to a solution or which of the solutions of severalmodels converges most closely to the solution of the correct model.4Conditions of Application of Forecasting Models

That there are some conditions in which the applicability of different forecasting mod-els can be compared is without doubt. We have proved in section 3 and Appendix A that,in general, there is no systematic means of knowing whether one forecasting model ismore appropriate than another. There must be a separate proof of the preferability of oneover another in each instance.

There is, however, substantial evidence that the accuracy of forecasting models can beimproved systematically by intervention based on the judgement of the model operators.In these cases, forecasters set residual values of individual equations in order to reflecttheir judgements about the values which the LHS variables should take. Moreover, Moss,Artis and Ormerod (1994) have exhibited a forecasting model of the UK economy inwhich some aspects of judgement-based interventions were implemented by expert-sys-tem-type rules. The rules described the actual intervention behaviour of the operator of theLondon Business School Quarterly Model of the United Kingdom Economy.

Rules, we have seen, are switches as defined in section 3. The evidence on the effectsof judgement together with the work of Moss,et. al. imply that some switches do system-atically improve forecasts. In other words, forecasting models which include a particulartype of switch are known systematically to generate more accurate forecasts than modelswhich do not include those switches. It therefore seems likely and is certainly possible thatthere are some (possibly weak) conditions in which a particular kind of switch is associ-ated with closer convergence to the output of a correct model than is achieved withoutsuch switches.

We have also seen that, provided we are considering discrete-time forecasts over finiteforecasting periods, there are always standard models which will generate correct fore-casts. Consequently, the analysis of section 3 must always apply to finite forecasting peri-ods. It is therefore certainly correct to suggest, as does the ESRC, that “there is no single‘correct’ model.”9 There are in principle many correct standard models which could cor-

9cf. the ESRC’s specification of its

Round 4 Macroeconomic Modelling Program (ESRC,

1994).

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 12

rectly forecast the variables of concern in the large macroeconometric forecasting modelsas well as the variables of concern in smaller more specialized models. The problem iden-tified here is the importance on welfare grounds of knowing the conditions in which anymodel’s forecasts converge more closely to the forecasts of a correct model than do theforecasts of any other model combined with the impossibility of any general means ofdetermining what are those conditions.

The alternative to forecasting is scenario modelling. Certainly the consortium manag-ing the ESRC’s Macroeconomic Modelling Programme now emphasize their support for“increasing the use of the models in carrying out policy simulations and in the analysis ofpolicy recommendation.” In any event, using macroeconometric forecasting models forsimulating policy has a long and honourable history. Nonetheless, simulations are not lesssubject to the strictures we have identified than are forecasts. The argument in section 2,for example, was developed first in relation to the general use of models to support policyrecommendations. The certain existence of standard models which would generate correctsimulations of the effects of policy measures implies that our computability theoretic argu-ments apply to policy simulation without change. Finally, the applicability of our argu-ments apply equally whether we consider a temporal sequence of models or a cross-section of alternative models. A “horses-for-courses” approach to modelling does notescape the need to identify the conditions of application of the individual models whenthey are to be used to inform policy.

What might be useful is to conduct a wide range of policy simulations under a varietyof simulated conditions in order to gain some feel for the conditions in which one policyor another will be successful. The purpose of such an extended simulation exercise is toidentify conditions in which particular classes of forecasting model are more accurate thanthe alternatives or particular classes of policy strategy yield greater benefits. Perhaps, aswith judgement-based interventions, we will find a set of modelling procedures whichyields unambiguously more accurate results than the alternatives.5Conclusion

The purpose of this paper has been to argue (i) that economic forecasters should in gen-eral identify conditions in which one forecasting model or another is applicable to a givenpolicy analysis and (ii) that there are no general algorithmic means of determining whichof several models best satisfies its conditions of application. The first point follows fromconventional economic welfare theory and the second from computability theory.

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 13

We do not see this result as a dilemma. We do infer from it that the use of a single fore-caseting model to generate policy prescriptions has no scientific basis in either economicsor logic. It may also have substantial costs as, for example, when UK interest-rate policywas predicated in the early 1990s on Treasure Model forecasts of an early upturn in macr-oeconomic activity which was not, in the event, realized until much later.

We propose more flexible use of models to generate a variety of scenarios which willhelp policy analysts formulate an appreciation of policy opportunities and pitfalls. Perhapsthis approach will lead in time to the identificaion of conditions in which the relative accu-racies of well specified classes of forecasting models can be compareda priori.6References

Binmore, K. (1987), ‘Modeling Rational Players, Part I’,Economics and Philosophy3.pp. 179-214.

Cutland, N. J. (1980),Computability, Cambridge University Press, Cambridge.

Friedman, Milton (1953), ‘Essay on the Methodology of Positive Economics’ inEssayson Positive Economics, (Chicago: University of Chicago Press), pp. .

Moss, S. (1993), ‘The Economics of Positive Methodology’ in R Blackwell, J. Chatta andE. Nell (eds.),Economics as Worldly Philosophy, (Basingstoke: Macmillan).

Moss, S., M. Artis and P. Ormerod (1994), ‘A Smart Automated Forecasting System’,Journal of Forecasting,13, pp. 299-312.

Prasad, K. (1991), ‘Computability and Randomness of Nash equilibria in infinite games’,Journal of Mathematical Economics, pp.429-442.

Rustem, B., Velupillai, K. (1990), ‘Rationality, Computability and Complexity’,Journalof Economic Dynamics and Control,14, pp. 419-432.

Sheperdson,J. C., Sturgis, H. E. (1963): ‘Computability of recursive functions’,J. Ass.Comp. Mach.,10, pp. 217-255.

Thomas, J. (1993): ‘Non-Computable rational expectations equilibria’,Math. Soc. Sci.,25, pp. 133-142.

Turing, A. M. (1936): ‘On Computable Numbers, with an application to the Entscheidung-sproblem’.Proc.London Math.Soc.,42, pp. 230-265.Appendix A

For any URM there is a AURM machine that is equivalent to it, such that it always gives

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

the same output for every input and it only terminates if the URM terminates.

Page 14

We construct an AURM program which simulates an arbitrary URM program. We needto also refer to two registers not used by the URM program, we call these d, e and f., falways has the value 0 in it. This is possible as the URM will use only a limited number ofregisters.

We show that each instruction in the URM program there is an equivalent set ofinstructions in an AURM that has the same effect. Of course, some renumbering of thejump addresses is needed to accommodate the substituted block of AURM instructions.Consider an arbitrary instruction in this program at positions. This instruction can oneof the forms S(n), Z(n), M(n,m) or J(n,m,q).

Case S(n)

Trivial, this is simulated by an identical instruction in the AURM program. Norenumbering is necessary.

Case Z(n)

Replaced by the code

ss+2

DJZ(n,s+2); decrementn and goto end if reached zeroDJZ(f,s); gotos

All jump addresses subsequent to the Z(n) instruction now need incrementing by 2.

Case M(n,m)ss+2s+4

DJZ(e,s+2)DJZ(f,s)DJZ(m,s+4)DJZ(f,s)S(n)

DJZ(n,s+9)S(m)S(e)

DJZ(f,s+4)S(e)

DJZ(e,s+14)DJZ(e,s+12)S(n)

DJZ(f,s+9)

;

; makee zero;

; makem zero

;

; ifn is zero gotos+9

; incrementm; incremente

; gotos+4

;

; ife is zero gotos+14; decremente

;

; gotos+9

s+9s+12s+14

All jump addresses subsequent to the M(n,m) instruction now need incrementing by14.

Case J(n,m,q)

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

ss+14s+28

M(n,d)M(m,e)S(d)

DJZ(d,s+35)S(e)

DJZ(e,s+37)DJZ(d,s+33)DJZ(e,s+34)DJZ(f,s+28)S(e)

DJZ(e,q')

; copyn tod; copym toe

;

; ifd is zero gotos+35

;

; ife is zero gotos+37; decrementd; decremente; gotos+28

;

; ife is zero gotoq

Page 15

s+33s+34s+35s+37

All jump addresses subsequent to the J(n,m,q) instruction now need incrementing by37. Here where it saysM(n,d) orM(m,e) then all of the instructions listed under theprevious case should be inserted with the appropriate numbers substituted. q' isequal to the q if q is before s and is equal to q+37 if after it.

For any AURM there is a URM machine that is similarly equivalent to it, such that it

always gives the same output for every input and it only terminates if the URM terminates.Similar to the above proof but easier. For each instruction at position q there are twocases.

Case S(n)

Is trivial.

Case DJZ(n,q)

is replaced by the URM code:

s

J(n,f,s+9)Z(d)Z(e)S(e)

J(n,e,s+8)S(d)S(e)

J(n,n,s+4)M(d,n)J(n,f,q)

; ifn is already zero gotos+9

; setd as 0;

; sete as 1

; ifn =e gotos+8

;d:= d +1;e :=e +1

; gotos+4; copyd ton

; ifn is zero gotoq

s+4

s+8s+9s+10

All jump addresses subsequent to the DJZ(n,q) instruction now need incrementingby 10.

There is a standard model that simulates an arbitrary AURM.

We will show that there is a model of the form shown above, such that for each AURMinstruction and each possible state of the registers in the AURM that one time iteration ofthe model has the identical effect as that AURM instruction.

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

Page 16

Consider an arbitrary AURM instruction at positionq in the program. The variablePckeeps track of the number of the instruction being executed. ThusPc(T) will have valueqwhen instruction q is to be simulated. There are two cases:

Case S(n)

This instruction adds one to the registerrn, and then execution passes on to the nextinstruction - numberq+1.In this case a block of the form:

Ps := 0

If Pc(T) = q Then Ps = 1Xn(T) := Xn(T-1) + Ps

exists in the model.

AsPc(T) has valueq thenPs will be set to 1 and this will have the effect of incre-menting variableXn.The block of form:

Inc := 0

If Pc(T)>0 Then Inc := 1Pc(T+1) := Pc(T) + Inc

will cause the value ofPcto be incremented by one as q>0, as the AURM programhas not terminated (otherwise instruction S(n) would not be being executed).None of the other blocks in the first section of form:

Ps := 0

If Pc = And Xn(T-1)>0 Then Ps = 1Xn(T) := Xn(T-1) - Ps

will have effect aswill not beq in these cases. Similarly for the switches inthe third section of form:

If Pc(T)= Then Pc:=

Thus the sole effect of the model in this iteration is to increment theXn andPc vari-ables.

Case DJZ(n,p)

This instruction subtracts one from the registerrn if this is non-zero, then if thevalue of rn is now zero execution continues at instruction numberp,otherwise exe-cution passes on to the next instruction - numberq+1.In this case a block of the form:

Ps := 0

If Pc(T) = q Then Ps = 1Xn(T) := Xn(T-1) - Ps

exists in the model as well as a switch in the third section of the form:

Methodology,Computability and Forecasting Evaluation13 September, 1994 (saved at 1306)

If Pc(T)=0 and Xn(T)=0 Then Pc:=p

Page 17

AsPc(T) has valueq thenPs will be set to 1 and this will have the effect of decre-menting the variableXn.The block of form:

Inc := 0

If Pc(T)>0 Then Inc := 1Pc(T+1) := Pc(T) + Inc

will cause the value ofPcto be incremented by one as q>0, as the AURM programhas not terminated (otherwise the instruction would not be being executed) but nowthe value ofPc will be reset top if, in additionXn is now 0.None of the other blocks in the first section of form:

Ps := 0

If Pc = And Xn(T-1)>0 Then Ps = 1Xn(T) := Xn(T-1) - Ps

will have effect aswill not beq in these cases. Similarly for the other switchesin the third section of form:

Thus the sole effect of the model in this iteration is to decrement theXn if it isgreater than zero and set thePc variable top if the result is zero andQ+1 otherwise.

If Pc(T)= Then Pc:=.

Halting

The AURM halts only ifq is ever set to zero. The model only ever settles down intoa steady state ifPc is set to zero, for in this case none of the first or third sectionswill have any effect and the second section is of form:

Inc := 0

If Pc(T)>0 Then Inc := 1Pc(T+1) := Pc(T) + IncRt := Rt + Inc

Which will only have effect ifPc>0.