Found this via Facebook: the simplest possible universal Turing machine has been discovered, along with a mathematical proof that it is what it seems to be. Turns out, all it takes is two possible internal states and three possible things to write on the tape.
If you don't follow that, here's my best amature shot at an explanation: a Turing machine is a theoretical entity conceived of as an infinitely long tape attached to a device which, on each operation, takes what's on the tape and its internal state and returns a new thing for the tape, a new internal state, and moves either left or right. It's possible to build a Turing machine--a "universal" Turing machine--that can imitate any other Turing machine given the right set up on the tape (a "program," if you will). Computers are designed around this idea, except that they don't have infinite memory, so whatever serves as their tape won't be infinite, and this limits what they can do.
Not sure if this has any grand theoretical significance, from what I've read on computer science and cognitive science I have no reason to think it does, but still kinda cool.
2 comments:
I know someone proved that it's a universal Turing machine, but did they also prove that it's the smallest one possible? (And if so, just how is "smallness" being measured?)
It's been proved that TS with 2 states and 2 symbols (colors) is not universal, so TS with 2 states and 3 symbols is next. The smallness is in the overall number of states and symbols used.
Post a Comment