Wolfram's 2,3 Turing Machine Is Universal! 288
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.
Comment removed (Score:3, Interesting)
Science is forever (Score:3, 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.
Re:A New Kind of Science (Score:2, Interesting)
if you like this... (Score:5, Interesting)
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/ [kisrael.com] 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...
Re:An Undergrad? (Score:4, Interesting)
Re:A New Kind of Science (Score:5, Interesting)
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?
Automat size (Score:2, Interesting)
Question for Turing Geeks. (Score:2, Interesting)
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?
Other simple universal machines (Score:3, Interesting)
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 [slashdot.org] 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.
Re:A New Kind of Science (Score:3, Interesting)
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.
A flaw in the argument:no *HALT*:resubmit for $25k (Score:4, Interesting)
Maybe someone should submit the same proof, concluding that it is *not* a universal Turing machine, and claim the $25k.
Re:A New Kind of Science (Score:2, Interesting)
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.
Re:Uhh, what? (Score:4, Interesting)
- 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.
Not What It Seems? (Score:3, Interesting)
Bits per symbol (Score:2, Interesting)
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!'
a CPU with 3 instructions and a 1-bit register? (Score:1, Interesting)