Talk:Wolfram's 2-state 3-symbol Turing machine

From Wikipedia, the free encyclopedia

Contents

[edit] How to read

I'm unsure how to read the table. For example take this column:

input 1,2
output 1,1,-1

I'm reading the following: if you're in state 1 and reading color 2 then set your state to 1, write color 1 and move head one cell to the left.

Yeah I think that's right; if not, I hope a locician/algorithmist corrects us. But you probably want to read the article about Turing Machines. (I would have said "move tape one cell to the left" but it amounts to equivalent thing.) Pete St.John (talk) 21:11, 5 February 2008 (UTC)

[edit] Universality proof disputed

According to discussion in the Foundation of Mathematics e-mail list, archives of which are available here, the members of the prize committee were "informed but not polled" as to the validity of the proof. The prize committee members were Lenore Blum, Gregory Chaitin, Martin Davis, Ronald Graham, Yuri Matiyasevich, Marvin Minsky, Dana Scott and Stephen Wolfram. On October 26, Martin Davis wrote to the FOM list that "The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings."

On October 29th, Stanford computer scientist Vaughan Pratt wrote to the FOM list, claiming that Smith's proof of the universality proof of the (2,3) Turing machine was flawed. Pratt asked "How did an argument containing such an elementary fallacy get through the filter?" Pratt points out that the fallacious reasoning of the alleged proof could be used to "prove" that a linear bounded automaton is universal, which is false. 72.89.108.196 21:33, 29 October 2007 (UTC)

A detailed write-up of Smith's claimed proof must be circulated among the committee members and to Vaughan Pratt, ASAP, so that the truth will out. I conjecture that this is not a straightforward exercise, because given Smith's age, he probably lacks experience with technical writing. Also, given that he is undergraduate student, his time is precious. I congratulate Wolfram Research on having put together a stellar prize committee, and trust that the doubts raised by the claim that that committee was "informed but not polled" can be put to rest.132.181.160.42 05:30, 31 October 2007 (UTC)

If I might throw in a remark here, the change made anonymously from IP address 140.180.175.90 turns a correct statement into an incorrect one. The new wording claims I object to Smith's proof on the ground that his proof "constructs its initial input in a somewhat complex way". Not only have I not said this but I don't find that aspect of the proof objectionable (though others might)---variations in definitions are fair game in mathematics. My objection is based solely on the ground that as it stands the same reasoning would prove that an LBA is universal, which broadens the definition of "universal" unreasonably far. Normally I'd revert such a change myself but in this case I should probably recuse myself. --Vaughan Pratt 16:35, 31 October 2007 (UTC)

I've often seen others targeted by the "spin doctors" on Wikipedia who don't like what others have written, but never expected to become the object of such tampering myself. The paragraph I wrote above objected only to the change to the article that produced "it constructs its initial input in a somewhat complex way," which puts words in my mouth, and stated more precisely what I did object to. But instead of making the appropriate correction User: Requiemdirge has taken this as a pretext not to revert the change I objected to but instead to remove all reference to any dispute about the proof, claiming that I had suggested such removal. I have suggested nothing to do with either the inclusion or the exclusion of any reference to the dispute itself since that sort of interference by someone an article mentions seems against the spirit of Wikipedia. I have only protested on this talk page the inaccurate attribution to me of statements that I have not only not made but do not even subscribe to. I leave it up to others as to whether the article should mention the existence of a dispute. I love the way people play hardball on Wikipedia, I wish I could pitch in and reciprocate but as I wrote above I should recuse myself. --Vaughan Pratt 05:36, 1 November 2007 (UTC)

One cannot take the claims from the discussion page of the source of the article to change the text of the wikipedia page in question. Imagine how many people would expect that complaining about something will change in his favor the text just because you are coming here saying so. The best would be to delete the part that the supposed author does not agree. Furthermore, either the former comment and your new statement does not fulfill Wikipedia's policy of reliable sources http://en.wikipedia.org/wiki/Wikipedia:Reliable_sources, including the discussion group from which those claims were taken. --Requiemdirge 11:58, 1 November 2007 (UTC)

According to a Wolfram representative [1], Smith's "proof" uses a definition of universal that is even more liberal than a known, liberal definition of Turing's classical definition. It seems odd to me that this would not be explained in the press. I assume this is because journalists were not informed as to this important distinction by Wolfram Research. There is an issue of academic honesty here, which is not helped by the irregularities how the prize was awarded without polling the committee. --Horoball 04:21, 1 November 2007 (UTC)

An explanation about the role of the committee was made, they weren't expecting to poll the committee, a common practice among program committees and editorial committees, they are only consulted when something very technical related to their field comes up and according to the company reply all the committee members had Smith's proof for two months in their hands (no committee member has refuted it). On the other hand, as Pratt himself recognize, generalizations in math are a fair game, and there is nothing odd with the generalization of the sort of Smith and has contributed to the discussion on universality. --Requiemdirge 11:58, 1 November 2007 (UTC)

For the record I'm fine with the preceding paragraph by Requiemdirge at 11:58 11/1/07. My only concern here is that the 1956 Chomsky-Putnam theorem, that LBAs are not universal, remain a theorem. I have no problem with WRI's award to Alex Smith so long as it is not taken as grounds for changing the status of the Chomsky-Putnam theorem. --Vaughan Pratt 06:46, 2 November 2007 (UTC)

Could you provide some specific references? Thanks --Requiemdirge 20:58, 2 November 2007 (UTC)

Traditionally it has been said that digital electronic computers are not strictly speaking Turing machines because they are not provided with unbounded tape. So one would argue that they are LBA's. However it has been widely accepted to talk about them as universal machines, since one can think in provide them with extra memory if necessary. This is also the case for other universality proofs as the Konrad Zuse's machine recently proved by Raul Rojas. This use of universality has been widely accepted and it is sound since the strictly application of the infinite blank tape as a requirement for universality is counter-intuitive, one cannot artificialy impose such narrow notion and then say that there is one single abstract universality. Smith's use of the concept is not different to the "abuse" of the term. Moreover, he is proposing that it is not an abuse but a sound generalization. If making a sound proposal makes a known theorem to fail under a more intuitive definition that has a lot to do with a mechanical sense of computing and general purpose, I do not see any problem with that. --Requiemdirge 21:10, 2 November 2007 (UTC)

Computers these days come with about 242 bits of space, or half a terabyte. To be an LBA a computer would have to work with inputs that long, corresponding to nearly a million novels. I know for sure that if I run my computer on an input that long I'll bring it to its knees, assuming even that there was any practical way of assembling such an input. Computers aren't remotely near being LBAs in any sense that's meaningful in practice. And LBAs aren't remotely near being universal Turing machines. So much for the Turing universality of your laptop. --Vaughan Pratt 08:43, 4 November 2007 (UTC)
I have difficulties following your reasoning. Computers have 242 bits of space because they use them, at least potentially and very often!, as well as for the RAM, which it is not uncommon to overflow and then use paging for virtual memory (traditionally a fixed amount of space in bits determined by the OS or the user). Common errors appear as a consequence of overflowing in computer programs, operating systems and digital computers in general. Furthermore, those bits are not "blank" tapes, the hard disk and the RAM work with pointers and file allocation tables that give the impresion of "erasing", so the storage media remains with a background that sometimes plays or not a role in the actual computation. How one would be able to defend universality for digital computers without mining your own argument about LBA's. One would need to take one or another position and then yield about the fact that there is no clear-cut. I am not arguing that Chomsky's result implies that LBA cannot be universal. Smith case is perhaps a chance to settle on this and come up with a more precise and accepted definition (perhaps more intuitive? more abstract?) of universality, or to propose levels of universality (which would be against the sense of universaility itself...) but not to stick to a narrow and perhaps inconsistent use of the term in behalf of keeping old theorems intact by dubious assumptions at the same time that the term is abused to say that digital computers are universal instances under the same assumptions! --Requiemdirge 3:31, 5 November 2007 (UTC)
I was struck by a journal article I read long ago by a linguist objecting to Chomsky's generative grammars on the ground that English clearly was not an infinite language, based on his conjecture that English sentences could not be longer than a million words. He expressed unwillingness to pin the maximum length down precisely but seemed confident that the upper limit should be a six-digit number. Chomsky draws the distinction between competence and performance: we possess a theoretical competence to understand indefinitely long sentences, but lack the practical resources of time and memory to do so. Likewise the finiteness of a practical computer is a performance issue; our modeling of a computer as having infinite memory is a competence assumption that simplifies reasoning about computers. When we prove correctness of Euclid's gcd algorithm we do so without worrying about the possibility of overflow, which will happen for ten-digit arguments on a 32-bit computer. But there is a difference from humans: the performance of computers can improve dramatically with time, so in due course the same gcd algorithm will work up to nineteen digits on a 64-bit computer and so on. By modeling the computer as infinite we avoid having to account for the complicated impact of a moving boundary on a simple algorithm. In some models the input tape may be finite, in others infinite. These are changes in axioms, which may change some theorems that follow from the axioms. There are two fundamental rules to follow when proving theorems: be clear as to which axioms each of your theorems depends on, and don't use inconsistent axioms, those that allow proving both P and not-P. My objection to Smith's proof is based not on his choice of axioms, whether this is finite or that is infinite, but whether he has been clear about his choice of axioms and whether they are consistent. An argument that can be adapted to show that all LBAs are Turing universal consistently with the rules by which Chomsky proved the opposite is an argument that can be used to show both P and not-P, where P is "LBAs are Turing universal." This is the essential inconsistency in Smith's reasoning. --Vaughan Pratt 18:08, 5 November 2007 (UTC)
Well, fortunately I am not that journalist. It is known that modeling a computer as having infinite memory simplifies reasoning about computers and I am not arguing against. What I am arguing is about the inconsistency of the use of the universality term, which is also what you are arguing too. The point is that while you are willing to relax your definitions for the benefit of simplicity (and many others too by avoiding a clear answer on why a digital computer is universal when it does not have an unbounded memory as a matter of fact), you do not accept anything else that does not fit the preconceptions of the "stablished theory" (this even sounds Ptolomeical!). As for example, discussing the implications of a hierarchy that makes universality unnatainable except when making assumptions of the sort described above --digital computers with an infinite tape. The point is that if one accepts that the best suitable model of universality is the actual digital computer with no infinite tape, then one would have to review what has been done before in the benefit of intuitiveness and feasibility and stop stating universality at that abstract level. I do not see any non-consistency on Smith's arguments of the type "P and not-P then Q", but of the type "if P then Q", where P is the generalization based on 1) generalizations of the sort done before and 2) the universality use in NKS (Stephen Wolfram seminal work) and widely accepted such as rule 110 cellular automaton. And Q the statement "is universal". What are you saying is that if P then the class of LBA would be universal (see that P in Smith's proof perhaps is not the P that you claim, but let's suppose it is). I see the problem as follows: this universality definition is on the limit of what one can allow for the construction of an initial condition, and that generalization has unleashed questions of foundational value that perhaps should be taken more seriously other than just saying that the proof is wrong or has an elementary flaw, or that WOlfram paid consultants that that would be more constructive. By the way, I think you are not correctly signing your time, if you are in the US you should either calculate the UTC and put it correctly or sign with CT, PT, ET or whatever according to your local time. Otherwise it looks pretty weird that I am posting a reply to your message before your own post. --Requiemdirge 9:27, 5 November 2007 (UTC)
It does look weird. You may have found a bug in how Wikipedia expands the four tildes. My watch says 9:21 am Pacific Standard Time (PST) which should be 17:21 Universal Coordinated Time (UTC). I only typed four tildes and Wikipedia is doing the rest. You should do the corresponding check at your end. --Vaughan Pratt 17:21, 6 November 2007 (UTC)
As noted at the bottom of my talk page, it seems to me at this point that enough opinions by those not on the official committee have been expressed that I for one am now going to step out of the debate and wait for any further word from the committee beyond the announcement last month by one its members that a proof has been accepted. I see my role in this as having been merely to argue that Smith's proof is insufficient to exclude LBAs from the class of machines coming under his proposed criterion for universality. Under the Rules and Guidelines of the prize only the committee can judge the merits of Smith's criterion; as far as I'm concerned, whether any additional post-decision judging is necessary or appropriate is up to them. --Vaughan Pratt 18:02, 6 November 2007 (UTC)

[edit] Minsky and Bobrow (1961)

I have cited Minsky and Bobrow (1961) in support of the fact that (2,2) is not universal, but cannot find the reference (neither Minksy nor Bobrow have complete CVs on the web). Would someone please add this reference to the entry?132.181.160.42 05:30, 31 October 2007 (UTC)

There is no paper about the non-universality of the class of (2,2) Turing machines, but Minsky claims to have the proof in his "Computation: Finite and Infinite machines" book and it is pretty obvious that if you use a halting state any (2,2) Turing machine will turn out to be extremely simple to support universality under any definition. Requiemdirge —Preceding unsigned comment added by Requiemdirge (talk • contribs) 21:42, 31 October 2007 (UTC)

How is Bobrow and Minsky's result relevant? They assume blank tape outside the finite initialized part. In order to compare like with like one would need to show nonuniversality of (2,2) machines under the criteria being allowed for (2,3) machines. This may or may not have been done by someone, but not by Bobrow and Minsky. --Vaughan Pratt 21:22, 5 November 2007 (UTC)

I am happy to see Minsky (1967) cited until further notice. I wish no more than a reference to the non-universality of (2,2) machines under the conventional assumptions made in the literature over the past several decades, including finite input. Because Alex Smith and Wolfram will, ultimately, be judged by those assumptions. You cannot enjoy the freedom to move goalposts and to declare yourself the winner...132.181.160.42 04:34, 12 November 2007 (UTC)

[edit] Controversy

I've glossed the controversy, as I understand it, in my user space here. Synopsis of the synopsis: the statement in the original announcement was misleadingly over broad. The specific result of the prizewinner is correct. The difference between the actual result (relaxing "Universal" to include infinite input, albeit restricted "repetitious" input) and the apparent result (taking "Universal" to imply finite input, a natural assumption based on the original, widespread definitions) is important. Feedback is of course welcome. Pete St.John 16:52, 1 November 2007 (UTC)


The description about the controvery was pretty sensible when you pointed it out yesterday and included this link to your own page and which I reproduce below:

-- This is a synopsis of the contraversy. Wolfram Research announced that they were awarding a prize to an author, Smith, for proving that a certain algroithm, Stephen Wolfram's (2,3) Turing machine, was Universal. The difficulty comes from interpreting the word "Universal". Consider the statement: "(2,3) is Universal": if "Universal" is taken to mean "as in Minsky's original defintion" then the statement is false, as pointed out by the Stanford logician Pratt in 1 to a newsgroup. I think this would be the natural interpretation from glossing the announcement as it was worded. Note that in the old-fashioned language of the original inventors (such as Turing), the requirement of storing the input in the computer can be taken to imply the input is finite. if "Universal" is taken to mean "Universal, relaxed to include infinite input sets" then the statement is trivial. (Your Pet Rock could solve the Travelling Salesman Problem if it were given all solutions to all problems as input). if "Universal" is taken to mean "Universal, relaxed to include infinite input sets, but the input is highly restricted in special ways" then the statement is (presumably) true. Such is the actual statement of the theorem in the prizewinning submission. The import of such a theorem is beyond my scope to judge; it's outside my field. I'd just trust the experts on the prize panel, which include Ron Graham and Dana Scott. See the rebuttal from Wolfram [Todd Rowland's rebuttal] My opinion: the Announcement from Wolfram Research was overly broad and merits criticism as such. The actual statement of the theorem may have been too technical but also would have been less attention-grabbing. My sense is that Wolfram is too self-promotional for the tastes of many scientists (but not too self-promotional by the standards of American business), but that the basic science is pretty good (if not as earth-shaking as the self-promotion makes it appear). --

You also expressed in this discussion page that " The specific result of the prizewinner is correct. The difference between the actual result (relaxing "Universal" to include infinite input, albeit restricted "repetitious" input) and the apparent result (taking "Universal" to imply finite input, a natural assumption based on the original, widespread definitions) is important." However you have re-worded your previous description and biased it in favor of Pratt saying that in any case the proof would be wrong, clearly contradicting your previous suggestion. That also goes against Wikipedia spirit, you cannot make a proposal and then apply completely different changes. Beside that there were some typos in your text I do not agree with the content. The validity of the proof clearly depends on the definition of universality and under the definition used in the prize the proof is sound. Pratt is arguing that if one accepts that definition LBA's would become universal, which would colapse 2 levels of the Chomsky hierarchy. However the generalization goes in spirit with recent generalizations used to prove universality of other systems Iincluding rule 110 which is widely accepted as universal, and other universal machines), so this enrich the discussion on the concept but it is far to be wrong. It is not just a matter of being right or wrong in general but about subtles. Pratt's or anyone's opinion on a list, even if he or the list are "respectable" are not reliable sources simply because it is in the process of being discussed and you cannot take the word of Pratt over the others, which are also respetable contributors (every member of the FOM list has cleared basic credentials required by the moderator of the discussion list). And even if you think that having an affiliation to Stanford University he would be immediatly right, that's completely false, just read one of the latest comments of one of his department colleagues asking " whether a non-periodic infinite string is computable". Regretable but true... If one would like to point out that there is an on-going discussion about the validity and the importance of the proof in a public list and provide a link it would be the reader who would take a position. I am not going to change your text right now in order to get some feedback, but definitely I will suggest and apply a change soon. Also consider that spreading biased information yields to a snowball phenomena permeating the whole world wide web almost immediatly (see slashdot for example... with people feeding each other thinking that they are all capable judges...) so one needs to be very careful with those sort of claims favoring a personal statement or opinion, even if he kindly comes here to express himself. --Requiemdirge 20::58, 2 November 2007 (UTC)

Not at all my intention (but please link me or quote me the wording that implies either way, the proof is wrong. Maybe someone elses?) The dichotomy I mean to express is definitely not "Smith is right or wrong" but instead "The wording of the paper is poor (if the definitions used were not explicit)" or "The wording of the press release was poor". In NEITHER case is the proof wrong, in my opinion. The problem seems to be the wording of the theorem, and probably only the way it was worded in the press release. What I would really like is for Pratt to say "The proof, with the hypotheses given in the original paper, is correct; but the announcement, using terms that have connoted finite conditions for decades in this field, was misleading" and then I would love for Wolfram to publish "We apologize for the overstatement in the press release and regret offending Pratt and other logicians, for whom obviously we hold the highest regard". That would be my perfect happy place world, but I haven't heard back yet from my formal-logician friend so I don't even know that happy result is completely correct technically. In the worst case, Smith didn't state definitions that he should have, and were only implicit in his paper; but I'm more inclined to doubt the press release, and accrue respect to Rowling's rebuttal. Pete St.John 20:26, 2 November 2007 (UTC)
few quick things. First, I've taken heat from both sides (trust me). I really really want everyone to be friends; Wolfram is a major purveyor of good software, and Graham (on the prize committee) is as cool as they get. On the other side, I'm a mathematician (sometimes :-). The actual truth comes from research and logic, not from publicity, and it's very plausible to me that Wolfram, being a business, overstated the case for publicity. Second, I note that Pratt has replied to this thread; and in fact I'm still unclear on the variance between my synopsis (ambiguous definitions) and his position, so I'll ask for a clarification. My premiss is that we will all come to agree. That's because we are talking about propositions in a predicate calculus, not personal opinions. There is some overlap because 1) editors are human; 2) even mathematicians make mistakes (see the Dear Abbey snafu famous among probabilists) and 3) businesses sell themselves with PR that is not Mathematics. And maybe some more reasons too. Let me illustrate my position by explicitly criticizing both parties: 1) Wolfram is self-promoting and 2) Pratt is stubborn. The former is very typical of businesspeople and the latter is (ahem) very typical of logicians. I've studied under both (the late) Joe Schoenfield and Jim Ax, "stubborn" is a polite term for it. Pete St.John 21:01, 2 November 2007 (UTC)
I looked up "stubborn" in Merriam-Webster and it said "unreasonably or perversely unyielding." There are many who are more competent mathematically than I, and if any of them were to point out a problem with my objection to the proof I would be reasonable and yield at once as soon as I understood their argument. Nothing like this has happened so far, and until it does the accusation of "stubborn" is just one more of a number of attempts at undermining my objection to the proof by rhetorical instead of logical means. --Vaughan Pratt 09:42, 4 November 2007 (UTC)
Please let me explain my use of the word "stubborn". First, I wanted to admit the possibility of imperfection on both sides of the debate, for the rhetorical purpose of encouraging compromise. Second, the wiktionary entry stubborn does not sound so negative, and I've known the word to have a very positive connotation, e.g. a stubborn defense (in a battle or a football game). Third, I don't believe at all that you are mistaken about the technical matters, and I would certainly be slow to critize if I did: I'd have to work out a complete proof in a field outside my own. I do however believe you were somewhat stubborn about attributing the error, particularly, "Smith's false proof" vs "Wolfram's self-promoting description". All that said, I really appreciate your recent effort at your talk page to clarify these things to me. Pete St.John 20:52, 5 November 2007 (UTC)
(In hindsight I used "rhetorical" where what I meant was "misattribution" (of statements to me I've never said). "Every aspect of human life and thought that depends on the articulation and communication of meaning can be said to involve elements of the rhetorical," sentence immediately preceding the Table of Contents of Rhetoric. Rhetoric properly used should clarify, not obfuscate.) --Vaughan Pratt 20:20, 5 November 2007 (UTC)
I certainly didn't meant to misquote you. Did I paraphrase you in a misleading way, somewhere? Pete St.John 20:52, 5 November 2007 (UTC)
If your position is based on criticizing Vaughan Pratt for supposedly having character traits similar to some of your former teachers due to a similarity of profession, you are on a weak footing. By the way, let's everyone learn to indent, shall we? It's really quite confusing to not indent.
I nowhere said, or meant to imply, that Pratt is wrong because he is stubborn. Never have I said he is wrong about anything. I explain use of the term "stubborn" above, in rely to him. Pete St.John 20:52, 5 November 2007 (UTC)
Furthermore, your comments reveal a lot about your ideas of what you think is going on. Sure, I guess you would like if all the people involved issued statements that match your theories, but they haven't. Let's not indulge in speculation and stick with the reported facts as others have suggested here. Your edits show a great liking for indulging in such speculation and yes it can be fun, but let's not. Think of the children! Or at least, let's stick with the core policies of Wikipedia and not insert this speculation into the actual article. Keep it restricted to this talk page, if you need to indulge. Currently the controversy subsection clearly reads like one editor's thoughts and is certainly not encyclopedic. I will therefore remove these additions. Please develop some consensus here before re-instating them. --Horoball 18:04, 4 November 2007 (UTC)
I would be very grateful if you would point out speculative passages, sentence fragments, or words, so I can try and improve items. Thanks. Pete St.John 20:52, 5 November 2007 (UTC)

The "controversy" section reads very much to me as original research. Can we restrict ourselves to describing what reliable people in this area have actually said, and not our interpretation of what it means or our speculation of how the peer review process will cause things to shake out, please? Also, regarding Pratt's complaint, it's not obvious to me from what he wrote that the problem is infinite inputs per se, but rather the argument involving limits of sequences of inputs, and whether such a limiting process can be construed as a universal computation. —David Eppstein 21:34, 2 November 2007 (UTC)

Effectively the problem are not the infinite initial conditions, Smith's proof contribution is non-periodic infinite conditions. Infinite initial conditions have been used commonly by the small Turing machine community, and Smith's contribution is of the same sort since he still maintains the initial condition computationaly-speaking simple enough. These kind of generalizations and variations have been made before, there is no single definition of universality, authors have been assumed different requirements before, some sound and some more artificial. Pratt's objection is not to the initial conditions, he finds them as he said here, non objectionable. Wolfram's definition of universality was enough clear in the page prize since he send people to his own work. It is widely accepted that rule 110, is universal, for instance. I would favor the idea about sending the reader to the actual discussion (the same for the other pages, Alex Smith's and others) and say that the proof has trigered a rich discussion about the grounds of computability, in particular the definition of universality. Then the reader can inform himself and take a position if he wants to. If so we would be avoiding doing wrong interpretations, or any interpretations at all. --Requiemdirge 11:22, 2 November 2007 (UTC)
Dr Eppstein, I intended the section to be reference to two external items, one ostensibly justifying the opinion of editors that Smith's paper is incorrect (they point to Pratt, and on that basis edit articles saying the proof is incorrect), and the other ostensibly justifying the opinion of different editors, e.g. me, that Smith's paper is technically correct (with his defintions as stated, which may not be conventional) and that the Wolfram Press release overstated it's case (by refering to "Universal" instead of "Universal, relaxed to include certain infinite input sets"). The later (concerning generalizing the notion of "universal") is described by the refernece to the Wolfram item. A problem we have is that editors are trampling on each other, one camp reverting the other. However if the wording explaining the controversy can be improved I'd be glad to hear it. I'm trying to steer the debate away from the technical correctness of Smith's paper, to debate about the use of the technical term "Universal". In my opinion Wolfram was excessively self-promoting in announcing the result without qualifying the term (since the result would be false restricted to conventional definition of "universal", as Wolfram agrees). But thanks for coming and giving this a look-see. Perhaps you can make one of your students write it up better :-) Pete St.John 21:56, 2 November 2007 (UTC)
I have to agree with David Eppstein here. Encyclopedias per se tend to report on stable knowledge, which is the antithesis of controversy. These talk pages are the appropriate place to thrash out controversies. The only mitigating factor in favor of allowing short half-life controversies into the article proper is that Wikipedia articles can be revised at the drop of a hat. The flip side is that people look to Wikipedia articles as authoritative (whether justifiably or not), making it inappropriate to rely on their malleability for the inclusion of controversial material. --Vaughan Pratt 09:42, 4 November 2007 (UTC)
So Pratt would agree after his arguments that an on-going discussion in a newsgroup is not stable knowledge. Controversy is when two sides notably disagree, and both sides have the authority to take a side, so it is a constroversy. There is no flaw in the proof, everything is based in the use of the universality definition. If Pratt is worried about the authoritative sense of Wikipedia from which people could jump conclusions he should also be worried about the contrary. His position has releashed other public and wrong claims. Both sides have been rethorical in some sense, but there is a proof, not rethorical at all. The prize organizers say that they are making a sound generalization, if that implies that some theorems assuming other definitions are not valid under it, that is fair, but not wrong. Theorems in math are not physical principles. Pratt has also used a rethorical folkloric language to refute arguments, such as the use of la Brea tar pits. With all my respect I heard that that comment unleashed some thoughts about the dinosaurs on the FOM list... the reluctance about accepting new changes is a common practice from people that has been working on the same subjects over decades, and they have even said to consider themselves the "defenders" of the knowledge. As it has been said nobody wants to work hard enough to figure things out themselves but once someone makes the effort they are all ready to try and find bugs. --Requiemdirge 18:32, 3 November 2007 (UTC)
There is definitely controversy, and there is precedent in Wiki for articles mentioning controversy, particularly for news items (as is the case here, at least on account of Slashdot) with developing stories. In this case, it may take a long time for everyone to agree (if ever), but it would be disinformative for the article to state a disputed result without mentioning the controversy. However, instead of trying to give any synopsis, i'll just point to this talk page (there is precedent for that also) since my synopses don't seem helpful. Pete St.John —Preceding comment was added at 18:27, 5 November 2007 (UTC)
It is not appropriate to point from the main namespace to talk pages. The article already points to Pratt's message describing his issues with the proof; what more is needed? —David Eppstein 18:33, 5 November 2007 (UTC)
PS Of course your ActiveDiscuss tag is appropriate. I meant that it is not appropriate to include wikilinks to Talk: within the text of an article. —David Eppstein 18:37, 5 November 2007 (UTC)
I didn't, myself, mean to link a userspace item from any article. By "point" I just meant "see the Talk page", which is that the ActiveDiscuss amounts to. The "wording for use in articles" at my scratchpad, I copied into articles. I meant for a single place where contributors could discuss even-handed, scholarly wording for it, but it seems not to have been effective. Pete St.John 19:16, 5 November 2007 (UTC)

[edit] PSJ-VRP dialog

(VRP: I've moved this section from my talk page to this one as a more appropriate place for it. Pete St.John approached the controversy by considering both sides (which unfortunately led some of those taking my side to assume he was taking the other) and asking me a number of clarifying questions that may be apropos for many. Had I answered him more carefully from the outset I would not have needed the round of clarifications, for which I apologize. For ease of reading this section of what had been on my talk page I had reformatted it to prefix PSJ at the start of Pete St.John's edits and VRP at the start of mine, separated the edits with horizontal rules (hr), and eliminated the indenting, hoping that this might improve on the alternative of indenting alone which sometimes obscures the structure of the dialog.) --Vaughan Pratt 16:54, 6 November 2007 (UTC)

PSJ: Dr Pratt, hi. I'm just a programmer, but I studied under Carlitz in the 70's and I care about math, and lately (on account of the Slashdot article) I've been trying to clarify debate about the (2,3) result. I'm unclear about one of your statements (which I only recently noticed):

  • (from the (2,3) Talk page) ...variations in definitions are fair game in mathematics. My objection is based solely on the ground that as it stands the same reasoning would prove that an LBA is universal, which broadens the definition of "universal" unreasonably far...
  • I had written up an attempt at clarification, at my scratchpad, with two items (so far), one my opinion, and the other proposed wording for use in wikispace articles (which I have used today, e.g. at (2,3)).
  • My view is that the main problems are with the statements of the definitions. So may I ask:
  • 1. Is Smith's result, with the definitions he gives in his paper, correct? I've been assuming this since, e.g. Ron Graham is on the prize committee, and I believe your statement implies it.
  • 2. Am I right interpreting you that if the definition (of "Universal"?) used in the paper were applied to LBA, then LBA would be universal?
  • 3. If the press release had said, "Wolfram's (2,3) algorithm was found to be Universal, by relaxing the defintion of Universal to include infinite, but very restricted, input sets" would you have objected? I'm thinking not.
  • 4. Would you agree with the statement:

Smith's paper is correct technically, but it relaxes the definition of "Universal" too far; for example, with that defintion, LBA would be universal, which would contradict convention and common usage in this field.

  • What I'm driving at is:

Wolfram's press release was excessive self-promotion, and I object to changing the defintion of "Universal" in general use. The result generalizes the notion of a Universal Turning machine in a way that is not implementable directly on actual computers.

  • Basically I want to blame the press release, and not the kid. Thanks very much, Pete St.John 21:25, 2 November 2007 (UTC)

VRP: Well, that last one is easy. The kid made a natural mistake, but he's just getting started and mistakes are how kids learn, that's what homeworks are for. The authors of the press release are not doing their job when they tell the kid he hasn't made a mistake when he has.

To answer your questions:

1. I've already expressed my opinion that it's not correct, with detailed rationale. You'll have to ask Ron Graham whether the committee thinks Smith's result is correct. Or Martin Davis, another committee member, who said at http://cs.nyu.edu/pipermail/fom/2007-October/012132.html that "no member of the committee has passed on the validity of this 40 page proof."

2. The paper doesn't give a sufficiently precise definition of "universal" to answer this question. However the answer is yes for any definition of "universal" that would make Smith's argument sound.

3. I wouldn't have objected since that modification of the definition is relatively minor and of no great consequence. However that issue wasn't the basis for my objection, which addressed a much more serious flaw in the argument.

4. No and yes. No in that Smith's 55-page solution is far too complex technically to simply agree that the whole thing is correct without weeks of close study---to see merely that it contains an elementary but fundamental flaw takes far less time by comparison. Yes in that any definition of "universal" that fixes the flaw I found makes LBAs universal, contrary to a half-century-old theorem. --Vaughan Pratt 09:05, 4 November 2007 (UTC)

PSJ: Thanks very much for your reply.

  • First, thanks for pointing out Prof Davis' email. At the risk of sounding glib, it sounds as if "Prize Committee" has been redefined also :-( Once I had to send software to a tradeshow before it could go through quality assurance. The result was horrible. Business is ... well. Rough.
  • Second, I'm still confused by items 2 vs 3: a new definition, call it "Wolfram-Smith Universal" (something like, "allowing for infinite input, but restrcited in special ways") would make LBA W-S Universal, but, from 3, there is an additional objection, besides an (implicit?) redefinition, to Smith's paper? Pete St.John 18:05, 5 November 2007 (UTC) (can't count past aleph-null)

VRP: The problem in trying to reconcile 2 and 3 is that your question 2 is asking about a counterfactual, what if Smith had applied his definition to LBAs. Counterfactuals are tough to deal with because they entail ill-defined rips in the fabric of truth and proof. In my answer to 2, instead of "yes" I should have said "yes and no," meaning that in that case Smith would be able to prove both P and not-P where P is the proposition "LBAs are Turing universal." His argument proves P in the case of this 2,3 machine in place of an LBA, but because he has not told us, for the rules Chomsky used to prove not-P, which of those rules he is now disallowing in order to prove P, he is now in the position of being able to prove both P and not-P, i.e. his reasoning is inconsistent. Rephrasing my answer to 2 in this way should bring it into complete agreement with my answer to 3, since my original objection to Smith's proof was precisely that. --Vaughan Pratt 18:49, 5 November 2007 (UTC)

VRP: On second thoughts I see that my answer to 3 was unclear too. What I meant by it is that I don't mind modifications to the definition of the behavior of this kind of machine, such as whether the "rest of the input" is blank or periodic, and the criterion for acceptance. What I do object to is any modification to the definition of "universal" that would make an LBA universal. Smith's argument is equally sound for this 2,3 machine and LBAs. By all means define a new concept called say Wolfram-universal that makes both LBAs and this 2,3-machine Wolfram-universal, but then be clear that you are not claiming that either LBAs or this 2,3 machine are universal as customarily understood. The consequences of the latter include both P and not-P, i.e. that line of reasoning is inconsistent. (While good concepts should be named after their inventor I feel that justice is better served by naming bad concepts such as this novel notion of universality after the most senior authority to endorse them.) --Vaughan Pratt 19:53, 5 November 2007 (UTC)

PSJ: Again, thanks for your reply, and more so for your patience. I'm pretty sure Shoenfield would have beaten me over the head with a goban by now.

  • Minor point, I'm watching this page so you needn't drop notes on my page. Maybe If I can get this clear, other folks can too.
  • Sidebar. I remember the faster grep from before I learned the word grep. That was dumbfounding, like someone discovering a Golden Mountain in the middle of Times Square.
  • Consider the proposition WSU: Wolfram's (2,3)-algorithm is Universal in the unconventional, extended sense of allowing certain infinite inputs. Has WSU been proven false? ...ah! I just saw your recent reply. OK, no. I believe we have converged, at least on the technical matter. Thanks very much! Pete St.John 20:21, 5 November 2007 (UTC)

VRP: Rather than WSU, write WSU(M) for the truth of the WSU criterion of universality for machine M. WSU(M) needs to be strengthened to include Smith's rerun protocol, by which he runs M repeatedly with different initial conditions in such a way that M runs longer at each rerun. I claim there exists an LBA A for which WSU(A) holds, namely a universal Turing machine modified so that for any given initial condition it uses only the amount of space that Smith's System 5 (if I've understood the numbering) uses for that initial condition. WSU holds for A. Assuming the other 54 pages of Smith's argument are correct WSU also holds for the system Smith runs his protocol on.

I don't plan to check the other 54 pages because (a) that would be more work than for Smith to implement his machine in a readily available programming language like C so I could see directly that it works instead of trying follow an impenetrable correctness proof that it works, (b) the rest of the world could then easily check it for themselves instead of having to take my word for it that every step of Smith's proof was correct, and (c) I attach even less importance to the WSU universality of small Turing machines than John McCarthy does to the standard notion of universality for small Turing machines. --Vaughan Pratt 21:02, 5 November 2007 (UTC)

PSJ: Thanks again. That clarifies the second objection, which I had missed, the "rerun protocol". (Somehow this reminds me of straightedge and compass constructions for trisecting general angles; giggling near-misses in a way that inconspicuously violates the strict conditions.) And particularly I appreciate your patience as my wording has not been well-received elsewhere. It just astonishes me to be seen as a Wolfram-defender, but that's how it has gone, so your cordial replies are very welcome. My sense is to blame the self-promoting PR for expressing the result (or claim) in a grandiose way. But blame is another matter than establishing the technical truth, which I think you've done pretty convincingly. Pete St.John 21:23, 5 November 2007 (UTC)

REPLY TO THE ABOVE INSERTED DIALOG INTO THIS TALK PAGE
For the benefit of others reading the dialog above, this was a private dialog between two people ocurred outside the discussion of this page and later artifically posted here. This also goes againt Wikipedia guidelines. The problem is that it could be seen (disregarding the title) as if everybody in this discussion would have agreed with Pratt or Pete St.John or no one had anything else to say, making people jump to conclusions. A more important consequence is that Pratt had not real interlocutor since Pete St.John seems to thank Pratt to teach him, certainly Pete St.John has not all the necessary elements to refute Pratt. Anyone would be grateful with Pratt in such a case, he is certainly a very good lecturer. Howevet there are several flaws in this dialog that at least someone should point out. To begin with I should say that several times the organizers have explained the role of the committee: http://cs.nyu.edu/pipermail/fom/2007-October/012149.html and http://cs.nyu.edu/pipermail/fom/2007-October/012163.html This shows the double moral in Pratt's behavior in which he has incured several times, both when pointing out supposed anomalities in the awarding of the prize and when claiming elementary flaws, since he is perfectly aware of the reply he got when he wondered about the committee role awarding the prize, and he did not say anything just pointing out to the messages in the FOM list that he favors to illustrate Pete St. John. As they announced, they were not expecting to poll the committee, the committee was there to serve as advisors for eventual technicalities. They also pointed out that all the committee members had in their hands for 2 months Smith's proof. On the technical hand, one would need for example to prove that the process that Smith uses to feed the 2,3 Turing machine is a universal LBA --under the supposed relaxation of the universality definition-- for which Smith claim it is not universal (or computationally simple enough), so when taking Pratt's claim that the same process would make a LBA universal and assuming that Pratt is right and enough informed about the process (even though he has not read the whole proof and does not pretend to read it), then some inconsistency of the type P and not-P would be possible as he also claims, otherwise not. Alex Smith has several times refuted and pointed out why the process is not computationally enough to perform universal computation. So even if Pratt is right there is no inconsistency. In other terms, Pratt is supposing that the assumed LBA in question (if it is the case for Smith construction of the initial conditions) is universal disregarding anything else, including the LBA transition function. Consider for example that even though Turing machines are universal as a class, that does not imply that every Turing machine is universal. For example, if Smith is using a subset of primitive recursive functions and a rule 60 cellular automaton predictor, that does not suffice to perform universal computations even if the process is allegedly a LBA, which is very unlikely to be because of the simplicity of the generator of the initial condition. Having pointed out at least 2 disagreements and, from my point of view, several logical mistakes in the previous dialog I strongly complain again about the insertion of that private discussion between 2 people into the actual development of the talk page related to this and any other article. Either keep your personal conversations private or have your conversations here. Each of Pete St.John and Vaughan Pratt posts would have been replied if publicly debated, either by me or perhaps others. Requiemdirge 19:11, 6 November 2007 (UTC)
I think what Vaughn Pratt said was that this was moved from his talk page rather than that it was private conversation. The short version seems to be that if Pratt had realized PSJ wasn't from Wolfram, he would have been nicer.
Pratt should perhaps have a look at the dubious collection of anonymous IPs, apparent sock puppetry, etc. of those supporting Pratt's position over the various pages on which the issues of the correctness of Alex Smith's proof has been discussed. I can provide further details privately. My email address is kathryn.cramer@gmail.com. --Pleasantville 19:30, 6 November 2007 (UTC)
  • Requiemdirge, I'll just address your ad hominem attack, not all of the above. You impute a purpose of "making people jump to conclusions" by "artificially post[ing]...a private dialog". The questions I posed to Pratt on his talk page were personal, that is specified to a recipient as opposed to broadcast, but not private as in confidential, as might be the case in email. His talk page is not only publicly readable but, I would guess, currently highly visible. The consequence of our question-and-answer thread was that he posted it to this talk page, believing it useful. He has every right to do that; there was nothing confidential about it, and in fact I explicitly said (quoted above!) that Maybe If I can get this clear, other folks can too. Now that it's here on the talk page, you and others can conveniently rebut any part of it, as you are doing.
  • Also I should mention the deference in my tone to Pratt. He's one of the world's leading authorities on this subject, and in my field. He's an older generation than I (somewhat) and graduate students at Stanford have a better claim to his time than I do. But actually I'd be pretty polite to Wolfram, too, if he contributed here. We're lucky that a principal in the controversy made himself available to us.
  • Regarding Pleasantville's convern over sock-puppetry; yes, I've noticed it too, and reverted some of that vandalism and mentioned the vandalims on an IP talk page. It would seem that the Pratt/Academic side (as opposed to the Wolfram/Business Side, for lack of better terms) has more irresponsible young students spamming from terminal rooms. Pete St.John 19:48, 6 November 2007 (UTC)
Pete St.John, I understand the purpose of your insertion, I am not saying that you did it maliciously. You are right about my misuse of the term "private", however I still think it was "personal" and then still innappropiate for a sudden insertion into a talk page with an on-going discussion. Consider that not only me but perhaps any of the possible interlocutors do not have the time to go through all the posts you have suddenly put here. And as I have said, this can give the impression that we all agreed in this talk page in favor of some position from an actual dialog between 2 people. As you can also see, it is easy to jump to conclusions when having only one side point of view, as for your comment on the redefinition of "committee" for which Pratt did not mention anything about an explanation given before. Thanks anyway for letting us know the valuable information that you and Pratt shared but I would have prefered just a pointer. Requiemdirge 21:05, 6 November 2007 (UTC)
(man, we need sub-sub sections to edit this). Requiemdirge, I just don't understand the "...sudden insertion into a talk page..." objection. Pratt pasting that thread is no more a sudden insertion than your typing the above paragraph. It's part of the dialog. As Wiki users we can use our mouse device. Nowhere is anyone in any way inhibitted from the discourse. Unlike the Erdos Number controversy, which is making me nuts, because the "opposing view" (which voted to delete the Category, and deleted it) is completely incoherent to me. I have no idea who those people are, or what they want, but they have multiple admins agreeing with their inchoate (to me) PoV. Here, I see a chance ultimately for a civilized conclusion. Pete St.John 22:02, 6 November 2007 (UTC)
Pete St.John. I also see a chance to ultimately agree here in a civilized way. Let me add that naming universality definitions is completely non-sense. I agree that one could use Turing-universality, although universality and Turing-universality are seen as synonyms. If one would like to name universality definitions, one would need to tag all them since there is no single definition. Even the most widely accepted definition by Martin Davis suffers of variations by Davis himself, so one would need to talk about Davis1-universality and Davis2-universality, one implies the other but not the other way around. Pratt himself, in some of the FOM threads, was also suggesting a definition of universality, in which he later found a bug. Requiemdirge 22:45, 6 November 2007 (UTC)
You'll need to take up your objection to giving names to different universality definitions with those who named them in the 1950s. One universality definition is Turing degree 0', which admits more sets than the r.e.-complete sets, which defines another notion of universality (which I personally prefer). In between these two are the sets that are truth-table-reducible to the r.e.-complete sets, and there is also bounded-truth-table (btt) reducibility. A much coarser notion of universality is "undecidable halting problem", more precisely sets with nonzero Turing degree. Chapters 6-10 of Rogers *Theory of Recursive Functions and Effective Computability* (McGraw-Hill 1967) gives a comprehensive overview of these various notions of universality. The notion of universality I suggested as being appropriate for cellular automata that never halt depended on two sets K and H, the latter being a predicate identifying which computations corresponded to the "halting" ones; the bug you mentioned was in my first attempt at defining H at http://cs.nyu.edu/pipermail/fom/2007-October/012143.html, which I realized after posting it was too generous; I fixed the problem the next day in http://cs.nyu.edu/pipermail/fom/2007-October/012146.html by tightening the condition on H. In the latter form I think this would be a suitable definition of universality for cellular automata as it gets around the problem that they don't halt in any obvious sense. However the mere fact that cellular automata are sufficiently different from Turing machines as to need their own notion of universality already tells you that a single one-size-fits-all definition of universality is difficult to arrange, even without considering the variety of notions from the 1950s. --Vaughan Pratt 23:39, 8 November 2007 (UTC)

[edit] Sockpuppetry

Further to the subject of sockpuppetry: note that User:210.54.245.44, who made a number of edits regarding the Pratt controversy, was just blocked for edit warring that involved the use of a sock puppet (User:Rabidly Placid). --Pleasantville 21:12, 6 November 2007 (UTC)

Lots of articles get victimized by various kinds of vandalism. So far I've only seen vandalism (e.g. inserting "megalomaniacal" repeatedly into the Wolfram article) but not fraud (as in, voting more than once on an issue by logging into multiple accounts). I agree that it seems to be most, or all, "Pro Pratt" doing it, why I attributed it to silly undergraduates. That said, I just want to add that while I've been criticised from "both sides", I've also gotten some nice civial cordiality from both sides, particularly you, and I thank you for it. Both sides have brilliant mathematicians, both sides have fair-minded people, but only one side is saddled with armies of idiot undergraduates. Not sure who's better off on that score. Pete St.John 21:53, 6 November 2007 (UTC)
Also, note that User:Concerned cynic has just been banned indefinitely for sock-puppetry as of last night. --Pleasantville 16:27, 7 November 2007 (UTC)
Makes sense to me. The excuses we implied in addressing him (one that his browser was broken, mine that he doesn't know how to use preview/save) sounded, even to me as I composed one, that he was just making excuses after the fact for deliberate vandalism. I think the fellow has some issues, but dunno what they may be. Pete St.John 17:13, 7 November 2007 (UTC)
Pleasantville! Maybe you could help us with the Erdos Number controversy?! See Mikkalai's userspace discussion and the discussion at the Wiki Proj Math where I wrote reasons to reverse the deletion subsection. Mathematicians shouldn't be fighting each other, we should be fighting the English Majors :-) But seriously, the admin who ruled "deleted" (on the third attempted vote, and without an apparent concensus), who then got stormed with whining from mathematicians, got exasperated and quit (seemingly). Generally, all the mathematicians are annoyed/uproarious about it, but have no concensus what to do about it, as it's a political problem and not a math problem. Maybe all of us arguing here could be on the same side there, which would be kinda cool. Pete St.John 17:13, 7 November 2007 (UTC)

[edit] recent reogranization

The recent "reorganization" of the article actually strikes me as at least benign, and maybe an improvement. Considering the recent controversy, anonymous editting can make some of us a bit jumpy, so I'd urge folks to log in, or create accounts and log in. But I retain my optimism that we are headed towards an improved article. It may have to wait for peer review concommitant to actual publication, which can be years. However it can also be only weeks or months, to get to the "verifiably accepted" stage, prior to actually appearing in print. Pete St.John 05:12, 12 November 2007 (UTC)

In fact Pratt has relaxed his claims once that Alex Smith has explained in further detail his construction. Smith's stronger reply is that a LBA would need to be restarted by hand while the 2,3 TM is able to restart automatically by following the encoding in the tape. He has also pointed out several misunderstandings giving precise page references from his proof. He said also that the supposed problems that people are pointing out on his proof were addressed by the prize reviewers, so everybody was aware that people would need further precisions:
http://cs.nyu.edu/pipermail/fom/2007-November/012227.html
http://cs.nyu.edu/pipermail/fom/2007-November/012241.html
http://cs.nyu.edu/pipermail/fom/2007-November/012246.html
I would suspect that Pratt will not completely give up. I think that at this stage he thinks that Smith's proof is perfectly reasonable, although controversial, which is understandable since it is proof on the limit of the border between decidability and universality, and that was the intention of the contribution of the prize and the proof. Requiemdirge 13:52, 13 November 2007 (UTC)
I think, all things considered, it would be helpful to quote or cite just what you mean by "Pratt has relaxed his claims". Also I myself think it's important to distinguish among the press release, the statement of the theorem, and the contents of the paper (which last is too long and complex, for me anyway). My own sense is that the press release was too extravagant and introduced confusion. However, the claim that the (2,3) restarts itself according to input data, without requiring an extension of the algorithm as defined by Wolfram to accomodate iterations, unlike LBA, seems pointed and interesting. Pete St.John 18:33, 13 November 2007 (UTC)

[edit] small changes but...

A recent change was described in the Edit Summary as "style edits, no change in content" but that's a bit misleading; nothing horrible, but in scientific work there is an important difference between "finding" something and "describing" something. Several of the changes in wording slightly shift the sense at a few points. I didn't notice any one point that I myself wanted to flatly contradict (e.g. I'm not up on authorship credit for (n,k) Turing Machines for any (n,k), myself) but I'll drop a note at the (anonymous IP) talk page (sigh). Pete St.John (talk) 21:18, 21 November 2007 (UTC)

I am inching in the direction of an RfC regarding the collective oeuvre of that contributor over the course of his participation in WIkipedia. --Pleasantville (talk) 21:42, 21 November 2007 (UTC)
The "describe" version in the new edits is, I think, more accurate, as the (2,5)-machine in question was actually found not by Wolfram but by Matthew Cook. —David Eppstein (talk) 21:48, 21 November 2007 (UTC)
Oh I didn't mean to imply that his edits made the article worse. The problem to me is that the Edit Summary was misleading; you agree that the (better) word "describe" is significantly different, and factual from references, compared to "find", so it's not a stylistic difference. This contributor doesn't seem malicious, quite the contrary, but the summary was misleading and I sure wish they'd create a user account and talk to us. And it looks like Pleasantville has a point, because on their talk page I noticed a reference to the same thing (misleading Edit Summary) from a year ago. This may be one of those things where the contributor is oblivious to the contributors, and is just responding to the impersonal ascii stream. Or something else, dunno, but inconvenient. We should all be worrying about important things, like the Erdos Number Categories :-) And maybe E8. Actually, E8xE8xE8. Pete St.John (talk) 22:49, 21 November 2007 (UTC)
David Eppstein, your assertion is false from many points of view, including the legal. But in particular, the (2,5) machine was not made by Cook, it is true that it is based in rule 110 but the (2,5) machine was by far not made by Cook. Furthermore, Cook was under a research contract and if you think that is different to what happens in universities or advisors-students relationships you do not know the field, you are too naive or too bad-intentioned by saying that. However, Wolfram's rule 110 first conjecture and his own work on the particular subject regarding its universality gives him all the rights to claim credit on the proof, but if you insist to acknowledge Cook then perhaps you should also acknowledge all the people that participated in Wolfram's NKS book as research assistants to him. —Preceding unsigned comment added by 80.125.177.239 (talk) 23:47, 3 December 2007 (UTC)

[edit] Discussion of objections is inadequate

It seems to me that the discussion of Vaughan Pratt's objections in the article is inadequate. Pratt gives examples in which seemingly trivial modifications to a tape (such as adding a single symbol) can in some circumstances turn a non-universal machine into a universal machine. He gives an example with two independent heads [2] and another example with a single head and a two-dimensional "tape" [3].

In Smith's construction, the tape is initialized with a non-repeating (triangular) pattern. Pratt points out that this resembles adding a counter to the machine. But we know that adding a counter can turn a non-universal machine (a one-counter register machine) into a universal one.

Smith's reply [4] appeals to our intuition about universality: surely, he argues, if the "initial condition is done in a highly computationally simple manner" then it is "intuitively reasonable that the system is universal". But Pratt's examples make it clear that our intuitions are suspect in this area: what could be simpler than adding a single symbol to a tape?

There's a good summary from Clive Gifford [5]. Gdr 23:24, 19 January 2008 (UTC)

There was a good bit of discussion about this at the time of the news-release. A very good bit :-) The current wording is in the nature of a compromise. My own view is basically that the language natural in a business' press release is overstatement compared to what one expects in academia (and BTW that an encyclopedia should aim more towards the academic standards of scholarship; really, we're an amateur component of academia). That is, I blame the wording of the press-release for overstating the claims. If the words "universal", "turing", and "machine" were all redefined arbitrarily, plainly any statement would be vapid; but the extensions employed in Smith's paper are not entirely arbitrary. There's good work in there, just the public claims in the press-release are overblown. I wrote about it at in my notes. But by all means, feel free to suggest specific improvements in the coverage, and thanks for asking first. We definitely want to be more civil here than the flamewars at the religious-convictions articles, such as "vi vs emacs" :-) Pete St.John (talk) 16:54, 21 January 2008 (UTC)

Yes, I read the discussion above, in sections 3 and 4, but it ends on 2007-11-08, before any of the messages I cited above were posted to the FOM list. So this is new information that needs to be taken into account in the discussion.

The key point I think we should make in the article is that Smith's work is not carried out within a robust theory of universality. We normally say that a Turing machine T computes a function f(x) if we have tape encoding and decoding functions E and D such that when T is started on the tape E(x) it eventually halts with tape T(E(x)) such that D(T(E(x))) = f(x). Normally we don't worry about the role of the functions E and D in this computation, because we're generally working in a context where the encoding doesn't matter -- for example, if we're investigating whether "f" is computable all that matters is that E and D are computable too. But in the context of universality it's clear that we need sharper criteria for allowable E and D.

There seems to be some prior work in this area: in particular Martin Davis, "A note on universal Turing machines" [6] Gdr 18:07, 21 January 2008 (UTC)

The sentence Smith's proof has unleashed a debate on the precise operational conditions a Turing machine must satisfy in order for it to be candidate universal machine does not, IMO, sufficient suggest that Smith's defintions for e.g. "Universal" are expansions of convention in the literature (but I'm not qualified to assert that myself). I was hoping that the paper, or a substantial version, would be submitted for review at some point, then we'd have plenty to cite. But sure, if the function D were noncomputable, nonhalting, whatever, then such should not be claimed for T. What I'd really like (myself) is a good statement of Smith's result, better than "Smith proves that a Turing (in the sense of Wolfram) machine is Universal (in the sense of Smith)", and then contrast that with the (overblown) wording of the press release. But simplest, is to quote a more recent review, if there is one. Pete St.John (talk) 19:58, 21 January 2008 (UTC)

It's not that Smith is using a non-standard definition of "universal", it's that he is using no definition of "universal". Gdr 21:05, 21 January 2008 (UTC)

Do you mean that Smith does not explicitly state his definition(s), or that no self-consistent definition is possible, that would comprise all his assumptions? Pete St.John (talk) 22:17, 21 January 2008 (UTC)

The former. Gdr 22:35, 21 January 2008 (UTC)

The optimistic theory is that a good statement with correct proofs will come out of Smith's work, and it will be contributory. As it stands, Smith's work is not in publishable form. The press release made too much of it, but that's normal promotional language in business. The wiki should distinguish established proofs of unambiguous theorems from other things, but acknowledge the existence of other things :-). The current wording of the article indicates the imperfection of the work, but I'd agree is imbalanced. On the other hand, I don't think it's necessary or desirable to dismiss the work, either. If you propose a specific sentence to change or include, that would be cool to me. Hopefully other people besides just you and me still care :-) and will chip in. Pete St.John (talk) 19:06, 22 January 2008 (UTC)