Slashdot Mirror

← Back to Stories (view on slashdot.org)

Wolfram's 2,3 Turing Machine Is Universal!

Posted by CmdrTaco on from the theory-flashbacks dept.

Rik702 writes "Wolframscience.com have announced that an undergraduate from Birmingham, UK has proved Wolfram's 2,3 Turing Machine is universal." You can read a pdf of the proof as well as some related coverage.

16 of 288 comments (clear)

  1. A New Kind of Science by CRCulver · · Score: 3, Interesting

    I remember the discussion here five years ago when Wolfram released his book A New Kind of Science . Many claimed that it was hogwash and (as it was apparently not peer-reviewed) irresponsible, but at least the movement he has tried to spark is finally showing some results.

    1. Re:A New Kind of Science by Anonymous Coward · · Score: 2, Interesting

      Another little-known fact is that Wolfram was just one of several people who initially coded Mathematica. He decided one day to take all the code, form a company on his own, and engage in expensive lawsuits with all of his former collaborators to gain ownership of the code.
      It (Originally SMP) was also written on Caltech equipment and Caltech sued Wolfram; hence Caltech does not pay for any copy of Mathematica they run.
    2. Re:A New Kind of Science by Hijacked+Public · · Score: 5, Interesting

      You don't read a lot of serious science here because this isn't the place for it.

      Every so often a fairly specialized technical discussion will crop up and even to people like me, who are casually interested, it is obvious that people who are serious about the subject are posting. They don't write full blown journal quality posts because a) see above, and b) as you correctly point out, Slashdot's demographic on the whole doesn't have the higher level knowledge necessary to understand them.

      But that doesn't mean there isn't an interesting discussion going on. On the contrary, there are good opportunities to interact with serious people you would otherwise never be able to access. If you can effectively ignore the "I got wireless working under Linux so I know everything" mentality anyway.

      Along the lines of the RIAA submissions from NewYorkCountryLawyer. How many attorneys who actively defend against RIAA lawsuits as their primary practice do you meet in a day?

      --
      "Sacrifice for the good of The State" - The State
    3. Re:A New Kind of Science by bmajik · · Score: 2, Interesting

      I'm about 1/4 of the way through the NKS book and I find it absolutely fascinating. It "inspired" me to create some basic 2-color nearest-neighbor automata (you can get through university without studying this sort of thing, btw (!)) and I found the material very approachably written. I'm sure you could cover the material with far fewer pages if you expected the reader to have pencil/paper (or a debugger?), and didn't have so many pretty images, but i thought that the comparison of automata-generated shells to actual aquatic life was the most damning evidence that what wolfram was postulating was fundamentally worth thinking about.

      That he may or may not be the first person to suggest anything in his book is not interesting to me; that his book was cheap enough (i got it about a year ago at a bargain table) and accessible enough (it's in my "bathroom reading" shelf) that I'm thinking and learning things I otherwise wouldn't be makes it sufficiently valuable IMO.

      Efforts to cast the book as some renegade peice of science that "conventional academia" won't publish are mostly drama. The guy's writing style is a bit dramatic at times (i seem to recall him using the same linking phrase to go from "thing that sounds implausible" to "i think it's actually true" in nearly every section of every chapter.) but that doesn't get in the way of it being a read that makes me think about it for hours after i've put it down.

      --
      My opinions are my own, and do not necessarily represent those of my employer.
    4. Re:A New Kind of Science by machinelou · · Score: 2, Interesting

      Off topic but.. You couldn't be more wrong. Lab animals could not be conditioned in the way behaviorism predicted? Really?

      First of all, behaviorism and conditioning are not theories in the sense that nobody sat in a chair, came up with stuff off the top of their head, and then tried to prove it. Rather, they were descriptions of the results of experiments THAT HAD ALREADY BEEN CONDUCTED. Hence, reinforcement? Yea, it works. Punishment? You bet. Stimulus discrimination, extinction, schedule effects.. Yea. The descriptions were also somewhat special because they were related to principles that were general enough to span species (humans, rats, mice, pigeons, dogs, birds, sea lions, dolphins, fish, insects) and responses (language, thinking, level pushing, drug abuse/self-administration, 2 and 3-point shots attempted by players on NCAA basketball team, imprinting by birds, self-injury). Basically, it's much harder to list things that animals and people do that can't be described using behavioral principles than things that can.

      Second, behavioral approaches have become the de-facto standard in many areas. Functional analysis, a behavioral technique to determine why people engage in behavior, was written into law (IDEA, the individuals with disabilities and education act). Know anyone with a child who has developmental disabilities? Chances are, their child works or has worked with a behavior analyst. And, as you alluded to, behavioral preparations are widely used by neuropsychologists to study the BRAINS of intact organisms (ironic?)!

      If anything, it seems like Chomsky's theories have died. I know people who have graduated from linguistics departments only to then become Board Certified Behavior Analysts and practice behavior analysis because its presents very practical way to assess and teach language to children. The only thing I'm confused about is why you (and many, many others) still think the opposite.

      Need citations? Google the Journal of Applied Behavior Analysis or the Journal of the Experimental Analysis of Behavior. There are several other good journals, but these are the best and they're available free online.

  2. Science is forever by Weaselmancer · · Score: 2, Interesting

    That all depends on your definition of accomplishment, now doesn't it.

    Yes it does, but that runs both ways.

    A scientific proof is something that gets to contribute to society forever. Your examples only help for a lifetime. Look around the room you're in and see how many examples of Pythagoras' theorem you can find.

    Dead and buried 2500 years, and he's still contributing to our society. Even makes Mother Theresa look a little weak, IMO.

    --
    Weaselmancer
    rediculous.
  3. if you like this... by kisrael · · Score: 4, Interesting

    yeah, I know I'm pimping my own site, sosumi...
    Anyway, I was thinking about 1D CA the other week, and realized one of the attractions was that you plot time and make it 2D... but there's no particular reason you can't do the same thing to a 2D CA, like Life...
    http://kisrael.com/2007/10/21/ is the result, ethereal blue sculptures made by plotting 2D Life with Time as a physical dimension.
    I'm not sure if I learned a lot or proved anything, but it *is* pretty...

    --
    SO YOU'RE GOING TO DIE: The Comic for Dealing with Death
  4. Re:An Undergrad? by stranger_to_himself · · Score: 3, Interesting

    I am. Not because I don't think they're capable, but when I was an undergrad we just learned things and then repeated them. It took me a long time to believe I could contribute anything meaningful to my subject. I also think it's notable that he was a computer science undergrad, and not reading mathematics. We need to encourage undergrads in math to think more, then maybe we'll see more of this kind of thing.

  5. Automat size by ledvinap · · Score: 2, Interesting

    Can anyone estimate how long tape is needed to do some real-world computation? Like adding/multiplying two (n-bit) integers?

  6. Question for Turing Geeks. by mightybaldking · · Score: 2, Interesting

    At the wolfram site, he shows the rules for this 2,3 machine (two state, three color).
    The two states being up and down, and the colors being white, yellow and orange.

    Is there an equivalent 3,2 machine - {up, down, charm} and {white, black}?
    His machine:
    {S,C) -> {S,C,O}
    {
    {D, O} -> {D, Y, L},
    {D, Y} -> {D, O, L},
    {D, W} -> {U, Y, R},
    {U, O} -> {D, W, R},
    {U, Y} -> {U, O, R},
    {U, W} -> {D, O, L}
    }

    3,2 machine
    {
    {c, w} -> {u, w, L},
    {u, w} -> {c, w, L},
    {d, w} -> {u, b, R},
    {c, b} -> {d, w, R},
    {u, b} -> {c, b, R},
    {d, b} -> {c, b, L}
    }

    Are these equivalent?

  7. Other simple universal machines by ortholattice · · Score: 2, Interesting
    I had thought that the Game of Life was one of the simplest possible, although someone else will have to clarify how it compares. I think Life was proved universal a number of years ago, and an actual implementation is here: Life Universal Computer.

    There are also universal machines possible with S-K combinators, which in a sense is also one of the simplest if not the simplest, with only two possible commands: S and K. (I guess it depends on how simplicity is measured.) Amazingly, the shortest universal machine found so far with SK combinators has 272 bits, compared to 5495 bits for Roger Penrose's universal Turning machine built from the original Turing machine and 268,096 cells for the Life version.

    I couldn't quite glean the size of a universal machine implemented with Wolfram's 2,3 cellular automaton, but I would imagine it would be very large.

  8. A flaw in the argument:no *HALT*:resubmit for $25k by viking80 · · Score: 3, Interesting

    The original Universal Turing machine was defined to end with the *HALT* instruction. The 2,3 Turing Machine can not halt, and is therefore not universal. It appears that Wolfram conceded that computers today dont really halt, they just keep ticking after the program is complete, so they accepted the 2,3 machine as universal, and the proof as completed.

    Maybe someone should submit the same proof, concluding that it is *not* a universal Turing machine, and claim the $25k.

    --
    don't cut it off www.mgmbill.org
  9. Re:Uhh, what? by Eponymous+Bastard · · Score: 3, Interesting

    Became depressed because of:
    - Estrogen treatment: gained weight, physical changes, possibly psychological changes too.
    - Lost his security clearance so couldn't work on any of the crypto/high security work he did. (spies usually tried to subvert homosexual and/or prosecuted people who were dissatisfied with their government). Half of that work couldn't be published either which left him in a bad position as an academic.
    - "most of the scientific community shunned his work due to some personal habits." as the GP said. Guess which habits this means

    Probably caused a lot of rifts in his personal life too.

    BTW, the inspiration for Apple computers' logo was actually Newton's apple. Older logos have a picture of Newton sitting under a tree with a glowing apple above him. It is unknown how much Turing influenced it. People often mention the rainbow apple in this regard.

  10. Not What It Seems? by Jane+Q.+Public · · Score: 2, Interesting

    TFA (the first link) claimed that this was a proof of the "simplest" Turing machine. However, as I understand what was written, and without reading the whole proof, it appears that this is not actually the case. What he proved was that his chosen candidate Turing machine, among "2,985,984 possible 2,3 machines", was universal. That does not mean that his machine is the simplest possible, only that it is among the simplest known CATEGORY of such machines (2,3). There may well be some kind of example of one that is, in a significant way, simpler.

  11. Bits per symbol by Kaenneth · · Score: 1, Interesting

    I was discussing that idea with a co-worker the other day.

    All the ramifications of using 8 bits for a byte.

    A 32 bit addressing system with an 8 bit byte can addresses about 4 billion sets of 8 bits, or 32 gibibits.

    If you just used 16 bits in a byte, you could double the useable storage capacity of a 32 bit address model.

    Advantage, a C 'char' would be able to hold a 16 bit unicode character, or a CD audio sample, or half a screen coordinate.

    A 32 bit byte could hold a pointer to it's own kind, or a 24 bit color plus alpha channel, or a full size Unicode character (For hieroglyphics or Klingon characters) in one memory location, while giving quick access to 16 gibioctets of RAM.

    Complex CPU instructions could be fixed-width single large bytes, allowing a very rich CISC dictionary, possibly some new instructions would be effective concatenation of multiple old instructions.

    Hard drive manufacturers may not want to label what is now a '500 gigabyte' drive as '125 gigabyte', until they realize it's also a '4 terabit drive!'

  12. a CPU with 3 instructions and a 1-bit register? by Anonymous Coward · · Score: 1, Interesting

    Is this a correct way of interpretting it? "Two states" could be a single 1-bit register. The tape holds the program and the "three colors" at each point are the CPU's three possible instructions. Hmmm, but where is the result of the program stored/output ?