Talk:Alex Smith (The Simplest Universal Computer Proof contest winner)

From Wikipedia, the free encyclopedia

Alex Smith (The Simplest Universal Computer Proof contest winner) is within the scope of WikiProject Mathematics Competitions, a collaboration created to improve and create articles related to mathematics competitions. Also see the project page and assessment table. Note that you do not have to edit the table every time an article's rating is changed; this is done automatically every few days by a bot.

When rating this article, you probably should leave a comment.
Stub This article has been rated as stub-Class on the assessment scale.
Low This article has been rated as low-importance on the importance scale.
This article is within the scope of WikiProject Biography. For more information, visit the project page.
Biography Portal
Stub This article has been rated as Stub-Class on the project's quality scale. [FAQ]
This article is supported by the Science and academia work group.


[edit] Controversy

I've written a synopis of the Wolfram (2,3) controversy, as I understand it, in user space here. Comments and rebuttals are welcome. Pete St.John 17:51, 1 November 2007 (UTC)

or, alternatively, we can just have an edit-war (sigh). It seems both the pro-Wolfram and anti-Wolfram camps are averse to diplomacy. But really I think this can settle down to mere scholarship in the coming days. Pete St.John —Preceding comment was added at 15:09, 2 November 2007 (UTC)
I'll try and maintain ongoing attempts at acceptable wording for use in articles, here in user space. Pete St.John 16:32, 2 November 2007 (UTC)
It looks like one of the citation links you made is broken. (See footnotes.) I don't know how to fix that style of citation. --Pleasantville 17:45, 2 November 2007 (UTC)
thanks, yes, besides mispelling "controversy" alot, I've bungled that citation, I was just fixing it at the (2,3) page. I'll go fix it everywhere. Pete St.John 18:12, 2 November 2007 (UTC)

[edit] revert re: controversy

Requiemdirge, I'm sorry to revert your last edit. But:

  • 1. There really is controversy, if only proven by the edit war. So mentioning two sides seems pertinent.
  • 2. It's a newsy topical item (because of Slashdot) and things are changing rapidly (witness ourselves) so warning the reader is appropriate and has precedent in wiki.
  • 3. You admit in your own version that Smith's paper relaxes, or generalizes, the defintion of "universal". That seems to be the main issue, not the technical correctness of the paper. But as a consequence, calling the press release "wrong" (as I did) for not stating the revised defintion of the term is defensible.
  • So I think my previous version somewhat better reflects the current state of the controversy than your replacement. I think in all fairness it's reasonable, in contested matters, to use the discussion page (as you have elsewhere, thanks). It's difficult to keep up in this case.
  • I'm seeking confirmation that Pratt's own opinion is not that Smith's paper is incorrect, but that redefining the term "Universal" to mean "Possibly infinite inputs" would be a bad idea. If Wolfram's press release had said "Universal, with relaxed conditions to allow for certain infinite input sets" or "Universal, of Type Smith-Wolfram" then there would have been no controversy. Pete St.John 21:41, 2 November 2007 (UTC)

Pete St.John, please see my comments on the 2,3 Wolfram's TM page. I do not agree with this but I will be patient to get some feedback. Your statements are wrong from several points of view. I thank your impartiality, though. The problem are not the initial conditions. The term "universal" as it is has been used before in the same sense and nobody call it different (except for some particular cases). Martin Davis himself has 2 definitions, and he does not name them differently. The main reason is that there is no single and widely accepted definition. Universality is a very intuitive concept which of course needs to fulfill strong requirements such as constructing the initial condition in a non-universal way, as in Smith's proof (as Pratt has agreed) is. But the procedure, as Pratt claims, would make a LBA a universal automata, what some traditional computer scientists are not willing to accept. So neither Wolfram nor the press were wrong and Smith's proof only suffers of renewing the discussion of universality again. Universality used for the prize was pretty clear since it clearly points out to previous work by Wolfram, including the rule 110 universality proof.

Check the following links from the prize website: First in techincal details it says (http://www.wolframscience.com/prizes/tm23/faqs.html): "What definition of universality are you using? The standard one appropriate for unbounded computations. It's the same as in the NKS book. See Technical Details."

and the technical details say (http://www.wolframscience.com/prizes/tm23/technicaldetails.html):

"Like many fundamental concepts, universality is in some ways clear and straightforward to define, and in other ways almost arbitrarily difficult to pin down. The general idea is that a system is universal if it can be "programmed" to emulate any other system. The difficulty comes in understanding what kinds of programming should be allowed. For if too much goes into the construction of the program, then computation can be done there, rather than in the system itself.

One common definition requires that the encoding of input for the universal system, and the decoding of its output, must both be done by a computation that always halts after a finite number of steps. One difficulty with this definition is that it may be too restrictive for infinite tapes. It is not clear, for instance, whether one should allow a Thue-Morse sequence in the initial conditions.

In most cases, it should nevertheless be fairly obvious whether something should be considered a valid encoding for a universal system. But in general there is no firmly established criterion. (For more information, see pages 722 and 1126 of the NKS book.)"

Alex Smith construction is precisely of the type of the Thue-Morse sequence: http://en.wikipedia.org/wiki/Thue-Morse_sequence

As bibliography they included:

  • There is a large amount of relevant material in A New Kind of Science.
  • The papers below by Delvenne,Kůrka,Blondel and Sutner contain recent attempts to formalize the concept of universality for ongoing computational systems.

Maybe this will help to make it clearer and that would be great. I think you are very sensible and smart so we are close to an agreement in benefit of the Wikipedia readers. Thanks. -- Requiemdirge 22:35, 2 November 2007 (UTC)


[edit]revert re: controversy PeterStJohn, I'm sorry to revert your last edit, I waited as much as you to apply my changes and look for your feedback. See current discussion above and the discussion on the Wolfram's 2 3 Turing machine. -- Requiemdirge 16:40, 3 November 2007 (UTC)

That's Ok, I belive you are being patient too. I tried to cool down over the weekend; the double whammy of controversies in 'two math topics at once, flabbergasted me (Erdos Numbers). Right now I'm going with a plan along the lines of flagging the articles as "Active Discussion", and punting my effort to actualy synopsize the debate, which effort seems appreciated by no one. Pete St.John 18:38, 5 November 2007 (UTC)