{\rtf1\ansi\ansicpg1252\uc1 \deff16\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f3\froman\fcharset2\fprq2{\*\panose 05050102010706020507}Symbol;}
{\f4\froman\fcharset0\fprq2{\*\panose 02020603050405020304}TIMES;}{\f16\froman\fcharset0\fprq0{\*\panose 00000000000000000000}TimesNewRoman;}{\f167\froman\fcharset238\fprq2 Times New Roman CE;}{\f168\froman\fcharset204\fprq2 Times New Roman Cyr;}
{\f170\froman\fcharset161\fprq2 Times New Roman Greek;}{\f171\froman\fcharset162\fprq2 Times New Roman Tur;}{\f172\froman\fcharset186\fprq2 Times New Roman Baltic;}{\f191\froman\fcharset238\fprq2 TIMES CE;}{\f192\froman\fcharset204\fprq2 TIMES Cyr;}
{\f194\froman\fcharset161\fprq2 TIMES Greek;}{\f195\froman\fcharset162\fprq2 TIMES Tur;}{\f196\froman\fcharset186\fprq2 TIMES Baltic;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;
\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}
{\stylesheet{\nowidctlpar\adjustright \f16\fs18\cf1 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\qj\li1008\sl400\slmult0\nowidctlpar\tx1008\adjustright \f16\fs22\cf1 \sbasedon0 \snext15 Block Text;}{\s16\nowidctlpar\adjustright
\f16\fs18\cf1 \sbasedon0 \snext16 Body;}{\s17\qj\nowidctlpar\adjustright \f16\fs18\cf1 \sbasedon0 \snext17 Body Text;}{\s18\qj\fi720\li288\sl600\slmult0\nowidctlpar\tx288\tx432\adjustright \f16\fs18\cf1 \sbasedon0 \snext18 Body Text 2;}{
\s19\qj\fi720\li288\sl400\slmult0\nowidctlpar\tx288\tx432\tx1008\adjustright \f16\fs22\cf1 \sbasedon0 \snext19 Body Text Indent 2;}{\s20\nowidctlpar\adjustright \f4\cf1 \sbasedon0 \snext20 Default_XREF_style;}{\s21\nowidctlpar
\tqc\tx1728\tqr\tx6048\adjustright \f16\fs18\cf1 \sbasedon0 \snext21 footer;}{\s22\li648\nowidctlpar\tx648\adjustright \f4\cf1 \sbasedon0 \snext22 Footnote;}{\s23\nowidctlpar\adjustright \f4\cf1 \sbasedon0 \snext23 header;}{\*\cs24 \additive \f4\cf1
page number;}{\s25\sl540\slmult0\nowidctlpar\adjustright \f4\cf1 \sbasedon0 \snext25 Subtitle;}{\s26\nowidctlpar\adjustright \f3\cf1 \sbasedon0 \snext26 Symbol;}{\s27\sl560\slmult0\nowidctlpar\adjustright \b\f16\fs20\cf1 \sbasedon0 \snext27 Title;}}{\info
{\title Computation Beyond Turing Machines}{\author D&D}{\operator D&D}{\creatim\yr2002\mo6\dy20\hr10\min17}{\revtim\yr2002\mo6\dy20\hr10\min17}{\version2}{\edmins1}{\nofpages5}{\nofwords1628}{\nofchars9282}{\*\company Q}{\nofcharsws11398}{\vern71}}
\margl1440\margr1440 \widowctrl\ftnbj\aenddoc\hyphcaps0\viewkind1\viewscale93\viewzk2 \fet0\sectd \sbknone\pgnrestart\linex0\sectdefaultcl {\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang
{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang
{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain
\s27\qc\sl560\slmult0\nowidctlpar\adjustright \b\f16\fs20\cf1 {\fs22\lang1024 Computation Beyond Turing Machines}{\b0\fs22\lang1024
\par }\pard\plain \sl280\slmult0\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s27\qc\ri108\sl460\slmult0\nowidctlpar\adjustright \b\f16\fs20\cf1 {\b0\i\fs22\lang1024 Peter Wegner, Brown University Dina Goldin, U. of Connecticut
\par }\pard\plain \s16\sl360\slmult0\nowidctlpar\adjustright \f16\fs18\cf1 {\i\lang1024 \tab \tab \tab \tab \tab \tab
\par }{\f4\fs24\lang1024
\par }\pard\plain \s17\qj\sa140\sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\b\fs22\lang1024 1. Turing\rquote s legacy}{\fs22\lang1024
\par }\pard \s17\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright {\fs22\lang1024
Alan Turing was a brilliant mathematician who showed that computers could not completely prove mathematical assertions, extending G\'f6del\rquote
s proof that logic could not completely model mathematical truth. This connection between computers and mathematics was later used to develop a mathematical foun\-dation for computer science, comparable to mathematical found
ations for physics and other sciences. The present article shows that Turing machines are inappropriate as a universal foundation for computational problem-solving, and that computer science is a fundamentally non-mathematical discipline. Though inter\-
action is not the only way to extend computation beyond Turing machines, we show that Turing, Milner, and others have used interaction for this purpose.
\par Turing was born in 1912. He was accepted by Cambridge in 1930 to study mathematics, and became a Fellow of Kings College in 1934 at the age of 22, completing a dissertation that extended group theory models of Von Neumann. His 1936 paper, \ldblquote
On Computable Numbers with an application to the }{\i\fs22\lang1024 Entsc\-heidungsproblem}{\fs22\lang1024 \rdblquote , proved that mathematics could not be completely mo
deled by computers. In the early 1940s he developed a computer model of German cipher code that helped England win World War II. In the late 1940s he developed computational models of artificial intelligence, chess, and the human mind, suggesting that com
p
uters could completely model human thought and would play chess better than humans before the end of the century. Though the 1936 paper was primarily about the inability of Turing machines to solve mathematical problems, Turing machines were adopted by th
eoretical computer scien\-tists in the 1960s as a mode of solving all problems of computing. In this essay we examine the historical evolution of Turing\rquote
s model from mathematical weakness in the 1930s to computational strength in the 1960s, and then to computational weakness in the 1990s as increases in the applicability of computation broadened our notion of \ldblquote computational problem\rdblquote
and revealed the limitations of the power of Turing machines to handle problem solving.
\par }\pard\plain \sl280\slmult0\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s17\qj\sa140\sl470\slmult0\nowidctlpar\adjustright \f16\fs18\cf1 {\b\fs22\lang1024 2. Hilbert, G\'f6del, and Church}{\fs22\lang1024
\par }\pard \s17\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright {\fs22\lang1024 In 1900 H
ilbert proposed that logic could completely prove the truth or falsity of mathematical asser\-tions, and listed 25 unproven mathematical assertions that mathematicians should try to prove. Russell and Whitehead\rquote s }{\i\fs22\lang1024
Principia Mathematica }{\fs22\lang1024 accepted Hilbert\rquote s principle and provided an account of mathematical logic as a universal model of mathematical provability. The failure to achieve their goals led to G\'f6del\rquote
s 1931 proof that logic could not prove all mathematical theorems [Go31]. G\'f6del showed that the }{\i\fs22\lang1024 Entsc\-heidungsproblem }{\fs22\lang1024 (\ldblquote decision problem\rdblquote
) was in principle unsolvable by logic, and this led to work by many mathematicians to further explain the theory and philosophy of mathematical unsolvability in terms of logic or other models of mathematics.
\par }\pard\plain \s16\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright \f16\fs18\cf1 {\fs22\lang1024 G\'f6del\rquote s ideas w
ere taken up by Church, who proved in 1935 that the }{\i\fs22\lang1024 Entscheidungsproblem }{\fs22\lang1024 could not be solved by the lambda calculus. By contrast, Turing showed by computers that the }{\i\fs22\lang1024 Entscheidungsprob\-lem}{
\fs22\lang1024 could not be solved, because the \ldblquote halting problem\rdblquote of Turing machines was itself unsolvable. Turing\rquote s result was accepted by G\'f6
del and Church as a simpler and better unsolvability argument. Turing was invited to Princeton in 1937 to work with Church on what was later called the Church-Turing thesis. This thesis equated log
ic, lambda calculus, Turing machines, and algorithmic computing as equivalent mecha\-nisms of problem solving. This thesis was later reinterpreted as a uniform complete mechanism for solving all computational problems.
\par Turing implied in his 1936 paper that Turing machines (which he called }{\i\fs22\lang1024 automatic machines}{\fs22\lang1024 , or }{\i\fs22\lang1024 a-machines}{\fs22\lang1024
) could not provide a complete model for all forms of computation, just as they could not provide a model for all forms of mathematics. He defined }{\i\fs22\lang1024 c-machines}{\fs22\lang1024 (choice machines) as an alterna
tive model of computation, which added interactive choice as a form of computation; later, he also defined }{\i\fs22\lang1024 u-machines}{\fs22\lang1024 (unorganized machines) as another alternative that modeled the brain. But Turing did not formal\-
ize them, and they were discarded in the 1960s as unnecessary, because it was assumed that Turing machine models could completely describe all forms of computation. Though this narrow interpretation of the Church-Turing thesis contradicted Turing\rquote
s assertion that Turing machines could only formalize }{\i\fs22\lang1024 algo\-rithmic}{\fs22\lang1024 problem-solving, it was accepted by the CS community in the 1960s and became a dogmatic prin\-
ciple of the theory of computation. Computer science was modeled by a mathematical model of theoretical Turing machines whose scientific model paralleled those of physics, chemistry, and biology, providing an acceptable but weak theory of computation.
\par }\pard\plain \sl280\slmult0\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s16\qj\sa140\sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\b\fs22\lang1024 3. From algorithms to interaction}{\fs22\lang1024
\par }\pard \s16\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright {\fs22\lang1024 After its beginning with Turing\rquote
s pioneering paper in 1936, computer science emerged as a mature discipline in the 1
960s, when universities nationwide started offering it as an undergraduate program of study. By 1968, there was a general consensus on what should be taught as part of this new discipline, enunciated in ACM's Curriculum '68 document [ACM68]. The new disci
pline of computer science viewed computation as }{\i\fs22\lang1024 information processing}{\fs22\lang1024 , a }{\i\fs22\lang1024 transformation}{\fs22\lang1024 of }{\i\fs22\lang1024 input}{\fs22\lang1024 to }{\i\fs22\lang1024 output}{\fs22\lang1024
-- where the input is com\-pletely defined before the start of computation, and the output provides a solution to the problem at hand. Such mechanistic transformations were long known in mathematics as }{\i\fs22\lang1024 algorithms}{\fs22\lang1024
; the approach to compu\-tation adopted by computer science is hence referred to as }{\i\fs22\lang1024 algorithmic}{\fs22\lang1024 .
\par The field of computing has greatly expanded since the 1960s, and it has been increasingly recognized that artificial intelligence, graphics and the Internet cannot be expressed by Turing machines. In each case, }{\i\fs22\lang1024 interaction}{
\fs22\lang1024 between the program and the world (}{\i\fs22\lang1024 environment}{\fs22\lang1024 ) that takes place during the computation plays a key role that cannot be replaced
by any set of inputs determined prior to the computation. In the case of artificial intelligence, interaction can be viewed as a prerequisite for intelligent system behavior, as argued by Brooks [Br91]:
\par }\pard\plain \sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s15\qj\li720\ri576\sl360\slmult1\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright \f16\fs22\cf1 {\lang1024 \ldblquote Real computational systems are not rational agents
that take inputs, compute logically, and produce outputs\'85 It is hard to draw the line at what is intelligence and what is environmen\-
tal interaction. In a sense, it does not really matter which is which, as all intelligent systems must be situated in some world or other if they are to be useful entities\rdblquote .
\par }\pard\plain \sl360\slmult1\nowidctlpar\tx720\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s16\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright \f16\fs18\cf1 {\fs22\lang1024
British computer scientist Robin Milner developed a new conceptual framework for models of compu\-tation, based on CCS and later the }{\f3\fs22\lang1024 \'70}{\fs22\lang1024 -calculus. In his Turing Award lecture \ldblquote Elements of Interaction
\rdblquote [Mi93], Milner asserts that established models of computation are insufficient:
\par }\pard\plain \sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s16\qj\li720\ri576\sl360\slmult1\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright \f16\fs18\cf1 {\fs22\lang1024 \ldblquote
Through the seventies, I became convinced that a theory of concurrency and interaction requires a new conceptual framework, not just a refinement of what we find natural for sequential [algorithmic] computing\rdblquote .
\par }\pard\plain \sl360\slmult1\nowidctlpar\tx720\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard \qj\sl360\slmult1\nowidctlpar\tx720\adjustright {\fs22\lang1024
\par }\pard\plain \s16\qj\sa160\sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\b\fs22\lang1024 4. Beyond Turing machines}{\fs22\lang1024
\par }\pard \s16\qj\fi360\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright {\fs22\lang1024 Milner\rquote
s Turing Award lecture in 1991 presented models of interaction as complementary to the closed-box computation of Turing machines. However, he avoided the question whether the computation of CCS and the }{\f3\fs22\lang1024 \'70}{\fs22\lang1024
-calculus went beyond Turing machines and algorithms. TMs had been accepted as a principal paradigm of complete computation, and it was premature to openly challenge this view in the late '70s and the early '80s. In the last two decades, comp
uting technology has shifted from mainframes and microstations to networks and wireless devices, with the corresponding shift in applications from number crunching and data processing to embedded systems and graphical user interfaces. We believe it is no
longer premature to encompass interaction as part of computation. A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today\rquote s computing systems and software agents.
\par The model o
f interaction machines as an extension of Turing machines was developed in the late 1990s [Weg97]. The theoretical framework has been improved in [GSW01]. Van Leeuwen, a Dutch expert on the theory of computation, wrote an article extending computers beyon
d Turing machines [VLW00], which referred to these recent models of interaction, admitting that
\par }\pard\plain \sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s16\qj\fi-360\li720\ri576\sl360\slmult1\nowidctlpar\tx360\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\adjustright \f16\fs18\cf1 {\fs22\lang1024 \tab \ldblquote
the classical Turing paradigm may no longer be fully appropriate to capture all features of present-day computing.\rdblquote
\par }\pard\plain \sl360\slmult1\nowidctlpar\tx360\adjustright \f16\fs18\cf1 {\lang1024
\par }\pard\plain \s16\qj\sl360\slmult1\nowidctlpar\adjustright \f16\fs18\cf1 {\fs22\lang1024 Our concept of interactive models was que
stioned because we originally failed to provide a theoretical framework comparable to that for Turing Machines. However, complete models of computation have often been developed with no theoretical foundation or mathematical models. Even Turing presented}
{\i\fs22\lang1024 c-machines}{\fs22\lang1024 [Tu36] and }{\i\fs22\lang1024 u-machines}{\fs22\lang1024 [Tu48] without a formal foundation.
\par }\pard \s16\qj\fi288\sl360\slmult1\nowidctlpar\tx288\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\adjustright {\fs22\lang1024
Though mathematics was adopted as a goal for modeling computers in the 1960s by analogy with mod\-els of physics, G\'f6del had shown in 1931 that logic cannot model mathematics [Go31] and Tur
ing showed that neither logic nor algorithms can completely model computing and human thought. In addition to inter\-action, other ways to extend computation beyond Turing machines have been considered, such as comput\-
ing with real numbers. However, the assumption that all of computation can be algorithmically specified is still widely accepted. Interaction machines have been criticized as an unnecessary Kuhnian paradigm shift. But G\'f6
del, Church, Turing, and more recently Milner, Wegner and Van Leeuwen have argued that this is not the case.
\par }\pard\plain \qj\fi720\li1152\sl600\slmult0\nowidctlpar\tx1152\tx1872\adjustright \f16\fs18\cf1 {\fs22\lang1024
\par }\pard\plain \s18\qj\fi-720\li720\sl280\slmult0\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright \f16\fs18\cf1 {\b\fs22\lang1024 Bibliography}{\fs22\lang1024
\par
\par [ACM68] Association for Computing Machinery, \ldblquote Curriculum '68: Recommendations for academic pro\-grams in computer science\rdblquote , In }{\i\fs22\lang1024 ACM Curricula recommendations for computer science, }{\fs22\lang1024
Association for Computing Machinery, 1968.
\par
\par [Br91] Rodney A. Brooks, \ldblquote Intelligence Without Reason\rdblquote , MIT AI Lab Technical Report #1293.
\par
\par [Go31] Kurt G\'f6del, \ldblquote On Formally Undecidable Propositions of Principia Mathematica and Related Sys\-tems\rdblquote , Monatshefte fur Mathematik und Physik (38), 1931 (in German); English translation in }{\i\fs22\lang1024 The Undecidable}{
\fs22\lang1024 , ed. Martin Davis, Raven Press 1965.
\par
\par [GSW01] Dina Goldin, Scott Smolka, Peter Wegner, \ldblquote Turing Machines, Transition Systems, and Interac\-tion\rdblquote ,}{\i\fs22\lang1024 8th Int'l Workshop on Expressiveness in Concurrency}{\fs22\lang1024 , Aarlborg, Denmark, August 2001.
\par }\pard \s18\qj\fi-720\li720\sl280\slmult0\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\adjustright {\fs22\lang1024
\par [Mi93] Robin Milner, \ldblquote Elements of Interaction\rdblquote (Turing Award lecture), }{\i\fs22\lang1024 Communications of the ACM}{\fs22\lang1024 (36:1), 1993.
\par }\pard \s18\qj\fi-720\li720\sl280\slmult0\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\tx10080\adjustright {\fs22\lang1024
\par [Tu36] Alan Turing, \ldblquote On Computable Numbers with an Application to the }{\i\fs22\lang1024 Entscheidungsproblem}{\fs22\lang1024 \rdblquote , }{\i\fs22\lang1024 Pro\-ceedings of the London Math Society}{\fs22\lang1024 2 (42), 1936, pp. 173-198.
\par
\par [Tu48] Alan Turing, \ldblquote Intelligent machinery\rdblquote , in D. C. Ince, }{\i\fs22\lang1024 Mechanical intelligence}{\fs22\lang1024 , North-Holland, 1992, pp. 107-127.
\par }\pard \s18\qj\fi-720\li720\sl280\slmult0\nowidctlpar\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\tx9360\adjustright {\fs22\lang1024
\par [VLW00] Jan van Leeuwen, Jiri Wiedermann, \ldblquote The Turing Machine Paradigm in Contemporary Comput\-ing\rdblquote , in }{\i\fs22\lang1024 Mathematics Unlimited - 2001 and Beyond}{\fs22\lang1024 , eds. B. Enquist and W. Schmidt, LNCS, Springer-Ver\-
lag, 2000.
\par
\par [Weg97] Peter Wegner, \ldblquote Why Interaction is More Powerful than Algorithms}{\i\fs22\lang1024 \rdblquote , Communications of the ACM}{\fs22\lang1024 40 (5), 1997.
\par }}