What is an Algorithm

 

What is an algorithm? Yuri Gurevich Microsoft Research

Technical Report MSR-TR-2011-116, July 2011

Microsoft Research Microsoft Corporation One Microsoft Way Redmond, WA 98052

 

0

Preamble

We pre presen sentt a tw two-p o-part art expo exposit sition ion on the not notion ion of alg algori orithm thm and fou founndati dation onal al an anal alys yses es of co comp mput utat atio ion. n. Th Thee first first pa part rt is bel below ow,, an and d the the secsecond is here:   http://research.microsoft.com/en-us/um/people/gurevich/ Opera/210.pdf .  This preamble was added in February 2012. In the first par part, t, aft after er a sho short rt in introd troduct uction ion,, we clar clarify ify some com common mon misconceptions related to Turing’s analysis of computation, consider whether the notion of algorithm can be rigorously defined in full generality, discuss what kind of entities algorithms are, and examine two approaches to the title problem problem in the liter literature ature.. The first part appeared in “SOFSEM 2012: Theory and Practice of Computer Science,” Springer LNCS 7147, 31–42. The second part is devoted entirely to fundamental analyses of computations in the literat literature, ure, by T Turing uring and by other otherss including this author. It will appear in the proceedings of “Turing Centenary Conference, CiE 2012: How the World Computes,” to be held in Cambridge, England, in June 2012.

1

 

What is an algorithm? Yuri Gurevich Microsoft Research We must, incidentally, make it clear from the beginning  that if a thing is not a science, it is not necessarily bad. For example, love is not a science. So, if something is said  not to be a science, it does not mean that there is something  wrong with it; it just means that it is not a science. –Richard –Richar d Feynman 

1

Intr Introd oduc ucti tion on

Two articles in a recent book [10 book  [10]] present two approaches to the title problem and offer different different answ answers. ers. Artic Article le [[19] 19] presents  presents an approach developed by Yiannis Moschovakis. “A characteristic feature of this approach is the adoption of a very abstract notion of algorithm that takes  recursion  as   as a primitive operation and is so wide as to admit ‘non-implementable’ algorithms” [ 19, p.87]. The article starts thus. In the sequence sequence of artic articles les . . . , Moscho Moschov vakis has proposed a mathematical modeling of the notion of algorithm — a set-theoretic “definition” of algorithms, much like the “definition” of real numbers as Dedekind cuts on the rationals or that of random variables as measurable functions on a probability space. We discuss this definition of algorithms in § in  §6. 6. Article [22 Article  [22]] presents an approach originally developed by Robin Gandy, a student of Alan Turing, in a 1980 article [9 article  [9]. ]. Gandy intended to complement Turing’s analysis of human computers with an analysis of computation by mechanical devices. He came up with an axiomatically defined class of computation putati on devic devices, es, later named Gandy machine machines. s. The approac approach h was adopted 2

 

by Wilfried Sieg. In article [22 [22], ], Sieg uses Gandy machines to “dispense with [Church’s and Turing’s] theses”. The article starts thus. Church’s and Turing’s theses dogmatically assert that an informal notion of effective calculability is adequately captured by a particular parti cular mathema mathematical tical concep conceptt of compu computabili tability ty.. I prese present nt an analys ana lysis is of ccalc alcula ulabil bilit ity y that that . . . dis dispens penses es wi with th th these eses. s. . . . The analysis leads to axioms for discrete dynamical systems (representing human and machine computations) and allows the reduction of models of these axioms to Turing machines. We discuss this axiomatization of discrete dynamical systems and dispensing with the theses in § in  §4. 4. In § In  §22, we discuss wheth whether er it is possible at all to define algorithm algorithms. s. (The (There re is als alsoo a que questi stion on wh why y both bother er to defi define ne algori algorithm thms. s. Well, ell, und unders erstan tandin dingg what algorithms are should — and does — have practical applications, to softwar soft waree specific specification ation and model-b model-based ased testing in parti particular cular,, as wel welll as theoretical application, like semantics of software or algorithmic completeness of  computation models. But that is a different issue to be addressed elsewhere.) In §3, 3, we  we discuss and clarify a couple of misconceptions related to Turing’s analysis of computations. In §4 we discuss Gandy machines. In §5, we discuss what kind of entities algorithms are; this discussion is closely related to  to   §6 where we discuss Moschovakis’s recursor theory. This article can be seen as a companion to our older article [5] [5]..

Acknowledgments Many thanks to Andreas Blass for numerous illuminating discussions, and to Serge Grigorieff and Oron Shagrir for useful suggestion.

3

 

2

Can Can the the noti notion on of al algo gori rith thm m be rigo rigoro rous usly ly defined?

Two articles   [19 [19]] and   [22] [22],, mentioned in   §1,   give different answers to the title question. question. The tw twoo answers are not at all equiv equivalen alent. t. A question arises whether the notion of algorithm can be defined at all. The answer is yes and no. Let us explain.

The negative answer In our opinion, the notion of algorithm cannot be rigorously defined in full ge gene nera rali litty, at leas leastt fo forr th thee ti time me bei being ng.. Th Thee reas reason on is that that the the no noti tion on is expanding. Concerning the analogy of algorithms to real numbers, mentioned in  in   §1, Andrea And reass Blas Blasss sug sugges geste ted d a bett better er analo analogy: gy: alg algori orithm thmss to num numbers bers.. Man Many y kinds of numbers have been introduced throughout history: positive integers, natural numbers, rationals, reals, complex numbers, quaternions, infinite cardinals,, infini dinals infinite te ordinals, etc. Simila Similarly rly many kinds of algor algorithms ithms hav havee b been een introduced int roduced.. In addition to class classical ical sequen sequential tial algorith algorithms, ms, in use from antiquity, we have now parallel, interactive, distributed, real-time, analog, hybrid, quant qua ntum, um, etc. alg algori orithm thms. s. New kin kinds ds of nu numbe mbers rs and alg algori orithm thmss ma may y be introduced int roduced.. The notions of number numberss and algori algorithms thms hav havee not cryst crystalliz allized ed (and maybe never will) to support rigorous definitions.

The positive answer But the pro proble blem m of rigor rigorous ous defini definitio tion n of algori algorithm thmss is not hopele hopeless. ss. Not at all. Some strat strataa of algori algorithms thms hav havee matured enough to support rigorou rigorouss definitions. This applies to classical (or classical sequential or just sequential) algorithms, essentially the only algorithms in use from antiquity to the 1950s. “Algorithms compute in steps of bounded complexity”, wrote Andrei Kolmogorov in 1953  1953   [14 [14]. ]. This is a good infor informal mal definit definition ion of sequen sequential tial algorithms. An axiomatic definition of sequential algorithms have been given in [12 [12]. ]. That definition was used to derive the Church-Turing thesis from first principles in  in   [8 [8]. ]. The derivation presumes that, at the time, Church and Turing

4

 

(and G¨oodel del and other experts) had in mind only sequential algorithms, which we believe believe they did. The axiomati axiomaticc defini definition tion was extende extended d to synchro synchronous nous parallel algorithms in [3] [3] and  and to interactive sequential algorithms in [6, [ 6, 7] 7]..

The status of the Church-Turing thesis As far as the inp inputut-out output put rel relati ation on is con conce cerne rned, d, syn synch chron ronous ous par parall allel el algorithms and interactive sequential algorithms can be simulated by Turing machines. This gives additional confirmation of the Church-Turing thesis. None of the other known kinds of algorithms seem to threaten the thesis but the thesis has not been dispensed with and probably never will be. The question whether some algorithm of a currently unknown kind would allow us to compute a function from natural numbers to natural numbers that is not Turing Turing computa computable ble remains open, possibly forev forever. er. And even if we had a satisfactor satisfactory y axioma axiomatic tic defini definition tion of algori algorithms thms in full generalit generality y, the thesi thesiss would not be dispensed with. It would be just reduced to the first principles enshrined in the axioms.

3

Rema Remark rkss on Turin uring’ g’ss analy analysi siss of comp comput utaation

Turing’s analysis of computation [24 [24]] was a stroke of genius. The analysis is extremely famous, and yet it is often misunderstood. Some people think that every computable function, total or partial, can be computed by a Turing machine. This is not so, and here are some counterexamples. examp les. Consid Consider er Euclid’s algorith algorithm m for computin computingg the greates greatestt common divisor d divisor  d =  = gcd(a, gcd(a, b) of two natural numbers a, numbers  a, b. let   M  =   = max(a, max(a, b), m  = min(a, min(a, b) while   M > m   do M, m  := max(M  max(M   − − m, m), min( min(M  M   − − m, m) d  :=  := M   M . The gcd function on natural numbers is of course Turing computable, but the algorithm was also applied — in theory and in practice — to the lengths of  segments of a straight line, which gives rise to a computable partial function (the algorithm does not terminate if the two given lengths are incommensurate) that is not Turing computable because you cannot place an arbitrary 5

 

length on the Turing tape. More generally, the functions computed by rulerand-compass and-co mpass algorit algorithms hms are not T Turing uring comput computable. able. And let us empha emphasize size that ruler and compass were practical tools in ancient Greece and that a number of ruler-and-compass algorithms were practical algorithms. It is common in mathematics to consider algorithms that work on abstract objects. objec ts. The func functio tions ns com comput puted ed by these algor algorith ithms ms ma may y not be Turi uring ng computable. One example is Gaussian elimination. Here is another example: a bisection algorithm that, given a real ε real  ε >  0 and a continuous function f  function  f    on a real segment [a, [a, b] with  with   f  f ((a)  <  0   < f  f ((b), computes a point  point   c   ∈   [a, b] with |f  f ((c)|  < ε. while   |f  f (( ((a a + b)  b)/2) 2)|| ≥  ε   do if   f  f (( ((a a + b)  b)/2) 2) <  < 0  0   then   a  := (a + b)  b)/2   else   b  := (a + b)  b)/2

c  := (a + b)  b)/2 One can argue that these functions are not truly computable, that in practice we can only approximate them. But then there are analog computers in practical use  that work in real time and compute functions that are not Turing computable. Of course Turing would not be surprised by our examples. He explicitly restricted his analysis to “symbolic” (symbol-pushing, digital) algorithms. He implicitly restricted his analysis to sequential algorithms, essentially the only onl y alg algori orithm thmss in his tim time. e. It is in inter terest esting ing that it turned turned out easi easier er to axiomatize all sequential algorithms [12] [12],, whet whether her symbolic or not, includin includingg the ruler ruler-and-c -and-compass ompass algorithms algorithms,, Gaussi Gaussian an elimi eliminatio nation n and the bisec bisection tion algorithm (but excluding analog algorithms which are not sequential in our sense). What about quantum algorithms? algorithms? Do they compute functi functions ons that are not Turing Turing comput computable? able? Eric Erich h Gr¨aadel del and Antje Nowack checked that the quantum computing models in the literature can be faithfully simulated by parallel abstract state machines [11 [ 11]. ]. And, as we mentioned above, functions computed by parallel ASMs are Turing computable. There is also a rather common misunderstanding that Turing defined the notion of algorithm, albeit restricted to symbolic sequential algorithms. Let us res restri trict ct att atten entio tion n to suc such h alg algori orithm thmss for a mom momen ent. t. Sup Suppose pose that yo your ur computation model (e.g. a programming language) is Turing complete. Does it mean that the model allows you to express all algorithms? Not necessarily. Turing machines simulate faithfully only the input-output behavior of algorithms. But there may be much more to algorithms than their input-output 6

 

behavior. Turing complet behavior. completeness eness does not mean algori algorithmic thmic comple completenes teness. s. It means only that, for every Turing computable function f  function  f ,, the language allows you to program an algorithm that computes f  computes  f .. For illustration consider Turing machines with one tape that may be multidimensiona tidime nsional. l. The model is obviousl obviously y Tu Turing ring comple complete. te. On any such machine, the problem of palindrome recognition requires Θ(n Θ(n2 / log n) time [2 [2]. But the problem is trivially solvable in linear time on a Turing machine with two one-dimensional tapes. For a deeper dive into algorithmic completeness, see [26 [26,,  §3].  § 3].

4

Gand Gandy’ y’ss ana analy lysi siss of mec mechani hanism smss

Robin Gandy argues in [9] [9] that  that “Turing’s analysis of computation by a human being does not apply dire directl ctly y to mech mechani anical cal devi devices ces.” .” The reas reason on is that humans sequentially but machines can perform parallel com-l putations. putati ons. In compute this connecti connection, on, Gandy analyzed computat computations ions by mec mechanica hanical devices and introduced (what we call now) Gandy machines. A set-theoretic form of description for discrete deterministic machines is elaborated and four principles (or constraints) are enunciated, ciate d, whic which, h, it is argued, any suc such h machin machinee must sati satisfy sfy.. . . . It is proved that if a device satisfies the principles then its successive states form a [Turing] computable sequence.   [9, [9, p. 123] Note “successive states”. Gandy machines work in sequential time. This type of parallelism parallelism is calle called d synchr synchronous. onous. In the rest of this secti section, on, paralleli parallelism sm will by default be synchronous. Gandy Gan dy pione pioneere ered d the use of axioms in the analy analysis sis of com comput putati ation. on. He came up with four principles (or constraints, or axioms) satisfied, he claimed, by all discrete deterministic machines. Contrast this with Turing’s analysis. While Turing’s analysis was convincing, it is hard to isolate first principles that, in Turing’s opinion, are satisfied by all symbolic sequential computations. Wilfried Sieg adopted Gandy’s approach and reworked Gandy’s axioms; see [23 [23]] and references there.

7

 

Critical remarks In a 2002 article  article   [20 [20], ], Oron Shagrir suggests that “there is an ambiguity regarding theions: types“Gandy of machines that as Gandy wasmachines”, postulating”. He offers three interpretations: interpretat machines physical “Gandy machines mach ines as finite-physical machines”, and “Gandy machines as a mathematical notion”. Shagrir concludes that none of the three interpretations “provides the basis for claiming that Gandy characterized finite machine computation.” This agrees with our own analysis. By the way, for our purposes, there is no difference between Gandy’s original axioms and Sieg’s versions of the axioms. So we will just speak about Gandy’s axioms. real-world devices devices satisfy satisfy Gandy’s Gandy’s axioms? axioms?   Probably very •   What real-world few do. One problem is the form of the states of Gandy machines: a collection of her heredi editar tary y fini finite te set sets. s. Ano Anothe therr pro proble blem m is the requ require iremen mentt tha thatt sta state te

transi tra nsitio ns are sync synchro hronou s. burden You, reader, may say say propo tha thatt we hav have pro prove ved dtions our poin point. t. W ell, ellnous. , the bur denthe of reade proo prooffr,isma ony the proponen nents ts ofe not the approach. And there are precious few examples in the papers of Gandy and Sieg, and none of the examples is a realreal-wor world ld device. The most prominen prominentt example in Gandy’s paper is the cellular automaton known as Conway’s game of life. Note that a cellular automaton can grow without any bound. In the real-world, such a cellular automaton would not stay synchronous. It seems obvious that Gandy abstracts from material and views discrete deterministic machines as algorithms, abstract algorithms. So Gandy’s claim can be restated thus: parallel algorithms satisfy the axioms. •  What algorithms satisfy Gandy’s axioms?   Typical parallel or even seque sequenti al algorithms notofsatisfy theithm axioms. Consid Consider for examp example a factorialntial algori algorithm. thm. The do state the algor algorithm is natur naturally allyer infinit infinite e and le consi consists sts of natural numbers. There is of course a Gandy machine that simulates the factorial facto rial algorit algorithm. hm. Note that, in additi addition on to simu simulatin latingg the factor factorial ial algorithm, the simulating machine may be forced to construct set representations of additional numbers. In our view, Gandy’s axioms are really used just to define another parallel co comp mput utat atio ion n mod model el.. (B (By y th thee way ay,, it is ou ourr am ambi biti tion on in  in   [3] [3] that parallel algorithms, algori thms, on their natural abstracti abstraction on lev levels, els, satisfy our axioms axioms.) .)

8

 

•  How does Gandy’s parallel computation model compare to other parallel parall el computation computation models?   By now now,, there are nu numerou merouss models of  synchronou sync hronouss paral parallelism lelism in the literatu literature, re, e.g. parallel random acce access ss machines, circuits, alternating Turing machines, first-order logic with the least fixed-point fixedpoint operator operator,, and parallel abstrac abstractt state mach machines. ines. What are the advant antages, ages, if any any,, of Gandy’s model over over the other models? Neit Neither her Gandy nor Sieg addressed this question. question. Gandy Gandy’s ’s model seems quite aw awkwa kward rd for programming or specifying algorithms. •   Dispensing with the Church-Turing thesis   Gandy pr prov oved ed that his machines can be simulated by Turing machines. This is another confirmation of the Ch Churc urch-T h-Turi uring ng thesis. thesis. But is it a good gro ground und for dis dispens pensing ing with the thesis? thesis? We do not thi think nk so, ev even en if we rest restric rictt att atten entio tion n to paral parallel lel algorit algo rithms hms and for forget get othe otherr kin kinds ds of alg algori orithm thms. s. By the firs firstt tw twoo bul bullet letss above, Gandy’s theorem does not imply that his axioms are satisfied by any discrete mechanical device or by any parallel algorithm.

5

What What kin kind d of enti entiti ties es are are algo algori rith thms ms? ?

One point of view is that the question about algorithm entities is of no importance. importan ce. We quoted alre already ady in in   §1  that “Mosc “Moscho hov vaki akiss has propos proposed ed . . . a set-theoretic ‘definition’ of algorithms, much like the ‘definition’ of real numbers as Dedekind cuts” [19] [19].. The quota quotation tion marks around the wo word rd definition make make goo good d sense. Ther Theree is anoth another er familiar defini definition tion of real num numbers, bers, as Cauchy sequences. Dedekind cuts and Cauchy sequences are different entities, yet the two definitions are equivalent for most mathematical purposes. The question of importance in re mathematics not rwhat kind ofallo entities numbers num bers are but what structu structure they form. isEithe Either definition allows ws onereal to establish that real numbers form a complete Archimedean ordered field. The analogy in the quotation is clear: concentrate on mathematical properties of algorithms rather than on what kind of entities they are. The analogy makes good sense but it is far from perfect because much more is known about algorithm entities entities than real-nu real-number mber entit entities. ies. Let us ske sketc tch h anothe anotherr point of view on algorithm entities. Consider Consi der algorith algorithms ms that compu compute te in sequ sequent ential ial time. This include includess sequential algorithms as well as synchronous parallel algorithms. A sequentialtime algorithm is a state transition system that starts in an initial state and 9

 

transits from one state to the next until, if ever, it halts or breaks. The very first postula p ostulate te in our axiom axiomatiza atizations tions of seque sequenti ntial al and sync synchrono hronous us paral parallel lel algorithms algori thms [12 12,,  3]  3 ] is that the algorithms in question are sequential time. The question question arises what kind of ent entities ities states states are. In our view view,, rathe ratherr common in computer science, algorithms are not humans or devices; they are abstract abstra ct entiti entities. es. Accor According ding to the second p postul ostulate ate in the axiomatiz axiomatizations ations of sequential and synchronous parallel algorithms, the states are (first-order) structures, up to isomorphism. This admittedly involves a degree of mathematical matic al modeling and ev even en arbitrar arbitrariness. iness. A particular form of structure structuress is used; use d; wh why y thi thiss par partic ticula ularr form? But this is a min minor or detai detail. l. Str Struct ucture uress are faithful representations of states, and that is all that matters for our purposes. It is convenient to declare that states  are  structures,   structures, up to isomorphism; but there is no need to do so. Thee poi Th point nt of vi view ew th that at se sequ quen enti tial al-t -tim imee algo algori rith thms ms are are stat statee tran transi si-tion tio n sys syste tems ms ext extend endss nat natura urally lly to oth other er cla classe ssess of alg algori orithm thms. s. In par partic ticuular, a sequential-time interactive algorithm (until now we considered noninteractive algorithms) is a state transition system where a state transition may be accom accompanie panied d by sendi sending ng and rece receiving iving messag messages. es. A distribut distributed ed algorithm is an ensemble of communicating sequential-time interactive algorithms.

6

Mosc Moscho hov vakis’s akis’s recursio recursion-ba n-based sed approac approach h

We sta start rt wit with h bas basics ics.. In rec recurs ursion ion-ba -based sed app approa roach ches es you you wri write te rec recurs ursiv ivee equations that specify a function. Typically the equations define a monotone operator, and semantics is given by means of the least fixed point of the operator. For example, equations exp(x exp( x + 1, 1, 0) = 1 exp(x, exp( x, y + 1) =



0 x × exp( exp(x, x, y)

if  x =  x  = 0 if  x  x >  0

specify exponentiation exp(x, exp(x, y) =   xy on natural natural num numbers. bers. The equ equations ations define a monotone operator on extensions of the standard arithmetical structuree wit tur with h par partia tiall bin binary ary funct function ion exp. Acc Accord ording ingly ly the follo followin wingg proc process ess gives meaning to exponentiation. Initially exp is nowhere defined. Apply the equations, obtaining exp(x, exp(x, 0) = 1 for every x every  x > 0; then apply the equations 10

 

again, obtaining additionally exp(x, exp(x, 1) =  x for all  x,, and so on. After ω After  ω steps  steps  x  for all x (where   ω  is the first infinite ordinal), you reach a fixed point; now exp(x, (where exp( x, y) is defined for all x, all  x, y  except  except x  x =  = y  y =  = 0. Often the evolution toward the fixed point involves not only the function that you are computing but also some auxiliary functions. In 1934, G¨odel odel formulated a recursion-based calculus of (in general partial) tia l) nume numeric rical al funct function ions. s. G¨ oodel’s del’s calculus can be seen as a specification language where a specification of a function f  function  f  is  is a system of recursive equations that, taking into account some global conventions, suggests a particular (possibly inefficient) way to compute f  compute  f .. Church Church’s ’s thesis (extende (extended d to partial functions by Kleene) asserts that every “effectively calculable”, that is computable by an algorithm, function on natural numbers is programmable in G¨oodel’s del’s calculus. Recursive specification of functions has much appeal. It is declarative and abstracts from computation details. It is often concise. There has been much progress progre ss since the 1930s. Logic Logicians ians deve developed loped recur recursion sion theory theory.. McC McCarth arthy y created a functional (that is recursion-based) programming language LISP, and many other functional languages followed. The key ideas of Moschovakis’s approach appear already in the 1984 article [16] [16] that  that seems to be the very first publication on the subject. If, by Church’s Thesis the precise, mathematical notion of  recur  recursive function  captures  captures the intuitiv intuitivee notion of  computable  computable function , then the n the pre precis cise, e, mat mathem hemati atical cal not notion ion of   recursion   . . . should model adequately the mathematical properties of the intuitive notion of  algorithm  [16,, p. 291]   algorithm .   [16 Moschovakis discusses Euclid’s algorithm for the greatest common divisor of  two natural numbers. Then he says: Following the drift of the discussion, we might be expected at this point to simply identify the Euclidean algorithm with the functional   gcd. We will not go quite tha thatt far, because the timehonored intuitive concept of algorithm carries many linguistic and intensional connotations (some of them tied up with  implementations ) with which we have not concerned ourselves. Instead we will make the weaker (and almost trivial) claim that   the functional   gcd  embodies all the essential mathematical properties of  the Euclidean algorithm . [16 16,, p. 295]

11

 

He gives recursive equations for the mergesort algorithm on a set  X   X    and proceeds to prove that at most   n · log2(n) comparisons are required to sort n   elements. Moschovakis’s views have been evolving. When algorithms algorithms are defined rigorously in Compu Computer ter Science literature (which only happens rarely), they are generally identified with abstract abstract mach machines, ines, mathe mathematic matical al models of compu computers ters.. . . . My aims here are to argue that this does not square with our intuitions about algorithms and the way we interpret and apply result res ultss about them them;; to pro promot motee the probl problem em of defi definin ningg alg algoorithms correctly; and to describe briefly a plausible solution, by which algorithms are recursive definitions while machines model implemen imple mentatio tations, ns, a special kind of algori algorithms. thms.   [17 [17,, p. 919].   recursor  The main technical notion in Moschovakis’s approach is that of  recursor  which is a gener which generaliza alization tion of funct function ion specific specification ation in G¨oodel’s del’s calc calculus. ulus. The most recent published definition of recursor is found in [19 [ 19,, p. 95]. Semantics is given given by mea means ns of the leas leastt fixe fixed d poin pointt of a mon monoto otone ne operat operator. or. In some cases, the least fixed point is not achieved in ≤ in  ≤ ω  ω  steps; then the recursor is infinitary  and   and cannot be implemented by abstract machines. For illustration, see “the infinitary Gentzen algorithm” in  in   [18 [18]. ]. Moscho Moschovakis vakis form formulates ulates this slogan:

The theory of algorithms is the theory of recursive equations. [18 [18,, p. 4]

Critical remarks Recursors vs. algorithms algorithms   We think that Mosc •   Recursors Moschov hovakis akis was right the first time around, in  in   [16 [16,, p. 295] when he refrain refrained ed from ident identifyin ifyingg (what he later called) recursors with algorithm “because the time-honored intuitive concept of algorithm carries many linguistic and intensional connotations” which are contrary to such identification. Consider the system of two recursive equations (and thus a recursor) for the exponentiati exponentiation on in the beginnin beginningg of this secti section. on. Is it an algorith algorithm m or not? The recursor certainly looks like an algorithm, and in many functional programming languages, this recursor would be a legitimate program (modulo

12

 

syntactic deta syntactic details ils of no importan importance ce to us here). Ty Typicall pically y exp( exp(x xy ) would be interpreted as a function call and, for example, the evaluation of 3 2 would proceed thus: 32 = 3 · 31 = 3 · (3 · 30 ) = 3 · (3 · 1)) = 3 · 3 = 9. But the recursor recursor theory is differen different. t. The meaning meaning of a recursor is given by the least fixed point construction, and there is   nothing nothing else . In tthe he case ase of the exponentiation recursor, the only “computation” is the process that we described described ab abov ove: e: start with the now nowhere here define defined d exp functio function, n, compu compute te 0 1 exp(x exp( x ) for  all   a ll   x >  0, compute x compute  x for   all   x, etc. What should we do in order 2 to compute 3 ? Should we wait until the “computation” of exp is completed and then apply exp, or should we wait only to the end of stage 3 when all  x 2 are computed? The recursor theory says nothing about that. It is not our goal to make make the recur recursor sor the theory ory look ridic ridiculo ulous. us. In fact we that are to useful for mathematical analysis of algorithms. Weagree just see norecursors good reason identify them with algorithms. Paraphrasing Richard Feynman, if thing is not an algorithm, it is not necessarily bad. •  The abstraction level of imperative algorithms   It se seems ems to us that recursor theorists underestimate the abstraction capabilities of imperative programming. progra mming. Imperat Imperative ive prog programs, rams, and in particul particular ar abstract stat statee machines, can be as abstract as needed. We addressed this point once [4] [ 4].. Here let us jus justt qui quick ckly ly say this. Yes, an alg algori orithm thm come comess wit with h a pro progra gram m for executing exec uting the algorit algorithm. hm. But this does not mean that the program necessa necessarrily addresses low-leve low-levell compu computatio tational nal detai details. ls. Ev Every ery algorithm operates on its natural natural lev level el of abs abstra tracti ction. on. Thi Thiss lev level el may be ve very ry low but it may be arbitrarily high. Declarative specifications   Rec •   Declarative Recurs ursion ion is ap appeal pealing ing.. A part of tthe he appeal comes from the declarative nature of recursion. That declarative nature is by itself a limitation for software specification; and note that every piece of software software is an algorithm. Decl Declarati arative ve specifica specification tion of soft softwar waree was ver very y popular in the 1980s and 1990s, but it was discredited to a large extent. As sof softw tware are is dev develo eloped, ped, it ev evolv olves. es. A book wit with h a dec declar larati ative ve specifi specificacation quickly becomes obsolete. If specification is not executable, you cannot experiment with it.

13

 

Recursion on is but one aspect aspect of an algori algorithm thm   The th theory eory ooff algo•   Recursi rithms rithms does not redu reduce ce to rec recurs ursion ion.. For one thing thing,, the there re are clev clever er data structure struc tures. s. For man many y linear linear-time -time algorith algorithms, ms, for examp example, le, it is cruc crucially ially important that an algorithm does not manipulate large objects directly; instead it manipu manipulat lates es onl only y poin pointer terss to tho those se objec objects. ts. Suc Such h aspe aspects cts of com comple plexit xity y analysis seem below the abstraction level of recursors.

recursor ursor approac approach h does not seem to extend • Distributed algorithms   The rec to distributed algorithms, and the number of useful distributed algorithms is large and growing. Monotonicity limitation   Here is somet •   Monotonicity something hing that the recu recursor rsor theory theory should be able to cove coverr but doesn’t doesn’t.. The curre current nt recur recursor sor theory is limited to recursors with semantics given by the least fixed point of a monotone operator. That is a serious limitation. For a simple example consider Datalog with negation   [1]. [1]. Th Thee ope opera ra-tor defined by a Datalog-with-negation program is not monotone but it is inflationary, and semantics is given by the inflationary fixed point [ 13] 13].. For illustration, here is a Datalog-with-negation program computing the complement   C  of complement C  of the transitive closure   T  T  of  of a nonempty binary relation  relation   R on a finite domain [1 domain  [1,, Example 3.3].

T  T ((x, y)  ←  ← R  R((x, y) T  T ((x, y)  ←  ← R  R((x, z ), T  T ((z, y) U (x, y)  ←  ← T   T ((x, y) V ( V (x, y)  ←  ← T   T ((x, y), R(x , z  ), T ( T (z  , y ), ¬T ( T (x , y ) 



















C (x, y)  ← ¬T  T ((x, y), U  U ((x , y ), ¬V ( V (x , y ) Explanati Explan ation. on. At ev every ery ste step p all rul rules es are fired fired.. By the first tw twoo rul rules, es, the computation of   T  proceeds T  proceeds in the usual way. Since the domain is finite, the computation of   T  T  completes  completes after some number   k   of steps. steps. The pa pairs irs of   T  are stored in U  in  U  with  with a delay of one step, so the computation of   U  completes U  completes after k after  k +1 steps. The computation of  V    V   is ident identical ical to that of   U , U , except that at the step k step  k + 1, whe when n  U  is  U  is completed, the last batch of pairs from  T  is  T  is not stored in  in   V . V . The final rule is idle during the first   k  steps but on step  step   k  + 1 it stores the complement of   T  into  C .. T    into C 

14

 

much uch useful to hav havee more example •  More examples, please.   It would be m of recursors of int interes erestt to computer scien scientists tists.. All curren currentt examples of that sort seem to be present already in the 1984 article [16] [ 16]..

References [1] Serge Abiteboul and Victor Vianu, “Datalog extensions for database queries and updates”, J. of Computer and System Sciences 43 (1991) 62–124. [2] Ther Therese ese Biedl, Jonat Jonathan han F. Buss, Erik D. Demaine Demaine,, Martin L. Demaine, Mohammadtaghi Hajiaghayi, Tom´aaˇˇs Vi Vinaˇ naˇrr,, ““Pal Palin indro drome me rreco ecogn gnit itio ion n us us-ing a multidemensional tape”, Theoretical Computer Science 302 (2003) 475–480. [3] Andreas Blass and Y Yuri uri Gurevich, “Abstract state machines machines capture parallel algorithms,” ACM Transactions on Computational Logic 4:4 (2003) 578–651. Correction and extension, same journal, 9:3 (2008) article 19. [4] Andreas Blass and Y Yuri uri Gurevich, “Algorithms vs. vs. machines”, Bull. European Association for Theoretical Computer Science 77 (2002), 96–118. [5] Andre Andreas as Blass and Yuri Gurevi Gurevich, ch, “Algori “Algorithms: thms: A quest for absolute definitions”; in Current Trends in Theoretical Computer Science, World Scientific, 2004, 195–225; also in Church’s Thesis after 70 Years (eds. A. Olszewski et al.), Ontos Verlag, 2006, 24–57. [6] Andreas Blass and Y Yuri uri Gurevich, “Ordinary inter interactive active small-step algorithms”, ACM Trans. Computational Logic 7:2 (2006) 363–419 (Part I), plus 8:3 (2007), articles 15 and 16 (Parts II, III). [7] Andreas Blass, Yuri Gurevich, Dean Rosenzweig, and Benjamin Rossman, “Interactive small-step algorithms, Logical Methods in Computer Science 3:4 (2007), papers 3 and 4 (Part I and Part II). [8] Nachum Dershowitz and Yuri Gurevich, “A natural axiomatization of  computability and proof of Church’s thesis”, Bull. of Symbolic Logic 14:3 (2008) 299–350.

15

 

[9] Robin Gandy Gandy,, “Ch “Churc urch’s h’s thesis and princ principles iples for mechanis mechanisms”, ms”, In The Kleene Symposium (eds. J. Barwise et al.), North-Holland, 1980, 123– 148. [10] S. Barry Cooper, Benedict L¨oowe we and Andrea Sorbi, editors, “New Computational Paradigms: Changing Conceptions of what is Computable”, Springer, 2008. [11] Erich Gr¨aadel del and Ant Antje je Now Nowack ack,, “Quan “Quantum tum compu computing ting and abstr abstract act state sta te mac machin hines” es”,, Spr Spring inger er Lec Lectur turee Not Notes es in Com Comput puter er Sci Scienc encee 2589 (2003), 309–323. [12] Yuri Gurevich, “Sequential Abstract State Mac Machines hines Capture Sequential Algorithms”, ACM Transactions on Computational Logic 1:1 (2000) 77– 111. [13] Yuri Gur Gurevi evich ch and Sah Saharo aron n She Shelah lah,, “Fi “Fixed xed-poi -point nt ext extens ension ionss of firs firsttorder logic”, Annals of Pure and Applied Logic 32 (1986) 265–280. [14] Andrei N. Kolmogorov, “On the concept of algorithm”, Uspekhi Mat. Nauk 8:4 (1953) 175–176, Russian. English translat translation ion in [25 in  [25,, p. 18–19]. [15] John McCarthy, “A basis for a mathematical theory of computation”, in Computer Programming and Formal Systems (eds. P. Brafford and D. Herschberg), North-Holland, 1963, 33–70. [16] Yiannis N. Moscho Moschovakis, vakis, “Abstrac “Abstractt recursion as a foundation of the theory of algori algorithms” thms”,, in Compu Computation tation and Proof theory theory,, Spring Springer er Lect Lecture ure Notes in Mathematics 1104 (1984) 289–364. [17] Yiann Yiannis is N. Mosc Moschov hovakis, akis, “What is an algorithm? algorithm?”, ”, in Math Mathemati ematics cs Unlimited — 2001 and beyond (eds. B. Engquist and W. Schmid), Springer, 2001, 919–936 919–936.. [18] Yiannis N. Moscho Moschovakis, vakis, “Algorith “Algorithms ms and implementations”, Tarski Lecture 1, March 3, 2008, http://www.math.ucla.edu/ ~ynm/lectures/tlect1.pdf . [19] Yiannis N. Moschov Moschovakis akis and Vasilis Paschalis, “Elementary algorithms and their implementations”, in [10 in  [10], ], 87–118.

16

 

[20] Oron Shagrir, “Effectiv “Effectivee computation by humans and mac machines”, hines”, Minds and Machines 12 (2002) 221–240. [21] Wilfried Sieg, “Calculations by man & machine: Mathematical presentation”, in Proceedings of the Cracow International Congress of Logic, Methodology Meth odology and Philos Philosophy ophy of Scien Science, ce, Kluwe Kluwer, r, 2002, 245–260. [22] Wilfr Wilfried ied Sieg, “Churc “Church h with without out dogma – Axiom Axiomss for computab computabilit ility”, y”, in [10 10], ], 139–152. [23] Wilfried Sieg, “On Computability”, in   Handbook of the Philosophy of    (A. Irvine, editor), Elsevier, 2009, 535-630. Mathematics  (A. [24] Alan M. Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of London Mathematical Society, series 2, vol. 42 (1936–1937), 230–265. Correction, same journal, vol. 43, 544–546. [25] Vladi Vladimir mir A. Uspensky and Alexe Alexeii L. Seme Semenov nov,, “Algorithm “Algorithms: s: Main Ideas and Applications”, Kluwer, 1993. [26] Pier Pierre re Valarc alarcher, her, “Habi “Habilitati litation on `a Diriger des Recherc Recherches”, hes”, Universit Universit´´e Paris Est Cr´eeteil, teil, LACL (EA 4219), D´eepartement partement d’Infor d’Informatique, matique, IUT Font ontaineb ainebleau, leau, France rance,, May 30, 2010.   http://www.paincourt.net/ perso/Publi/hdr.pdf

17