<p>Here's my favorite analogy.  Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because <i>Turing machines can't toast bread</i>.  Therefore, you need my revolutionary <i>new</i> model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.</p>

<p>You might say: sure, I have a "point", but it's a totally uninteresting one.  No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals.  If you want a TM to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster's <i>internal logic</i> (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!).  In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer.  In neither case are we saying anything that wouldn't have been obvious to Turing himself.</p>

<p>So, I'd say the reason why there's been no "followup" to Wegner and Goldin's diatribes is that TCS has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.</p>

<p><b>Update (8/30):</b> A related point is as follows.  Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing's notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?</p>

<p><b>Another Update:</b> To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question.  What is it that lets all those high-level languages <i>exist</i> in the first place, that ensures they can always be compiled down to machine code?  Could it be ... err ... <b>THE CHURCH-TURING THESIS</b>, the very same one you've been ragging on?  To clarify, the Church-Turing Thesis is not the claim that "TURING MACHINEZ RULE!!"  Rather, it's the claim that any reasonable programming language will be equivalent in expressive power to Turing machines -- and <i>as a consequence</i>, that you might as well think in terms of the higher-level languages if it's more convenient to do so.  This, of course, was a radical new insight 60-75 years ago.</p>

<p><b>Final Update:</b> I've created a <a href="http://www.scottaaronson.com/blog/?p=1121">blog post</a> for further discussion of this answer.</p>

CC BY-SA 3.0
2012-08-29T09:50:41.717Z
There is a substantial difference between toasters and interaction: every model of computation has some IO mechanism. Toasters show up only rarely. Some models of computation model IO naively: for example Turing machines deal with IO only informally. This is not problematic where computation is understood to be functional, i.e. starting with
an input and ending with an output, as it is with Turing
machines. However, this naively becomes burdensome when you want to deal with genuine concurrent phenomena, e.g. when are two interactive computations equal? (Continued below.)
Martin Berger
CC BY-SA 3.0
2012-08-29T09:51:11.247Z
(Continued.) How does this equality fare under parallel composition etc. In order to put such questions on a firm scientific basis, IO must be mathematised. TMs are mostly an inappropriate vehicle for such mathematisation. Whence concurrency theory.
Martin Berger
CC BY-SA 3.0
2012-08-29T10:03:52.103Z
I would argue that interaction is more fundamental than functional computation on binary strings (as e.g. modelled by Turing machines), and that computation should be seen as finitary, rule guided interaction.
Martin Berger
CC BY-SA 3.0
2012-08-29T13:25:54.187Z
I think this answer is overly dismissive. As Martin said, there is a difference between interaction and toast, and it can be argued that 1. interaction is fundamental to the mathematical structure of higher-order computation, and 2. higher-order structures arise naturally in the study of first-order computation.  So, the notion that any "internal logic" can be easily handled by TMs is begging the question: the point is that it may be easier to express (and reason mathematically about) this internal logic in higher-order/interactive terms.
Noam Zeilberger
CC BY-SA 3.0
2012-08-29T19:12:59.997Z
Martin and Noam: If your claim is that *the notion of a Turing machine did not, by itself, answer all interesting questions about computation*, then you're preaching to the converted and beating down an open door! Concurrency theory and higher-order programming languages are just two of the many wonderful things Turing left for the rest of us to figure out when he bit the apple -- others include complexity theory, graphics, operating systems, quantum computing, and more. Crucially, though, none of those things challenge the original Church-Turing Thesis, contrary to Wegner and Goldin's claim.
Scott Aaronson
CC BY-SA 3.0
2012-08-29T21:20:35.280Z
Scott, that is not their claim: "...the [CT] thesis is commonly interpreted to imply that Turing machines model all computation. It is a myth that the original thesis is equivalent to this interpretation of it. In fact, the [CT] thesis only refers to the computation of functions, and specifically excludes interactive computation. The original contribution of this paper is to identify and analyze the historical reasons for this myth." Whether you buy their argument is a separate question, but precisely they are not trying to refute the CT thesis, rather argue that its scope has been overstated.
Noam Zeilberger
CC BY-SA 3.0
2012-08-29T21:57:43.657Z
Noam: Yes, OK, looking again at their stuff ("Refuting the Church-Turing Thesis," "The Church-Turing Thesis: Breaking the Myth," etc. etc.), I stand corrected.  Their line is not that they refute the "original" Church-Turing Thesis, but something they call the "strong" Church-Turing Thesis: the "myth that TMs capture all of computation."  But I claim that their "Strong Church-Turing Thesis" is *itself* a myth.  The ideas they "refute" are ones that no sane person ever defended, exactly like the idea that computational universality implies that Turing machines can toast bread.
Scott Aaronson
CC BY-SA 3.0
2012-08-29T22:04:39.560Z
In case my views aren't clear enough yet, I should add that I find the whole "myth of the Church-Turing Thesis" literature not merely hectoring, but (more to the point) depressingly barren of ideas.  Reading it brings all the joy of reading someone claiming to refute Newtonian physics, not because of something cool like quantum mechanics or relativity, but because *"Newton's laws ignore friction"*.  Or listening to a child explain why she technically won a board game because she moved the pieces while you left to go to the bathroom.
Scott Aaronson
CC BY-SA 3.0
2012-08-29T22:56:12.043Z
I think the Lance Fortnow quote extracted below in vzn's answer (original article here: http://ubiquity.acm.org/article.cfm?id=1921573) demonstrates that at least a few sane people do hold the "Strong" thesis. Fortnow claims that the CT thesis can be "simply stated" as "everything computable is computable by a Turing machine", writing "everything" where he should have really written "every $f : \mathbb{N} \to \mathbb{N}$".
Noam Zeilberger
CC BY-SA 3.0
2012-08-29T23:26:49.210Z
(...and probably he was just being loose and writing that for rhetorical purposes, but I think it's indicative of the sort of ingrained cognitive dissonance Wegner and Goldin were arguing is harmful.)
Noam Zeilberger
CC BY-SA 3.0
2012-08-30T00:14:16.670Z
Noam: I'd say Lance's comment is like an 18th-century physicist's triumphant claim that Newtonian principles capture all currently-known phenomena. Other people might then object: what about the knowledge of glassblowing, lens-grinding, woodworking, etc. needed for us to "communicate" with these Newtonian principles via experiment? But in the sense he intended, the triumphant physicist would clearly have been right *at the time he was speaking*. All that other stuff fits snugly within the paradigm -- it doesn't *challenge the paradigm on its own territory*, as relativity and QM would do later.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T00:37:41.530Z
One can get into endless debates about what exactly the Church-Turing Thesis means. Personally, though, I've always preferred the version that takes it to be a *falsifiable empirical claim,* about what sorts of computational problems can be solved in the physical world. For that version has the enormous advantage of *clarity*: it makes it clear exactly what it would take to *falsify* the CT (namely, a revolution in physics), and why none of the stuff Wegner and Goldin talk about comes anywhere close to qualifying.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T01:24:22.700Z
@scott, find it pretty wild if you are comparing the current assertion of the supremacy/transcendance (in the sense that it _transcends_ all other possibilities, past, present, _future_) of the TM model with _newtonian physics_.. do you want to think that out a little further? think it actually undermines your initially stated position seriously....
vzn
CC BY-SA 3.0
2012-08-30T02:03:28.990Z
vzn: I chose my analogy very carefully. I was trying to show you how *open-minded* I was, which is why you might have found it "wild"! :) I'd be *thrilled* to be able to abandon the Church-Turing Thesis, just as quantum mechanics already caused most of us to abandon its polynomial-time version. My point was that that would require another scientific revolution on the same scale as QM. If people cry wolf (or cry Wegner?) at every trivial observation about TMs not being able to "interact" or toast bread, then how will they even recognize a *real* challenge to the CT if and when it ever comes?
Scott Aaronson
CC BY-SA 3.0
2012-08-30T02:29:45.150Z
newsflash, the new paradigm has arrived! in fact there are multiple new paradigms. the good news, it seems to me that QM computing is one of them! and it uses a model with qubits & their interactions. its modelled by a TM only in a very awkward way. the bad news, respectable academic work is being semitrashed by the TCS ivory tower & its self appointed guardians of the status quo. the toaster analogy is an obvious, embarrassing (but admittedly colorful!) straw man, and imho its a bit shameful that its currently the highest rated answer here. guess the old paradigm is quite safe for now!
vzn
CC BY-SA 3.0
2012-08-30T03:15:23.377Z
@vzn: CT pertains to how real-world computations can be simulated by TMs, and says nothing about how elegantly/awkwardly this is accomplished. If you meant what you said with "modelled by a TM only in a very awkward way", then I see nothing to challenge CT. Did you mean something else?
mikero
CC BY-SA 3.0
2012-08-30T03:29:18.987Z
how can we debate about a so-called Thesis named after both Turing and Church, neither of whom actually stated in their own writing the thesis as it has later been interpreted & evolved? Turing and Church made assertions about computation that were _correct in their time_ and even a few decades later, but life goes on! science _evolves_... Turing invented the idea _before electric typewriters_. the Turing machine is an analogy with one of the most sophisticated machines of Turings era-- a _manual typewriter_.... arguably we should update our models as our own understanding progresses...
vzn
CC BY-SA 3.0
2012-08-30T11:44:21.160Z
_how can we debate about a so-called Thesis named after both Turing and Church, neither of whom actually stated in their own writing the thesis as it has later been interpreted & evolved?_ — See also: Euler's formula, Gaussian elimination, Euclid's algorithm, the Pythagorean theorem.
Jeffε
CC BY-SA 3.0
2012-08-30T14:47:53.793Z
further thought-- am thinking of writing this up as a question someday. has anyone noticed that the qm computer model seems to assume _infinite precision in the position/orientation/coordinates of the qubits_? what is the proof that the QM computer model is not _more powerful_ than TMs? moreover, only ~1.5decade ago, pre Shor factoring, a complexity version variant of the CT thesis was held by a significant TCS segment, namely that QM computers are not significantly faster that TMs.... as my TCS prof(s) taught me, its called a _thesis_ and not a _law_ for a _reason_. _"it cannot be proven"_
vzn
CC BY-SA 3.0
2012-08-30T15:02:30.987Z
vzn: *Has anyone noticed* that QCs seem to assume infinite precision? ROTFL ... please read the Bernstein-Vazirani and BBBV papers from the early 90s, or learn about Holevo's Theorem, quantum fault-tolerance, etc.  The point of all that seminal work was to explain why the linearity of QM makes the continuity of amplitudes essentially as "benign" as the continuity of classical probabilities: for example, both can be rounded to finite precision without causing problems.  What's the proof that QCs can be simulated on a classical TM?  You'll find it in Bernstein-Vazirani, if you care to look.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T15:11:32.877Z
(cont'd) Also, the polynomial-time Church-Turing thesis was *never* as widely accepted as the original computability thesis, for excellent reason (though a tiny, wrong minority still clings to the classical polynomial-time CT even today).  I do, however, completely agree with you about even the original CT being an empirical thesis subject to falsification ... indeed, that was the entire point of my comment above explaining the Newtonian physics analogy, which you seem not to have read or understood.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T15:26:02.160Z
BQP==P is open last I heard! arguably this is closely connected to CT thesis. (since there are so many variants/versions, maybe someone can provide a link to the one actually under discussion...?) the basic _theoretical_ QM model is _noiseless_, no? it can be _amended_ to consider noise. _agreed_ the work on fault tolerance & the noise is crucial to a real-world implementation of the model. ("application-of-theory")
vzn
CC BY-SA 3.0
2012-08-30T15:32:20.043Z
I didn't say there's currently a *mathematical proof* that the holdouts for the classical polynomial-time CT are wrong -- I just said that they *are* wrong. :)  And BQP is contained in PSPACE; the point is that you can discretize without much affecting the acceptance probability.  You don't need any fancy fault-tolerance theorems to prove that result.  Again, please see Bernstein-Vazirani for the proof.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T16:11:41.990Z
are you talking about Bernstein Vazirani 1993? consider Deutsch 1985 "Quantum theory, the Church-Turing principle and the universal quantum computer" who states physics is continuous & TMs are discrete and that therefore QM computers can compute functions not computable by TMs (including perfectly random values etc). but later research seemed to go in a different direction.... anyway complexity theory has definitively shown over the years (& will continue to do so) that the CT thesis is just not so clearcut or cut-and-dried as was historically thought... it has _subtlety_ & _nuance_
vzn
CC BY-SA 3.0
2012-08-30T17:13:09.920Z
vzn: Deutsch was simply confused about this issue in the 80s. In his more recent writings, like "The Beginning of Infinity," he talks about the CT thesis more carefully (though still very differently than I would). Bernstein-Vazirani marked the first time anyone thought about quantum vs. classical computing in the "modern" way.  As for "subtlety & nuance," those are *precisely* what I find missing in Wegner and Goldin's diatribes, which set up a simplistic "Church-Turing dogma" no sane person actually believes in order to knock it down!
Scott Aaronson
CC BY-SA 3.0
2012-08-30T17:16:34.110Z
You want "subtlety & nuance" about what the (Extended) Church-Turing Thesis actually says?  Try, I dunno, http://www.scottaaronson.com/papers/samprel.pdf http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/optics.pdf http://www.scottaaronson.com/papers/qchvpra.pdf :-)
Scott Aaronson
CC BY-SA 3.0
2012-08-30T17:18:40.423Z
twenty comments! scott successfully turned a cstheory answer to a Shtetl Optimized blogpost...
Sasho Nikolov
CC BY-SA 3.0
2012-08-30T17:31:07.860Z
@ScottAaronson, the applications you list generally feature
terminating interative computation with simple communication
topologies. Things become more interesting and complicated when talking about non-terminating interactive computation. Consider for example the question: when are two non-terminating interactive computations equal (which has deep connections with proof-theory). Hundreds of answers have been given. Moreover, making the communication topology dynamic also complicates things. (Continued below.)
Martin Berger
CC BY-SA 3.0
2012-08-30T17:32:58.077Z
(Continued.) Moreover, looking at e.g. papers in multi-party cryptographic protocols, treatment of interaction is ad-hoc and not fully mathematised (e.g. the original Micali, Goldreich, Widgerson paper). A substantial problem in cryptographic protocols is compositionality. The original papers were super informal. Modern tools for the (semi-) automatic analysis of cryptographic protocols
(e.g. [CryptoVerif](http://www.cryptoverif.ens.fr)) are based on the
pi-calculus and not interactive TMs. For good reason. (Continued below.)
Martin Berger
CC BY-SA 3.0
2012-08-30T17:34:14.300Z
(Continued.) Finally, programming language researchers are primarily interested in
developing better languages and making verification easier. Since
there is no good algebra of TMs, let alone ITMs, basing this work on
(I)TMs is hopeless.
Martin Berger
CC BY-SA 3.0
2012-08-30T17:41:13.930Z
I also don't believe that researchers in the fields you list use TMs to form their intuitions about interaction. Instead they form their intuitions in other contexts, and then, painfully force their intuitions into the straightjacket of ITMs when writing papers, because in some communities that is the go-to model for formalisation. Partly this is for good reason, because TMs shine when thinking about complexity of computation on integers, which is often a concern.
Martin Berger
CC BY-SA 3.0
2012-08-30T17:46:45.433Z
it is depressing that someone built their reputation on a strawman argument. sure, there are models that capture some aspects of computation more elegantly that TMs. for what it's worth, word RAM machines are better for algorithm analysis; at our current level of understanding, the cell probe model is better for data structure lower bounds. the CT thesis (and yes, it is irrelevant whether Church and Turing actually thought that) states that all function-computing procedures inside a computational system are computable by a TM if and only if they are computable in the physical world.
Sasho Nikolov
CC BY-SA 3.0
2012-08-30T17:51:14.630Z
@MartinBerger: OK, but I see not a shadow of a hint of a challenge to the "Church-Turing paradigm" from that stuff---any more than the CT is challenged by the fact that Python is more fun to program in than assembly language. They're still friggin' Turing-equivalent! (And of course, the pioneer of the "algebraic" approach to computability was none other than Church!) Also, hardly anyone in TCS wastes their time anymore "painfully translating their intuitions into Turing-machine notation"---that went out of fashion in the 80s. Which, again, has nothing to do with the CT's intellectual status.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T18:05:35.907Z
@ScottAaronson, I agree with you, none of this challenges in any way the CT thesis.  I've said that much in my old reply to the original post below.  I find the Wegener/Goldin rhetoric unhelpful.   Maybe one way of looking at the issue is asking: is Turning equivalency a good
way of thinking about programming languages or computing paradigms?
Martin Berger
CC BY-SA 3.0
2012-08-30T19:39:57.527Z
@SashoNikolov: careful, you must say procedures computing *numeric* functions. At higher types, the Church-Turing thesis is false. This is why Martin and Noam are banging the drum on compositionality -- looking at the algebraic structure of programs leads to the question of how to compose higher-type objects, and this is a different world.
Neel Krishnaswami
CC BY-SA 3.0
2012-08-30T20:10:51.953Z
@NeelKrishnaswami this is a valid point but framing it as a statement about CTT obscures the real point imo. what happens physically in a computer when a function calls another function is perfectly well modeled by a TM receiving an encoding of another TM. i understand that this is not what you'd like to do in PL theory. but it does not mean that a TM cannot model the physical reality of what your computer does when say a system call is made. so I still think "CTT is false for higher order functions" is a confusing way to say "we want a more elegant abstraction for these questions"
Sasho Nikolov
CC BY-SA 3.0
2012-08-30T20:20:42.890Z
Could you people move over to some meta-thread somewhere?
Andrej Bauer
CC BY-SA 3.0
2012-08-30T20:25:04.647Z
Tell you what, I'll create a post on my blog, so people can continue the discussion there.
Scott Aaronson
CC BY-SA 3.0
2012-08-30T21:22:27.227Z
"depressingly barren of ideas" & like "listening to a child explain why she technically won a board game because she moved the pieces while you left to go to the bathroom." wow! anyway thx for all the refs to your own papers. actually one of my faves is [why philosophers should care about computational complexity](http://www.scottaaronson.com/papers/philos.pdf). from abstract: _...I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis._ — as long as its not 3rd rail/sacred cow topics like CT thesis, alternative models of computation etc! =)
vzn
CC BY-SA 3.0
2012-08-30T21:53:20.977Z
vzn: I think we should respect Andrej's request to move this discussion elsewhere.  But briefly, if alternative models of computation are "third rails" to me, then I suppose I've spent the last 13 years of my career electrocuting myself! :)  The *reason* I found quantum computing so exciting is that it *really* challenged the Polynomial-Time Church-Turing Thesis, in a way that no other realistic computing proposal yet has.  QC set a standard, compared to which most other challenges to the CT have all the advantages of theft over honest toil!  Please take further discussion to my blog.
Scott Aaronson
CC BY-SA 3.0
2012-09-01T03:30:00.370Z
scott, all due respect, but andrej is not a moderator. moderators have no comment/involvement so far except dave clark who posted an almost identical question on cs stackexchange & maybe some voting on this. comments are hidden & post does not go to top unless someone edits Q/A. just want to say, feel your position on this subj amts to a [double bind](http://en.wikipedia.org/wiki/Double_bind). think this work is harmless/innocuous taken as bordering on philosophy as it is partly intended. you say you encourage CS philosophy but then turn around & squish it like a bug on the windshield. =(
vzn
CC BY-SA 3.0
2012-09-01T15:02:29.963Z
vzn, I love "philosophy of science," but *never* when people interpret it to mean (as they sometimes do), "the use of philosophy as an excuse to avoid engaging with scientific discoveries that are well-established in the relevant field but that the speaker doesn't understand or doesn't like."  If you reread my CS&philosophy essay, I think (hope!) you'll find that I never use the word "philosophy" in that sense.
Scott Aaronson
CC BY-SA 3.0
2012-08-25T17:18:12.193Z
2012-08-30T20:55:26.743Z
2012-08-30T20:55:26.743Z
Scott Aaronson
<p>I think the issue is quite simple.</p>

<ol>
<li><p>All interactive formalisms can be simulated by Turing machines.</p></li>
<li><p>TMs are inconvenient languages for research on interactive computation (in most cases)    because the interesting issues get drowned out in
the noise of encodings.</p></li>
<li><p>Everybody working on the mathematisation of interaction knows this.</p></li>
</ol>

<p>Let me explain this in more detail.</p>

<p>Turing machines can obviously model all existing interactive models of
computing in the following sense: Choose some encoding of the relevant
syntax as binary strings, write a TM that takes as input two encoded
interactive programs P, Q (in a chosen model of interactive
computation) and returns true exactly when there is a one-step
reduction from P to Q in the relevant term rewriting system (if your
calculus has a ternary transition relation, proceed mutatis mutandis).
So you got a TM that does a step-by-step simulation of computation in
the interactive calculus.  Clearly pi-calculus, ambient calculus, CCS,
CSP, Petri-nets, timed pi-calculus and any other interactive model of
computation that has been studied can be expressed in this
sense. This is what people mean when they say interaction does not go beyond TMs. 
If you can come up with an interactive formalism that is physically
implementable but not expressible in this sense, please apply for your
Turing award.</p>

<p>N. Krishnaswami refers to a second approach to modelling interactivity
using oracle tapes. This approach is different from the interpretation
of the reduction/transition relation above, because the notion of TM
is changed: we move from plain TMs to TMs with oracle tapes. This
approach is popular in complexity theory and cryptography, mostly
because it enables researchers in these fields to transfer their tools
and results from the sequential to the concurrent world.</p>

<p>The problem with both approaches is that the genuinly concurrency
theoretic issues are obscured. Concurrency theory seeks to understand 
interaction as a phenomenon sui generis. Both approaches via TMs simply replace a
convenient formalism for expressing an interactive programming
language with a less convenient
formalism.</p>

<p>In neither approach genuinely concurrency theoretic issues,
i.e. communication and its supporting infrastructure have a direct
representation. They are there, visible to the trained eye, but encoded, hidden in the impenetrable fog of
encoding complexity.  So both approaches are bad at mathematisation of
the key concerns of interactive computation.  Take for example what
might be the best idea in the theory of programming languages in the
last half century, Milner et al's axiomatisation of scope extrusion (which
is a key step in a general theory of compositionality):</p>

<p>$$P|(\nu x)Q \ \equiv\ (\nu x)(P|Q) \quad\text{provided}\ x \notin fv(P)$$</p>

<p>How beautifully simple this idea is when expressed in a tailor-made
language language like the pi-calculus. Doing this using the encoding
of pi-calculus into TMs would probably fill 20 pages.</p>

<p>In other words, the invention of explicit formalisms for interaction
has made the following contribution to computer science: the direct
axiomatisation of the key primitives for communication (e.g. input and
output operators) and the supporting mechanisms (e.g. new name
generation, parallel composition etc). This axiomatisation has grown
into a veritable research tradition with its own conferences, schools,
terminology.</p>

<p>A similar situation obtains in mathematics: most concepts could be
written down using the language of set theory (or topos theory), but
we mostly prefer higher level concepts like groups, rings, topological
spaces and so on.</p>

CC BY-SA 3.0
2012-08-29T16:01:46.803Z
+1 for explaining the TM model's power w.r.t. interactive computation systems (it can simulate them).
Kaveh
CC BY-SA 3.0
2012-08-30T21:03:56.280Z
If only I could vote this up multiple times.
Vijay D
CC BY-SA 3.0
2012-08-29T10:01:17.460Z
2012-08-29T10:15:27.143Z
2012-08-29T10:15:27.143Z
Martin Berger
<p>In terms of number computability (i.e., computing functions from $\mathbb{N} \to \mathbb{N}$), all known models of computation are equivalent. </p>

<p>However, it's still true that Turing machines are fairly painful for modelling properties like interactivity. The reason is a little bit subtle, and has to do with the kinds of questions that we want to ask about interactive computations. </p>

<p>The usual first pass at modelling interaction with TMs is with oracle tapes. Intuitively, you can think of the string printed on the oracle tape as being a "prediction" of the Turing machine's I/O interaction with the environment. However, consider the sorts of questions we want to ask about interactive programs: for example, we might want to know that a computer program will not output your financial data unless it receives your username and password as input, and furthermore that programs do not leak information about passwords. Talking about this kind of constraint is very painful with oracle strings, since it reflects a temporal, epistemic constraint on the trace of the interaction, and the definition of oracle tapes ask you to supply the whole string up front. </p>

<p>I suspect getting this right is doable, and essentially amounts (1) to considering oracle strings not as a set, but as a topological space whose open sets encode the modal logic of time and knowledge that you want to model, and (2) ensuring that the theorems you prove are all continuous with respect to this topology, viewing predicates as continuous functions from oracle strings to truth values viewed as the Sierpinski space. I should emphasize that <strong>this is a guess</strong>, based on the analogy with domain theory. You'd need to work out the details (and probably submit them to LICS or something) to be sure.</p>

<p>As a result, people prefer to model interaction using things like the <a href="http://en.wikipedia.org/wiki/Dolev-Yao_model">Dolev-Yao</a> model, where you explicitly model the interaction between computers and the environment, so that you can explicitly characterize what the attacker knows. This makes it a lot easier to formulate appropriate modal logics for reasoning about security, since the state of the system plus the state of the environment are represented explicitly. </p>

CC BY-SA 3.0
2012-08-23T15:04:36.417Z
2012-08-23T15:04:36.417Z
Neel Krishnaswami
<p>reading <a href="http://blog.computationalcomplexity.org" rel="nofollow">Lance Fortnows blog,</a> just ran across this recent/nice/long survey article on the subj with many perspectives &amp; refs [1] (which has not been cited so far), includes Wegner/Goldin's perspective (among many others). Ill just quote Fortnows excellent/emphatic summary/declaration/assertion of the <b>near-official/uniform/unanimous TCS party line:</b></p>

<blockquote>
  <p>"A few computer scientists nevertheless try to argue that the [Church-Turing] thesis fails to capture some aspects of computation. Some of these have been published in prestigious venues such as Science, Communications of the ACM, and now as a whole series of papers in ACM Ubiquity. <b>Some people outside of computer science might think that there is a serious debate about the nature of computation. There isn't."</b></p>
</blockquote>

<p>[1] <a href="http://cacm.acm.org/magazines/2012/3/146259-turings-titanic-machine/fulltext" rel="nofollow">Turings Titanic Machine</a> by Barry S Cooper CACM Vol 55</p>

CC BY-SA 3.0
2012-08-29T21:51:03.913Z
2012-08-29T22:19:28.843Z
2012-08-29T22:19:28.843Z
vzn
<p>I am very much in agreement with Aaronson's comments.</p>

<p>I don't understand Milner's work. (e.g. pi calculus, which Milner invented to describe communicating processes). It is quite unreadable to me, as are nearly all papers on maths and logic, such as Lambek's theories. I have no doubt that Lambek's ideas are very good, but I would like to see them translated into some kind of pidgin English that I can read.</p>

<p>I am thrown by Milner's comment that lambda calculus is fine for "sequential processes" but that something more is needed for communicating processes. </p>

<p>My (perhaps naïve) viewpoint was that cannot be so, because pi-calculus is Turing complete, and  therefore can be converted mechanically to another Turing-complete notation, i.e. lambda calculus. Therefore Milner's pi-calculus notation can be converted automatically to lambda calculus.</p>

<p>It seems that I have identified a project: intuitively, it should be possible to mechanically convert from one Turing-complete language to another. is there an algorithm to do this? I will have to look on Google. Maybe this is incredibly hard to do, and as hard as the halting problem.</p>

<p>I looked yesterday on the net, and found papers on models of lambda calculus. I surprised to find that this seems to be a very deep rabbit hole.</p>

<p>Richard Mullins</p>

CC BY-SA 3.0
2016-02-26T12:11:15.913Z
2016-02-27T13:21:56.617Z
2016-02-27T13:21:56.617Z
richard mullins
<p>skimming Wegner's paper, its clear he's being a bit melodramatic and contrarian, but he has a point. the future of computing is arguably much more significantly centered in <em>robotics</em>, <em>AI</em>, or <em>datamining</em> (of vast real world "big data") which he doesnt seem to mention very much by name, but which he is clearly alluding to with his model. and these areas very much largely focus on the universe outside of a TMs inputs and outputs.</p>

<p>historically it also went by the name <em>cybernetics</em> as invented/formulated by Weiner. the point of robotics is that inputs and outputs are not merely digital and without meaning, which one might conclude looking at a TM; they are, but they have real world implications/effects/causes etc., and the machine forms a feedback loop with the environment.</p>

<p>so I would argue that TMs and robotics form a very natural synergy or symbiotic relationship so to speak. but this is not a radical assertion and what Wegner announces with great fanfare is, phrased in different terms, not very controversial or novel. in other words, Wegner seems to be setting himself up as an intellectual or academic iconoclast in his style on purpose... and so who is the TCS community to deny him that melodramatic framing? nevertheless see [2] for a serious rebuttal.</p>

<p>Wegner's example of driving a car is very relevant &amp; other key recent breakthoughs in <em>TCS</em> can be cited: </p>

<ul>
<li>the DARPA road race challenge and also Google's closing in on the technology of a driving car.[3]</li>
<li>the case of the Big Blue AI chess victory over Kasparov</li>
<li>the recent Deep Blue Jeopardy Challenge victory</li>
<li>the increasingly autonomous Mars rover</li>
<li>a recent announced breakthrough in unsupervised object recognition by Google.[4]</li>
<li>commercialized speech recognition</li>
</ul>

<p>but it is true, what started out decades ago as mere theory with TMs is now a very real-world phenomenon and segments of the <em>ivory tower</em> TCS community might be in some resistance or even denial of that fact and the associated, fundamental [near Kuhnian] transformation and shift "currently in play". this somewhat ironic because Turing was very applied in many of his perspectives &amp; studies such as his interest in an operational AI test (the Turing test), chemical dynamics, chess solving computation, etc [5]. </p>

<p>you can even see this in a microcosm on this site in clashes over how to define the scope, and heated arguments over whether a specific seemingly innocuous tag called <em>application-of-theory</em> is legitimate.[7]</p>

<p>and lets note that TCS is in fact studying many <em>interactive</em> models of computation and much key research is going on in that area... particularly interactive proof systems of which all the important computing classes can be defined in terms of.[6]</p>

<p>[1] <a href="http://www.cse.uconn.edu/~dqg/papers/cie05.pdf" rel="nofollow noreferrer">The Church-Turing thesis-- breaking the myth by Goldin &amp; Wegner</a></p>

<p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.3854&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Are there new models of computation? a reply to Goldin &amp; Wegner by Cockshott &amp; Michaelson</a></p>

<p>[3] <a href="http://m.theatlantic.com/technology/archive/2012/08/googles-self-driving-cars-300-000-miles-logged-not-a-single-accident-under-computer-control/260926" rel="nofollow noreferrer">Googles self-driving cars-- 300K miles logged, not a single accident under computer control, the Atlantic</a></p>

<p>[4] <a href="https://cstheory.stackexchange.com/questions/2681/algorithm-for-finding-similar-images/12001#12001">Google unsupervised object recognition of Youtube images</a></p>

<p>[5] <a href="https://cstheory.stackexchange.com/questions/11797/alan-turings-contributions-to-computer-science">Alan Turings contributions to CS</a></p>

<p>[6] <a href="https://cstheory.stackexchange.com/questions/12348/landscape-of-interactive-proof-systems">Landscape of interactive proof systems</a></p>

<p>[7] <a href="https://cstheory.meta.stackexchange.com/questions/1572/on-modifying-our-scope-a-proposal">On modifying our scope-- a proposal</a></p>

CC BY-SA 3.0
2012-08-26T01:29:09.000Z
_what started out decades ago as mere theory with TMs is now a very real-world phenomenon_ — Of course, we know that.  We call it "computer science".
Jeffε
CC BY-SA 3.0
2012-08-27T17:19:37.300Z
addendum, see also [Interactive computation, the new paradigm by Goldin, Smolka, Wegner (2006)](http://www.cs.brown.edu/sites/interaction-book/)
vzn
CC BY-SA 3.0
2012-08-29T22:35:51.873Z
an analogy that was at the edge of my thoughts while writing this, but finally figured out later: think the distinction of _in vivo_ vs _in vitro_ biology is relevant. the TM is analogous to the latter. other (emerging) models are analogous to the former. =)
vzn
CC BY-SA 3.0
2012-08-30T01:46:48.357Z
anyway the 2006 volume shows many prestigious computer scientists agreeing with the new paradigm. note also the final essay in the collection: Lynn Stein, Interaction, Computation, and Education — _This volume as a whole documents a fundamental shift in the culture of computation from a focus on algorithmic problem solving to a perspective in which interaction plays a central role. In this chapter, Stein points out that such a shift must be accompanied by a corresponding shift in computer science education, in the fundamental ``story'' we tell our students in their introductory courses._
vzn
CC BY-SA 3.0
2012-08-30T06:27:09.973Z
@vzn [Argument from authority](http://en.wikipedia.org/wiki/Argument_from_authority)
Martin Berger
CC BY-SA 3.0
2012-08-30T15:11:14.663Z
agreed! JeffE=authority =)
vzn
CC BY-SA 3.0
2012-08-25T22:05:54.513Z
2012-08-25T22:22:12.693Z
2017-04-13T12:32:28.080Z
vzn
<p>Here's the thing, once you add (pure) interactivity, formality goes out the window.  It's no longer a "closed" system.  The question then is, what is the notion of <strong>computation</strong> once interactivity enters in?   That answer:  well, either the other user/machine is substituting for some of your computation (which can be enscribed by just another, bigger, state machine) <em>or</em> you're no longer in a formally-definable system and you're now playing a <strong><em>game</em></strong>, in which case there is no application of the Church-Turing thesis.</p>

CC BY-SA 3.0
2012-08-30T06:22:43.523Z
Interactive models of computation like process calculi are games in the sense of [game semantics](http://en.wikipedia.org/wiki/Game_semantics).
Martin Berger
CC BY-SA 3.0
2012-08-30T18:13:59.890Z
@Martin:  No, you cannot "model" (human) interactivity.  What you are talking about are formal rule behaviors (as in a game), but then as soon as you've codified such, you're no longer in an interactive model.
Mark Rosenblitt-Janssen
CC BY-SA 3.0
2012-09-03T13:05:50.833Z
Human behaviour is irrelevant. What matters is that computable interactive devices act in an algorithmic, mechanical manner to their inputs.
Martin Berger
CC BY-SA 3.0
2012-09-03T16:46:47.160Z
Aye, there's the rub, i'nnit?  "...*computable* interactive devices".  But *is* it computable?
Mark Rosenblitt-Janssen
CC BY-SA 3.0
2012-09-04T00:06:43.203Z
@Martin:  I want to further elucidate the issue, because it's important.  The situation is analogous to an experiment measuring the veracity of the 2nd Law of Thermodyamics:  yes one may notice a local increase in order (computability), seemingly at odds with the 2nd Law, but it comes at an expense at a larger scale where it again returns to disorder (incomputable).  The error is where (i.e. at what level) is the system closed enough in order to be considered a "process calculi"?
Mark Rosenblitt-Janssen
CC BY-SA 3.0
2012-09-04T09:58:14.530Z
@ Mark J, I don't understand what you are saying. The interactive approach simply says that a device is computable if it reacts to its inputs in a mechanical way, using finite resources. Yes, if the other part of the interaction does something crazy, like inputting Chaitin's Omega, then the mechanical device can do something crazy, like computing the halting problem. So what?
Martin Berger
CC BY-SA 3.0
2012-09-04T10:00:26.303Z
In my opinion the CTT is not about what is physically implementable. Instead, it's a crude test that rules out certain clearly not implementable things: If the CTT says something is not computable, then it is not physically implementable, but I don't think the reverse implication holds.
Martin Berger
CC BY-SA 3.0
2012-09-04T21:20:57.877Z
@MartinBerger: "a device is computable if it reacts to its inputs ina mechanical way, using finite resources" -- but then it shouldn't be considered "interactive" should it?  It's more a double-sized Turing machine with the other machine at the other end of the tape and the translation table having a code to distinguish between one FSM and the other (i.e. still completely implementable in a single Turing machine).
Mark Rosenblitt-Janssen
CC BY-SA 3.0
2012-09-05T09:31:27.453Z
@ Mark J, the requirement "a device is computable if it reacts to its inputs in a mechanical way, using finite resources" does not require the inputs be generated mechancially. Certainly inputting Chaitin's Omega cannot be mechanically generated.
Martin Berger
CC BY-SA 3.0
2012-09-05T09:33:00.353Z
And yes, as I said in my comment below, interactive formalisms can be step-by-step simulated by TMs. However, step-by-step simulation is not the same thing as TM-simulatability in the sense of the strong CTT thesis.
Martin Berger
CC BY-SA 3.0
2012-08-30T02:29:59.720Z
2012-09-07T14:23:54.823Z
2012-09-07T14:23:54.823Z
Mark Rosenblitt-Janssen
<p>Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere.  That is, it is presented as encompassing all computation when in fact it applies only to computation of functions, which is a very small subset of all computation.  Instead they suggest we should seek to model interactive computation, where communication with the outside world happens during the computation.</p>

<p>The only critique I have seen of this work is in the <a href="http://lambda-the-ultimate.org/node/1038">Lambda the Ultimate</a> forum, where somebody lamented these authors for continually publishing what is obviously known.  My question then is, is there any more critique into this line of thinking, and in particular their Persistent Turing Machines.  And if not, why then is it seemingly studied very little (I could be mistaken).  Lastly, how does the notion of universality translate to an interactive domain.</p>

CC BY-SA 3.0
2012-08-22T06:13:51.913Z
ps: you may want also have a look at [this question](http://cstheory.stackexchange.com/q/9555/186) about hyper-computation.
Kaveh
CC BY-SA 3.0
2012-08-22T10:52:27.970Z
Here's another similar [question](http://cs.stackexchange.com/q/438/31).
Dave Clarke
CC BY-SA 3.0
2012-08-23T19:20:49.527Z
I think Andrej and Neel have explained [here](http://cstheory.stackexchange.com/q/1117/186) that the answer is negative for the higher-type function computation problems. So essentially Church-Turing Thesis is about *number* function computation problems. The usual equivalences between models of computation do not hold over higher-types. (However, as I understand it, this is more about the interaction mechanisms and how higher-type objects are represented than about the computational power of models.) (reposting to fix a few typos)
Kaveh
CC BY-SA 3.0
2012-08-23T21:19:54.663Z
I agree with Kaveh.
Andrej Bauer
CC BY-SA 3.0
2012-08-31T01:26:05.573Z
actually wegners 1st paper along these lines seems to date to 1996-1997, "Why interaction is more important than algorithms" or "The Paradigm Shift from Algorithms to Interaction". later in the paper there is ref to Platos cave, "the Turing tarpit" (?), Kants Critique of Pure Reason, Marx's dialectical logic, Descartes, Penrose, Searle. so maybe it should be seen as bordering on the philosophical and not so much in the vein of technical/math TCS. no math, no lemmas or proofs or thms. while maybe a bit grandiose, he earnestly seeks to understand "the big picture" of CT thesis wrt history etc...
vzn
<computability><turing-machines><machine-models><church-turing-thesis>
Applicability of Church-Turing thesis to interactive models of computation 
zenna
# Applicability of Church-Turing thesis to interactive models of computation 

(Asked by: username_0 on 2012-08-21)

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. That is, it is presented as encompassing all computation when in fact it applies only to computation of functions, which is a very small subset of all computation. Instead they suggest we should seek to model interactive computation, where communication with the outside world happens during the computation.

The only critique I have seen of this work is in the [Lambda the Ultimate](http://lambda-the-ultimate.org/node/1038) forum, where somebody lamented these authors for continually publishing what is obviously known. My question then is, is there any more critique into this line of thinking, and in particular their Persistent Turing Machines. And if not, why then is it seemingly studied very little (I could be mistaken). Lastly, how does the notion of universality translate to an interactive domain.

**Tags:** computability, turing-machines, machine-models, church-turing-thesis
> **Comments:**
> **username_1**: ps: you may want also have a look at [this question](http://cstheory.stackexchange.com/q/9555/186) about hyper-computation.  
> **username_2**: Here's another similar [question](http://cs.stackexchange.com/q/438/31).  
> **username_1**: I think Andrej and Neel have explained [here](http://cstheory.stackexchange.com/q/1117/186) that the answer is negative for the higher-type function computation problems. So essentially Church-Turing Thesis is about *number* function computation problems. The usual equivalences between models of computation do not hold over higher-types. (However, as I understand it, this is more about the interaction mechanisms and how higher-type objects are represented than about the computational power of models.) (reposting to fix a few typos)  
> **username_3**: I agree with Kaveh.  
> **username_4**: actually wegners 1st paper along these lines seems to date to 1996-1997, "Why interaction is more important than algorithms" or "The Paradigm Shift from Algorithms to Interaction". later in the paper there is ref to Platos cave, "the Turing tarpit" (?), Kants Critique of Pure Reason, Marx's dialectical logic, Descartes, Penrose, Searle. so maybe it should be seen as bordering on the philosophical and not so much in the vein of technical/math TCS. no math, no lemmas or proofs or thms. while maybe a bit grandiose, he earnestly seeks to understand "the big picture" of CT thesis wrt history etc...  

---

## 7 answers

### Answer by username_5 on 2012-08-25. Score: 76

Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because *Turing machines can't toast bread*. Therefore, you need my revolutionary *new* model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.

You might say: sure, I have a "point", but it's a totally uninteresting one. No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals. If you want a TM to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster's *internal logic* (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!). In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer. In neither case are we saying anything that wouldn't have been obvious to Turing himself.

So, I'd say the reason why there's been no "followup" to Wegner and Goldin's diatribes is that TCS has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.

**Update (8/30):** A related point is as follows. Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing's notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?

**Another Update:** To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question. What is it that lets all those high-level languages *exist* in the first place, that ensures they can always be compiled down to machine code? Could it be ... err ... **THE CHURCH-TURING THESIS**, the very same one you've been ragging on? To clarify, the Church-Turing Thesis is not the claim that "TURING MACHINEZ RULE!!" Rather, it's the claim that any reasonable programming language will be equivalent in expressive power to Turing machines -- and *as a consequence*, that you might as well think in terms of the higher-level languages if it's more convenient to do so. This, of course, was a radical new insight 60-75 years ago.

**Final Update:** I've created a [blog post](http://www.scottaaronson.com/blog/?p=1121) for further discussion of this answer.

> **Comments:**
> **username_6**: There is a substantial difference between toasters and interaction: every model of computation has some IO mechanism. Toasters show up only rarely. Some models of computation model IO naively: for example Turing machines deal with IO only informally. This is not problematic where computation is understood to be functional, i.e. starting with an input and ending with an output, as it is with Turing machines. However, this naively becomes burdensome when you want to deal with genuine concurrent phenomena, e.g. when are two interactive computations equal? (Continued below.)  
> **username_6**: (Continued.) How does this equality fare under parallel composition etc. In order to put such questions on a firm scientific basis, IO must be mathematised. TMs are mostly an inappropriate vehicle for such mathematisation. Whence concurrency theory.  
> **username_6**: I would argue that interaction is more fundamental than functional computation on binary strings (as e.g. modelled by Turing machines), and that computation should be seen as finitary, rule guided interaction.  
> **username_7**: I think this answer is overly dismissive. As Martin said, there is a difference between interaction and toast, and it can be argued that 1. interaction is fundamental to the mathematical structure of higher-order computation, and 2. higher-order structures arise naturally in the study of first-order computation.  So, the notion that any "internal logic" can be easily handled by TMs is begging the question: the point is that it may be easier to express (and reason mathematically about) this internal logic in higher-order/interactive terms.  
> **username_5**: Martin and Noam: If your claim is that *the notion of a Turing machine did not, by itself, answer all interesting questions about computation*, then you're preaching to the converted and beating down an open door! Concurrency theory and higher-order programming languages are just two of the many wonderful things Turing left for the rest of us to figure out when he bit the apple -- others include complexity theory, graphics, operating systems, quantum computing, and more. Crucially, though, none of those things challenge the original Church-Turing Thesis, contrary to Wegner and Goldin's claim.  
> **username_7**: Scott, that is not their claim: "...the [CT] thesis is commonly interpreted to imply that Turing machines model all computation. It is a myth that the original thesis is equivalent to this interpretation of it. In fact, the [CT] thesis only refers to the computation of functions, and specifically excludes interactive computation. The original contribution of this paper is to identify and analyze the historical reasons for this myth." Whether you buy their argument is a separate question, but precisely they are not trying to refute the CT thesis, rather argue that its scope has been overstated.  
> **username_5**: Noam: Yes, OK, looking again at their stuff ("Refuting the Church-Turing Thesis," "The Church-Turing Thesis: Breaking the Myth," etc. etc.), I stand corrected.  Their line is not that they refute the "original" Church-Turing Thesis, but something they call the "strong" Church-Turing Thesis: the "myth that TMs capture all of computation."  But I claim that their "Strong Church-Turing Thesis" is *itself* a myth.  The ideas they "refute" are ones that no sane person ever defended, exactly like the idea that computational universality implies that Turing machines can toast bread.  
> **username_5**: In case my views aren't clear enough yet, I should add that I find the whole "myth of the Church-Turing Thesis" literature not merely hectoring, but (more to the point) depressingly barren of ideas.  Reading it brings all the joy of reading someone claiming to refute Newtonian physics, not because of something cool like quantum mechanics or relativity, but because *"Newton's laws ignore friction"*.  Or listening to a child explain why she technically won a board game because she moved the pieces while you left to go to the bathroom.  
> **username_7**: I think the Lance Fortnow quote extracted below in vzn's answer (original article here: http://ubiquity.acm.org/article.cfm?id=1921573) demonstrates that at least a few sane people do hold the "Strong" thesis. Fortnow claims that the CT thesis can be "simply stated" as "everything computable is computable by a Turing machine", writing "everything" where he should have really written "every $f : \mathbb{N} \to \mathbb{N}$".  
> **username_7**: (...and probably he was just being loose and writing that for rhetorical purposes, but I think it's indicative of the sort of ingrained cognitive dissonance Wegner and Goldin were arguing is harmful.)  
> **username_5**: Noam: I'd say Lance's comment is like an 18th-century physicist's triumphant claim that Newtonian principles capture all currently-known phenomena. Other people might then object: what about the knowledge of glassblowing, lens-grinding, woodworking, etc. needed for us to "communicate" with these Newtonian principles via experiment? But in the sense he intended, the triumphant physicist would clearly have been right *at the time he was speaking*. All that other stuff fits snugly within the paradigm -- it doesn't *challenge the paradigm on its own territory*, as relativity and QM would do later.  
> **username_5**: One can get into endless debates about what exactly the Church-Turing Thesis means. Personally, though, I've always preferred the version that takes it to be a *falsifiable empirical claim,* about what sorts of computational problems can be solved in the physical world. For that version has the enormous advantage of *clarity*: it makes it clear exactly what it would take to *falsify* the CT (namely, a revolution in physics), and why none of the stuff Wegner and Goldin talk about comes anywhere close to qualifying.  
> **username_4**: @scott, find it pretty wild if you are comparing the current assertion of the supremacy/transcendance (in the sense that it _transcends_ all other possibilities, past, present, _future_) of the TM model with _newtonian physics_.. do you want to think that out a little further? think it actually undermines your initially stated position seriously....  
> **username_5**: vzn: I chose my analogy very carefully. I was trying to show you how *open-minded* I was, which is why you might have found it "wild"! :) I'd be *thrilled* to be able to abandon the Church-Turing Thesis, just as quantum mechanics already caused most of us to abandon its polynomial-time version. My point was that that would require another scientific revolution on the same scale as QM. If people cry wolf (or cry Wegner?) at every trivial observation about TMs not being able to "interact" or toast bread, then how will they even recognize a *real* challenge to the CT if and when it ever comes?  
> **username_4**: newsflash, the new paradigm has arrived! in fact there are multiple new paradigms. the good news, it seems to me that QM computing is one of them! and it uses a model with qubits & their interactions. its modelled by a TM only in a very awkward way. the bad news, respectable academic work is being semitrashed by the TCS ivory tower & its self appointed guardians of the status quo. the toaster analogy is an obvious, embarrassing (but admittedly colorful!) straw man, and imho its a bit shameful that its currently the highest rated answer here. guess the old paradigm is quite safe for now!  
> **username_8**: @vzn: CT pertains to how real-world computations can be simulated by TMs, and says nothing about how elegantly/awkwardly this is accomplished. If you meant what you said with "modelled by a TM only in a very awkward way", then I see nothing to challenge CT. Did you mean something else?  
> **username_4**: how can we debate about a so-called Thesis named after both Turing and Church, neither of whom actually stated in their own writing the thesis as it has later been interpreted & evolved? Turing and Church made assertions about computation that were _correct in their time_ and even a few decades later, but life goes on! science _evolves_... Turing invented the idea _before electric typewriters_. the Turing machine is an analogy with one of the most sophisticated machines of Turings era-- a _manual typewriter_.... arguably we should update our models as our own understanding progresses...  
> **username_9**: _how can we debate about a so-called Thesis named after both Turing and Church, neither of whom actually stated in their own writing the thesis as it has later been interpreted & evolved?_ — See also: Euler's formula, Gaussian elimination, Euclid's algorithm, the Pythagorean theorem.  
> **username_4**: further thought-- am thinking of writing this up as a question someday. has anyone noticed that the qm computer model seems to assume _infinite precision in the position/orientation/coordinates of the qubits_? what is the proof that the QM computer model is not _more powerful_ than TMs? moreover, only ~1.5decade ago, pre Shor factoring, a complexity version variant of the CT thesis was held by a significant TCS segment, namely that QM computers are not significantly faster that TMs.... as my TCS prof(s) taught me, its called a _thesis_ and not a _law_ for a _reason_. _"it cannot be proven"_  
> **username_5**: vzn: *Has anyone noticed* that QCs seem to assume infinite precision? ROTFL ... please read the Bernstein-Vazirani and BBBV papers from the early 90s, or learn about Holevo's Theorem, quantum fault-tolerance, etc.  The point of all that seminal work was to explain why the linearity of QM makes the continuity of amplitudes essentially as "benign" as the continuity of classical probabilities: for example, both can be rounded to finite precision without causing problems.  What's the proof that QCs can be simulated on a classical TM?  You'll find it in Bernstein-Vazirani, if you care to look.  
> **username_5**: (cont'd) Also, the polynomial-time Church-Turing thesis was *never* as widely accepted as the original computability thesis, for excellent reason (though a tiny, wrong minority still clings to the classical polynomial-time CT even today).  I do, however, completely agree with you about even the original CT being an empirical thesis subject to falsification ... indeed, that was the entire point of my comment above explaining the Newtonian physics analogy, which you seem not to have read or understood.  
> **username_4**: BQP==P is open last I heard! arguably this is closely connected to CT thesis. (since there are so many variants/versions, maybe someone can provide a link to the one actually under discussion...?) the basic _theoretical_ QM model is _noiseless_, no? it can be _amended_ to consider noise. _agreed_ the work on fault tolerance & the noise is crucial to a real-world implementation of the model. ("application-of-theory")  
> **username_5**: I didn't say there's currently a *mathematical proof* that the holdouts for the classical polynomial-time CT are wrong -- I just said that they *are* wrong. :)  And BQP is contained in PSPACE; the point is that you can discretize without much affecting the acceptance probability.  You don't need any fancy fault-tolerance theorems to prove that result.  Again, please see Bernstein-Vazirani for the proof.  
> **username_4**: are you talking about Bernstein Vazirani 1993? consider Deutsch 1985 "Quantum theory, the Church-Turing principle and the universal quantum computer" who states physics is continuous & TMs are discrete and that therefore QM computers can compute functions not computable by TMs (including perfectly random values etc). but later research seemed to go in a different direction.... anyway complexity theory has definitively shown over the years (& will continue to do so) that the CT thesis is just not so clearcut or cut-and-dried as was historically thought... it has _subtlety_ & _nuance_  
> **username_5**: vzn: Deutsch was simply confused about this issue in the 80s. In his more recent writings, like "The Beginning of Infinity," he talks about the CT thesis more carefully (though still very differently than I would). Bernstein-Vazirani marked the first time anyone thought about quantum vs. classical computing in the "modern" way.  As for "subtlety & nuance," those are *precisely* what I find missing in Wegner and Goldin's diatribes, which set up a simplistic "Church-Turing dogma" no sane person actually believes in order to knock it down!  
> **username_5**: You want "subtlety & nuance" about what the (Extended) Church-Turing Thesis actually says?  Try, I dunno, http://www.scottaaronson.com/papers/samprel.pdf http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/optics.pdf http://www.scottaaronson.com/papers/qchvpra.pdf :-)  
> **username_10**: twenty comments! scott successfully turned a cstheory answer to a Shtetl Optimized blogpost...  
> **username_6**: @ScottAaronson, the applications you list generally feature terminating interative computation with simple communication topologies. Things become more interesting and complicated when talking about non-terminating interactive computation. Consider for example the question: when are two non-terminating interactive computations equal (which has deep connections with proof-theory). Hundreds of answers have been given. Moreover, making the communication topology dynamic also complicates things. (Continued below.)  
> **username_6**: (Continued.) Moreover, looking at e.g. papers in multi-party cryptographic protocols, treatment of interaction is ad-hoc and not fully mathematised (e.g. the original Micali, Goldreich, Widgerson paper). A substantial problem in cryptographic protocols is compositionality. The original papers were super informal. Modern tools for the (semi-) automatic analysis of cryptographic protocols (e.g. [CryptoVerif](http://www.cryptoverif.ens.fr)) are based on the pi-calculus and not interactive TMs. For good reason. (Continued below.)  
> **username_6**: (Continued.) Finally, programming language researchers are primarily interested in developing better languages and making verification easier. Since there is no good algebra of TMs, let alone ITMs, basing this work on (I)TMs is hopeless.  
> **username_6**: I also don't believe that researchers in the fields you list use TMs to form their intuitions about interaction. Instead they form their intuitions in other contexts, and then, painfully force their intuitions into the straightjacket of ITMs when writing papers, because in some communities that is the go-to model for formalisation. Partly this is for good reason, because TMs shine when thinking about complexity of computation on integers, which is often a concern.  
> **username_10**: it is depressing that someone built their reputation on a strawman argument. sure, there are models that capture some aspects of computation more elegantly that TMs. for what it's worth, word RAM machines are better for algorithm analysis; at our current level of understanding, the cell probe model is better for data structure lower bounds. the CT thesis (and yes, it is irrelevant whether Church and Turing actually thought that) states that all function-computing procedures inside a computational system are computable by a TM if and only if they are computable in the physical world.  
> **username_5**: @MartinBerger: OK, but I see not a shadow of a hint of a challenge to the "Church-Turing paradigm" from that stuff---any more than the CT is challenged by the fact that Python is more fun to program in than assembly language. They're still friggin' Turing-equivalent! (And of course, the pioneer of the "algebraic" approach to computability was none other than Church!) Also, hardly anyone in TCS wastes their time anymore "painfully translating their intuitions into Turing-machine notation"---that went out of fashion in the 80s. Which, again, has nothing to do with the CT's intellectual status.  
> **username_6**: @ScottAaronson, I agree with you, none of this challenges in any way the CT thesis.  I've said that much in my old reply to the original post below.  I find the Wegener/Goldin rhetoric unhelpful.   Maybe one way of looking at the issue is asking: is Turning equivalency a good way of thinking about programming languages or computing paradigms?  
> **username_11**: @SashoNikolov: careful, you must say procedures computing *numeric* functions. At higher types, the Church-Turing thesis is false. This is why Martin and Noam are banging the drum on compositionality -- looking at the algebraic structure of programs leads to the question of how to compose higher-type objects, and this is a different world.  
> **username_10**: @NeelKrishnaswami this is a valid point but framing it as a statement about CTT obscures the real point imo. what happens physically in a computer when a function calls another function is perfectly well modeled by a TM receiving an encoding of another TM. i understand that this is not what you'd like to do in PL theory. but it does not mean that a TM cannot model the physical reality of what your computer does when say a system call is made. so I still think "CTT is false for higher order functions" is a confusing way to say "we want a more elegant abstraction for these questions"  
> **username_3**: Could you people move over to some meta-thread somewhere?  
> **username_5**: Tell you what, I'll create a post on my blog, so people can continue the discussion there.  
> **username_4**: "depressingly barren of ideas" & like "listening to a child explain why she technically won a board game because she moved the pieces while you left to go to the bathroom." wow! anyway thx for all the refs to your own papers. actually one of my faves is [why philosophers should care about computational complexity](http://www.scottaaronson.com/papers/philos.pdf). from abstract: _...I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis._ — as long as its not 3rd rail/sacred cow topics like CT thesis, alternative models of computation etc! =)  
> **username_5**: vzn: I think we should respect Andrej's request to move this discussion elsewhere.  But briefly, if alternative models of computation are "third rails" to me, then I suppose I've spent the last 13 years of my career electrocuting myself! :)  The *reason* I found quantum computing so exciting is that it *really* challenged the Polynomial-Time Church-Turing Thesis, in a way that no other realistic computing proposal yet has.  QC set a standard, compared to which most other challenges to the CT have all the advantages of theft over honest toil!  Please take further discussion to my blog.  
> **username_4**: scott, all due respect, but andrej is not a moderator. moderators have no comment/involvement so far except dave clark who posted an almost identical question on cs stackexchange & maybe some voting on this. comments are hidden & post does not go to top unless someone edits Q/A. just want to say, feel your position on this subj amts to a [double bind](http://en.wikipedia.org/wiki/Double_bind). think this work is harmless/innocuous taken as bordering on philosophy as it is partly intended. you say you encourage CS philosophy but then turn around & squish it like a bug on the windshield. =(  
> **username_5**: vzn, I love "philosophy of science," but *never* when people interpret it to mean (as they sometimes do), "the use of philosophy as an excuse to avoid engaging with scientific discoveries that are well-established in the relevant field but that the speaker doesn't understand or doesn't like."  If you reread my CS&philosophy essay, I think (hope!) you'll find that I never use the word "philosophy" in that sense.  

---

### Answer by username_6 on 2012-08-29. Score: 37

I think the issue is quite simple.

1. All interactive formalisms can be simulated by Turing machines.
2. TMs are inconvenient languages for research on interactive computation (in most cases) because the interesting issues get drowned out in
   the noise of encodings.
3. Everybody working on the mathematisation of interaction knows this.

Let me explain this in more detail.

Turing machines can obviously model all existing interactive models of
computing in the following sense: Choose some encoding of the relevant
syntax as binary strings, write a TM that takes as input two encoded
interactive programs P, Q (in a chosen model of interactive
computation) and returns true exactly when there is a one-step
reduction from P to Q in the relevant term rewriting system (if your
calculus has a ternary transition relation, proceed mutatis mutandis).
So you got a TM that does a step-by-step simulation of computation in
the interactive calculus. Clearly pi-calculus, ambient calculus, CCS,
CSP, Petri-nets, timed pi-calculus and any other interactive model of
computation that has been studied can be expressed in this
sense. This is what people mean when they say interaction does not go beyond TMs.
If you can come up with an interactive formalism that is physically
implementable but not expressible in this sense, please apply for your
Turing award.

N. Krishnaswami refers to a second approach to modelling interactivity
using oracle tapes. This approach is different from the interpretation
of the reduction/transition relation above, because the notion of TM
is changed: we move from plain TMs to TMs with oracle tapes. This
approach is popular in complexity theory and cryptography, mostly
because it enables researchers in these fields to transfer their tools
and results from the sequential to the concurrent world.

The problem with both approaches is that the genuinly concurrency
theoretic issues are obscured. Concurrency theory seeks to understand
interaction as a phenomenon sui generis. Both approaches via TMs simply replace a
convenient formalism for expressing an interactive programming
language with a less convenient
formalism.

In neither approach genuinely concurrency theoretic issues,
i.e. communication and its supporting infrastructure have a direct
representation. They are there, visible to the trained eye, but encoded, hidden in the impenetrable fog of
encoding complexity. So both approaches are bad at mathematisation of
the key concerns of interactive computation. Take for example what
might be the best idea in the theory of programming languages in the
last half century, Milner et al's axiomatisation of scope extrusion (which
is a key step in a general theory of compositionality):

$$P|(\nu x)Q \ \equiv\ (\nu x)(P|Q) \quad\text{provided}\ x \notin fv(P)$$

How beautifully simple this idea is when expressed in a tailor-made
language language like the pi-calculus. Doing this using the encoding
of pi-calculus into TMs would probably fill 20 pages.

In other words, the invention of explicit formalisms for interaction
has made the following contribution to computer science: the direct
axiomatisation of the key primitives for communication (e.g. input and
output operators) and the supporting mechanisms (e.g. new name
generation, parallel composition etc). This axiomatisation has grown
into a veritable research tradition with its own conferences, schools,
terminology.

A similar situation obtains in mathematics: most concepts could be
written down using the language of set theory (or topos theory), but
we mostly prefer higher level concepts like groups, rings, topological
spaces and so on.

> **Comments:**
> **username_1**: +1 for explaining the TM model's power w.r.t. interactive computation systems (it can simulate them).  
> **username_12**: If only I could vote this up multiple times.  

---

### Answer by username_11 on 2012-08-23. Score: 28

In terms of number computability (i.e., computing functions from $\mathbb{N} \to \mathbb{N}$), all known models of computation are equivalent.

However, it's still true that Turing machines are fairly painful for modelling properties like interactivity. The reason is a little bit subtle, and has to do with the kinds of questions that we want to ask about interactive computations.

The usual first pass at modelling interaction with TMs is with oracle tapes. Intuitively, you can think of the string printed on the oracle tape as being a "prediction" of the Turing machine's I/O interaction with the environment. However, consider the sorts of questions we want to ask about interactive programs: for example, we might want to know that a computer program will not output your financial data unless it receives your username and password as input, and furthermore that programs do not leak information about passwords. Talking about this kind of constraint is very painful with oracle strings, since it reflects a temporal, epistemic constraint on the trace of the interaction, and the definition of oracle tapes ask you to supply the whole string up front.

I suspect getting this right is doable, and essentially amounts (1) to considering oracle strings not as a set, but as a topological space whose open sets encode the modal logic of time and knowledge that you want to model, and (2) ensuring that the theorems you prove are all continuous with respect to this topology, viewing predicates as continuous functions from oracle strings to truth values viewed as the Sierpinski space. I should emphasize that **this is a guess**, based on the analogy with domain theory. You'd need to work out the details (and probably submit them to LICS or something) to be sure.

As a result, people prefer to model interaction using things like the [Dolev-Yao](http://en.wikipedia.org/wiki/Dolev-Yao_model) model, where you explicitly model the interaction between computers and the environment, so that you can explicitly characterize what the attacker knows. This makes it a lot easier to formulate appropriate modal logics for reasoning about security, since the state of the system plus the state of the environment are represented explicitly.


---

### Answer by username_4 on 2012-08-29. Score: 1

reading [Lance Fortnows blog,](http://blog.computationalcomplexity.org) just ran across this recent/nice/long survey article on the subj with many perspectives & refs [1] (which has not been cited so far), includes Wegner/Goldin's perspective (among many others). Ill just quote Fortnows excellent/emphatic summary/declaration/assertion of the **near-official/uniform/unanimous TCS party line:**

> "A few computer scientists nevertheless try to argue that the [Church-Turing] thesis fails to capture some aspects of computation. Some of these have been published in prestigious venues such as Science, Communications of the ACM, and now as a whole series of papers in ACM Ubiquity. **Some people outside of computer science might think that there is a serious debate about the nature of computation. There isn't."**

[1] [Turings Titanic Machine](http://cacm.acm.org/magazines/2012/3/146259-turings-titanic-machine/fulltext) by Barry S Cooper CACM Vol 55


---

### Answer by username_13 on 2016-02-26. Score: -4

I am very much in agreement with Aaronson's comments.

I don't understand Milner's work. (e.g. pi calculus, which Milner invented to describe communicating processes). It is quite unreadable to me, as are nearly all papers on maths and logic, such as Lambek's theories. I have no doubt that Lambek's ideas are very good, but I would like to see them translated into some kind of pidgin English that I can read.

I am thrown by Milner's comment that lambda calculus is fine for "sequential processes" but that something more is needed for communicating processes.

My (perhaps naïve) viewpoint was that cannot be so, because pi-calculus is Turing complete, and therefore can be converted mechanically to another Turing-complete notation, i.e. lambda calculus. Therefore Milner's pi-calculus notation can be converted automatically to lambda calculus.

It seems that I have identified a project: intuitively, it should be possible to mechanically convert from one Turing-complete language to another. is there an algorithm to do this? I will have to look on Google. Maybe this is incredibly hard to do, and as hard as the halting problem.

I looked yesterday on the net, and found papers on models of lambda calculus. I surprised to find that this seems to be a very deep rabbit hole.

Richard Mullins


---

### Answer by username_4 on 2012-08-25. Score: -8

skimming Wegner's paper, its clear he's being a bit melodramatic and contrarian, but he has a point. the future of computing is arguably much more significantly centered in *robotics*, *AI*, or *datamining* (of vast real world "big data") which he doesnt seem to mention very much by name, but which he is clearly alluding to with his model. and these areas very much largely focus on the universe outside of a TMs inputs and outputs.

historically it also went by the name *cybernetics* as invented/formulated by Weiner. the point of robotics is that inputs and outputs are not merely digital and without meaning, which one might conclude looking at a TM; they are, but they have real world implications/effects/causes etc., and the machine forms a feedback loop with the environment.

so I would argue that TMs and robotics form a very natural synergy or symbiotic relationship so to speak. but this is not a radical assertion and what Wegner announces with great fanfare is, phrased in different terms, not very controversial or novel. in other words, Wegner seems to be setting himself up as an intellectual or academic iconoclast in his style on purpose... and so who is the TCS community to deny him that melodramatic framing? nevertheless see [2] for a serious rebuttal.

Wegner's example of driving a car is very relevant & other key recent breakthoughs in *TCS* can be cited:

* the DARPA road race challenge and also Google's closing in on the technology of a driving car.[3]
* the case of the Big Blue AI chess victory over Kasparov
* the recent Deep Blue Jeopardy Challenge victory
* the increasingly autonomous Mars rover
* a recent announced breakthrough in unsupervised object recognition by Google.[4]
* commercialized speech recognition

but it is true, what started out decades ago as mere theory with TMs is now a very real-world phenomenon and segments of the *ivory tower* TCS community might be in some resistance or even denial of that fact and the associated, fundamental [near Kuhnian] transformation and shift "currently in play". this somewhat ironic because Turing was very applied in many of his perspectives & studies such as his interest in an operational AI test (the Turing test), chemical dynamics, chess solving computation, etc [5].

you can even see this in a microcosm on this site in clashes over how to define the scope, and heated arguments over whether a specific seemingly innocuous tag called *application-of-theory* is legitimate.[7]

and lets note that TCS is in fact studying many *interactive* models of computation and much key research is going on in that area... particularly interactive proof systems of which all the important computing classes can be defined in terms of.[6]

[1] [The Church-Turing thesis-- breaking the myth by Goldin & Wegner](http://www.cse.uconn.edu/~dqg/papers/cie05.pdf)

[2] [Are there new models of computation? a reply to Goldin & Wegner by Cockshott & Michaelson](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.3854&rep=rep1&type=pdf)

[3] [Googles self-driving cars-- 300K miles logged, not a single accident under computer control, the Atlantic](http://m.theatlantic.com/technology/archive/2012/08/googles-self-driving-cars-300-000-miles-logged-not-a-single-accident-under-computer-control/260926)

[4] [Google unsupervised object recognition of Youtube images](https://cstheory.stackexchange.com/questions/2681/algorithm-for-finding-similar-images/12001#12001)

[5] [Alan Turings contributions to CS](https://cstheory.stackexchange.com/questions/11797/alan-turings-contributions-to-computer-science)

[6] [Landscape of interactive proof systems](https://cstheory.stackexchange.com/questions/12348/landscape-of-interactive-proof-systems)

[7] [On modifying our scope-- a proposal](https://cstheory.meta.stackexchange.com/questions/1572/on-modifying-our-scope-a-proposal)

> **Comments:**
> **username_9**: _what started out decades ago as mere theory with TMs is now a very real-world phenomenon_ — Of course, we know that.  We call it "computer science".  
> **username_4**: addendum, see also [Interactive computation, the new paradigm by Goldin, Smolka, Wegner (2006)](http://www.cs.brown.edu/sites/interaction-book/)  
> **username_4**: an analogy that was at the edge of my thoughts while writing this, but finally figured out later: think the distinction of _in vivo_ vs _in vitro_ biology is relevant. the TM is analogous to the latter. other (emerging) models are analogous to the former. =)  
> **username_4**: anyway the 2006 volume shows many prestigious computer scientists agreeing with the new paradigm. note also the final essay in the collection: Lynn Stein, Interaction, Computation, and Education — _This volume as a whole documents a fundamental shift in the culture of computation from a focus on algorithmic problem solving to a perspective in which interaction plays a central role. In this chapter, Stein points out that such a shift must be accompanied by a corresponding shift in computer science education, in the fundamental ``story'' we tell our students in their introductory courses._  
> **username_6**: @vzn [Argument from authority](http://en.wikipedia.org/wiki/Argument_from_authority)  
> **username_4**: agreed! JeffE=authority =)  

---

### Answer by username_14 on 2012-08-30. Score: -8

Here's the thing, once you add (pure) interactivity, formality goes out the window. It's no longer a "closed" system. The question then is, what is the notion of **computation** once interactivity enters in? That answer: well, either the other user/machine is substituting for some of your computation (which can be enscribed by just another, bigger, state machine) *or* you're no longer in a formally-definable system and you're now playing a ***game***, in which case there is no application of the Church-Turing thesis.

> **Comments:**
> **username_6**: Interactive models of computation like process calculi are games in the sense of [game semantics](http://en.wikipedia.org/wiki/Game_semantics).  
> **username_14**: @Martin:  No, you cannot "model" (human) interactivity.  What you are talking about are formal rule behaviors (as in a game), but then as soon as you've codified such, you're no longer in an interactive model.  
> **username_6**: Human behaviour is irrelevant. What matters is that computable interactive devices act in an algorithmic, mechanical manner to their inputs.  
> **username_14**: Aye, there's the rub, i'nnit?  "...*computable* interactive devices".  But *is* it computable?  
> **username_14**: @Martin:  I want to further elucidate the issue, because it's important.  The situation is analogous to an experiment measuring the veracity of the 2nd Law of Thermodyamics:  yes one may notice a local increase in order (computability), seemingly at odds with the 2nd Law, but it comes at an expense at a larger scale where it again returns to disorder (incomputable).  The error is where (i.e. at what level) is the system closed enough in order to be considered a "process calculi"?  
> **username_6**: @ Mark J, I don't understand what you are saying. The interactive approach simply says that a device is computable if it reacts to its inputs in a mechanical way, using finite resources. Yes, if the other part of the interaction does something crazy, like inputting Chaitin's Omega, then the mechanical device can do something crazy, like computing the halting problem. So what?  
> **username_6**: In my opinion the CTT is not about what is physically implementable. Instead, it's a crude test that rules out certain clearly not implementable things: If the CTT says something is not computable, then it is not physically implementable, but I don't think the reverse implication holds.  
> **username_14**: @MartinBerger: "a device is computable if it reacts to its inputs ina mechanical way, using finite resources" -- but then it shouldn't be considered "interactive" should it?  It's more a double-sized Turing machine with the other machine at the other end of the tape and the translation table having a code to distinguish between one FSM and the other (i.e. still completely implementable in a single Turing machine).  
> **username_6**: @ Mark J, the requirement "a device is computable if it reacts to its inputs in a mechanical way, using finite resources" does not require the inputs be generated mechancially. Certainly inputting Chaitin's Omega cannot be mechanically generated.  
> **username_6**: And yes, as I said in my comment below, interactive formalisms can be step-by-step simulated by TMs. However, step-by-step simulation is not the same thing as TM-simulatability in the sense of the strong CTT thesis.  

---

