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

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)

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 2⁴² 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 2⁴² 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)

This talk page makes me wonder if there could be devised a framework for debate such that word sequences in a natural language are attributed with unambiguous statements in a domain specific language. A really smart editor could actually tell you if you are contradicting yourself or stating something illogical as you typed it. Gabriel Green (ggreen at netschool101 dot com) May 24, 2009 at 3:45 PM (GMT -06:00)

"the members of the prize committee were "informed but not polled" as to the validity of the proof."

"prize committee"("members"(list<PERSON>)) —Preceding unsigned comment added by 99.31.195.246 (talk) 20:46, 24 May 2009 (UTC)

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)

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)

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)

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)

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)

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)

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)

What definitions would you have explicitly stated? Smith's most important particularity in his proof was stated very early in the proof, that is that he is not using a traditional blank or periodic tape yet simple enough. Most of the proof is about proving that producing that tape is not carrying the universal computation but it is perhaps only aiding the computation, as it is legitimately expected, yet that doesn't mean that the 2,3 TM cannot be found to be universal starting from a blank tape, and although it might be thought to be unlikely I recall that it has only be proven that there cannot be 2,2 universal TMs, yet there might be 2,3 universal TMs even starting from blank tapes, and that is an interesting question too. Wolfram people and Smith himself have however rejected Vaughan Pratt's claim several times. Pratt has even gave up on his main LBA argument to the counter-argument that a LBA would need to be hand restarted unlike Wolfram-Smith's 2,3 TM, so the universality of the system is not in jeopardy because it would make a LBA universal as Pratt initially said. The fact is that the 2,3 system with that init condition (as stated so early in Smith's proof and several times explained) *is* universal in the most legitimate sense (no universal agreed definition of universality exists, but with those which exist, the use of Smith's universality is fully compatible with and it might even contribute to a better understanding of the concept of universality) and there is a proof of so endorsed by Wolfram's research prize that is not better or worse than any other peer-reviewing endorsement of a journal of any other result. However the proof has been said to be published in Wolfram's Complex Systems journal peer-reviewed by non-Wolfram staff soon. Worth to mention is also the fact that as it has been said, the blue-ribbon committee, if not polled, had the proof in their hands several months, and apparently Smith made tweaks to his proof after some committee member's comments, yet no committee member has refuted any part of the proof so far. There has been some endorsement however, particularly from authoritative researchers in the field with several publications acknowledging the universality of the Turing machine. Someone should add the references to the Wikipedia article, I can make a list if necessary. Requiemdirge (talk) 05:25, 21 February 2010 (UTC)

What the hell is going on with the intro?

The intro (and title) seems more interested in promoting the reputation of Stephen Wolfram than following [7], [8] or [WP:MOS]. Does he really need to be mentioned in the title, and before the name of the automaton in the intro? —Preceding unsigned comment added by 219.73.77.123 (talk) 01:36, 20 July 2008 (UTC)

how would you call it? just "2-state 3-symbol Turing machine"? moron... 79.74.178.19 (talk) 23:46, 20 March 2009 (UTC)

State table

If we're going to use the pictures from the Wolfram page, then the state table should use the same state symbols as the pictures. Otherwise, we should have pictures that use A, B or what ever state names we designate. Asmeurer (talk ♬ contribs) 05:21, 19 October 2008 (UTC)

I agree. 79.74.178.19 (talk) 23:30, 21 March 2009 (UTC)

The table in the 'description' section here is incomprehensible to anyone unfamiliar with formal accounts of Turing machines. The state table in the formal definition section of the Turing machine article on the other hand is self-explanatory and I suggest that a similar table be used here. --Brian Josephson (talk) 11:15, 26 November 2015 (UTC)

It turns out to be very easy to rewrite the description so as to be clear, and I have amended the article accordingly. --Brian Josephson (talk) 17:54, 26 November 2015 (UTC)

Misrepresentations in article

(I'm bringing this up now because it was drawn to my attention yesterday that this Wikipedia article continues to misrepresent my position despite this having been pointed out by others as long ago as January 2008, see the section above under "Discussion of objections is inadequate". Looking more closely I see it contains other misrepresentations as well.)

In the section headed "Proof of universality," second paragraph, there are two misrepresentations in the sentence "In their reply to Pratt, Wolfram Research and Alex Smith rejected Pratt's claim.[6][7][8][9]," one explicit and the other implicit.

The explicit misrepresentation is that neither of the two WRI articles cited, [6] by Wolfram and [7] by Todd Rowland, reject my claim, contrary to what the article states. [6] does not even mention my claim, while [7] acknowledges that "The issue mentioned by Vaughan Pratt was, in fact, one of the central points of discussion during the judging of the Wolfram 2,3 Turing Machine Research Prize" and admits that "Smith's use of non-repetitive infinite initial conditions is controversial" while defending the use as "a natural extension of current definitions which allow infinite repetitive initial conditions." Yes, the extension is natural, but in view of my claim, all one can infer from Rowland's defense is that some "natural extensions" can turn a non-universal machine into a universal one, which was my original objection. In no sense can this be considered a rejection.

The article should therefore clarify that neither [6] nor [7] constitute rejections of my claim.

The implicit misrepresentation is the article's failure to cite my responses to articles [8] and [9] by Smith. The implication is that I have not contested these rejections. In [8] Smith had clearly not yet come to grips with the problem in his proof, and my article at [9] explained what the problem was in more detail. In order not to fall afoul of WP:NPOV stating that "All Wikipedia articles and other encyclopedic content must be written from a neutral point of view, representing fairly, and as far as possible without bias, all significant views that have been published by reliable sources," the article should cite my response to [8].

Smith's reply at [9] defended his proof much better than his [8] by describing the kind of non-periodicity his proof relied on, which amounted to a variant of the pattern 101001000100001.... With such a pattern his simulator can run without restarting by reading this pattern. Of course what the pattern allows simulator A to do is to simulate simulator B (I forget whether there are 4 or 5 levels of simulation in the whole proof but together they stretch the argument out to some 50 pages) which does restart, by letting A read steadily along the tape restarting B each time it encounters a 1. (The actual tape described by Smith is more complicated than this in order to ease the simulator's task, but it should be straightforward to adapt Smith's argument to the above simpler pattern by using a simulator that supplies the additional complexity on its own without the additional assistance from the tape supplied by Smith's variant.)

Smith's argument is that a non-universal machine can generate this pattern, and that therefore the universality he proves for the whole system must reside in the 2,3 machine ultimately being simulated by all these other simulators. Were simulator B Smith's top-level simulator, my LBA argument would be sound, but the fact that simulator A does not restart has been taken by Smith, and accepted by WRI, as conferring immunity to the objection that I raised, and that (according to Rowland) WRI also raised initially.

Automata theory can be tricky sometimes. However transparent you might consider this additional layer of simulation, it is a fair question whether there can exist a class of automata that is non-universal when its input tape is initialized to a periodic pattern (plus a finite amount of input "in the middle") but becomes universal when the portion of the tape beyond the finite input is initialized to the pattern 101001000100001....

Intuitively one might expect to be able to extend my LBA argument to this situation. The problem with doing so is that my argument against Smith's approach becomes sufficiently complicated as to be hard to follow intuitively. To keep the overall argument simple, a better approach is to attack the new question raised by Smith's additional layer of simulation head-on. I do this at [10], as Pete St.John pointed out on this page in January 2008.

That this rebuttal of the only one of [6]-[9] to have any merit is omitted from the article is perhaps its most egregious omission, deserving of protest to the Wikipedia management. (As I said near the top of this page I've recused myself from editing the article for obvious reasons.) What I argue in my article (a posting to FOM, as are [6]-[9]) is that Smith's pattern is sufficient to permit simulation of a two-counter automaton, known to be universal, by a machine that without Smith's pattern is not universal.

To my knowledge this is the final word on Smith's argument, neither WRI nor Smith having raised any objection to my proof that the pattern 101001000100001... can convert a non-universal machine into a universal one, contrary to Smith's claim based on his argument that any pattern of this nature is too simple to do such a thing. --Vaughan Pratt (talk) 05:46, 20 March 2009 (UTC)

Well, even when you claim not to want to edit the article yourself, you pretend even worst: others to change it for you. You suggest Wikipedia to follow the discussion on a newsgroup and cite the answer to the answer to the answer as long as you remain the last to give the impression you are the only making sense around and with the final word. Personally I think this article is already doing a lot by citing a newsgroup post in which you have refuted a proof risking almost nothing probably trying to atract a lot of attention. You have the right to do so, but also the others to reply. Whether you or they are right or wrong is another issue not to come to pretend to bring up here for resolution. Btw, it seems you have changed your argument several times, that's low, specially when you pretend to let people believe that you have made your mind since the beginning on what is presumably wrong with the proof. You will probably unleash now here again your beautiful prose to refute me but despite being so smart you haven't get it: of course an init condition such as the one in question can convert a non-universal Turing machine into a universal one. Why the heck one would then use such an init condition as a generalization of what is allowed on the tape. You should at least read the bibliography on weak universality. That doesn't make the proof wrong or less valuable, it makes it even more interesting, because as you acknowledge the init configuration is still simple enough and represents a valid generalization that has enriched the discussion of what universality is or depends upon. 79.74.178.19 (talk) 00:29, 21 March 2009 (UTC)

And no, an LBA would not be converted by such an init condition, precisely because of the restarting issue. 79.74.178.19 (talk) 00:50, 21 March 2009 (UTC)

Any question whose answer requires a 50-page proof like Alex Smith's has to be considered a complicated one. It is clear from 79.74.178.19's rambling attacks above that he or she would have great difficulty with even a short argument like the one I used to pinpoint the fallacy in Smith's answer to Wolfram's question. Wikipedia is a magnet for such anonymous cranks. Unless they disclose their identity, like Smith, Wolfram, Rowland, and myself, there is no point in responding to them. --Vaughan Pratt (talk) 09:31, 21 March 2009 (UTC)

Vaughan Pratt is correct to raise his objection on the talk page for discussion. This is the appropriate way to go about it. --Pleasantville (talk) 12:03, 21 March 2009 (UTC)

Even when I agree with Pleasantville on Vaughan Pratt's right to come and raise any objection about the article content I do not agree on patronized attitudes to bias the opinion of poorly-informed people in order to fulfill personal goals (not because Wikipedians are stupid but simply because Wikipedians cannot be experts in every field). I am sure Pleasantville will then agree and perhaps tell Pratt that not disclosing an identity is nothing to be ashamed of and a common practice in Wikipedia and all over the Net precisely to avoid being part of personal attacks, among other reasons. I just want to keep myself away from Pratt's beautiful-wrapped-in-prose true ramblings attacks. Look, I think Pratt does not dispute my argument and claims that I am not capable of understanding his because he actually does not have any argument at all. His great discovery is that Wolfram called 'universal' what in the academic literature is called 'weak' or 'semi-weak universal' that Pratt clearly seems to be unaware of since the beginning (understandable coming from the old school in computer science). If Smith, Wolfram or whoever can be accused for something is perhaps for not having ascribed to this terminology, but Pratt's argument is completely void and non-sense once one understands the right context, the one that Smith and others have explained before. However Vaughan Pratt keeps on trying to convince himself and others, perhaps not with success but quite iteratively, something that might be seen as obscure in its motivations, perhaps just to avoid having to accept that he misinterpreted it since the beginning [and in the process he seemss to have tried to sound like making sense all the time by opting to make what might be seen as small variations of his original argument but desesperately trying to look for a good one]. I agree that Smith should perhaps make an extra effort to clarify this point, specially to non-specialists like Pratt who is certainly very well informed in many areas of computer science to which he has personally contributed, but not so in the field of small Turing machines and universality generalizations as it seems to be clear from his so called 'arguments'. Perhaps Vaughan Pratt should then generalize his refutation to the whole field and ask why all those tape encodings transforming all those non-universal machines (starting from a blank tape) into universal machines (not starting from a blank tape) are studied. Notice that the convention of accepting a blank tape rather than a non-blank tape is just so: a convention. The question of whether a machine is universal when starting with a non-blank tape is completely valid (assuming the tape encoding is not carrying the universal computation, as it is clearly not the case in Smith's proof, i.e. the tape construction for the 2 state 3 symbol Turing machine does not carry out alone the universal computation. The question is of course equivalent to the investigation of coupled machines, in this case Smith is proving that the original machine together with something like a Rabin automaton preparing the tape, which by itself is not universal, is universal). 79.74.178.19 (talk) 22:39, 21 March 2009 (UTC)

Can you please provide a reference for "weak" or "semi-weak" universality? Bobhearn (talk) —Preceding undated comment added 02:21, 22 March 2009 (UTC).

Sure, the subfield started with Minsky and Watanabe in the early 60's. To mention a few important papers: - Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215–240, November 1996. And more recently: - Damien Woods and Turlough Neary. Small semi-weakly universal Turing machines. In Jérome Durand-Lose and Maurice Margenstern, editors, Machines, Computations, and Universality (MCU), volume 4664 of LNCS, pages 306–323, Orléans, France, September 2007. Springer. which includes a list of many other references. 79.74.178.19 (talk) 10:24, 22 March 2009 (UTC)

Thank you. However, the terms "weak" and "semi-weak" seem to be used only by Woods and Neary -- it may well be good terminology, but it is hardly mainstream. It is also not used in Wolfram's NKS. Also Rogozhin's work, as far as I can tell, was only for "standard", not "weak" universality. And I am certain that Minsky had nothing whatsoever to do with weak universality. In fact, regarding "weakly universal" machines, he said "However, it needed to start with an infinite tape that was preprinted with a periodic pattern--which eliminated one of the states. Most researchers did not consider this to be a legitimate trick" (personal communication). In any case, Smith's construction is not the at all the same as the weakly or semi-weakly universal condition as defined by Neary and Woods, which allows only periodic input. See e.g. this FOM post by Neary and Woods: [11] . Bobhearn (talk) 17:38, 22 March 2009 (UTC)

I am not quite sure but I think it was Maurice Margenstern that came up with the "weak" and "semi-weak" universality terminology. I am quite sure however that it wasn't Neary and Woods and that these terms might have been used before by people simulating tag systems with cellular automata, simulation techniques developped by Minsky and Rogozhin, hence I think indirectly contributing to the field itself as 79.74.178.19 points out, however as Bobhearn points out Rogozhin machines were standard universal Turing machines. Watanabe's 5-symbol 8-state and 5-symbol 6-state universal Turing machines were "weakly universal" and were published in 1961 and yet called only "universal" even from the title so I would agree with Bobhearn that the terminology is not necessarely mainstream although it somewhat has spread out among the people that has taken over the field in academia, and different to the NKS point of view, which as far as I understand claims that non-blank tapes are more intuitive in the physical sense than blank-tape artificial constructions, in other terms a physical phenomena is more likely to be interacting with a noisy background rather than a "blank tape" (one has to remember that Stephen Wolfram is a physicist) and reach universality. However, even people in the field sometimes use "weak" and sometimes don't when talking about cellular automata, making the terminology even more fuzzy. On the other hand, it is true that the term weak has been used for periodic configurations but the point is that generalizations of these sort have been made before by weakening the standard model that required a blank tape, but that doesn't make them less universal, only universal under that initial configurations. Watanabee first "weak" universal machine was published in the Journal of ACM, 8(4):476–483 (1961) and he later improved his own results giving other smaller (weak) universal Turing machines. Requiemdirge (talk) 13:35, 26 March 2009 (UTC)

Yes, in fact Woods and Neary in their 2007 paper "The complexity of small universal Turing machines: a survey" credit Margenstern with the term "weakly universal." Watanabe's 5-symbol 8-state machine ((8,5) in the current terminology) was universal in the standard sense and therefore can be meaningfully paired with Bobrow and Minsky's (2,2) strict lower bound (unpublished) when bracketing the range containing small universal TM's in the standard sense. Watanabe's (6,5) machine, "slightly extended" as he put it, made the point that a periodic background allowed a reduction in the number of states; had both his machines been only weakly universal as you suggest, he would have had no reason to mention the (8,5) machine, and moreover the referees might have considered the point too minor to justify a whole JACM paper, especially given that Watanabe offered no practical application for his invention of a Turing machine whose tape required an infinite amount of work to precondition.

As I've said before I have no problem with weak universality (of this periodic kind) so long as it is recognized as a separate category of machine when judging size of small universal TMs. Given any class C of machines closed under modifications to its finite state control, if C contains no universal machine then it contains no weakly universal machine, since any such benefit derivable from a periodic background can be simulated by instead modifying the finite state control to simulate the periodic background. However the modification will in general increase the size of the machine, whence mixing categories is like allowing motorbikes in the Tour de France.

Smith's yet weaker notion allowing nonperiodic backgrounds such as 1101001000100001... does not have this property: there exist classes of machines closed under modifications to their finite state control which contain no universal machine, yet which contain a Smith-universal machine. I gave an example of such a class at [12], namely the class of read-only finite-state automata with two "whitelocked" heads (the heads must move oppositely when both are scanning a white square). This class was for the case where the background tape contains nothing else, e.g. if the input tape is separate, or if the input is determined solely by the initial position of the heads. If the input is on the same tape as the background then replace the "whitelock" condition with the requirement that the heads can never move so far apart that there are more than two black tape cells between them. (Requirements of this kind are intended to be "architectural" in the sense that they are enforced by "low-level" hardware which cannot be overridden by modifications to the finite state control, much as the requirement that a head be restricted to one direction of motion is architectural.)

The role of such classes is as a source of counterexamples to Smith's principle that two noninteracting nonuniversal mechanisms can't be combined to make a universal mechanism. Smith's nonperiodic background is nonuniversal in the sense that it can be written by a one-counter machine; these form a nonuniversal class. It is furthermore noninteracting in the sense that the task of writing the background is completed before the (2,3) machine is started, whence there can be none of the usual sort of concurrent activity associated with two collaborating LBA's or one-counter machines. The test for whether universality-creating collusion is nonetheless possible is to ask whether there is a nonuniversal class that becomes universal when allowed to consult such a tape. In the case of the pattern 1101001000100001... there is. --Vaughan Pratt (talk) 22:11, 16 April 2009 (UTC)

Since no one seems to be defending citations [6] and [7] as supporting this article's statement that WRI "rejected" my claim, would someone in a position to edit the article please remove both them and the statement that WRI has rejected my claim? The point of citations is to make it possible to verify whether they support the statement they're attached to, and in this case it is easily verified that they don't. --Vaughan Pratt (talk) 21:51, 4 April 2009 (UTC)

I tried to fix the problem. I am not familiar with the problem and acted merely on what I saw in the FOM archive, without going too much into the details, so it seems quite possible that someone else finds a better solution. --Hans Adler (talk) 21:06, 30 April 2009 (UTC)

Wolfram people and Smith himself do have rejected your claims (to Vaughan Pratt)! And you have even given up on your main LBA argument to the counter-argument that a LBA would need to be hand restarted unlike Wolfram-Smith's 2,3 TM, so the universality of the system is not in jeopardy because it would make a LBA universal as you initially said. So I honestly don't understand your position at coming here and still once again defend yourself to try to hide that you were wrong, simply wrong, by adding more prose to your already obscure non-sense arguments. You wanted all this extra public attention to promote yourself, now I politely ask you to face the consequences and now let people know that you were wrong jumping to conclusions too soon. Of course there are machines that with an extra color, an extra state, or a different init tape would turn a non-universal machine into a universal one, you are still fooling yourself repeating all the time the same overused argument of yours but ignoring the fact that there is a legitimate whole branch of study of what has been called weak-universal machines (it is just a name, it doesn't mean it is a real weaker form of universality). Your counterexamples are not counterexamples of anything, are examples of interesting coupling non-universal machines that as systems are legitimately universal. With all respect, you just have to be a little bit smarter to open your mind and see the contribution of Smith as the simplest universal system found to be universal. It might have needed a little further explanation from Wolfram's group to the media to understand these interesting subtle details , but you better try to explain this to the media and see if they get something. The fact is that the 2,3 system with that init condition (as stated so early in Smith's proof and several times explained) *is* universal in the most legitimate sense (no universal definition of universality exists, but with those which exist, the use of Smith's universality is fully compatible with). Requiemdirge (talk) 05:11, 21 February 2010 (UTC)

"Of course there are machines that with an extra color, an extra state, or a different init tape would turn a non-universal machine into a universal one" That is exactly Pratt's point though? That this 2,3 machine is not universal without the assistance of the start condition. And allowing an infinite, nonperiodic pattern is sufficient to grant universality to other simple machines such as the examples given by Pratt. 192.183.214.163 (talk) 23:30, 21 April 2023 (UTC)

This talk page recommended in Notices of the AMS

In an article about undecidability in this month's issue of the Notices of the American Mathematical Society, Chaim Goodman-Strauss recommends this talk page as introduction to the controversy about the proof:

The interested reader can ask for no better starting point than the talk page of the relevant Wikipedia article [46], following the many outward links from there.

Regards, HaeB (talk) 07:36, 9 March 2010 (UTC)

Amusingly, I wonder if this is the first academic article citing a wikipedia talk page as a reference! Surely one of the first! But seriously, this seems like just about the best place to begin for understanding the issues and viewpoints surrounding this construction. C Goodman-Strauss (talk) 14:27, 8 August 2011 (UTC)