Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.The "Choice Machines" from Turing's paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin's claim that Turing asserted his machines have limited power.In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.
But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.
I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.
The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.Call me a rationalist then as I continue to hold the belief that no matter how complicated the computational model, we can still use the simple Turing machine to capture its power.We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.
Makes me glad I stopped subscribing to CACM more than 10 years ago.
ReplyDeleteIf I remember correctly, former ACM President Dave Patterson claimed, in some of his official addresses, that a good way to increase ACM memberships is to make CACM a more interesting publication to read for all CS community. Publishing articles such as Wegner and Golding's doesn't really seem a step in the right direction, IMO.
ReplyDeleteHowever, there are several people on the Usenet who'd be glad to submit aplenty such kind of contributions. Closed-minded rationalists tend arrogantly to call them "crooks". How snobbish...
wtf is going on here?
ReplyDeleteGoldin teaches a theory of computation course at uconn where she explains how Chapter 3 of Sipster is incorrect.
and they have a grant:
NSF CISE/CCF SGER grant, Persistent Turing Machines: Beyond the Turing Thesis
I'm confused. I quit
What is Chapter 3 of Sipster about?
ReplyDeletePuppy dogs.
ReplyDeleteThese two researchers are professors in two (relatively) well-known universities.
ReplyDeleteEven though I am aware that what they support is incorrect, it seems quite strange that the community hasn't put some effort to convince them they are wrong.
I am also very surprised that UConn allows Goldin to teach theory of computation.
Even though I am aware that what they support is incorrect, it seems quite strange that the community hasn't put some effort to convince them they are wrong.
ReplyDeleteForget incorrect- read any of their articles, and you'll see that they're literally cranks. They are arguing something unprofound which they claim exhibits a vast hole in classical computability (and in fact the philosophical underpinnings of all of TCS), and they are doing it very, very badly. Their argument could be phrased in a single sentence, yet they write pages upon pages of vague nonsense. I feel sorry for Alex Russell.
Makes me wonder how the review process of CACM is done? It may be an honest mistake on the editor's part. But it seems to me, at the very least, an article on TM (and its limitation) should have been refereed by a complexity theorist.
ReplyDeleteThe point is that (e.g.) an answering machine can do a kind of computation that a Turing machine cannot.
ReplyDeleteIt's the interactive streams that change the nature of the computation. I like the point, because it always seemed bogus to me whenever someone claimed "and this Turning machine could even do Windows NT!" (it was a while ago). You cannot simulate Windows NT on a Turning machine without giving it all of the expected user input first. But the user input is only determined based on where the computation has lead you.
You need to start to run the program first (on paper, in your head, or on a computer) to determine what the next user input in this Windows NT session would be. That's what makes it empirical.
Some people have made the point that Wegner's observation isn't as deep as it first seems. I think the jury is still out on that one, but I think his work should be done and has demonstrated a valid point that many have missed.
All this outrage obscures the fact that these researchers are in the mainstream. For instance, Dina Goldin collaborates with Amit Chakrabarti.
ReplyDeleteLF: Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis. ... Call me a rationalist then as I continue to hold the belief that no matter how complicated the computational model, we can still use the simple Turing machine to capture its power. :LF
ReplyDeleteLance
=====
The problem with combining a rationalist philosophy with the classical expression of the Church-Turing Thesis - as a strong identity - is that it commits one to the following, strong, definition of computability / decidability:
(i) Def: A number-theoretic function / relation, say F(x1, x2, ..., xn), is effectively computable / decidable if, and only if, there is an effective method T such that, given any sequence of natural numbers (a1, a2, ..., an), T will always compute / decide F(a1, a2, ..., an).
The classical form of CT follows straightforwardly from definition (i):
(ii) Classical CT: A number-theoretic function / relation is effectively computable / decidable if, and only if, it is partial recursive / Turing-computable.
The question arises: Is such a strong commitment really necessary?
Interestingly, the question of whether (ii) is a definition, a theorem, or a thesis, was the subject of a substantive exchange of views between Church and Goedel, neither of whom, apparently, was comfortable with the eventual acceptance of (ii) as a thesis.
That their discomfort was well-founded is seen if we replace definition (i) by the weaker, but broader, definition:
(iii) Def: A number-theoretic function / relation, say F(x1, x2, ..., xn), is effectively computable / decidable if, and only if, given any sequence of natural numbers (a1, a2, ..., an), there is an effective method T, which may depend on (a1, a2, ..., an), such that T will always compute / decide F(a1, a2, ..., an).
Clearly, (i) implies (iii). Hence, by the dictum of Occam's razor, it is to be preferred as the definition of effective computability / decidability.
Moreover, the significance of (iii) over (i) is that it admits the broader possibility of number-theoretic functions / relations that are effectively computable / decidable instantiationally, but not algorithmically.
The significance, and necessity, of a thesis linking effective computability / decidability with recursiveness / Turing-computability then emerges in the form of a weakened expression of CT as an equivalence, rather than as a strong identity:
(iv) Instantiational CT: A number-theoretic function / relation is effectively computable / decidable if, and only if, it is instantiationally equivalent to a partial recursive / Turing-computable function / relation.
Since (iv) is an equivalence, and not an identity, we can now admit number-theoretic functions / relations that are effectively computable instantiationally, but not algorithmically.
The question arises: Are there such functions / relations?
Clearly, Turing's Halting function, and Chaitin's Omegas, are well-defined, total, number-theoretic functions that are effectively computable instantiationally, but not algorithmically.
However, in the absence of (iv), we cannot link them instantiationally to recursive / Turing-computable functions.
More significantly, if [(Ax)R(x)] is Goedel's undecidable arithmetical proposition, then, under the reasonable assumption that, if a total arithmetical relation is Turing-computable then the algorithm can be converted into a proof sequence in Peano Arithmetic, it can be shown that R(x), too, is effectively computable instantiationally, but not algorithmically.
What makes this case significant is that Goedel has shown (in Theorem VII of his seminal 1931 paper on undecidable arithmetical propositions) that R(x) is, indeed, instantiationally equivalent to a primitive recursive relation.
So, Wegner and Goldin's essential thesis - that there can be effectively computable functions / relations that are not Turing-computable / decidable ought not be dismissed so cursorily - although the validity of the particular arguments underlying their belief may be debatable.
I stressed this point in 'Can Turing machines capture everything we can compute?', where I addressed your criticism of their earlier paper, 'Computation Beyond Turing Machines'.
http://alixcomsi.com/Can_Turing_machines.htm
http://alixcomsi.com/Can_Turing_machines.pdf
Regards,
Bhup
The point is that (e.g.) an answering machine can do a kind of computation that a Turing machine cannot. [...]
ReplyDeleteSome people have made the point that Wegner's observation isn't as deep as it first seems. I think the jury is still out on that one, but I think his work should be done and has demonstrated a valid point that many have missed.
The point is that they make some very strong claims, give no formal proof of such claims whatsoever, and then say that the rest of the CS community is wrong. These are the hallmarks of crackpots. If they believe that their models of computation cannot be simulated by a TM, they must provide a valid proof: handwaving is not going to work.
Quoting Carl Sagan: "Extraordinary claims require extraordinary proof".
All this outrage obscures the fact that these researchers are in the mainstream.
I think the outrage is a consequence of their being in the mainstream. People in their right mind expect the mainstream to refuse certain contributions.
The point is that they make some very strong claims, give no formal proof of such claims whatsoever, and then say that the rest of the CS community is wrong.
ReplyDeleteActually, there is a "proof" in there somewhere--essentially, they argue that human actions are uncomputable (presumably due to quantum gravity affects in the microtubules in our brains), and thus we cannot model persistent human input by a computational process.
While I agree with Lance that Wegner and Goldin failed to propose anything that would in any significant way demonstrate that a simple Turing machine is insufficient to model computation, I also think that there is absolutely no need to insult them and express astonishment at their rank and affiliations! All they are trying to do is to remind us that the very definition of what computation is, is not set in stone. Granted, I don't buy their particular argument, but I do very strongly believe that, especially from people who are pretty accomplished in CS (as Peter Wegner undoubtedly is, even if readers of this blog are unfamiliar with his work because it is outside TCS!), contributions of this nature should be welcome and encouraged.
ReplyDeleteThe point is that they make some very strong claims, give no formal proof of such claims whatsoever, and then say that the rest of the CS community is wrong. These are the hallmarks of crackpots. If they believe that their models of computation cannot be simulated by a TM, they must provide a valid proof
ReplyDeleteThey have probably a half a dozen papers published on the matter that provide the details that you require. My opinion was not based on just their two articles in CACM.
Much of it is based on non-well founded set theory.
This seems like the perfect opportunity to ask about this paper that appeared in CACM quite some time ago. This author also wrote a paper entitled "The rise and fall of the Church-Turing Thesis," in which he claims that his theory of super-recursive algorithms disproves the Church-Turing Thesis. I read the latter paper, and - to me - it seemed very "non-rigorous," to put it nicely.
ReplyDeleteAfter that, I found the CACM article and also noticed that the author has recently published a book as well. Is this theory of "super-recursive" algorithms being taken seriously? If not, how does someone publish a book about it? How does one get papers in the CACM about it?
I noticed that in the CACM article, he cites Wegner and Goldin. In addition, he makes the same claim about an OS that macneil makes in an earlier comment.
Macneil: Thank you for explaining their point. However, it's a very simple exercise to make a variant on a turing machine which can take input and give output, and it in no way changes the computational strength of anything, because such an extended turing machine is entirely capable of simulating any other machine capable of taking input and giving output.
ReplyDelete"Thank you for explaining their point. However, it's a very simple exercise to make a variant on a turing machine which can take input and give output, and it in no way changes the computational strength of anything, because such an extended turing machine is entirely capable of simulating any other machine capable of taking input and giving output."
ReplyDeleteYes, and such a Turing machine can be called an interactive Turing machine, which is Wegner's term for it. All of this has been formalized by Wegner.
Imagine you had to crossexamine someone. Would you rather be able to ask 20 questions, leading the conversation wherever the answers go; or would you rather be forced to write down all 20 questions before getting any answers and sticking to the preset questions?
The first is interactive communication, while the second is a batch communication. No one should buy the claim that they are "equivalent" just because you could write 20 static questions that constitute a tree over every expected answer and history (provided you assume no answer is longer than some bound).
Thus, think of Wegner's point as saying that interactive crossexaminations are more powerful than batch crossexaminations. You can say that this is not an amazing observation, but I think Lance is wrong in thinking a non-interactive Turing machine is "the same" as an interactive Turing machine. At best, you can say "well, of course they are different, but it doesn't matter," but that was not the point Lance was making.
Imagine you had to crossexamine someone. Would you rather be able to ask 20 questions, leading the conversation wherever the answers go; or would you rather be forced to write down all 20 questions before getting any answers and sticking to the preset questions?
ReplyDeleteDoesn't an interactive protocol (as in IP = PSPACE) have this capability? Can't a Turing machine simulate an interactive protocol?
I still don't understand how these other types of interactions are different...
Doesn't an interactive protocol (as in IP = PSPACE) have this capability? Can't a Turing machine simulate an interactive protocol?
ReplyDeleteLet me give you a simple version of their argument: A Turing machine cannot simulate a hair dryer, because it doesn't blow hot air. Yes, it is idiotic.
Now, computationally, we believe that the Turing machine could, in fact, simulate the physics of the hair drying event, and therefore eventually compute any result that the hair dryer system computes- but your hair still won't be dry.
They take it one step further- they disallow you to simulate e.g. the human being interacting with you because they claim that the human being is in fact doing something uncomputable.
And what's the point? We didn't learn anything, and yet somehow all those Windows Vista programmers are still coding away, oblivious to the fact that they are exercising a new computing paradigm.
I had my suspicions, but I now classify Macneil as either a crank or a tool.
Is this the stuff that's not getting into FOCS and STOC?
ReplyDeleteAs far as I can tell, there's really nothing new or revolutionary here. There are plenty of TCS researchers working with things like linear logic and process algebras (like the pi calculus), which are used to model and study concurrency in computer science. In fact, such tools are often used to give (supercomputer-aided) brute-force proofs of correctness for interactive situations.
ReplyDeleteThese papers they are writing don't sound the least bit deep or provacative.
I completely agree with the previous commenter. Mathematical formalisms for rigorous modeling interactive systems have existed for decades.
ReplyDeleteOne such tool that proved to be successful in modeling complex distributed, concurrent, networked, etc. systems is the Input/Output Automata (IOA), originally introduced by Nancy Lynch and Mark Tuttle in
N. Lynch and M.R. Tuttle. An introduction to input/output automata. CWI Quarterly, 2(3):219--246, 1989.
Since it was first introduced, IOA had been extended to capture both timed (TIOA) and probabilistic (PIOA) computation.
More recently, it was extended to allow modeling crypto protocols:
Time-Bounded Task-PIOAs: A Framework for Analysing Security Protocols. R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala.
-- Gregory Chockler
Is this the stuff that's not getting into FOCS and STOC?
ReplyDeleteNo, that stuff is getting into SODA and ICALP.
This is Dina Goldin, one of the authors of the CACM article in question. I would like to address a couple of comments that have been made.
ReplyDeleteOne is that no formal proofs have been provided for any of our claims. This is false. I encourage everyone to read my Information & Computation paper (Nov. 2004, with Smolka and Attie). A draft of it can be found on my web site, www.cse.uconn.edu/~dqg. The model formalized there, Persistent Turing Machines, is a type of Wegner's Interactive machine that minimally extends Turing machines to model interaction. The results presented concerning this model are very formal.
The second comment is regarding my teaching of TOC. That comment came with a link to my course web page, also on my web site. I again encourage anyone who has questions about the material I teach to see that web page for themselves to verify that the course is 100% legit.
Lastly, I would like to point out that the negative comments in this thread are of TWO types: (a) this is wrong, and (b) this is trivial and has been done before [by concurrency people]. I have seen the same range of opinions before, e.g. from reviewers. Think about it -- how can something be both trivially right and completely wrong?? Clearly, there is more to it than either side sees.
There's nothing more to this than anyone sees, except for the authors. The sweeping philosphical conclusions (that the Church-Turing thesis is wrong) are ridiculous, and the underlying technical results (that the standard definition of a Turing machine does not allow interaction but can easily be modified to do so) are trivial.
ReplyDeleteDr. Goldin,
ReplyDeleteYou failed to respond to the following point:
The "Choice Machines" from Turing's paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin's claim that Turing asserted his machines have limited power.
Also, you mention that your course is legit. Don't you think the following statement on the course website is a little inappropriate?
# The Church-Turing Thesis: Breaking the Myth. My paper about why the claim at the beginning of Chapter 3 is wrong (11 pages in PDF format)
Perhaps your paper calls into question the claim at the beginning of Chapter 3, but it certainly does not show that "the claim at the beginning of Chapter 3 is wrong," and should not be represented as such - especially if you want the establishment to take your work seriously.
The fact that you misrepresent Turing's paper in both the CACM article and your paper AND you make such absurd claims (to paraphrase - "My paper shows Sipser is WRONG!") makes your work far less credible.
Lastly, I would like to point out that the negative comments in this thread are of TWO types: (a) this is wrong, and (b) this is trivial and has been done before [by concurrency people]. I have seen the same range of opinions before, e.g. from reviewers. Think about it -- how can something be both trivially right and completely wrong?? Clearly, there is more to it than either side sees.
ReplyDeleteFirst of all, this is the strategy of a crank (person A is saying it's wrong and person B is saying its trivial- I guess "revolutionary" is halfway between trivial and wrong?)
There is a way for it to be both trivial and wrong; it depends on how one interprets your arguments (i.e. at which point someone tries to give you the benefit of the doubt, probably depending on their aesthetic about which is worse, to be trivial or to be wrong). If you are claiming that a Turing machine cannot dry hair, and that drying hair is an important process that should not be excluded from the realm of "computation", then you are saying something trivial. If you are claiming that a hair drying system can compute more than a Turing machine (now using the classical definition of "compute"), then you are wrong (well, at least you haven't proved to us the amazing power of hair dryers yet).
Finally, it is also perfectly reasonable to say that concurrency people have been doing this for years, and also that your argument is trivial. The point is that concurrency people are not simply yelling "concurrency! concurrency!" Rather, they are saying interesting things about it.
I don't want to get into technical arguments about papers I haven't read. (Though (1) I would be interested in understanding the relation between the mentioned works and the notion of interactive computation introduced by Goldwasser-Micali and Rackoff in the context of interactive proofs and zero knowledge and (2) while there are many computational tasks such as interaction, sampling, learning, solving a search problem, etc.. that do not consist of computing a function, TMs can be used to model all of them, so I don't understand how such tasks have any impact on the Church-Turing thesis).
ReplyDeleteI just think that the "TCS response" would look better if it consisted of polite and signed comments. Actually, sticking to comments with these two qualities (especially the former) wouldn't hurt as a general rule. It is possible to criticize, and even strongly criticize, a technical work while staying polite.
In any case, people should remember that this weblog (and in particular its comments section) does not necessarily provide an accurate representation of the views and manners of the TCS community.
Boaz Barak
A simpler analogy might help bring more light than heat to this discussion.
ReplyDeleteThe analogy is with programming languages. In a PL course, we're all told the great lie that anything you can do in one (Turing complete) programming language you can do in any other (Turing complete) programming language. But as anyone who's programmed in C versus a simple Basic would know that's not the case at all!
For example, no matter how hard you try, you cannot access low-level system calls in Basic. In C, this is trivial and vital to even getting the program to run. Similarly, lambda calculus lacks exactly the properties of interactiveness that we find most useful in C. No matter how hard we try, we cannot write any lambda calculus expression that has any hope of acting like Windows XP the way we view Windows XP.
So, yes, when we talk about computations on integers or strings, we could define functions and encodings in any of C, lambda calculus, and Basic. But we can clearly do more in C.
Now, getting back to the main topic: To state that a single-tape TM can model interaction is a slight-of-hand that once again ignores the larger context of computation. Sure, a single-tape TM can model interaction *if* someone (or another TM, indirectly written by someone) puts in all of the interactions beforehand! No matter how hard you try, you cannot remove the role of the agent interacting with the TM.
The computer I'm interacting with now can do all that a TM could do, and more(*). We should just admit that there is a difference between the computations a TM can perform and the computations an interactive TM can perform.
((*)Footnote: actually, it can't do more in all cases, because my computer's memory is finite. I think the finite/arbitrary-length-tape distinction is something we should consider trivial. But we should still study the properties of linear bounded TMs anyway.)
As for the claims that this is trivial: I say that the jury is still out on this one because I'm not sure if this has introduced a new paradigm shift in our understanding or not.
But I would be willing to wager that the same people who resist interactive TMs are the same people who resist Object-Oriented Programming. Goldin and Wegner have thought much more about this than I have, and I think their comparison to empiricism and rationalism has something to it.
Sure, a single-tape TM can model interaction *if* someone (or another TM, indirectly written by someone) puts in all of the interactions beforehand! No matter how hard you try, you cannot remove the role of the agent interacting with the TM.
ReplyDeleteI would be willing to wager that you've never seen the proof that IP = PSPACE.
Macneil:
ReplyDeleteGo ask Mihir or Russell about the proof of IP=PSPACE
Do it before you post again.
Thank you.
Macneil writes: *if* someone (or another TM, indirectly written by someone) puts in all of the interactions beforehand!
ReplyDeleteIf it is shown that a certain TM property holds for ANY stream of inputs (oracle), then the property holds regardless of "when" the inputs are given or "where" they come from.
The problem, as usual, is not so much with what Goldin/Wegner say, but how they say it. I doubt anyone (Lance included) would be up-in-arms if Wegner and Goldin quietly made the point that Turing machines provide a poor model for operating systems and web servers. The problem is when they blatantly try to attract attention to themselves by making claims like "Sipser Chapter 3 is wrong" and implying (or saying outright) that the TCS community is "backwards" for sticking to the Turing machine model.
ReplyDeleteWhen such blatant PR is necessary (or believed to be necessary) for research to be taken seriously, that's when you need to question the intrinsic value of that research.
PS: who else is doing "research" in this area? Goldin/Wegner are planning to publish a book about interactive computing; who, I wonder, is their intended audience?
[...] a persistant Turing machine which is a model of a component of a larger and undefined system.
ReplyDeleteI see a problem involving "undefined" and "formal proof". Can a Turing machine with a halting oracle decide the halting problem? Yes. Can an "interactive Turing machine" operated by an alien (with supercharged microtubuli, possibly?) decide SAT in polynomial time? Sort of...
--ff
The simplest distillation of the point is that an interactive Turing machine can do more than a batch Turing machine. Those who don't understand this point should read the primary materials first.
ReplyDeleteI would much rather see people say "yes, there is a point, but this observation is trivial" (and to provide logical reasons for why they think so!) than to see people completely misinterpret information that they are getting second and third hand. I think some folks view "computation" too narrowly, and that is the source of the misunderstandings and negative reactions.
In terms of Lance's research, he can view computation in the narrower sense and do wonderfully. Yet, in his everyday life, he's participating in interactive computations (whenever he uses his computer, checks his voice mail, leaves someone a message, ...) all the time.
When Lance is talking about "capturing its power" he's really saying he's capturing the power that he's interested in. That being, the questions his line of research leads him to. If Lance considers a voice-mail system to not have any "interesting power" beyond a TM that's up for him to decide. But isn't there enough room for others to say "let's study computational models that could better reflect voice-mail systems"?
Macneil,
ReplyDeleteIt's been twice pointed out that the "primary materials" misrepresent Turing's paper - this point has not yet been contested.
Secondly, TCS has modeled interaction in several different contexts; your posts have repeatedly shown that you are ignorant of this fact.
Thirdly, it has been repeatedly pointed out in prior comments that these interactive models, in fact, can not "do more" than a Turing machine.
You have not made a single post that leads me to believe that you're listening to these points. You're dogmatically defending a position (and a paper) which you most likely just learned about a few days ago. Why would you do such a thing? If you're a Computer Scientist, your first goal should be to learn and understand the established body of knowledge before you attempt to debunk it!
Your posts are so reminiscent of statements made by the internet proponents of intelligent design that it's scary!
"You're dogmatically defending a position (and a paper) which you most likely just learned about a few days ago."
ReplyDelete1) I'm actually leaving it open if the statement is trivial or not, but there is something to the statement that most here choose to misunderstand.
2) There's nothing dogmatic about it... I'm using logic and reason just like the any of us. The sad part is, people keep assuming I'm saying something else that I'm not (see 1 above). I suppose it's easy to misread someone who is sufficiently far away from your own field.
3) I've known about interactive TMs, and in particular I mean Wegner's work, since the Clinton administration.
I had the great fortune to meet Wegner and one of his students at a visit day at Brown and I was very impressed. The 20 questions example I gave you was actually an example Wegner told to me. His example was Ken Starr asking Clinton questions.
At Northeastern I also took two classes from Paul Attie and spoke with him about his own papers on interactive Turing machines.
4) At the end of the day, I'm not sure if interactive TMs will be seen as a radical paradigm shift or just a footnote. What I do know is that the claims we tell our undergraduates are certainly false.
I've known about interactive TMs, and in particular I mean Wegner's work, since the Clinton administration.
ReplyDeleteThen I sincerely apologize for my statement to the contrary. But it begs the question - if you've known about the work for so long, why can't you address the three points that were made in my previous post? If you have studied and understand the subject enough to defend it, please enlighten us!
The 20 questions example I gave you was actually an example Wegner told to me. His example was Ken Starr asking Clinton questions.
If you've known about this particular example for so long, then please explain how this is different from an interactive protocol.
I suppose it's easy to misread someone who is sufficiently far away from your own field.
Your postings are appearing on a website which has an audience largely made up of people in the TCS community. In them, you are making bold (and arguably unfounded) claims about TCS research and the TCS body of knowledge. If this is not your field, perhaps you should spend your time learning a little about TCS before you come in and make claims such as:
What I do know is that the claims we tell our undergraduates are certainly false
This is the reason you're not being taken seriously. I wouldn't go on a software engineering website and make controversial unfounded claims about object-oriented programming, even if I knew several top researchers in the field who supported such claims - unless I first understood the claims and the controversy completely.
Oh please. The whole point of having a blog with comments is so that anyone can say whatever they want to. And also, isn't it great that people outside of TCS are reading it and contributing?
ReplyDeleteOh please. The whole point of having a blog with comments is so that anyone can say whatever they want to. And also, isn't it great that people outside of TCS are reading it and contributing?
ReplyDeleteI love TCS and I've always thought that the community is so welcoming and friendly. And, yes, one can say whatever they want in the comments section of a blog.
The problem here, I think, is the bold claims. My point was that if you're going to make such claims you should be prepared to back them up.
What's worse is to make such claims about a particular field and then say something like "I suppose it's easy to misread someone who is sufficiently far away from your own field," instead of "well, I'm not in the field, so it's entirely possible that I don't understand your questions and replies to my comments - but I will try to understand them before I make anymore such claims or posts."
What I do know is that the claims we tell our undergraduates are certainly false
Statements like this, however, are inflammatory attempts to either provoke or insult, or maybe both.
What I do know is that the claims we tell our undergraduates are certainly false
ReplyDeleteIf I understand MacNeil's point (and he can correct me if I am wrong), we should not tell our undergraduates that "Turing machines can model any form of computation" but instead that "Turing machines, and their extensions, like interactive Turing machines, can model any form of computation.
Can we all agree on that (whether or not we think it is trivial)?
This discussion reminds me of a Software Engineering Professor (at a well known university) who liked to boast/insult that algorithms researchers don't know what they are doing. This person claimed that algorithms folks ignored the operating system and that his work was a revolutionary way to handle this issue. Of course when you read his papers, it was all trivial drivel.
ReplyDelete"If I understand MacNeil's point (and he can correct me if I am wrong), we should not tell our undergraduates that "Turing machines can model any form of computation" but instead that "Turing machines, and their extensions, like interactive Turing machines, can model any form of computation."
ReplyDeleteYes, that's exactly my point.
I'm just waiting for people to say it's a trivial footnote. If only everyone would either agree to Wegner's point or to the point that it's trivial we will have made great progress.
The next person who can't even agree to this point should read Goldin's paper and tell me how exactly they expect a non-interactive TM to model the problem discussed in section 3.2.
WTF!?
ReplyDeleteWhat on earth is supposed to be the difference between a "function" and "computational problem"? Is it possible to define "computational problem" precisely?
What is wrong with using Turing machine to compute the FUNCTION that maps the current sensory input and the history to the next move of the car?
And was the car thing the big example? When they claim in bullet 6 that here are computational problems not computable by TMs... what exactly is the "computational problem" in question?
YEEAAARRRGGG!!!
A little perspective, folks!
ReplyDeleteWhile it is unfortunate that some professors choose to produce papers that wouldn't get past the bogus-o-meter of a five year old (but do get past some program committees), it is time we appreciated the rich literature that has sprung up settling the P vs NP question, disproving the Church-Turing thesis etc for what it really is -- a counterweight to all that "truth" and "intellectual honesty" stuff that is taken too seriously by the establishment. NSF should allocate more funds for this research to get a truly fair and balanced research scene.
(please, try to stick to the point, and no personal abuse and other nonsense; apologies if some of it is too naive for some readers)
ReplyDeleteThe car example: revisited.
Lets assume an agent A (a car) is navigating through a complex
unknown environment E (same as in the Goldin's paper). E is
represented as a set of input streams to A. The question is
about the nature of the computation that A performs in E. In
particular, the question is if this computation can be represented by
a Turing machine.
Interpretation A:
* the nature of the streams is computable, and all the streams are
synchronised and operate in discrete time units
* the computation performed by A in such E is Turing-computable, and
can be represented by a simple single-tape TM
Interpretation B:
* the nature of the streams is uncomputable (we do not care how this
is the case), and all the streams are synchronised and operate in discrete time units
* the computation performed by A in such E is equivalent to TM with an
access to an external Oracle, and as such, goes beyond a normal
TM. Such a computation cannot (by definition of an Oracle) be
represented as a TM.
Both interpretations are not really controversial,
and are known since Turing 1936 paper.
Interpretation C:
* the nature of the streams is computable, and the streams are
asynchronous and do not operate in discrete time units (continuous time)
* the computation performed by A in such E is equivalent to an analog
machine, that operate on real numbers, hence, it cannot be represented
on TM
Interpretation D:
* the nature of the streams is uncomputable, and the streams are
asynchronous and do not operate in discrete time units (continuous time)
* the computation performed by A in such E is equivalent to an analog
machine with an access to an Oracle, hence, it cannot be represented
on TM.
Any comments to the above? Inconsistencies?
It seems to me, Wegner/Goldin idea is that ``interactive computing''
removes a strict discrete computable aspects of algorithms and TM
computation, and it provides a model that is a (potential) mix of
o-machines and analog computation. The ``trick'' is not to actually
make any assumptions as to the availability of analog computability
or/and access to Oracles. If real values computing is not available
(the nature of time is not continuous) and if oracles are not
accessible (all input streams are computable), the interactive
computing is equivalent to TM. But, if the nature of the streams
``allows'' oracles or continuous time delays, then interactive
computing ``works'' better than TM.
Whether the nature of time is continuous, and whether there are
``oracles'' (some argue that input provided from humans is
uncomputable, for example) is another story, that can be pursued on a
personal preference basis and that is not quite
relevant to the discussion about the expressiveness of the computing models.
Simply, if there are oracles/continuous time delays, Wegner/Goldin
model goes beyond TM: Right? Wrong? Comments?
Footnote #8 argument revisited.
ReplyDeleteLance (and others) seem to be misusing footnote [8] of the Turing 1936 paper as a demonstration that any c-machine can be represented as a-machine. This is plainly wrong and misleading.
Footnote [8] demonstrates a method of providing an a-machine that would be equivalent to c-machine exclusively in a very narrowly defined context. It does not provide a general method of turning a c-machine into a-machine. [8] is used only in the context of Hilbert functional calculus that is modified to by systematic with finite number of symbols. Turing says:
"If the notation of the Hilbert functional calculus [7] is modified so as to be systematic, and so as to involve only a finite number of symbols, it becomes possible to construct an automatic [8] machine K which will find all the provable formulae of the calculus."
where [8] states:
"It is most natural to construct first a choice machine (�2) to do this. But it then easy to construct the required automatic machine. [...]"
And, (�2) provides a short description of what c-machine is:
"If at each stage the motion of a machine (in the sense of �1) is completely determined by the configuration, we shall call the machine an �automatic machine� (or a-machine). For some purposes we might use machines (choice machines or c-machines) whose motion is only partially determined by the configuration (hence the use of the word �possible� in �1). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix a-."
It is clearly an intention of Turing that c-machine model goes beyond of a-machine. A-machine can generate all computable proofs in any axiomatic system, apart those that are non-computable. That's where the c-machine configuration is ambiguous, and the machine must ask human operator for choice (for a decision upon unprovable theorem). We can speculate here as to Turing own beliefs about computability and uncomputable properties of human mathematicians. If you cannot restrain yourself, then go ahead, and share your own personal feelings and beliefs here. But, as long as the logical argument goes, try to stick to the facts.
What is clear that c-machine is not in general sense equivalent to a-machine. Why? Because in similar way to Oracles, the nature of the human operator is not assumed to be a-machine equivalent, and it may provides uncomputable choices to the machine.
(please avoid commenting if you have not actually read the article)
For any interactive machine, if you have finite interaction, then it can be simulated with a non-interactive TM by trying all possible interactions.
ReplyDeleteIf you have infinite interaction, then the computation already need to take infinite time! No point discussing about computability!
Same for stream computing because they need to involve infinite streams.
8.11.2010
ReplyDeleteWe could make the theory of Turing machines more "user friendly". For example, it could take the age of the universe to do a simple computation - this is called "effective computability" but is not, in ordinary language, an effective method because it is not directly usable.
However I do not buy the recent arguments that there is something wrong with Church-Turing theory.
But I think a lot of new discussion is necessary and worthwhile. So for this reason I would support the work by Wegner and others, even though I do not agree with their findings.
I have even wondered if Wegner's work is a coded attack on the one-way communication we have today in managerialism which has swept the world of work and education. He wants to promote interactive models of computation - perhaps we need to promote people interacting instead of the extremes of division of labour what we have today.
Jum Underwood, formerly professor at UTS in Sydney, got a Ph.D a few years ago promoting the idea that all steps in system design and development can be done by discussions of stakeholders. (He allows the system being developed, itself, to be a stakeholder. Also inanimate objects such as photocopiers can also be stakeholders).
Richard Mullins
Brisbane, Australia
nrmullins@sctelco.net.au
portal0001@lycos.com
There is no problem in having interacting machinery. for example our "Turing machine" (or computer, if you like) can call an arbitrarily complex function by pasting the name of the function into a cell of the tape, and waiting for the answer to arrive in another cell. The processing will be provided by other machinery using these two cells of the tape as shared memory.
ReplyDeleteThere has been intense interest in concurrent processing since the late 1960's (Dijkstra, Wirth, for example). In 1964, three men spent a weekend at a motel developing a concurrent operating system for a computer of 4Kbytes. They included the ex-Xerox and Microsoft luminary, Charles Simonyi (then 16 years old), and Per Brinch Hansen, famous in the 1970's for his work on concurrent programming.
For this reason, it seems odd to me that Wegner has more recently been promoting interactive computing as a new paradigm. Wegner is another luminary from the early 1970's and is extremely well informed on the Turing-completeness of computing devices.
For me, Wegner's comments serve as a coded attack on managerialism. A coded cry against the horrors of bureaucracy.
Richard Mullins
Brisbane, Australia
portal1943@gmail.com
wayzata1944@gmail.com