Wolfram's 2,3 Turing Machine Is Universal!
Yao Ziyuan
News Release
Wolfram's 2,3 Turing Machine Is Universal!
October 24, 2007--Wolfram Research and Stephen Wolfram today announced
that 20-year-old Alex Smith of Birmingham, UK has won the US $25,000
Wolfram 2,3 Turing Machine Research Prize.
In his 2002 book A New Kind of Science, Stephen Wolfram hypothesized
that a particular abstract Turing machine might be the simplest system
of its type capable of acting as a universal computer.
In May 2007, the Wolfram 2,3 Turing Machine Research Prize was
established to be awarded to the first person or group to prove either
that Wolfram's Turing machine is universal, or that it is not.
Alex Smith was able to demonstrate--with a 40-page proof--that
Wolfram's Turing machine is in fact universal.
This result ends a half-century quest to find the simplest universal
Turing machine.
It demonstrates that a remarkably simple system can perform any
computation that can be done by any computer.
It also provides important further evidence for Wolfram's general
Principle of Computational Equivalence--a central hypothesis developed
in A New Kind of Science.
"I had no idea how long it would take for the prize to be won," said
Stephen Wolfram. "It could have taken a year, a decade, or a century.
I'm thrilled it was so quick. It's an impressive piece of work."
The immediate implications of the result are primarily scientific.
But potential future implications include the possibility of using
Wolfram's 2,3 Turing machine to construct a computer operating at a
molecular scale.
"I saw the prize problem primarily as a puzzle," said Alex Smith. "At
first, I didn't think the Turing machine would be universal. But then
I found a way to show that it is."
Smith is an undergraduate studying electronic and computer engineering
at the University of Birmingham, UK. He grew up in Birmingham, and was
an alternate for the UK International Mathematical Olympiad team.
Smith's proof will be published in the journal Complex Systems.
An official prize ceremony is being planned for November at Bletchley
Park, UK, the site of Alan Turing's wartime work.
The prize was adjudicated by a distinguished committee consisting of
Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, Yuri
Matiyasevich, Marvin Minsky, Dana Scott, and Stephen Wolfram.
For additional information, see the original media release announcing
the prize, or the prize website.
For Stephen Wolfram's personal reaction to the prize, see his blog
post.
The prize is part of Wolfram Research's ongoing commitment to the
support of scientific research and education. In addition to its
acclaimed Mathematica software system, Wolfram Research is also
responsible for MathWorld, the world's #1 mathematics information
website, as well as the new Wolfram Demonstrations Project. Wolfram
Research also sponsors the prestigious annual NKS Summer School and
the Wolfram Science Conference.
Dweeb
>... Stephen Wolfram today announced
> that 20-year-old Alex Smith of Birmingham, UK has won
> established to be awarded to the first person or group to prove either
> that Wolfram's Turing machine is universal, or that it is not.
> Smith is an undergraduate studying electronic and computer engineering
> Smith's proof will be published in the journal Complex Systems.
So, has it passed peer review yet?
Phil Carmody
Yes, in that Wolfram and his croneys have perused version 1,
found it somewhat lacking, and then approved the revised version.
The independence of the committee which reviewed it may
also be something that could be questioned. Wolfram himself
of course, despite having to pay out for the prize, wanted
the proof to be correct, but I'm not sure how much of a
presence he had in the peer review process.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
gjed...@gmail.com
wrote:
Is ANKOS any use? Has it led to any useful contributions to science?
( and I mean specifically, ANKOS itself, not Cellular Automata in
general )
Wolfram seems, to me at least, to believe his work is hugely important
(even more important than James Harris' ? ). I'm not qualified to
judge whether or not he's a crackpot, though clearly his success in
other areas would mark him as if very unusual crackpot if that were
the case. I genuinely want to know if anything significant has been
discovered due to ANKOS that otherwise might not have been.
Jesse.N...@gmail.com
> > > So, has it passed peer review yet?
Here is the list of prize committee members.
Lenore Blum
Greg Chaitin
Martin Davis
Ron Graham
Yuri Matiyasevich
Marvin Minsky
Dana Scott
Stephen Wolfram
Apparently all of these people agree that the proof is correct. The
paper is also available now on the website, and has Perl and
Mathematica implementations of the compilers used in the proof.
Also there is a Mathematica notebook that illustrates the proof
available on the site here: http://www.wolframscience.com/prizes/tm23/TM23Emulations.nb
This would need Mathematica, but you can also look at it with the
Player: http://www.wolfram.com/products/player/download.cgi
In the Mathematica form, the code for the proof doesn't look super
complicated.It's obviously straight out of the paper and probably
could be simplified even more sometime.
One good question about this is if really simple turing machines are
the practical answer to create real computers. I don't know. It
certainly seems that the kinds of materials that can be used by us
becomes larger as more is developed in this area of simple programs.
Phil Carmody
His principle of computational equivalence is more a mathematical
result than a scientific one. As such, I don't think it can do much
to influence the rest of science. What did science do when Gödel
published his incompleteness result? Probably chatted about it over
a coffee in the break room, and then went back to doing the same
science the same way as they did before.
He's certainly not a crank by the standards set on sci.{maths,physics},
but he does perhaps suffer from being a little too close to what
he's working on to be able to see its boundaries. I don't think
his claims are any wilder than what I've seen in any of the coffee-
table science books by well known respected scientists. They give you
half a book of interesting facts, and when you're softened up they
feed you their pet theory, hoping you take it on board as unquestioningly
as you did all the obvious stuff earlier in the book.
tommy1729
> journal Complex Systems.
> > > > So, has it passed peer review yet?
>
> Here is the list of prize committee members.
>
> Lenore Blum
> Greg Chaitin
> Martin Davis
> Ron Graham
> Yuri Matiyasevich
!!!!
if yuri says the proof is correct , it is probably correct...
Regards
tommy1729
Riemann, Matheyasevich and Wiles forever
David Bernier
Wolfram is the founding editor of ``Complex Systems". ANKOS was
self-published.
Doing computer experiments predates ANKOS. I think the universality of
Wolfram's 2,3 Turing Machine is an interesting result [ just my opinion]
. I read that the proof
submitted and accepted initializes the tape using a compiler (or translator)
for universal computation with another TM known to be universal.
cf.:
"There's quite a bit of subtlety. Early definitions of universality [...]"
from:
< http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html >.
The 2,3 TM has no Halt state, but the neither has the game of Life.
I tried to rewrite the TM description given by Wolfram in a format that is
common in the literature on the Busy Beaver problem.
I like Heiner Marxen's TM Glossary from here:
< http://www.drb.insel.de/~heiner/BB/glossary.html >
He has lots of TM transition tables...
(Wolfram's 2-state, 3-symbol TM):
on A read 0: B1R /*** 'B1R' means (i) write a '1' now, (ii) go Right
one square and lastly (iii) change to state B ***/
on A read 1: A2L
on A read 2: A1L
on B read 0: A2L
on B read 1: B2R
on B read 2: A0R
Evolution starting on all-zero tape:
------------------------------------------
0
10
12
022
122
102
101
111
1120
1122
1112
1212
02212
12212
10212
10112
11112
11212
11222
112200 /*** 2 trailing zeros appear because the read/write head
has been over them before ***/
1122010 /*** the scanned square is not marked or in a special
position ***/
1122012
1122022
1122122
1122102
1122101
1122111
11221120
11221122
11221112
11221212
11222212
11212212
11112212
12112212
022112212
[...]
This conforms to the figure on the left side of
<
http://www.wolframscience.com/prizes/tm23/Wolfram23TuringMachinePrize.pdf >
where the colours white, yellow and orange are used for the symbols
'0', '1' and '2' respectively.
The ! and "upside-down" ! show the TM's state plus the square under the
TM's read/write head.
As a bonus, Turing's 1936 paper is here:
< http://www.wolframscience.com/prizes/tm23/images/Turing.pdf >
David Bernier
Ben Rudiak-Gould
> Wolfram seems, to me at least, to believe his work is hugely important
> (even more important than James Harris' ? ). I'm not qualified to
> judge whether or not he's a crackpot, though clearly his success in
> other areas would mark him as if very unusual crackpot if that were
> the case.
His work is not important. I'd tend to classify him as a crank. He's
arrogant (as you noted) and ignorant (of the prior art). I liked this review
of the book:
http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/
> I genuinely want to know if anything significant has been
> discovered due to ANKOS that otherwise might not have been.
Not in the sense of ANKOS contributing materially to the discovery, since it
didn't contribute anything to the field of computer science. Someone might
have read it and been inspired to do research they wouldn't otherwise have
done, and discovered something that wouldn't otherwise have been discovered.
I don't know of any example of that happening, and it could just as well
happen with The Da Vinci Code.
ANKOS seems to be a lot like memetics. My impression (which may be totally
wrong) is that they've both attracted a lot of people who want to do
research but aren't part of the academic system and probably couldn't get
hired in it. They set up their own journals and conferences and do research
as a hobby. They basically have the field to themselves because it's not
really a new field of study; they're duplicating work the real academics
have already done. I don't know if this has a name ("indie science"?) or if
it's been studied (by, er, real sociologists), or if it's all in my mind.
In any event, I'm sure this proof is real and that it's a new result. It's
not a very important result, since lots of simple computationally universal
systems are already known. This one just happens to be a cellular automaton
of the kind that Wolfram is keenly interested in for some reason. I don't
think it would have attracted much interest among serious researchers if not
for the prize money.
My favorite computationally universal automaton is SMETANA:
http://catseye.tc/projects/smetana/
Someone explicitly constructed a Turing machine in it a few years ago. You
need an infinite (algorithmically generated) program for this, though, since
a finite program can only be in finitely many states. Malbolge has also been
shown universal with caveats:
http://www.lscheffer.com/malbolge.shtml
And Conway's Life was proven universal ages ago; I think all of those are
more interesting than this new result. By the way, if you haven't been
following the progress in Life technology over the last couple decades,
download Golly (golly.sourceforge.net) and play with the included examples.
Now /that's/ cool indie research.
-- Ben
OwlHoot
> > > > > > Smith's proof will be published in the
> > journal Complex Systems.
> > > > > So, has it passed peer review yet?
>
> > Here is the list of prize committee members.
>
> > Lenore Blum
> > Greg Chaitin
> > Martin Davis
> > Ron Graham
> > Yuri Matiyasevich
>
> !!!!
>
> if yuri says the proof is correct , it is probably correct...
I must admit, Tommy, that was my first thought exactly.
Chaitin too (and doubtless one or two of the others,
although I haven't heard of them.)
(and whoever gave you a single star for that post is a tosser,
even if a few of your other low star ratings are well deserved)
Cheers
John R Ramsden
P.S. What's the betting I'll get a one star rating for this post..
Phil Carmody
> On Oct 25, 12:26 pm, tommy1729 <tommy1...@gmail.com> wrote:
> > > > > > > Smith's proof will be published in the
> > > journal Complex Systems.
> > > > > > So, has it passed peer review yet?
> >
> > > Here is the list of prize committee members.
> >
> > > Lenore Blum
> > > Greg Chaitin
> > > Martin Davis
> > > Ron Graham
> > > Yuri Matiyasevich
> >
> > !!!!
> >
> > if yuri says the proof is correct , it is probably correct...
>
> I must admit, Tommy, that was my first thought exactly.
I thought it about Graham and Minsky too.
Minsky's the one of the godfathers of AI, being the father of neural nets.
Graham et al.'s /Concrete Mathematics/ seems to be second only
to TAoCP when it comes to frequency of book recommendations
in the fields I play with,. (Where et al. includes author of TAoCP.)
Assuming Blum is one of the two Blums in BBS, then he punches with
the heavyweights too.
> Chaitin too (and doubtless one or two of the others,
> although I haven't heard of them.)
But isn't Chaitin adopting the crank mantle with his Omega
obsession more than Wolfram and his CA?
> P.S. What's the betting I'll get a one star rating for this post..
No-one who uses usenet the proper way would rate it at all.
G. Frege
<thefatphi...@yahoo.co.uk> wrote:
>>
>> Chaitin too (and doubtless one or two of the others,
>> although I haven't heard of them.)
>>
> But isn't Chaitin adopting the crank mantle with his Omega
> obsession more than Wolfram and his CA?
>
This may be the case (or not), but he certainly know his stuff (i.e.
TMs).
So if these guys have checked the proof, it might very well be correct.
F.
--
E-mail: info<at>simple-line<dot>de
tommy1729
but the difference is the 2,3 is not only universal,
but the smallest universal !
not ?
and wouldnt the property of being the smallest make it more intresting and important than the others ?
not ?
regards
tommy1729
Ivar Rosquist
> Minsky's the one of the godfathers of AI, being the father of neural
> nets.
And possibly the main reason that underpins the current lack of
prestige of AI as a scientific discipline. It was him, together with a
bunch of less well-known AI practitioners, the driving force behind the
exaggerated projections for the AI field put forth during the 60s and
70s. They probably got intellectually inebriated with the spectacular
initial successes of the field, without realizing that they wer in fact
solving very easy problems. Forty years down the road computers are much
faster than they used to be, but only slightly less stupid.
Ivar Rosquist
> Wolfram seems, to me at least, to believe his work is hugely important
> (even more important than James Harris' ? ). I'm not qualified to judge
> whether or not he's a crackpot, though clearly his success in other
> areas would mark him as if very unusual crackpot if that were the case.
> I genuinely want to know if anything significant has been discovered due
> to ANKOS that otherwise might not have been.
Wolfram is not a crank. He probably is a very bitter man though,
despite his business success with Mathematica. In his teens, he was
groomed to become the next Einstein, and not only has he not lived up to
expectations but, as a scientist, he has produced precious little. His
cellular automata work from the early 80s was cute, and did contain some
decent science; but it has by no means revolutionized the field. In fact,
I remember a conversation with a respected dynamicist about 15 years ago,
in which he said that Wolfram's work in this respect was competent, but
not any better than that produced by a decent graduate student in the
field.
Wolfram's ANKOS, for all I know, has been all but ignored by the
scientific world, on the grounds that anything good that it contains is
not original (despite Wolfram's best efforts to claim the opposite) and
anything original that it contains is not all that good (unless you are
into pretty pictures.)
Another aspect to Wolfram is that every single individual I have
met who had the chance to interact with him at a professional level have
been unable to come up with a single flattering word about him as a
person.
Gerry Myerson
Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> OwlHoot <raven...@googlemail.com> writes:
> > On Oct 25, 12:26 pm, tommy1729 <tommy1...@gmail.com> wrote:
> > > > > > > > Smith's proof will be published in the
> > > > journal Complex Systems.
> > > > > > > So, has it passed peer review yet?
> > >
> > > > Here is the list of prize committee members.
> > >
> > > > Lenore Blum
> > > > Greg Chaitin
> > > > Martin Davis
> > > > Ron Graham
> > > > Yuri Matiyasevich
> > >
> > > !!!!
> > >
> > > if yuri says the proof is correct , it is probably correct...
> >
> > I must admit, Tommy, that was my first thought exactly.
>
> I thought it about Graham and Minsky too.
>
> Minsky's the one of the godfathers of AI, being the father of neural nets.
>
> Graham et al.'s /Concrete Mathematics/ seems to be second only
> to TAoCP when it comes to frequency of book recommendations
> in the fields I play with,. (Where et al. includes author of TAoCP.)
>
> Assuming Blum is one of the two Blums in BBS, then he punches with
> the heavyweights too.
She.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Phil Carmody
As far as I understand it, it wasn't MM who produced the impotent
theories, it was he who blasted the impotent theories (perceptrons)
out of the water, and then replaced them with things that actually
worked (at the limited set of problems they were being thrown at).
I'm not close enough to the field to know accurate your painting
of the picture is though, it's certainly not in contradiction with
what I am aware of.
Ivar Rosquist
Even in that respect his influence is now acknowledged as having
been a determinant factor in the slowdown in neural networks research.
His conclusions applied to a simple class of preceptrons, and his
unwarranted (and ultimately incorrect) generalization to more complex
classes led people to believe that research on neural networks was a
waste of time - which in the end perhaps it was, but not for his reasons.
Quite frankly, anything espoused by Minsky is suspicious in my
books.