Term paper writing

Turing'sIdeasandMo delsofComputation Eugene Eb erbach

1, Dina Goldin

2, and Peter Wegner

3 1Computer and Information Science Department, University of Massachusetts, North Dartmouth, MA 02747, eeb [email protected] 2Computer Science & Engineering Department, University of Connecticut, Storrs, CT 06269, [email protected] 3Department of Computer Science, Brown University, Providence, RI 02912, [email protected] Summary.Thetheoryofcomputationthatwehaveinheritedfromthe1960's fo cusesonalgorithmiccomputationasemb o diedintheTuringMachinetothe exclusion of other typ es of computation that Turing had considered. In this chapter we present new mo dels of computation, inspired byTuring's ideas, that are more appropriate for to day's interactive, networked, and emb edded computing systems. These mo dels representsuper-Turingcomputation, going b eyond Turing Machines and algorithms. We identify three principles underlying sup er-Turing computation (interaction with the world,in nity of resources, andevolution of system) and apply these principles in our discussion of the implications of sup er-Turing computation for the future of computer science. 1Intro duction:Algorithmiccomputation Alan Turing is known mostly as the inventor ofTuring Machines, whichhe created in an e ort to formalize the notion ofalgorithms. Algorithm:systematic pro cedure that pro duces { in a nite number of steps { the answer to a question or the solution to a problem [2]. This notion well precedes computer science, having b een a concern of math- ematicians for centuries. It can b e dated back to a 9-th century treatise by a Muslim mathematician Al-Koarizmi, after whom algorithms were named. Algorithmic computationrefers to the computation of algorithms. Algorithmic computation:the computation is p erformed in aclosed- boxfashion,transforming a niteinput,determinedbythestartof the computation, to a nite output, available at the end of the com- putation, in a nite amount of time. TuringMachineshavethefollowingprop ertiesthatmo delalgorithmic computation:- their computation isclosed(shutting out the world); - their resources (time and memory) are nite; - their b ehavior is xed(all computations start in same con guration). 2E.Eb erbach, D.Goldin, P.Wegner TheTuringMachinemo delformedthefoundationsofcurrenttheoretical computer science. This is largely due to thestrongTuringThesis, found in p opularundergraduate textb o oks,whichequatesTuringMachineswithal l forms of computation:Strong Turing Thesis:ATuring Machine can do everything a real computer can do [35]. It is little known that Turing had prop osed other, non-algorithmic mo dels of computation, and would have disagreed with the strong Turing Thesis. He did not regard the Turing Machine mo del as encompassing all others. As with many of his other ideas, Turing was far ahead of his time. Only now, with the developmentofnew powerful applications, it is b ecoming ev- ident to the wider computer science community that algorithms and Turing Machines do not provide a complete mo del for computational problem solv- ing.Overview.WestartwithadiscussionofTuring'srichcontributions tocomputerscience,fo cusingonvariousmo delsofcomputation.Next,we present examples of sup er-Turing computation, which is more p owerful than Turing Machines, and discuss the three principles that contradict thealgo- rithmic prop erties ab ove, making it p ossible to derive sup er-Turing mo dels: -interaction with the world; - in nity of resources; -evolution of the system. While the strong Turing thesis denies the existence ofsuper-Turingmo d- els, we explain whyTuring was not the author of this thesis and would dis- agree with it. We show that sup er-Turing mo dels are a natural continuation of Turing's own ideas. We then discuss how sup er-Turing computation might in-

uence computer architecture, programming paradigms and the foundations of computer science. We conclude on a philosophical note. 2Turing'scontributionstocomputerscience 2.1TheEntscheidungsproblemand Turing's Automatic Machines Alan Turing was b orn in 1912, and enrolled at King's College in Cambridge in 1931 as a mathematics undergraduate. He b ecame a fellow of King's College in1934, completingadissertation ontheCentral LimitTheorem.Hethen b ecameinterestedintheEntscheidungsproblem(decisionproblem),oneof themostalluringconjecturesinmathematics,prop osedbytheprominent mathematician David Hilb ert in 1918. Hilb ert's conjecture that any mathematical prop osition could b edecided (proved true or false) by mechanistic logical metho ds was unexp ectedly dis- proved byG odel in 1931, who showed that for any formal theory, there will Turing's Ideas and Mo dels ...3 alwaysbeundecidabletheoremsoutsideofitsreach.Mathematicianslike Alonzo Church [5] and Turing continued G odel's work, lo oking for alternate techniques for proving this undecidability result. Turing's pro of, provided in his 1936 pap er [37], \On Computable Numb ers withanApplicationtotheEntscheidungsproblem"wasbasedonanovel mo del ofautomatic machines(a-machines), which can b e built to carry out anyalgorithmiccomputation.Turingshowedthatdespitetheirversatility, thesemachines cannot computeallfunctions;inparticular, heproved that the now-famoushalting problemis undecidable. Thea-machine mo del consists of: a one-dimensionalerasable tapeof in nite length, capable of storing sym- b ols, one on each cell of the tap e; a read/writetapeheadcapable of moving to the left or right on the tap e, and of retrieving or storing one tap e symb ol at a time at the current tap e lo cation; acontrol mechanismthat maybe in any of a b ounded numb er of states; atransitiontablewhich, given the symb ol under the tap e head and the current state of the machine, sp eci es the next action of the tap e head and the new state of the machine. Attheb eginningofacomputation,themachineisinasp ecialinitial state.Ateachstepofthecomputation,themachine'scontrolmechanism causesonesymboltobereadfromthecurrenttap elo cation.Thecontrol mechanism then lo oks up in the transition table actions that dep end on the value of the retrieved symbolaswell as on the current state of the machine. Itthenwritesanewsymbolatthecurrenttap elo cation,transitionstoa newstate,andmovesleftorrightonecellonthetap e.Thecomputation terminates once the machine reaches a sp ecialhaltingstate.

Finite control

6 -

:::

B B X1 X2 ::: Xi ::: Xn B B ::: Fig. 1.Turing Machine Wenowknowa-machinesasTuringMachines,andthisishowwewill refer to them for the rest of this chapter. Turing Machine computations have the following prop erties: 4E.Eb erbach, D.Goldin, P.Wegner TheTMmo delsclosedcomputation, whichrequires thatallinputsare given in advance; The TM is allowed to use an unb ounded but only nite amount of time and memoryfor its computation; Every TM computation starts in an identicalinitialcon guration; for a given input, TM b ehavior is xed and do es not dep end on time. These prop erties are p erfectly suitable for mo delingalgorithmiccomputation. Note however that they prevent TMs from mo deling directly many asp ects of mo dern computing systems, as we discuss in section 3. Turing Machines were adopted in the 1960's, years after Turing's prema- ture death, as a complete mo del for algorithms and computational problem solving. They continue to serve as a standard mo del of computation to this day.Turing's 1936 pap er has come to represent the birth of computer science, though the motivation and substance of this pap er were entirely mathemat- ical. 2.2Algorithms and the history of the Turing thesis In the early 1930's, the quest to prove (or disprove) Hilb ert's famousEntschei- dungsproblemled to many new classes of functions. G odel de nedrecursive functions.So onthereafter, Churchinvented -calculus)and showed thatit de nes the same class of functions [5]. A third class of functions, those com- putablebyTuringMachines(TMs),wasestablishedbyTuringaroundthe same time, and also proved equivalent to recursive functions([37]). BothChurchandTuringwereinsearchofe ectivewaysofcomputing functions, where \e ectiveness" was a mathematical notion synonymous with \mechanical" and lacking a formal de nition. Church prop osed to identify the notion of an e ectively calculable function withthe notion of a -de nable function. Turing made the same app eal on b ehalf of his machines [37]: Turing's thesis:Whenever thereisane ective method for obtaining the values of a mathematical function, the function can becomputed by a Turing Machine. Veryso onthereafter,TuringestablishedthatChurch'slamb da-de nability and his own machine-based computability are equivalent [37]. Notethatthein nitelengthoftheTMtap eplaysakeyroleinthis result. With a b ound on the length of the tap e, only nitely many di erent con gurationsofthetap earep ossible,reducingtheTMtoa nite-state automaton(FSA). The class of FSAs, corresp onding toregular languages,is known to b e less expressive than the class of TMs. The in nityofTM tape is reconciled with the niteness of the physical world by recognizing that it is a formal mo del rather than an actual machine. Whereas a physical machine can only have a nite tap e, this tap e can b e upgraded to a longer one when needed; hence a prop er mo del for it is one where the tap e is in nite. Turing's Ideas and Mo dels ...5 The equivalence of the three classes of functions ( -de nable,recursive, and Turing-computable) was taken as con rmation that the notion of e ec- tive function computation had nally b een formally captured. The claims of ChurchandTuringareusuallycombinedintoone,knownastheChurch- Turing thesis:Church-Turing thesis:The formal notions of recursiveness, -de nability, and Turing-computability equivalently capture the intuitive notion of e ective computability of functions over integers. However,G odelmuchpreferredTuring'sapproach,sinceitsidenti cation with e ectiveness is more immediate [8]. While this work was purely mathematical, and applied only tofunctions over integers, it had a strong in

uence on the eld of computer science when it emerged as a mature discipline decades later. In particular, the robustness of the notion of e ective function computation has served to give it a central role inthefoundationofcomputerscience.TuringMachinesprovidedthisnew eld with legitimacy on par withphysics and mathematics, by establishing it as the study of a class of concrete and well-de ned phenomena: Physics:study of prop erties of matter; Mathematics:study of quantity and space; Computer Science:study of algorithmic problem solving computable byTuring Machines. While the Church-Turing thesis only applied to the e ectiveness of com- puting functions over integers, it extends easily to functions over nite strings, since strings can b e naturally enco ded as integers. However, it do es not ex- tend to other typ es of computation, such as functions over real-valued inputs, or suchasinteractive computation. Both Church and Turing were aware of this limitation. Whereas Church's concerns did not go b eyond functions over integers,Turing'sconcernsweremoregeneral.Aswediscussnext,healso prop osed machines for interactive computation, distinct from a Turing Ma- chine. 2.3Turing's questforinteraction:ChoiceMachinesandOracle Machines Automaticmachines(a-machines)werenottheonlymo delintro ducedby Turinginhis1936pap er.Inthesamepap er,Turingalsoprop osedchoice machines(c-machines)asanalternatemo delofcomputation.Whereasa- machines op erate ina closed-b ox fashionas ifon\automatic pilot"(hence theirname),c-machinesinteractwithanop eratorsuchasahumanuser duringthecomputation.InTuring'swords,ac-machine's\motionisonly partially determined by the con guration"; in certain con gurations, it stops and \cannot go on until some arbitrary choice has b een made by an external op erator" [37]. 6E.Eb erbach, D.Goldin, P.Wegner Choice machines were intro duced byTuring as an alternative conceptu- alization of computation, one that is interactive. Turing clearly realized that the algorithmic computation of automatic machines is not the only typ e of computation p ossible. However, Turing's goal in [37] was to prove the unsolv- abilityoftheEntscheidungsproblemrather than to set standards for mo dels of computation. Formalization ofa-machines enabled him to reach his goal, so the bulk of the pap er was concerned with them rather than withc-machines. Eventually,a-machineswereadoptedasthestandardmo delofcompu- tation,andc-machinesSomeb elievethatoraclemachines,intro ducedby Turingjustafewyearslater[38],provideaformalizationofc-machines, making them unnecessary. Thereisindeedanimp ortantsimilaritybetweenchoicemachinesand oracles machines: b oth make queries to an external agent during the compu- tation. In the case of an oracle machine, this agentisanoraclerather than a human op erator. This oracle is formally describ ed as a set that can b equeried ab out anyvalue; it returnstrueif the queried value is in this set andfalse otherwise.In ancient Greece,oracleswere p eople whom others consulted for advice; they were b elieved to p ossess access to hidden knowledge that came to them directly from the deities. Just as Greek oracles have sup er-human knowledge, Turing's oracles are meant to representuncomputableinformation obtained from outside the system. Turing sp eci cally excluded the p ossibility that the oracle was an e ective computing entity: We shal l not go any further into the nature of this oracle apart from saying that it cannot be a machine[38]. Sinceoraclescannotbemachines,dotheymo delhumans,suchasthe op eratorsofc-machines?Theset-basedsemanticsoforaclesprecludethis p ossibility. Because they are sets, oracles arestatic, and the outcome of each queryispredeterminedb eforetheoraclemachine(o-machine)startscom- puting. During the computation, the same query will always yield the same answerfromagivenoracle.Clearly,thesamecannotbesaidofhumans, for whom the same question can yield a di erent answer dep ending on their mo o d or some other circumstance. Hence, Turing'schoicemachinesare not justoracle machinesby another name, but a di erent mo del of computation. 2.4Turing's contributiontocryptologyandcomplexity theory: work on Enigma and Colossus During WarWorld I I,Alan Turing worked as a topcryptanalyst andchief consultantattheGovernmentCo deandCipherScho olatBlechleyPark. Byusinghispreviousexp eriencewithciphers,aswellashisknowledgeof combinatorics,co detheoryandstatistics,Turingcontributedsubstantially to breaking the co de of theEnigma, the encrypting/decrypting machine that Turing's Ideas and Mo dels ...7 the German navy used for all its radio communications. More imp ortantly, he mechanized the decryption pro cess, using an electromechanical machine of his invention { theTuring Bombe. Later, a much faster device { theColossus {was deployed; it can b e considered the world's rst electronic computer. Just as the primary purp ose of Turing Machines was to show that there existproblems whichcannot b esolved bymechanical (algorithmic) means, Turing'sworkatBlechleyParkdealtwith ndingthemechanicalmeans tosolveproblemsthatarehard,butnotimp ossible.Theartofbreaking co desrequiredtheabilitytodealwiththeintricatecomplexityofmulti- level encryption algorithms. This was Turing's direct practical contribution tocryptography andindirectlytocomplexitytheory.Infact,hepioneered whatnowwould b ecalled aninteractive randomized approach to breaking ciphers, byintelligent guessing the key based on the statistical evidence, and exploring the lo opholes in the Germans' use of Enigma. This, together with thesp eedoftheBombeandthenColossus,slicedthroughtheintractable search space of the problem. Turing was also chief liaison b etween American and British cryptanalysts. The work of British scientists at Blechley Park was highly regarded by British primeministerWinstonChurchill,andrecognizedasoneofthedeciding factorsinwinningthewar.Howeverthatwork,b ecauseofitstopsecret nature, remained unpublished and unknown for manyyears. 2.5Turing'sworkonACEasaprecursorofgeneralpurp ose universal computers After the end of the war Turing joined the National Physical Lab oratory in 1945 to work on theAutomatic Computing Engine (ACE).ACE was one of several p ostwar attempts to build a working computer; other contemp orary pro jectsincludeEDVACandIAScomputersintheUSA(atUPennand Princeton, resp ectively), and Wilkes EDSAC machines at Cambridge in the UK.Turing's plan was to build the rst programmable general-purp ose com- puter, whichwould keep b oth the co de and the data in memory, and execute the co de over the data. Turing drew his inspiration for ACE directly from his earlier theoretical work. As he said in a lecture to the London Mathematical so ciety [40], Machines such as the ACE may b e regarded as practical versions of [the Turing Machine]. There is at least a very close analogy. In particular, Turing saw a direct parallel b etween the capabilityof ACE toacceptandexecuteprograms, andhisnotionofauniversalTuringMa- chine, whichwas part of his 1936Entscheidungsproblempap er [40]: the complexity of the machine to b e imitated is concentrated in the tap e[oftheUniversal TuringMachine] anddo es notapp ear inthe 8E.Eb erbach, D.Goldin, P.Wegner universal machine prop er... This feature is paralleled in digital com- puting machines such as the ACE. They are in fact practical versions oftheuniversal machine...Whenany particular problemhastobe handled the appropriate instructions... are stored in thememory of the ACE and it is then `set up' for carrying out that pro cess. Turing'svisionofaprogrammablecomputerisinstarkcontrasttoall other computer designs of that time, including the Colossus and the ENIAC, whichrequiredamanualrecon gurationforeverynewcomputation.Itis notsurprisingthatACE'scomputerarchitecturewasverydi erentfrom, and more complicated than, other computer designs of the time.ACE was planned to b e the fastest (1 microsec. clo ck cycle) and having thelargestmemoryintheworld(60,000bits).ACE'sdesign[39]involved many pioneering concepts that b ecome standard part of computer architec- turedecadeslater.ACEwouldhavealargesetof32general-purp ose reg- isters,andasimplehardware systemimplementingfastbasicminimumof arithmetical and Bo olean functions; Turing b elieved that other functions (in- cluding

oating-p ointarithmetic)shouldbeprogrammed.Thispioneering approach to hardware design did not receive due recognition until the early 1980's, when it b ecame known asRISC(Reduced Instruction Set Comput- ers).Turing also pioneeredsubroutinehierarchies(then calledinstructionta- bles) which can b e viewed as a precursor to high-level programming languages. Turing inventedcalling stacks forinvoking them(thencalledburyandun- buryroutines).Heprop osedself-mo di ableco detoimplementconditional branching. By contrast, the comp eting designs of the EDVAC, the IAS, and the EDSAC machines were based onaccumulatorarchitecture, whose design was relatively straightforward. Turing's vision to build a machine that would show \genuine intelligence" went far b eyond the pro ject's original mission of doing \large di cult sums" andfrightenedhissup eriors.TheadministrationoftheNationalPhysical Lab oratories, under the directorship of Sir Charles Darwin (grandson of the well-known English naturalist) found Turing's ideas to o revolutionary, esp e- cially in the context of p ostwar British frugality. In retrosp ect, the ideas emb o died in the design of ACE make p erfect sense. In time, many asp ects of Turing's ACE design have proved as valuable as the TuringMachineandtheTuring test(section2.7).Butwithouttheb ene t ofhindsight,Turing'scontemp orariesworkingonsimilarpro jects,suchas MauriceWilkes,wereskepticalwhetheramachineofsuchcomplexityand with such revolutionary architecture would ever work. The ACE pro ject never received the funding it sought, and the disapp ointed Turing left the National Physical Lab oratory in 1948 for the University of Manchester. Turing's Ideas and Mo dels ...9 2.6Turing'sUnorganizedMachinesasaprecursorofneural networks,evolutionarycomputationandreinforcement learning BeforeleavingforManchesterin1948,Turingpro duceda nalrep orton ACE whichcanalso b eviewed asa blueprintfor thefuture eldofneural networks. TitledIntel ligent Machinery[41], this rep ort was left unpublished until 1968, b ecause Darwin considered it to b e a \scho olb oy essay" not suit- able for publication.In this rep ort, among other futuristic ideas, including rob ots taking coun- try walks, Turing prop osed new mo dels of computation, which he calledun- organized machines (u-machines). There were twotyp es of u-machines, those based onBoolean networksand those based on nite state machines[41,36]. Turingto okhisinspirationfromtheworking ofthehumancortex, andits ability for self-adaptation. A-typ eandB-typ eu-machineswereBo oleannetworksmadeupof two-input NAND gates (neurons) and synchronized by global clo ck; the numb er of neurons remained xed. While in A-typ e u-machines the con- nections b etween neurons were xed, B-typ e u-machines had mo di able switchtyp e interconnections. Starting from the initial random con gura- tionand applying a kindof geneticalgorithm, B-typ e u-machines were supp osed to learn which of their connections should b e on and which o . P-typ eu-machines were tap eless Turing Machines reduced to their Finite State Machine control, with an incomplete transition table, and two input lines for interaction: thepleasureand thepainsignals. For con gurations with missing transitions, the tentative transition to another state could b e reinforced by pleasure input from the environment, or cancelled in the presence of pain. In his B-typ e u-machines, Turing pioneered two areas at the same time: neural networksandevolutionary computation; his P-typ e u-machines repre- sentreinforcement learning.However, this work had no impact on these elds, duetotheunfortunatecombination ofTuring's deathandthetwenty-year delay in publication. As a result, others got the credit for these ideas: Neuralnetworksare typicallycredited toPittsand McCullo chneurons (1943) [21] and Rosenblatt's p erceptron (1958) [30]. Evolutionarycomputationis typically credited to Holland's work (1968) [1] on genetic algorithms, although it is acknowledged that the area has b een rediscovered around ten times b etween the 1950's and 1960's [14]. Reinforcementlearninghas b een b eenattributed to Minsky and Farley and Clark pap ers from 1954 [26,13], or Samuel's checkers program from 1959 [32]. TuringwasconvincedthathisB-typ eu-machinecansimulatehisUni- versal Turing Machine, though he never provided a formal pro of. In order to 10E.Eb erbach, D.Goldin, P.Wegner simulate the in nite tap e of a Turing Machine, a u-machine with an in nite numb er of neurons would b e needed. This is due to thediscretenature of the neurons, whichwere based on two input Bo olean NAND gates. By contrast, tworeal-valuedneurons are su cientto model aTuring Machine. B-typ e u-machines were de ned to have a nite numb er of neurons, and it is not clear whether Turing was aware that in nitely many neurons were needed for the simulation. This inconsistency would certainly have b een un- covered when working on the formal pro of. But p erhaps Turing was aware of it, and exp ected to have no problems extending his de nitions to the in nite case. 2.7Turing as afounder of Arti cial Intelligence Inthissection,weexploreTuring'scontributionstoArti cialIntel ligence (AI), of which he is considered one of the founders. Turing's interest in AI can b e traced at least to his nal rep ort on ACE, where he envisions \intelligent" b ehaviors of future generations of computers [41]. At that p oint, intelligence was viewed mainly in terms of asearchstrategy;anintelligent agentisone that can nd the b est action based on current knowledge. Turing identi edchess as a go o d starting p oint for exploring intelligent search strategies. Ever optimistic ab out the progress of computing research, Turing estimated in 1941 that computers would b e able to b eat human chess champions by ab out 1957. To make progress towards this goal, Turing and David Champ ernowne wrote theTurochampchess program in 1948, applying a search strategy known asMinimaxtowards cho osing the next move. Even- tually,computerswerebuiltthatcouldb eathumanchesschampions,but itto ok 40 years longer thanTuring predicted.UsingavariantofMinimax known as the alpha-b eta search, a sup ercomputer namedDeep Blueb eat the world chess champion Garry Kasparov in 1997. Turingexp ectedcomputerstomatchhumansnotonlyinchess,butin every intelligent endeavor. In a famous 1950 pap er [42] Turing provo catively led with the question \Can Machines Think?" and prop osed his famous test for intelligence. Now known as theTuring Test, it is based on the \imitation principle":TuringTestforAI:Ifacomputer,onthebasisofitswrittenre- sponses to questions, could not be distinguishedfrom a human respon- dent, then one has to say that the computer is thinking and must be intel ligent. The imitation principle, inspired by the then-p opular b ehaviorist scho ol of thought, stated that there was no way to tell that other p eople were hink- ing" or \conscious" except by the pro cess of comparison with oneself. Thus if computers b ehaved like p eople (i.e., the \black-b ox" approach, indep endently how they are internally built),they should b e credited with human-like at- tributes of consciousness, intelligence, or emotion. As the result, a new eld of Turing's Ideas and Mo dels ...11 arti cial intel ligencegrew up around the problems of de ning and duplicating consciousness and intelligence. TheTuring test,andtheearly arti cial intelligenceresearch whichwas based on it, attracted much criticism. In order to explore the arguments of thecritics,itisusefultobreakdownthequestion\CanMachinesThink" into two separate questions: (Extensionality)Canmachinessimulatethebehaviorassociated with thinking? (Intensionality)Canwesaythatmachinesthatsimulatethinking are actual ly thinking? Turing answered \yes" to b oth of these questions, while the critics were divided into those who b elieved that machines cannot simulate thinking (ex- tensionalskeptics)andthosewhob elievedthatsimulationwithoutunder- standing do es not capture the essence of thinking (intentional skeptics). Ex- tensional skeptics place limits on the expressivepower of computation, while intensionalskepticsrejecttheb ehavioristviewthatunobservableinnerat- tributes are irrelevant. The second questionhas a metaphysical

avor, andis therefore outside the scop e of a computer science inquiry.However, the rst question is very muchofinterest to computer scientists, esp ecially when rephrased as:\Can machines act intel ligently?"We explore this question in the context of inter- active mo dels of computation in section 5.1. 2.8Turing as aprecursor of Arti cial Life In1952,Turingpublishedapap eronmorphogenetictheoryintheRoyal So cietyPro ceedings[43].Turingtriedtocapturethegrowthandpattern o ccurrencesinplantsandanimals,describingthemasdynamicalsystems, in the form of nonlinear di erential equations. Turing was fascinated by the app earance in nature of the Fib onacci numb ers series in the leaf arrangements and

ower patterns. This work, along with that of John von Neumann, can b e considered as precursorsofthereareaofarti ciallifeandofbiogeneticcomputing.Von Neumann's work considered the universal computability and universal con- structibilityofcellularautomata,basedonhistheoryofself-repro ducing automata from 1952.BothVonNeumannandTuring'sworkonarti cialliferemainedun- nishedb ecauseoftheauthors'death.However,ArthurBurkseditedand published von Neumann manuscript in 1966 [45], while Turing's work in this area remained practically unknown. As a result, usually only von Neumann is given full credit for founding the area of arti cial life. 12E.Eb erbach, D.Goldin, P.Wegner 3Sup er-TuringComputation InthissectionwediscusswhyTuringMachines(TMs)donotrepresenta complete theory for problem solving. In particular, the three prop erties of TM computation,whilep erfectlysuitedformo delingalgorithmiccomputation, act to prevent it from mo deling directly many asp ects of mo dern computing systems: TM computations areclosed, which requires that all inputs are given in advance; TM computations are allowed to use an unb ounded but only nite amount of time and memory; TM computations all start in an identicalinitial con guration; for a given input, TM b ehavior is xed and do es not dep end on time. Bycontrast,mo derncomputingsystemspro cessin nitestreamsofdy- namical lygeneratedinput requests. They are exp ected to continue comput- inginde nitelywithout halting. Finally, their b ehavior ishistory-dependent, with the output determined b oth by the current input and the system's com- putation history. A large p ercentage of the computer-science community b elieves that while Turing Machines are not very convenient to mo del some asp ects of computa- tion, they nevertheless cover all p ossible typ es of computation. As a conse- quence, it is considered futile to lo ok for mo dels of computation going b eyond TMs. In this section, we identify the source of this common misconception, and discuss three di erent directions for extending TM computation to sup er- Turing computation:interaction,in nity, andevolution. Theseextensionscanbecontrastedwiththemanyfailedattemptsto breakoutofthe\Turingtarpit"ofTM-equivalentcomputationknownto us from theory of computation textb o oks, such as increasing the number of Turing Machinetap es. Thoseattemptsalways remained inthealgorithmic paradigm,andconsequentlyweredo omedtofallwithintheb oundsofthe Church-Turing thesis. By contrast, each of these three extensions lifts com- putation out of the algorithmic paradigm, by rede ning the space of compu- tational problems. What is b eing computed is no longer just xed functions from integers to integers (or some equivalent), but also non-algorithmic com- putational problems, or tasks. 3.1The strong interpretation of the Turing thesis AUniversal Turing Machineis a sp ecial Turing Machine intro duced byTur- ing in [37], that can simulate any other Turing Machine { hence its name. It served as theinspiration for thenotion of general-purp ose computing (sec- tion 2.5).The principle of universality can easily b e extended to any other class of machines for computing functions. As long as each machine in this class can Turing's Ideas and Mo dels ...13 b e captured by a nite description which de nes what this machine \would do in every con guration in which it might nd itself " [40], a Turing Machine can b e created to simulate all machines in this class: Universalitythesis:Anyclassofe ectivedevicesforcomputing functions can be simulated byaTuring Machine. Both the Turing thesis (section 2.2) and the Universality thesis constitute fundamental yet distinct contributions to the theory of computation, which wasestablishedasaseparateareaofcomputerscienceinthe1950's.Itis astonishingthattheseresultswereaccomplishedbyTuringsimultaneously in his seminal pap er on Turing machines [37], which predated any computers. The original digital computers were infactdevicesfor computingfunc- tions, much likeTuring Machines; their architecture did not allowanyinter- action during the computation. This led to the equating of computers with algorithmiccomputation,andtothefollowing(incorrect)corollaryofthe universality thesis: Universality corollary:Any computer can be simulatedbyaTuring Machine. Whiletheuniversalitycorollary istruewhencomputersarelimitedtothe task of computing functions or algorithms, it do es not apply in the context of to day's highly interactive computing systems such as the Internet. Whenthe rstundergraduatecomputersciencetextb o okswereb eing written in the 1960's, Turing's contributions to theory of computation needed to b epresented in a more accessible fashion. As a result, the Turing thesis and the Universality corollary were glibly combined into one, resulting in the following (incorrect)strong interpretationof the Turing thesis that one sees in undergraduate textb o oks:StrongTuringthesis:Wheneverthereisane ectivemethodfor solvingaproblemwithacomputer,itcanbecomputedbyaTuring Machine. Thecurrentgenerationofcomputerscientistshasabsorb edthestrong interpretation of theTuring thesis withtheir undergraduate education, b e- lievingitaheresytoquestionit.However,thisinterpretationneedstobe distinguished from the actual contributions of Turing or his contemp oraries on which it is based. There is no question that b oth the Turing thesis and the Universality thesis only applied in the realm of functions over integers. When thesesourcesofthestrongTuringthesisarereexamined,itsp ositionasa dogma ofcomputer science b ecomes shaky. Thestrong Turing thesis needs to b e recognized as incorrect { despite common b elief to the contrary. 3.2Driving Home From Work In this section, we discuss the problem ofdriving home from work(DH W) [46], which cannot b e solved algorithmically, but is nevertheless computable. The 14E.Eb erbach, D.Goldin, P.Wegner existence of computable problems that a Turing Machine cannot solve con- tradicts the strong Turing Thesis, proving it incorrect. TheDH Wproblem.Consider anautomaticcarwhose task isto drive us across town from work to home. The output for this prob- lem should b e a time-series plot of signals to the car's controls that enableittop erformthistaskautonomously.Howcanwecompute this output? In thealgorithmicscenario, where all inputs are provideda prioriof com- putation, the input to theDH Wproblem includes a map of the city which mustbepreciseenoughtocomputetheexactpaththecarwilltake.This scenario, typical ofAI approaches to similar problems through most ofthe second half of the last century, is illustrated in Figure 2.

Fig. 2.Driving home from work: the algorithmic scenario Notethatinadditiontothemap,theinputneedstosp ecifytheexact roadconditionsalongtheway,includingeveryp otholeandeverygrainof sand. By the principles ofchaoticbehavior, such elements can greatly a ect the car's eventual course { like the Japanese butter

y that causes a tsunami on the other end of the world. In astaticworld, this input is in principle sp eci able, but the real world is dynamic. The presence of mutable physical elements such as the wind and the rain a ect the car's course, b oth directly (as the wind blows at the car) and indirectly (as the wind shifts the sand in the path of the car). It is doubtful whether these elements can b e precomputed to an accuracy required for the DH Wproblem. We can remain optimistic until we rememb er that the world also includes humans, as p edestrians or drivers. Toavoid collisions, wemust precompute theexact motionsofeveryone whomightcomeacross ourway.Toassume thathumanactionscanbecomputedaheadoftimeistantamounttoan assertionoffatalism{ado ctrinethateventsare xedinadvancesothat human b eings are p owerless to change them { clearly b eyond the purview of any computer scientist. Therefore, wemust conclude that theDH Wproblem is unsolvable: Computational tasks situated in the real world which includes human agents are not solvable algorithmical ly. Turing's Ideas and Mo dels ...15 Nevertheless,theDH Wproblemiscomputable{interactively,witha driving agent. In this scenario, the agent's inputs, orpercepts[31], consist of a stream of images pro duced by a video camera mounted on the moving car. The signals to the car's controls are generated by the agenton-linein resp onse to these images, to avoid steering o the road or running into obstacles.

Fig. 3.Driving home from work: the interactive scenario This change in the scenario, illustrated in gure 3, is akin to taking the blindfolds o the car's driver, who was driving from memory and b ound to a precomputed sequence of actions. Now, he is aware of his environment and uses it to guide his steering.TheDH Wexampleprovesthatthereexistproblemsthatcannotbe solved algorithmical ly,but are nevertheless computable. Notethatwehavenotjustrestructuredtheinputs,butalsochanged themodelofcomputationas well as the notion of acomputationalproblem. Algorithmic problems are computedo -line;the output is generatedbefore the driving b egins. Interactive problems are computedon-line; the output is generated as the car drives. Furthermore, the inputs and outputs for interac- tive computation are interdep endent; decoupling them, such as replacing the video camera witha prerecorded videotap e oftheroad, will b etantamount to putting the blindfolds back on the driver. 3.3Sup er-Turing computation We refer to computation that violates the strong interpretation of the Turing thesis (section 3.1) assuper-Turing computation;driving home from workwas an example.Sup er-Turing computation:al l computation, including that which cannot becarried out by a Turing Machine. Sup er-Turing computation is morepowerfulthan thealgorithmic computa- tion of Turing Machines, in that it can solve a wider class of computational problems. Our use of the termsuper-Turingis meantto have a p ositive con- notation.Wedonotconsiderthehigherexpressivenessofnewcomputing mo delsassomethingexcessive,butratherasadesirablefeature,andasa natural continuation of Turing's ideas. 16E.Eb erbach, D.Goldin, P.Wegner We identify three principles that allow us to derive mo dels of computation more expressive than Turing Machines: -interaction with the world; - in nity of resources; -evolution of the system. We discuss these principles next. Interaction with the environment.In his 1936 and 1939 pap ers, Turing showed that Turing Machines were only appropriate for computing recursive functions over integers, and prop osedchoicemachines(c-machines) andor- acle machines(o-machines) as alternate mo dels that supp orted richer forms of computation than Turing Machines [37,38]. Both of these mo dels extend Turing Machines byinteraction. Interactive computationinvolves interaction with an external world, ortheenvironmentofthecomputation,duringthecomputation{ rather thanbeforeandafterit, as in algorithmic computation. Driving home from work (section 3.2) is an example of interactive compu- tation. Asanother example,consider missile tra jectory computations. This was an early application of computers, dating to World War I I. In the original (algorithmic) scenario, the input includes the lo cation of the target and the

ightcharacteristics of the missile; the output is the direction and angle at which to launch the missile so it (hop efully) hits the target. By contrast, the computationforto day'ssmartmissilesisinteractive.Oncelaunched,they continue to monitor their progress and to adjust their tra jectory to remain on target. In the presence of wind gusts and air pressure changes, interaction has proven necessary to assure accurate long-distance targeting. Twotyp esofinteractivecomputationcanbeidenti ed[47].Sequential interactiondescrib esthecomputationofasingleagent,suchasthesmart missile, as it interacts with itsenvironment. All inputs are interleaved into a singleinputstream, and are pro cessed sequentially.Bycontrast,distributed interactioninvolvesmanyagentsworkingconcurrentlyinanasynchronous fashion,withmultipleautonomouscommunicationchannelswhichcanbe automatically recon gured during the computation.Whilealgorithmicproblemsaresolvedbyalgorithmicsystemssuchas TuringMachines,interactiveproblemsarethosesolvedbyinteractivesys- tems:Algorithmic problem: transforming input strings to output strings Interactiveproblem: carrying out a computational task or service The intuition that computing corresp onds to formal computabilitybyTuring machines breaks down when the notion of what is computable is broadened to Turing's Ideas and Mo dels ...17 include interaction. Though the Church-Turing thesis is valid in the narrow sense that Turing Machines express the b ehavior of algorithms, the broader assertion that algorithms precisely capture what can b e computed is invalid [47]. By interacting with the external world, interactive systems can solvea larger class of problems, such as driving home from work or the smart missile. Interactive computation has b een captured under many di erent forms, suchasconcurrent,distributed,orreactivecomputation. It is a di erent com- putationalparadigm,whichexpandsthenotionofacomputationalprob- lem [46,49]. The paradigm shift from algorithms to interaction captures the technology shift from mainframes to workstations and networks, from num- b er crunching to emb edded systems and user interfaces, and from pro cedure- oriented to ob ject-based and distributed programming. Greaterproblem-solvingpowerissynonymouswithgreaterexpressive- ness. An argument for greater expressiveness of interactive mo dels was made byMilner[24],wherehestatedthatthe -calculusneedstobeextended tomo delinteractivesystems.Sincethe -calculusmo delsallalgorithmic computation, it follows that interactive computation is more expressive. An alternateapproachtoprovingthesameresult,basedonPersistentTuring Machines, can b e found in [18]. When an interactive system consists of many autonomous (or asynchronous) concurrent comp onents, it cannot in general b e simulated byinterleaving the b ehaviors of its subsystems. Distributed interaction is more expressive than sequential interaction, just as sequential interaction is more expressive than algorithmic com- putation. Multi-comp onentsystemsarecapableofricherb ehaviorsthansequential agents.Theirb ehaviorsareknownasemergent,sincetheyemergeasthe prop erty of the whole system without b eing present, in whole or part, in any ofitscomp onents.Theexistenceofemergentb ehaviorswasdemonstrated bySimon[34];whilehediscussedcomplexsystemsingeneral,interactive computing systems are a sp ecial class of such systems. In nityofresources.TheTuringMachinemo delcanbeextendedby removing anya priorib ounds on its resources, p ossibly resulting in: an in nite initial con guration, an in nite architecture, in nite time, an in nite alphab et. The impracticality of p ossessing in nite resources should not b e an obstacle here. Just as Turing allowed in nite length of tap e in Turing Machines, and cellular automata are allowed to contain in nitely many cells, we can allow an in nite numb er of tap es or states in our mo dels of computation. And just 18E.Eb erbach, D.Goldin, P.Wegner asthein nitelengthoftheTuringMachinetap eallowsformoreexpres- sivenessthanb ounded-tap emo dels(section2.2),theseextensionsincrease expressiveness yet further. Below, we discuss the four di erenttyp es ofextension by in nity. Persistenceofmemorybetweencomputationisrepresentedbycellular automata, PersistentTuring Machines [17,18], and $-calculus [10]. When the Turing Machine preserves some information from one computation to the next, we can obtain an unb ounded growth of its initial con guration, and we need to mo del it with anin nite initial con guration. Whenmo delingmassivelyparallelscalablecomputersortheInternet, we do not put restrictions on the numb er of computing elements. Allow- ing in nitely many computing elements (in nityofarchitecture) can b e mo deledbyanin nitenumberofTuringMachinetapes,oranin nite number of read/write heads, resulting in an unb ounded parallelism. The approachisrepresentedbycellularautomata[45],discreteneuralnet- works with an in nite numb er of cells, random automata networks [15], -calculus [23], and $-calculus [10]. Just as the large memories of digital computers provide a practical approximation to Turing Machines' in nite tap es, so do es system scalability, such as scalable massively parallel com- putersordynamicnetworksofautonomousagents,provideapractical approximation to the in nite architecture of sup er-Turing computers. Any system that is not exp ected to halt on its own needs to b e mo deled by allowingin nite time. This applies to manyinteractive systems such as op erating systems, servers on the Internet, software agents or viruses, or evolutionary programs. Allowingin niteprecisionisrepresentedbyanalogcomputers,neural networks and hybrid automata [33]. Analog computers or real-value neu- ral networks can b e interpreted as op erating on uncountable alphab ets { each real numbercorresp onding tooneuniquesymbol ofthealphab et. Alternately, real numb ers can b e simulated by in nite strings over nite discrete alphab ets, but then we trade one typ e of in nity for another. For thesamepracticalreasonswhyevolutionaryprogramsareterminated aftera nitenumberofgenerations,currentdigitalcomputersrequire truncating all real numb ers to nite precision. Evolutionofthesystem.Extensionbyevolutionallowingthecomput- ingdevicetoadaptovertime.TheTuringMachinestopsb eingstaticbut continuously evolves, soitisabletosolve newtyp esofproblems.Turing's unorganized machine learning [41] can b e viewed as an example of this. He prop osed strategies, now known asgenetic algorithms,toevolve the connec- tions b etween the neurons within the u-machine. In general, evolution can b e done by upgrade of either hardware or soft- ware, by self-adaptive, learning programs, or evolvable, self-repro ductive hard- ware. Evolution may happ en in continuous or discrete steps, leading p ossibly Turing's Ideas and Mo dels ...19 to capabilities previously not present. In particular, an ordinary Turing Ma- chine can evolve to one with an oracle, or to a p ersistent TM that do es not reinitialize its tap e b efore computations, or one that replicates its tap es in- de nitely. The p ossibilities of evolution (the typ es of variation op erators) are endless.Evolution canbecontrolled byinteraction withtheenvironment, or by some p erformance measure, suchasits tness,orutility,orcost. The evolu- tion principle is used bysite and internet machines[44],$-calculus[10], and Turing'su-machines[41]. Discussion.The three principles wehave identi ed and discussed ab ove are consistentwiththeworkofotherresearchers inthisarea. Forexample,in theirsearchformoreexpressivemo delsofcomputation,vanLeeuwenand Wiedermann [44] stressed: interaction of machines; in nity of op erators; non-uniformity of programs (upgrade of computer hardware and system software), incorp orated here as part of the evolution principle. Each of the three extensions is su cient to obtain mo dels more expres- sive than Turing Machines. However, the three approaches are not disjoint; it is imp ossible to haveevolution without in nity, or to b ene t from in nity withoutinteraction. Itisnotclear whetherour listofp ossibleTuringMa- chine extensions is complete. At this p oint, we are rather interested that such extensions are reasonable, and that they cover all mo dels discussed in next section. 3.4Examples of sup er-Turing computation Wenow present three examples of sup er-Turing computation requiring new mo dels of computation going b eyond Turing Machines: dynamic interaction of clients and servers on the Internet; mobile rob otics; in nite adaptation of evolutionary computation. DistributedClient-ServerComputation.The Internet connects many separate computer networks. Theclient/servermodelisatypical paradigm used by computer networks. In this mo del, servers provide services to mul- tiple clients (e.g., in the form of web browsers); the clients query the server simultaneously, unaware of the presence of other clients. With the Internet, each client can gain access not just to its lo cal server, but to any server on the Internet, and interact with it as with its lo cal server. 20E.Eb erbach, D.Goldin, P.Wegner The resulting concurrentinteraction of multiple clients and servers, with adynamiccon gurationofcommunicationlinksandno des,cannotbede- scrib ed as a Turing Machine computation, whichmust b e sequential, static, and with all input prede ned.It can b e argued that everything is a matter of providing the prop er initial descriptionoftheworldonthein nitetap eoftheTuringMachine.While there is no b ound on the length of the input string, the input for any given probleminstancemustbe niteandprede nedaheadofcomputation.By contrast, the p otential interaction streams for dynamic systems may not only b e in nite, but even non-enumerable [46,47]. The input values in this in nite dynamic stream dep end on the current state of a p otentially ever-changeable and uncomputableworld, whichinturndep endson theearlier outputval- ues of the interactive system. Thus Turing Machines can only approximate interaction on the Internet, but cannot b e used as its precise mo del. Mobilerob otics.Mobilerob otscanbeviewedascomputersaugmented withsensors and actuators to p erceive theirenvironment and to physically act up on it. Rob ots interact with environments which are often more complex than rob ots themselves; in fact, the environments can b e noncomputable, e.g. when they include human actors. Theoriginalapproachofarti cialintelligence,nowknownasGOFAI (go o d old fashioned arti cial intelligence), was to implement the rob ot algo- rithmically.Deliberative symbolic roboticsprecomputed all the rob ot's actions b efore anywere carried out, enco ding the rob ot's environment as prede ned input. It is not surprising that GOFAI failed miserably with mobile rob ots. If the environment can b e noncomputable, it can neither b e prede ned, nor computed using a Turing Machine. This is not just an issue of the enor- mouscomputationalcomplexityrequiredtobuildgoodmo delsofreality, butoftheimp ossibilityofdoing itin nitetimeusing niteenco dings,as inalgorithmic computation. Heeding Bro oks' p ersuasive arguments against the algorithmic oyworld" approach for building reactive rob ots [3], AI has madea paradigm shiftinthelast decade towards theinteractive approach for building intelligent agents. Evolutionary computation.Turing Machines have problems with captur- ing evolution, b oth natural and that simulated on computers, b ecause Evolutionarycomputationcanbeundersto o dasaprobabilisticb eam search, lo oking for thesolution withaglobally optimalvalue ofthe tness function.The tnessfunctionrepresents thequalityofthesolution,andis obtained by the pro cess of interaction of the solution with its environment. Populationsofsolutionsandevolutionaryalgorithmsarechangedineach generation,andtheprobabilisticsearchforasolutionis,inageneral,an in nite pro cess. Turing's Ideas and Mo dels ...21 When the b est solutions are preserved from generation to generation (the so-calledelitist strategy), evolutionary computation is guaranteed to converge to its goal in the in nity; otherwise, there is no guarantee that the goal will b e reached. Usually,evolutionary computation is terminated after a nite num- b er of generations, pro ducing approximate solutions. The halting of genetic algorithmsisenforcedbythenecessityto tthemtotheTuringMachine mo del of computation, with its niteness restrictions.An in nite pro cess cannot b e prop erly captured using nitary means (al- gorithms and Turing Machines). The lack of nitary termination applies also to reactive systems (op erating systems and servers). When viewed as a com- puting system, the Internet also escap es nitary description; its size, as mea- sured by the numb er of no des, in principle has no b ounds and can \outgrow" any nitedescriptionthatwemaydeviseforit.Thisisanalogoustothe fact that Turing Machines need an in nite tap e for their expressiveness (sec- tion 2.2) even though their tap e contents is always nite. 4Mo delsofsup er-Turingcomputation In this section we discuss three formal mo dels of sup er-Turing computation: PersistentTuringMachines,the -calculusandthe$-calculus.Attheend of this section we presentanoverview of some other sup er-Turing mo dels of computation, for a more complete p ersp ective. Regarding the feasibility of implementing sup er-Turing mo dels, we note thatthesamecriticismappliestoTuringMachines.In1936,whenTuring Machines were invented, no one knew how to build a computer. Even now, whendigitalpro cessorsareubiquitous,noonehasimplementedaTuring Machine, since that would require in nite memory. While technically not implementable (due to the in nite size of their tap e), Turing Machines serveas avery useful theoretical to ol for understanding the algorithmic computation of digital computers. Similarly, sup er-Turing mo dels are useful for providing a theoretical understanding of sup er-Turing computa- tion that involves elements ofinteraction,in nity, andevolution(section 3.3). 4.1PersistentTuring Machines PersistentTuringMachines(PTMs)areamo delofsequentialinteractive computationobtained by a minimal extension of the Turing Machine mo del [17,18]. While the \hardware" (syntax) of the PTM is not new, the wayweinterpret its computation (semantics) is. A PTM is a 3-tap e Turing Machine, with an input,anoutput, and awork tape. It continuously interacts with its environ- ment during the computation, pro cessing a stream ofinputsthat are dynami- cally generated by the environment, and pro ducing the corresp onding stream ofoutputtokens.Up onreceivinganinputtokenfromitsenvironment,the 22E.Eb erbach, D.Goldin, P.Wegner PTM computes for a while and then outputs the result to the environment, and this pro cess is rep eated forever. A PTM ispersistentin the sense that its work-tap e contents (its \mem- ory") is maintained from one computation to the next. Hence, initial con g- uration of the PTM is not identical for each input token, as it would b e for aTuring Machine. Since the value of the output dep ends b oth on the input andthememory,PTMsexhibithistory-dep endentb ehaviorthatistypical of interactive computation, but imp ossible for algorithmic computation (sec- tion 3).The following is a simple yet practical example of a PTM, ananswering machine(AM).AM'smemoryisthetap eoftheansweringmachine;itis unb ounded. AM's computational steps are expressed byaTuring computable function mapping the pair (input token, current memory) to the pair (output token, new memory): Example 1.Ananswering machineAMis a PTM whose work tap e contains a sequence of recorded messages and whose op erations arerecord,playback, anderase. The Turing-computable function forAis: fA

(recordY, X) = (ok, XY);fA

(playback, X) = (X, X); fA

(erase,X) = (done, ). ToillustrateAM'sabilitytoexpresshistorydep endentb ehavior,consider the input stream(recordA,playback,recordB,playback,:::); the corresp onding output stream is(ok,A,ok,AB,:::). Thesame inputtoken (playback)generated di erentoutputtokens(Aand AB) when called at di erent times, b ecause of the di erent op erations that preceded it.The notion ofequivalencefor PTMs isobservational,based only onthe observable asp ects of its b ehavior: inputs and outputs; memory is not consid- ered observable. As the example ab ove shows, the whole input stream needs to b e observed, rather than just the current token as for a Turing Machine. The resulting notion of equivalence is analogous to that ofbisimulationfor concurrent processes. Alternatenotionsofequivalencecanbede ned,basedon nitetrace observationsratherthanin nitestreamobservations.Infact,thereisan in nitehierarchyofsuccessively nerequivalenceclassesforPTMs,when observed over nite stream pre xes. This is in contrast to Turing Machines, which admit only one notion of equivalence, corresp onding to the equivalence of the function b eing computed. Turing's Ideas and Mo dels ...23 The answering machine example illustrated how PTM constitutes a nat- ural mo del for sequential ob jects. Mobile intelligent agents are also naturally mo deled by PTMs. Dynamically b ounded input and output streams allowus to express uncertaintyofbothsensors and actuators, whilethecontents of the p ersistentworktap e \evolves" to re

ect the agent's changingstateas it adapts to its environment. While distributed interaction is not captured by PTMs, one can imagine howtode nesystemsofPTMsthatmo deldistributedinteraction.PTMs would b e equipp ed with additionalcommunication tapes.To allow dynamic recon gurationofPTMsystems,newprimitivesforcreating,sharing,and mo difying communication tap es are needed, but the underlying \hardware" of the system would still b e based on Turing Machines. 4.2The -calculus Milner's -calculus[23,24,29]isamathematicalmo delofconcurrentpro- cesses, which aremobilein the sense that their interconnections dynamically change during the computation. -calculus can b e considered a dynamic ex- tension of CCS (Calculus of Communicating Systems), Milner's earlier mo del whichwas not mobile [22]. Similar to PTMs (section 4.1), the -calculus is built around the central notion ofinteraction. -calculus rests up on the primitive notion of interaction via message passing, just as Turing Machines rest up on the notion of reading andwritingastoragemedium,andjustasrecursivefunctionsandthe - calculusrestup onmathematicalfunctions.Itisamo delofthechanging connectivityofinteractive systems, wherehandshakingallows for synchronous message passing among asynchronous pro cesses. The ability to directly represent mobility, allowing pro cesses to recon gure their interconnections while they execute, makes it easy to mo del networked systemsofmobileagents,oranyothersystemwherecommunicationlinks and other resources are allo cated dynamically. -calculus subsumesChurch -calculus;bytheChurch-Turing thesis,it follows that -calculus is at least as expressiveas Turing Machines. It actu- ally is more expressive, extending Turing Machines along all three dimensions (section3.3):interaction(b etweenpro cesses),in nity(oftimeforpro cess computation),andevolution(ofthecommunicationtop ology).Thisisev- idencedbytheexistenceofcomputablenon-algorithmicproblemssuchas driving home from work,aswell as by Milner's own assertion that \a theory ofconcurrencyandinteractionrequiresanewconceptualframework"and cannot b e expressed byTuring Machines [24]. Unfortunately, there is yet no de nite metrics for measuring the expressiveness of the -calculus [29]. -calculus is closely related to Hoare's CSP [19]. Both have b een imple- mented in practice. The OCCAM programming language is based on CSP; the PICT programming language implements an asynchronous version of the 24E.Eb erbach, D.Goldin, P.Wegner -calculus[28].However, -calculushasyettogainp opularacceptanceor commercial success. 4.3The $-calculus $-calculus(pronounced\costcalculus")isamathematicalmo delofinter- activeprocess-basedproblemsolving,capturingb oththe naloutcomeof problem solving as well as the interactive incremental pro cess of nding the solution. It was intro duced in the 1990's [9{11] as a formalization of resource- b ounded computation, also known asanytime algorithms. Anytime algorithms, prop osed by Dean, Horvitz, Zilb erstein and Russell in the late 1980's [20], are approximate algorithms whose solution quality in- creases monotonically as more resources (e.g., time or memory) are available. $-calculus is a pro cess algebra forboundedrational agents. Justas -calculuswasbuiltaroundacentralconceptofinteraction,$- calculusrestsup ontheprimitivenotionofcost.Anexampleofcostisthe notion ofpower consumptionforsensor network querying.Power is consumed ata di erentratefor di erentactivitiesof thesensor, includingcommuni- cation;minimizationofoverall p owerconsumptiondrivesthedesignquery evaluation and optimization for sensor networks. $-calculus provides supp ort forproblemsolvingviaanincrementalsearchforsolutions,usingcostto direct the search. $-calculushasthesameprimitivestomo delinteractionas -calculus, communication by message passing, and the ability to create and destroy pro- cesses and communication links. In addition, its cost mechanism p ermits the mo deling of resource allo cation, or quality-of-service optimization. $-calculus isthereforeapplicabletorob otics,softwareagents,neuralnets,andevo- lutionary computation. Potentially, it could b e used for design of cost-based programming languages, cellular evolvable cost-driven hardware, DNA-based computing and molecular biology, electronic commerce, and quantumcom- puting.$-calculusexpressesevolutionnaturally.Itscostp erformancemeasure mo dels the tness function. Additionally, $-calculus can simultaneously lo ok for the b est solution and lowest search cost. That is, it provides direct sup- p ort for optimizing not only the outcome of problem solving, but the problem solving metho ds used to obtain the results.Itis exp ectedthattheacceptance of sup er-Turing computation willre- sult in new classes of programming languages.Cost languages, based on the $-calculus mo delofcomputation,intro duceanewprogramming paradigm. They are inherently parallel, highly p ortable,

exible, dynamic, robust, mo d- ular, with a 3D graphical interface [9]. The

exible and automatic cost opti- mization mechanism distinguishes them from other agent related languages. For example, costs can b e mo deled with probabilities or fuzzy set memb ership to represent uncertainty. Turing's Ideas and Mo dels ...25 4.4Other Sup er-Turing Mo dels In this section, we provide a survey of other sup er-Turing mo dels of compu- tation. C-machines, o-machines and u-machines.Choice machines,oracle ma- chines, andunorganized machinesare three sup er-Turing mo dels of computa- tion de ned byTuring [37,38,41] (section 2). Choice machines and oracles ma- chines derive their expressiveness from theinteractionprinciple; unorganized machines, assuming an in nite supply of neurons, derive their expressiveness from thein nityandevolutionprinciples. Cellularautomata.Cellularautomata[45,4](CAs)wereintro ducedby John von Neumann in search of mo dels for self-repro duction, universal com- putability, and universal constructibility. They consist of an in nite number ofcel ls, where each cell is a nite state machine. CAs are known to b ecompu- tation universal, referring to their ability to implementany algorithm. While CAscansimulateanyTuringMachine,thereverseisnottrue;thereexist problemssolvablebyCAs,butnotbyTMs.Forexample,therecognition that an in nite sequence of 9's after a decimal p oint, i.e., 0.9999..., is another representation of 1, or the problem of the universal constructability requiring the ability to build a clone copy of the TM by the TM itself, cannot b e solved by TMs. However CAs can do that [15,45]. ThegreaterexpressivepowerofCAsisduetoanunb oundednumber of cells { thein nityprinciple. Note that whereas the unb ounded TM tap e onlyholdsa nitestringatanyonetime,CAsenco deanin nitestring. CAs are alsoconstruction universal, which refers to their ability to construct arbitrary automata, including themselves (i.e., self-repro duction). Construc- tion universality is one of the cornerstones for researchinarti ciallifeand robotics. Site and Internet Machines.Van Leeuwen [44] intro duced Site and Inter- net machines to capture the prop erties of computation that are not mo deled directly byTuring Machines: interaction of machines (ourinteraction), non-uniformity of programs (ourevolution), and in nity of op erations (ourin nity). Sitemachinesare generally interactiveTuring Machines withadvice,which isalimited(butneverthelessmorepowerfulthanTM)version ofTuring's oracle.Theyareequipp edwithseveralinputandoutputp ortsviawhich theycommunicatebysendingandreceivingmessages. Inparticular,asite machinemayexchangemessageswiththeadviceoracle,toobtainuncom- putable advice from it. 26E.Eb erbach, D.Goldin, P.Wegner AnInternet machine, as its name implies, mo dels the Internet; it consists of a nite but time-varying set of Site machines that work synchronously and communicate by exchanging messages. Each machine in the set is identi ed by itsaddress, andthesize of thesetcan grow at mostp olynomially with time.VanLeeuwenprovesthathisInternetmachineisnotmoreexpressive than a singleSite machine;however, this pro of sacri ces the dynamic nature of messages and assumes they can b e precomputed. However, b othSiteand InternetmachinesaremorepowerfulthanTMs.Thisisgenerallydueto thepowerofadvice,whichrepresentstheuncomputablenatureofthesite machine's environment. Analogneuralnetworks.NeuralNetworks(NNs)consistofcomputa- tional cells (callednodesorneurons), much like cellular automata. However, the underlying network is no longer homogeneous but an arbitrary digraph; the transition functions compute weighted sums of inputs from neighb oring cells. Dep ending on whether they op erate over discrete or real values, neural networks can b ediscreteoranalog. Despite having nitely many cells, analog NNs neural networks can com- pute nonrecursive functions. In particular, they can compute theanalog shift map, known to b e non-recursive [33]. In fact, neural networks can b e a stan- dard mo del for sup er-Turing analog computing, analogous to the role of the Turing Machine in the Church-Turing thesis: No possible abstract analog devicecan have morecomputational capa- bilities(up to polynomialtime) than rst-order (i.e.,the net neuron functionisaweightedsum ofitsinputs) recurrent neuralnetworks. [33]. The extra p ower of analog NNs stems from their real-valued weights, allowing the neurons to take continuous values in their activation functions. The im- plementation of such a neural network can b e viewed as an idealized chaotic physical system. EvolutionaryTuringMachines.ByanEvolutionaryTuringMachine (ETM) [12], we mean a (p ossibly in nite) series of Turing Machines, where the outcome tap e from one generation forms the input tap e to the next gen- eration. In this sense ETM resembles a PersistentTuring Machine. The tap e keepsb othap opulationofsolutions,andthedescriptionofanevolution- ary algorithm. Both p opulation of solutions and evolutionary algorithms can evolve from generation to generation. The goal (or halting) state of ETM is represented by the optimum of the tness p erformance measure. The higher expressiveness of ETM is obtained either evolving in nite p opulations, or ap- plying an in nite numb er of generations (the in nity principle), or applying variation(crossover/mutation)op eratorspro ducingnonrecursivesolutions (the evolution principle). Turing's Ideas and Mo dels ...27 Accelerating Universal Turing Machines.Another sup er-Turing mo del is theAccelerating Universal Turing Machine(AUTMs) [7], where programs areexecutedatanever-acceleratingrate,p ermittingin niteprogramsto nish in nite time. AUTMs require a maximum of two time units to execute any p ossible program; for example, the rst op eration takes 1 time unit, the second 0.5 time unit, the third 0.25, and so on. 5Towardsanewkindofcomputerscience In this section, we will sp eculate on the e ect of the paradigm shift to Sup er- Turingcomputationonseveralareasofcomputerscience:arti cialintelli- gence, programming languages, and computer architecture. 5.1Sup er-Turingintelligence:interactiveextensionsofthe Turing Test When Turing prop osed his famous Turing Test, he raised the question:Can machinesact intel ligently?, which he then answered in the a rmative (sec- tion2.7).NoteveryonesharedTuring'soptimism.SkepticssuchasPen- rose [27]argued thatTuringMachines cannotsimulatetheextensionalbe- havior of humans or physical systems, b elieving that computers' b ehavior is essentially to o weak to mo del intelligence. Replacing Turing Machines with interactive systems, eithersequentialor distributed(section 3.3) in the Turing Test allows us to mo del stronger exten- sionalb ehavior.TheinteractiveTuringTestpreserves Turing'sb ehaviorist assumption thatthinkingissp eci able byb ehavior, butextendsmo delsof questioning and resp onding to b e interactive [46,48]. Analysis of interactive question answering yields b ehaviorist mo dels of hinking" that are qualita- tively stronger than the traditional, algorithmic, Turing Test mo del. algorithmicTuringTest: measures ability to answer a set of un- relatedquestionsfrom a predetermined script; sequentialTuringTest:measures abilitytocarry outadialogue involving follow-up questions, where the answers must show adaptive history-dep endent thinking; distributed Turing Test: measures ability to carry outprojectsin- volving co ordination and collab oration for multiple autonomous com- munication streams. Algorithmic, sequential, and multi-agent thinking are progressively more powerful forms of b ehavioral approximation to humanthinking, de nedby progressively more stringent empirical tests of b ehavior. While we agree with Penrose's arguments [27] against the algorithmic Turing Test, we b elieve they no longer hold for the stronger interactive forms of the test. 28E.Eb erbach, D.Goldin, P.Wegner The interactiveTuring test extends machines without changing the form of the Turing test. Turing would certainly have accepted the interactivever- sions of the Turing Test as legitimate, and would have approved of the b e- haviorist notions of sequential and distributed thinking as conforming to the spirit of his notion of machine intelligence. Wealsoconsiderin niteandevolutionaryversionsoftheTuringTest. The rst will allow the testing to continue for an inde nite p erio d of time. Like elections for the presidency in a country without term limits, the system needstocontinueproving itselfover andover inordertoavoidfailingthe test. An evolutionary version is even stronger; the rules for intelligence evolve as the test progresses, and the system is exp ected to adapt to the new rules.RussellandNorvig[31]prop oseanotherextension:atotalTuringTest where thethecomputer hastheabilitytomove ab out,to p erceive itssur- roundings,andtomanipulateob jects.Thiswouldfreethetesterfromthe need to interact withthe system via an arti cial interface, as well as allow her to test the system's ability to act within and on its environment. 5.2Sup er-Turing architectures The architecture for sup er-Turing computers has the following three require- ments, re

ecting the three principles of sup er-Turing computation (section 3.3): (interactionprinciple)Highly interactive b oth with the environment and other computers. (in nityprinciple)Highlyscalable{allowinguseofmoreandmore time, memory, and other resources in the computation. There should b e no limit on that, i.e., computers will b e closer and closer to satisfy in the

limit the in nity principle. (evolutionprinciple)Highly adaptable allowing mo di cation of b oth hardware and software. Evolvable hardware and software may lead in a more natural way to computers that learn rather than b e programmed. Today's computers are still based on the 50-year-old \von Neumann archi- tecture", whichwas inspired by the Universal Turing Machine mo del. There are cosmetic changes, suchasmulti-level caches and pip elining, but under the hooditremains thesameoldmo del.Whileto day'ssystemsaresomewhat interactive, they fall far short in each of these three categories. So far, none of the attempts to build asupercomputerbased on non-von Neumannarchitecturewascommerciallysuccessful.TheFifthGeneration Projectin Japan, Europ e, and USA pro duced manyambitious non-von Neu- mann architecture designs, from whichvery few (if any) survived.Reduction anddata

owcomputers, attempting to eliminate the so-calledvon Neumann bottleneckand increase the sp eed of computers, turned out to b e ine cient. Cel lularcomputershad their p eak with the massively parallel architectures ofConnection Machines. Their creator, the Thinking Machine Corp oration, Turing's Ideas and Mo dels ...29 is no longer inthe business ofbuilding parallel pro cessors. Cray Computer Corp oration,anothermanufacturerofmassivelyparallelarchitectures,has likewise declared bankruptcy.Intel and DEC have also stopp ed manufactur- ing sup ercomputers.We conjecture that a single computer based on a parallel architecture is thewrongapproachaltogether.Theemerging eldofnetworkcomputing, where many autonomous small pro cessors (orsensors) form a self-con gured network that acts as a single distributed computing entity, has the promise of delivering what earlier sup ercomputers could not. This is consistent with Turing's design of the ACE [39,40], where Turing advo cated putting the whole complexityinto software keeping the hardware as simple as p ossible. An evolvable and self-recon gurable network is not a single machine, but it constitutes a single distributed computing system, which can b e mobile, em- b edded, or environment-aware. These systems are the basis for theubiquitous andpervasivecomputingapplicationswhichareexp ectedtobethe\killer apps" of the next generation. They get us closer to von Neumann's Theory ofSelf-Repro ducingAutomata[45],Turing'smorphogenesis theory[43],or the total Turing Test (section 2.7). 5.3Programming languages for sup er-Turing computers We can identify four paradigms for programming languages, in the order of their app earance: pro cedural functional declarative (logic, constraints) ob ject-oriented (sequential, asynchronous) This classi cation applies to high-level languages. Very rarely is it applicable toassembly languages andmachine languages, whichtendtobeuniformly pro cedural.Theob ject-orientedapproachallowsthe\encapsulation"ofotherpro- gramming paradigms, creating hybrid o-o-pro cedural, o-o-functional, and o- o-declarative languages. It also provides nice supp ort for the developmentof graphical user interfaces, and it is claimed to b e an appropriate implemen- tationto olforinteractiveparallelprogramming. Havewefoundinob ject- oriented programming the universal paradigm to program sup er-Turing com- puters?How should the programming languages for sup er-Turing computers lo ok? The three principles of sup er-Turing computation,interaction,in nity, and evolution(section3.3), serve as b eacons in our search for an answer: Programminglanguagesforsup er-Turingcomputingshouldbehighly dynamic, to express learning and programming in rapidly changing envi- ronments, and to sp ecify highly interactive applications. 30E.Eb erbach, D.Goldin, P.Wegner Programs should adapt automatically to the environments and new goals. These languages should provide supp ort for solving problems expressed in a declarative fashion. They should have built-in optimization engines for hard search problems that may arise during computation, much more p owerful than the depth- rst search strategy used in Prolog. They should b e able to solvein the limitcurrently undecidable problems; that is, to obtain approximate solutions with arbitrarily high precision, or to obtain correct solutions probablistically with arbitrarily lowchance of error. Most likely, ob ject-orientation is here to stay, but not in its current form. When mobile emb edded networked sensors are mo deled as asynchronous con- current ob jects, it is clear that their programming will require new primitives so interaction (communication) and mobility can b e handled explicitly.Fur- thermore, we conjecture that constraints will play a greater role in the pro- gramming languages of the future, to enable declarative sp eci cation of de- sired system b ehavior. To translate these sp eci cations into executable co de, the languages will also have built-in dynamic search strategies and approxi- mate solvers for undecidable problems, as discussed ab ove. This will require new computing technologies, such as analog, optical, biological, or quantum technologies, which will b e part of sup er-Turing architectures. 6RethinkingtheTheoryofComputation While sup er-Turing systems mo del new forms of computation, they may allow usto ndnewsolutions foroldproblems.Inthissection,welo ok atsome asp ects of theoretical computer science that will b e a ected by the paradigm shiftto sup er-Turing computing. Whilethese ideas sound rather futuristic, theywouldhave b eenwelcomedbyTuring,who always lo oked b eyondthe horizon of practical feasibility of the moment. 6.1Computing the undecidable Thehaltingproblemwasthe rstproblemidenti edbyTuringasunsolv- able[37].Thusitistypicalforsup er-Turingmo delstodemonstratetheir higher expressiveness by the solution of the halting problem. The pro ofs use either interaction, in nityorevolution principles. The rst such pro of was given by Alan Turing himself, who demonstrated thathiso-machinecansolve(nonalgorithmically)thehaltingproblem,by interactingwithanoracle.Later,Garzonshowedhowtosolvethehalting problembyanin nitenumberofdiscreteneurons [15]. In[11], threeways arepresentedforsolvingthehaltingproblemin$-calculus{usingeither interaction, or in nity,orevolution principles. Turing's Ideas and Mo dels ...31 HavaSiegelmanndepartedfromthehaltingproblem,andshowedthat real value neural networks can solve a non-recursive analog shift map using an in nity principle [33]. Note that none ofthese solutions ofthe Halting Problem (H) are algo- rithmic.Inthepro ofs,eithersomestepsofthesolutionsdonothavewell de ned (and implementable) meaning { this is when we refer to the help or oracles { or we use in niteresources (anin nitenumb er of steps requiring p erhaps an in nite initialization time).Also note that, while the undecidabilityofHled us to prove the unde- cidabilityofmanyotherproblems,itsdecidabilitydo esnothavesimilarly wideimplications. GiventhatHis undecidable,thepro of thatsome other problemPis undecidable relies on an argumentby contradiction:ifPwere decidable, thenHwould b e to o. However, if the original problemHturns out to b e solvable (using more p owerful means), it do es not imply the solvability of the other problem. 6.2Is the Church-Rosser theorem still valid? AccordingtotheChurch-Turingthesis,TuringMachinesareequivalentto recursive functions. The rstChurch-Rosser theorem[6] states that: Given a function,no matter whichevaluation order of thefunction parameters is chosen, the result will b e the same (up to renaming of b ound variables) as long as the computation terminates. The p ossible interpretation of this theorem can b e the following: if the se- quence do es not matter, then the evaluations can b e done in parallel without worrying ab out the order in which they nish b ecause the nal outcome will b e the same. The ab oveis typically interpreted that sequential programming isequivalenttoparallelprogrammingb ecauseb othlead,accordingtothe Church-Rosser theorem, to the same results. However,wemustrealizethattheChurch-Rossertheoremisvalidfor so-called\pure"functionalcomputationwithoutsidee ects.Bycontrast, b oth assignments statements from pro cedural languages as well as interaction bymessage-passingfromob ject-orientedlanguagesentailsidee ects.For languagesthatallowsidee ects,ithasb eenassumedthatanequivalent program without side e ects can always b e found, to ensure the applicability of the Church-Rosser theorem. Whilethisassumptionhaslongb eenseenasoverly optimistic,proving itfalse wouldbeequivalenttoarejectionoftheChurch-Turing thesis.We b elieve it to b e false. This follows from the fact that interaction is more ex- pressive than algorithms, and that distributed interaction is more expressive than sequential interaction. The Church-Rosser theorem, while valid for algorithmic computation, is not valid for super-Turing computing. 32E.Eb erbach, D.Goldin, P.Wegner One of the most imp ortant principles of sup er-Turing computation is in- teraction,whichisnotside-e ect-free.Infact,thesidee ectsarecrucial forthepowerofinteraction,suchasitsabilitytoexpressemergentbehav- ior.Forexample,manyscientistshavep ointedoutthatthecomplexityof the b ehavior of an ant colony (which is a distributed interactive system) is caused by sidee ectsoftheir interaction rather than bythecomplexityof ants themselves. 6.3Rewriting complexity theory:IstheP=NPquestionstill relevant? The classPconsists of all those algorithmic problems solved by somedeter- ministicTM whose running time is p olynomial in the size of the input. The classNPcan b e de ned in twoways { either as an analogue ofP, but with anondeterministicTM, or as those algorithmic problems whose solutions, if given to us by others, can b everi edby some deterministic TM in p olynomial time.The question of whetherP=NPhas b een o ccupying researchers since thesetwosetswere rstde ned,havingb ecomethethegreatestunsolved question of computer science. While it is simple to show thatPis a subset of NP, the other direction remains a mystery. The problems inPare considered to b e easy and tractable; those outside ofPare not. Are there problems inNP whicharenotinP?ManyNPproblemshaveb eenidenti edthatapp ear unlikelytobeinP,butwithoutapro of.AmongthemaretheTraveling Salesman Problem(is there a tour of all the no des in a graph with total edge weight k?), SAT (do es a Bo olean expression have a satisfying assignment ofitsvariables?),andCLIQUE(do esagraphhaveasetofkno deswith edges b etween every pair?). Donald Knuth b elieves thatP=NP, and that we will eventually nd a nonconstructivepro of that the time complexityofallNPproblems is p oly- nomial,butwewillnotknowthedegree ortheco e cientsofthisp olyno- mial.WeconjecturethattheP=NPquestionisinherentlyundecidable, that it can b e neither proved nor disproved. However, the great ma jorityof computer scientists b elieve thatP6

=NP[16]. Most, including Je Ullman, b elieve that it will take another hundred years to prove it, b ecause wehave notyetinventedtherighttechniques.Butsome,includingRichardKarp, thinkthattheproblemwillbesolvedearlier,byayoungresearcherwith non-traditional metho ds, unencumb ered by theconventional wisdom ab out howtoattacktheproblem{somethinginthespiritofAlanTuring,who never followed conventional paths. Weexp ectthattheP=NPquestionwillloseitssigni canceinthe contextofsup er-Turingcomputation.Beingabletointeractwiththereal world duringthecomputation,or toaccessin niteresources, ortoevolve, willreframecomputationalproblemsinanon-algorithmicwaythatshifts the fo cus away from theP=NPquestion. So far, the sup er-Turing research Turing's Ideas and Mo dels ...33 has concentrated on undecidable problems, but the e ective means of solving traditionally intractable problems should and will b e their equally imp ortant ob jective. 7Conclusions Sup er-Turingmo delsextendTuringMachinestop ermitinteractiveinput from the environment during computation, thereby mo deling problems that cannot b e mo deled byTuring Machines - like driving home from work,

ying airplanes, arti cial intelligence, and human thinking. Driving home requires knowledge of the environment not expressible by TMs,

ying planes requires environmental knowledge of temp erature and other airplanes, arti cial intel- ligence requires knowledge on intelligent tasks, and human thought requires knowledge of human environments during thought. Each of these topics can- notbehandledbyTMsbutcanbehandledbysup er-Turingmo delslike Interactive Machines or pro cess algebras like -calculus. The adoption of TMs as a mo del of universal problem solving has raised many computational problems that can b e solved by extending TMs to inter- active mo dels. AI has for manyyears b een viewed as unsolvable b ecause TMs could not handle certain problems that can b e handled byinteractive mo dels. The Turing test, prop osed byTuring as a basis for human thought, has b een criticized by Searle, Penrose and others as b eing intractable to question an- swering by TMs but b ecomes tractable if question answering is extended to interactive systems (section 5.1). The Japanese Fifth-generation computing paradigm was found to b e intractable b ecause logic programming could not b e expressed by TMs, but could in principle b e handled by an extended form ofinteractivelogic programming. Algorithmsexpress enumerableproblems that can b e constructed, while interaction expresses observable problems that may b e nonenumerable. Thetransitionfromenumerableconstructiontononenumerableobser- vationrequiresamathematicalchangeinmo delsofproblemsolvingthat eliminatestraditionalmo delsbasedoninductionandcanbeviewedasan elimination of traditional mathematics as a mo del of computation. Interac- tive mo dels are not mathematical in the traditional sense, but an extended mo del of mathematics not yet sp eci ed could in principle provide an accept- able mo del.Sup er-Turing mo dels require a change in mo dels of philosophyaswell as of mathematics. Philosophers have widely debated the relation b etween ra- tionalist mo dels of the mind and empiricist mo dels of exp erimental b ehavior. Aristotle's mo del of logic and mathematics is rationalist, while Plato's mo del of the cave is empiricist, requiring knowledge of the environment for problem solving. Descartes \cogito ergo sum" is rationalist while Hume's mo del is em- piricist, and was accepted by Kant in his b o ok \Critique of Pure Reason" as an empiricist principle of reasoning as a form of problem solving. Hilb ert and 34E.Eb erbach, D.Goldin, P.Wegner Russell'smo delsofmathematicsarerationalist,whileG odelandTuring's pro of of unsolvability of the Entscheidungsproblem is empiricist. Mathemat- ical acceptance of Turing Machines as a universal mo del for all computation can b e viewed as a rationalist transformation of Turing's empiricist mo del. Interaction is an empiricist mo del of computation consistent with G odel and Turing's original mo dels and with the need of future computer mo dels. The imp ortance of interaction as a mo del of computation corresp onds to the im- p ortance of empiricism over rationalism as a principle of philosophy. Robin Milner has asserted [25] that Turing would have b een excited by the direction in which computing has evolved; we agree. In particular, we b elieve thatAlanTuringwouldapproveofsup er-Turingmo dels,andhewouldbe the rst to argue that they,rather than the Turing Machine, represent the future of computing.Weexp ectsup er-Turingcomputationtob ecomeacentralparadigmof computerscience.However,wecannotclaimthatsup er-Turingmo dels,as describ ed in this chapter, are de nitive and complete. Most likely, they will b e sup erseded in the future by mo dels that are even b etter and more complete forproblemsolving,intheneverendingquestforab etterdescriptionof reality. References1.B ack T., Fogel D.B., Michalewicz Z. (eds.),Handbook of Evolutionary Compu- tation, Oxford University Press, 1997. 2.\Algorithm."Encyclopedia Britannica 2003Encyclop edia Britannica Premium Service.. 3.Bro oksR.A.,ElephantsDon'tPlayChess,inP.Maes(ed.),DesigningAu- tonomous Agents: Theory and Practicefrom Biology to Engineering and Back, The MIT Press, 1994, pp. 3-15. 4.Burks A.,Essays on Cel lular Automata, Univ. of Illinois Press, 1970. 5.Church A., An Unsolvable Problem of Elementary Numb er Theory,American Journal of Mathematics58, 1936, pp. 345-363. 6.Church A., Rosser J.B., Some prop erties of conversion,Trans. AMS39 (1936), pp. 472-482. 7.Cop eland B.J., Sup er-Turing Machines,Complexity, 4(1), 1998, pp. 30-32. 8.Martin Davis, Why G"o del Didn't HaveChurch's Thesis,Information & Con- trol54, 1982, pp. 3-24. 9.Eb erbachE.,Bro oksR.,PhohaS.,FlexibleOptimizationandEvolutionof Underwater Autonomous Agents, LNAI 1711, Springer-Verlag, 1999, pp. 519- 527. 10.Eb erbach E., $-Calculus Bounded Rationality = Pro cess Algebra + Anytime Algorithms, in: (ed.J.C.Misra)Applicable Mathematics:Its Persp ectivesand Challenges, Narosa Publishing House, New Delhi, Mumbai, Calcutta, 2001, pp. 213-220. 11.Eb erbach E., Is Entscheidungsproblem Solvable? Beyond Undecidabilityof Tur- ing Machines and Its Consequence for Computer Science and Mathematics, in: Turing's Ideas and Mo dels ...35 (ed.J.C.Misra) Computational Mathematics, Mo deling and Simulation, Narosa Publishing House, New Delhi, Chapter 1, 2003, pp. 1-32. 12.Eb erbachE.,OnExpressivenessofEvolutionaryComputation:IsECAlgo- rithmic?,Proc. 2002 World Congress on Computational Intel ligence(WCCI), Honolulu, HI, 2002, pp. 564-569. 13.Farley B.G., Clark W.A., Simulation of self-organizing systems by digital com- puter,IRE Transactions on Information Theory4, 1954, pp. 76-84. 14.Fogel D.B. (ed.),EvolutionaryComputation:The FossilRecord,IEEE Press, NY, 1998. 15.Garzon M., Mo dels of MassiveParallelism: Analysis of Cellular Automata and Neural Networks, An EATCS series, Springer-Verlag, 1995. 16.Gasarch W., Guest Column: The P=?NP Poll,SIGACT News, 33:2, June 2002, pp. 34-47. 17.Goldin D., PersistentTuring Machines as a Mo del of Interactive Computation, FoIKS'00, Cottbus, Germany, 2000. 18.Dina Goldin,Scott Smolka, Peter Wegner, Turing Machines,TransitionSys- tems, and Interactionproc. 8th Int'l Workshopon Expressivenessin Concur- rency, Aalb org, Denmark, August 2001 19.Hoare C.A.R.,Communicating Sequential Processes, Prentice-Hall, 1985. 20.Horvitz E., Zilb erstein S. (eds.), Computational Tradeo s under Bounded Re- sources,Arti cial Intel ligence126, 2001, pp. 1-196. 21.McCullo ch W., Pitts W, A Logical Calculus of the Ideas Immanent in Nervous Activity,Bul letin of Mathematical Biophysics5, 1943, pp. 115-133. 22.MilnerR.,A CalculusofCommunicating Systems,Lect.NotesinComputer Science94, Springer-Verlag, 1980. 23.Milner R., Parrow J., Walker D., A Calculus of Mobile Pro cesses, I & I I,In- formation and Computation100, 1992, pp. 1-77. 24.MilnerR.,ElementsofInteraction,CommunicationsoftheACM36:1,Jan. 1993, pp. 78-89. 25.MilnerR.,Turing,ComputingandCommunication,alectureforthe60'th anniversary of Turing's \Entscheidungsproblem" pap er, King's College, Cam- bridge England, 1997. 26.Minsky M.L., Theory of Neural-Analog Reinforcement Systems and Its Appli- cations to the Brain-Mo del Problem, Ph.D. Thesis, Princeton University, 1954. 27.Penrose R.,The Emperor's New Mind, Oxford, 1989. 28.Pierce B., Turner D., Pict: A Programming Language Based on the Pi-Calculus, in: Plotkin G. et al (eds.),Proof, Language, and Interaction: Essays in Honour of Robin Milner, The MIT Press, 2000, pp. 455-494. 29.Plotkin G., Stirling C., Tofte M. (eds.),Proof, Language, and Interaction: Es- says in Honour of Robin Milner, The MIT Press, 2000. 30.Rosenblatt F., The Perceptron: A Probabilistic Mo del for Information Storage and Organization in the Brain,Psychological Review65, 1958, pp. 386-408. 31.Russell S., Norvig P.,Arti cial Intel ligence: A Modern Approach, 2nd edition, Prentice-Hall, 2003. 32.SamuelA.L.,Somestudiesinmachinelearningusingthegameofcheckers, IBM Journal of Research and Development3, 1959, pp. 211-229. 33.Siegelmann H.,Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhauser, 1999. 34.Simon, H.A.The Sciences of the Arti cial.MIT Press, 1969. 36E.Eb erbach, D.Goldin, P.Wegner 35.Sipser, M.Introduction to the Theory of Computation, PWS Publishing Com- pany, 1997. 36.TeuscherCh.,Turing'sConnectionism:AnInvestigationofNeuralNetworks Architectures, Springer-Verlag, 2001. 37.TuringA.,OnComputableNumb ers,withanApplicationtotheEntschei- dungsproblem,Proc. London Math. Society, 42:2, 1936, pp. 230-265; A correc- tion, ibid, 43, 1937, pp. 544-546. 38.Turing A., Systems of Logic based on Ordinals,Proc. LondonMath. Society, 45:2, 1939, pp. 161-228. 39.Turing A., The ACE Rep ort, inA.M. Turing's AceReport of 1946 and Other Papers, eds. B.E. Carp enter and R.W. Doran, MIT Press, 1986. 40.Turing A., Lecture to the London Math.So ciety on 20'thFebruary 1947,in A.M. Turing's AceReport of 1946 and Other Papers, eds. B.E. Carp enter and R.W. Doran, MIT Press, 1986. 41.TuringA.,IntelligentMachinery,1948;inCol lectedWorksofA.M.Turing: Mechanical Intel ligence, ed. D.C.Ince, Elsevier Science, 1992. 42.Turing A., Computing Machinery and Intelligence,Mind, 1950. 43.TuringA.,TheChemicalBasisofMorphogenesis,Phil.Trans.oftheRoyal SocietyB237, 1952. 44.Van Leeuwen J., Wiedermann J., The Turing Machine Paradigm in Contemp o- rary Computing, in. B. Enquist and W. Schmidt (eds.)Mathematics Unlimited - 2001 and Beyond, LNCS, Springer-Verlag, 2000. 45.VonNeumannJ.,TheoryofSelf-Repro ducingAutomata,(editedandcom- pleted by Burks A.W.), Univ. of Illinois Press, 1966. 46.Wegner P., WhyInteraction is More Powerful Than Algorithms,Communica- tions of the ACM40:5, May 1997, pp. 81-91. 47.Wegner P., InteractiveFoundations of Computing,Theoretical Computer Sci- ence192, 1998, pp. 315-351. 48.Wegner P., Goldin D., Interaction as a Framework for Mo deling, LNCS 1565, April 1999. 49.Wegner P., Goldin D., Computation Beyond Turing Machines,Communications of the ACM, April 2003.