tag:blogger.com,1999:blog-3722233.post115289266064033389..comments2024-09-19T15:49:06.865-05:00Comments on Computational Complexity: Principles of Problem Solving: A TCS ResponseLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger51125tag:blogger.com,1999:blog-3722233.post-24649506091065926702017-01-11T19:07:36.148-06:002017-01-11T19:07:36.148-06:00There is no problem in having interacting machiner...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.<br /><br />There 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.<br /><br />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.<br /><br />For me, Wegner's comments serve as a coded attack on managerialism. A coded cry against the horrors of bureaucracy.<br /><br />Richard Mullins<br />Brisbane, Australia<br />portal1943@gmail.com<br />wayzata1944@gmail.com<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6925040444678475072010-11-07T20:33:03.874-06:002010-11-07T20:33:03.874-06:008.11.2010
We could make the theory of Turing machi...8.11.2010<br />We 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.<br /><br />However I do not buy the recent arguments that there is something wrong with Church-Turing theory.<br /><br />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.<br /><br />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.<br /><br />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).<br /><br />Richard Mullins<br />Brisbane, Australia<br />nrmullins@sctelco.net.au<br />portal0001@lycos.comAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153374225761467292006-07-20T00:43:00.000-05:002006-07-20T00:43:00.000-05:00For any interactive machine, if you have finite in...For any interactive machine, if you have finite interaction, then it can be simulated with a non-interactive TM by trying all possible interactions.<BR/><BR/>If you have infinite interaction, then the computation already need to take infinite time! No point discussing about computability!<BR/><BR/>Same for stream computing because they need to involve infinite streams.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153347925474880082006-07-19T17:25:00.000-05:002006-07-19T17:25:00.000-05:00Footnote #8 argument revisited.Lance (and others) ...Footnote #8 argument revisited.<BR/><BR/>Lance (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.<BR/><BR/>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:<BR/><BR/>"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."<BR/><BR/>where [8] states:<BR/><BR/>"It is most natural to construct first a choice machine (�2) to do this. But it then easy to construct the required automatic machine. [...]"<BR/><BR/><BR/>And, (�2) provides a short description of what c-machine is:<BR/><BR/>"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-."<BR/><BR/><BR/>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.<BR/><BR/>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. <BR/><BR/>(please avoid commenting if you have not actually read the article)Corneliohttps://www.blogger.com/profile/03818896228850567845noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153316403316089812006-07-19T08:40:00.000-05:002006-07-19T08:40:00.000-05:00(please, try to stick to the point, and no persona...(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)<BR/><BR/>The car example: revisited.<BR/><BR/><BR/>Lets assume an agent A (a car) is navigating through a complex<BR/>unknown environment E (same as in the Goldin's paper). E is<BR/>represented as a set of input streams to A. The question is<BR/>about the nature of the computation that A performs in E. In<BR/>particular, the question is if this computation can be represented by<BR/>a Turing machine.<BR/><BR/>Interpretation A:<BR/>* the nature of the streams is computable, and all the streams are<BR/>synchronised and operate in discrete time units<BR/>* the computation performed by A in such E is Turing-computable, and<BR/>can be represented by a simple single-tape TM<BR/><BR/>Interpretation B:<BR/>* the nature of the streams is uncomputable (we do not care how this<BR/>is the case), and all the streams are synchronised and operate in discrete time units<BR/>* the computation performed by A in such E is equivalent to TM with an<BR/>access to an external Oracle, and as such, goes beyond a normal<BR/>TM. Such a computation cannot (by definition of an Oracle) be<BR/>represented as a TM.<BR/><BR/>Both interpretations are not really controversial,<BR/>and are known since Turing 1936 paper.<BR/><BR/>Interpretation C:<BR/>* the nature of the streams is computable, and the streams are<BR/>asynchronous and do not operate in discrete time units (continuous time)<BR/>* the computation performed by A in such E is equivalent to an analog<BR/>machine, that operate on real numbers, hence, it cannot be represented<BR/>on TM<BR/><BR/>Interpretation D:<BR/>* the nature of the streams is uncomputable, and the streams are<BR/>asynchronous and do not operate in discrete time units (continuous time)<BR/>* the computation performed by A in such E is equivalent to an analog<BR/>machine with an access to an Oracle, hence, it cannot be represented<BR/>on TM.<BR/><BR/><BR/>Any comments to the above? Inconsistencies? <BR/><BR/><BR/>It seems to me, Wegner/Goldin idea is that ``interactive computing''<BR/>removes a strict discrete computable aspects of algorithms and TM<BR/>computation, and it provides a model that is a (potential) mix of<BR/>o-machines and analog computation. The ``trick'' is not to actually<BR/>make any assumptions as to the availability of analog computability<BR/>or/and access to Oracles. If real values computing is not available<BR/>(the nature of time is not continuous) and if oracles are not<BR/>accessible (all input streams are computable), the interactive<BR/>computing is equivalent to TM. But, if the nature of the streams<BR/>``allows'' oracles or continuous time delays, then interactive<BR/>computing ``works'' better than TM.<BR/><BR/>Whether the nature of time is continuous, and whether there are<BR/>``oracles'' (some argue that input provided from humans is<BR/>uncomputable, for example) is another story, that can be pursued on a<BR/>personal preference basis and that is not quite<BR/>relevant to the discussion about the expressiveness of the computing models. <BR/><BR/>Simply, if there are oracles/continuous time delays, Wegner/Goldin<BR/>model goes beyond TM: Right? Wrong? Comments?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153286928873029112006-07-19T00:28:00.000-05:002006-07-19T00:28:00.000-05:00A little perspective, folks!While it is unfortunat...A little perspective, folks!<BR/><BR/>While 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153280797916854812006-07-18T22:46:00.000-05:002006-07-18T22:46:00.000-05:00WTF!?What on earth is supposed to be the differenc...WTF!?<BR/><BR/><BR/>What on earth is supposed to be the difference between a "function" and "computational problem"? Is it possible to define "computational problem" precisely?<BR/><BR/>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? <BR/><BR/>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?<BR/><BR/>YEEAAARRRGGG!!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153262289444495872006-07-18T17:38:00.000-05:002006-07-18T17:38:00.000-05:00"If I understand MacNeil's point (and he can corre..."<I>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.</I>"<BR/><BR/>Yes, that's exactly my point.<BR/><BR/>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.<BR/><BR/>The next person who can't even agree to this point should read <A HREF="http://www.cse.uconn.edu/~dqg/papers/cie05.pdf" REL="nofollow">Goldin's paper</A> and tell me how exactly they expect a non-interactive TM to model the problem discussed in section 3.2.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153248433154346142006-07-18T13:47:00.000-05:002006-07-18T13:47:00.000-05:00This discussion reminds me of a Software Engineeri...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153244179867616862006-07-18T12:36:00.000-05:002006-07-18T12:36:00.000-05:00What I do know is that the claims we tell our unde...<EM>What I do know is that the claims we tell our undergraduates are certainly false</EM><BR/><BR/>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, <EM>and their extensions, like interactive Turing machines</EM>, can model any form of computation.<BR/><BR/>Can we all agree on that (whether or not we think it is trivial)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153225891118654452006-07-18T07:31:00.000-05:002006-07-18T07:31:00.000-05:00Oh please. The whole point of having a blog with c...<I>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?</I><BR/><BR/>I 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.<BR/><BR/>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.<BR/><BR/>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."<BR/><BR/><I>What I do know is that the claims we tell our undergraduates are certainly false</I><BR/><BR/>Statements like this, however, are inflammatory attempts to either provoke or insult, or maybe both.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153194901926778042006-07-17T22:55:00.000-05:002006-07-17T22:55:00.000-05:00Oh please. The whole point of having a blog with ...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153191324781640422006-07-17T21:55:00.000-05:002006-07-17T21:55:00.000-05:00I've known about interactive TMs, and in particula...<I>I've known about interactive TMs, and in particular I mean Wegner's work, since the Clinton administration.</I><BR/><BR/>Then 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!<BR/><BR/><I>The 20 questions example I gave you was actually an example Wegner told to me. His example was Ken Starr asking Clinton questions.</I><BR/><BR/>If you've known about this particular example for so long, then please explain how this is different from an interactive protocol.<BR/><BR/><I>I suppose it's easy to misread someone who is sufficiently far away from your own field.</I><BR/><BR/>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:<BR/><BR/><I>What I do know is that the claims we tell our undergraduates are certainly false</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153187642020536142006-07-17T20:54:00.000-05:002006-07-17T20:54:00.000-05:00"You're dogmatically defending a position (and a p..."<I>You're dogmatically defending a position (and a paper) which you most likely just learned about a few days ago.</I>"<BR/><BR/>1) 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.<BR/><BR/>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.<BR/><BR/>3) I've known about interactive TMs, and in particular I mean Wegner's work, since the Clinton administration.<BR/><BR/>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.<BR/><BR/>At Northeastern I also took two classes from Paul Attie and spoke with him about his own papers on interactive Turing machines.<BR/><BR/>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.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153182474084045572006-07-17T19:27:00.000-05:002006-07-17T19:27:00.000-05:00Macneil,It's been twice pointed out that the "prim...Macneil,<BR/><BR/>It's been twice pointed out that the "primary materials" misrepresent Turing's paper - this point has not yet been contested.<BR/><BR/>Secondly, TCS has modeled interaction in several different contexts; your posts have repeatedly shown that you are ignorant of this fact.<BR/><BR/>Thirdly, it has been repeatedly pointed out in prior comments that these interactive models, in fact, can not "do more" than a Turing machine.<BR/><BR/>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!<BR/><BR/>Your posts are so reminiscent of statements made by the internet proponents of intelligent design that it's scary!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153180081947402492006-07-17T18:48:00.000-05:002006-07-17T18:48:00.000-05:00The simplest distillation of the point is that an ...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.<BR/><BR/>I 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.<BR/><BR/>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.<BR/><BR/>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 Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153161545845356692006-07-17T13:39:00.000-05:002006-07-17T13:39:00.000-05:00[...] a persistant Turing machine which is a model...<I>[...] a persistant Turing machine which is a model of a component of a larger and undefined system.</I><BR/><BR/>I 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...<BR/><BR/>--ffAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153150436181560322006-07-17T10:33:00.000-05:002006-07-17T10:33:00.000-05:00The problem, as usual, is not so much with what Go...The problem, as usual, is not so much with <EM>what</EM> Goldin/Wegner say, but <EM>how</EM> 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 <B>wrong</B>" and implying (or saying outright) that the TCS community is "backwards" for sticking to the Turing machine model.<BR/><BR/>When 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.<BR/><BR/>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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153143558290226902006-07-17T08:39:00.000-05:002006-07-17T08:39:00.000-05:00Macneil writes: *if* someone (or another TM, indir...Macneil writes: <I>*if* someone (or another TM, indirectly written by someone) puts in all of the interactions beforehand!</I><BR/><BR/>If 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153101092469661412006-07-16T20:51:00.000-05:002006-07-16T20:51:00.000-05:00Macneil:Go ask Mihir or Russell about the proof of...Macneil:<BR/><BR/>Go ask Mihir or Russell about the proof of IP=PSPACE<BR/><BR/>Do it before you post again.<BR/><BR/>Thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153100691792248252006-07-16T20:44:00.000-05:002006-07-16T20:44:00.000-05:00Sure, a single-tape TM can model interaction *if* ...<I>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.</I><BR/><BR/>I would be willing to wager that you've never seen the proof that IP = PSPACE.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153099302407562902006-07-16T20:21:00.000-05:002006-07-16T20:21:00.000-05:00A simpler analogy might help bring more light than...A simpler analogy might help bring more light than heat to this discussion.<BR/><BR/>The 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!<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>((*)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 <I>should</I> consider trivial. But we should still study the properties of linear bounded TMs anyway.)<BR/><BR/>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.<BR/><BR/>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.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153097348406069892006-07-16T19:49:00.000-05:002006-07-16T19:49:00.000-05:00I don't want to get into technical arguments about...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).<BR/><BR/>I 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. <BR/><BR/>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.<BR/><BR/><BR/>Boaz BarakAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153094136833804952006-07-16T18:55:00.000-05:002006-07-16T18:55:00.000-05:00Lastly, I would like to point out that the negativ...<I>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.</I><BR/><BR/>First 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?) <BR/><BR/>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).<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153089473661527562006-07-16T17:37:00.000-05:002006-07-16T17:37:00.000-05:00Dr. Goldin,You failed to respond to the following ...Dr. Goldin,<BR/><BR/>You failed to respond to the following point:<BR/><BR/><I>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.</I><BR/><BR/>Also, you mention that your course is legit. Don't you think the following statement on the course website is a little inappropriate?<BR/><BR/><I># 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)</I><BR/><BR/>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.<BR/> <BR/>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.Anonymousnoreply@blogger.com