The LEGO Turing machine

Just to get back into blogging mode, here it is.  They do a good job of hamming it up, too.  Courtesy of Mikkel Vester, Anders Nissen, Martin Have, and Sean Geggie at the University of Aarhus (which is hereby forgiven for coming before me alphabetically).

37 Responses to “The LEGO Turing machine”

  1. hk Says:

    That approach kind of fails for Turing machines with 2 tapes :p

  2. sam_nead Says:

    All approaches fail for Turing machines with two heads… (Am I missing the joke here?)

  3. Koray Says:

    Scott, if blogging mode is on, what do you think of quantum logic (with the distributive law out of the window) and its consequences for logic (and science and the S&P500, etc.) in general?

  4. KaoriBlue Says:

    Martin, could you please explain your notation better? How does “The binomial theorem [3]: ..+.. ..= ..” make sense? What are these dots?

  5. KaoriBlue Says:

    Also, are you the guy who wrote the screenplay for ‘Solstice’?

  6. Martin M. Musatov Says:

    Sure, can I show in letters? I’ll be right back. Btw, wasn’t that Poincare at the end of the video?

    But first to answer your question re: the binomial theorem and the dots…

    Do like this:
    The next row, 1 3 3 1, are the coefficients of (a + b)3; and so on. To construct the triangle, …. That will constitute a proof of the binomial theorem. …

  7. Martin M. Musatov Says:

    Yeah, that’s me. It was such a better script…. :), I mean … It was great waiting for two years for a movie to come out in theaters and then be able to rent it at Blockbuster and collect crazy pics of one-sheets from foreign territories, such as…

  8. Martin M. Musatov Says:

    In concordance, the Encarta Dictionary: English (North America): The class P contains the in decision problems. a(1)(noun) = a [ay](a’s)(A’s, As)
    1. 1st letter of English alphabet=the first letter of the English alphabet, representing a vowel sound
    2. Letter “a” written=a written representation of the letter “a”
    a (2)(symbol)=a
    1. acceleration=acceleration=ac·cel·er·a·tion

  9. Job Says:

    Who says concordance anymore?

  10. Geordie Says:

    Someone needs to back off the crystal meth.

  11. Martin M. Musatov Says:

    But to answer your questions specifically, the “dots” become literally, the variables…

    i.e. by Martin A. Moskowitz, Hossein Abbaspour – 2003 – Mathematics – 120 pages
    Clearly, the total number of dots is (k + I)2, while the number on the diagonal … by means of the binomial theorem, which is itself proven by induction. ……

  12. Job Says:

    I thought Martin was a bot. In fact i still do. We’re all in “concordance” there right?

  13. Mike Says:

    If it is Martin, he must have a new script coming out and this is part of some marketing campaign 🙂

  14. Martin M. Musatov Says:

    Ha, thanks, I like to have fun with it. Just mixing it up, a little. Trying to learn as much as I can about something new.

    No bot here…

    It seems I had missed the tryout at

    Jan 3, 2007 … Google Job-bot… is there no end to Google’s take over of the world? …well maybe. I’ve been following Tom Smith’s article about Google … – 18k –

  15. KaoriBlue Says:

    “I thought Martin was a bot. In fact i still do. We’re all in “concordance” there right?”

    Right. But you have to admit that, if this were true, he’d have a REALLY good shot at passing the Turing test.

  16. KaoriBlue Says:

    This is actually really interesting…. Martin, who is ‘dlefsmur dlanod’ (reverse)?

  17. Martin M. Musatov Says:

    The former secretary of Defense…

    or….if I was Hal…

    …fo ekaw eht ni sraw owt gnieesrevo sraey laisrevortnoc lareves retfa 6002 ni dengiser ohw esnefed fo yraterces eht…

  18. KaoriBlue Says:

    Job, see, he’s not a bot. Or my last point has a lot of weight.

  19. Martin M. Musatov Says:

    for the record, I have no idea what “El Naschie” means…

  20. Jonathan Vos Post Says:

    there’s a foundational attack (reviewing Turing Test, Weizenbaum, Chinese Room) on the false assumptions of Naive A.I., and specifically undercutting the Rapture of the Nerds:

    [This essay appears in the Winter 2009 print edition of The New Atlantis, available now in bookstores and on newsstands. It appears here as a free preview. To read future articles in The New Atlantis before they appear online, purchase a subscription here.]

    Why Minds Are Not Like Computers
    Ari N. Schulman

    So while transhumanists may join Ray Kurzweil in arguing that “we should not associate our fundamental identity with a specific set of particles, but rather the pattern of matter and energy that we represent,” we must remember that this supposed separation of particles and pattern is false: Every indication is that, rather than a neatly separable hierarchy like a computer, the mind is a tangled hierarchy of organization and causation. Changes in the mind cause changes in the brain, and vice versa. To successfully replicate the brain in order to simulate the mind, it will be necessary to replicate every level of the brain that affects and is affected by the mind….

    If the future of artificial intelligence is based on the notion that the mind is really not a computer system, then this must be acknowledged as a radical rejection of the project thus far. It is a future in which the goal of creating intelligence artificially may succeed, but the grandest aspirations of the AI project will fade into obscurity.

  21. Job Says:

    Not convinced. Martin, what is the third number greater than 10 that is prime?

  22. Stas Says:

    This would be hard for some humans too 🙂

  23. Job Says:

    It’s ok if some humans get filtered in the process. 🙂

  24. ScentOfViolets Says:

    What’s nice about this particular machine is how imperfect it is. There’s a lot of jawing about how the universe is ‘really’ just a simulation being run on a machine somewhere (usually assumed to be a Turing machine), but one gets the sense from the proponents that it’s an exceedingly well-constructed one, machined to micro-micro tolerances in some ideal material. Angels pushing a bejeweled reading head along a platinum tape. But there’s nothing to prevent the simulation, if such it is, from being run on a Lego equivalent in some higher space. Maybe the machine breaks from time to time, maybe it misreads the tape. Maybe the whole thing is put away for eons, and the game is taken down from the top of the bookcase to be played on rainy days when there’s nothing else to do.

    Shades of Egan and his Dust.

  25. Job Says:

    I’ve wondered, if the universe is being simulated from the outside then how much did i pay for this? I guess i don’t have alot of money outside the universe either.

  26. KaoriBlue Says:


    You could probably push one a bot pretty far if you gave it access to a service like, I think it’s called ChaCha? There have been a number of news articles on it… and I hear you can get rather sophisticated answers pretty quickly from the network of users.

  27. John Sidles Says:

    A Google search for “xkcd: A bunch of rocks” and “xkcd: Turing Test” will link to two mathematical comics that relate to this thread—both comics are very enjoyable IMHO.

  28. John Sidles Says:

    … and as a follow-up, appreciation of “xkcd: A bunch of rocks” is immensely heightened if you download and run Paul Rendell’s Turing Machine implemented in Conway’s Game of Life … this being the computational engine that the xkcd strip is largely based upon.

  29. Scott Says:

    Everyone: I’m so, so sorry for disappearing, and leaving a roving P=NP hoodlum to run rampant through my comments section. That’s what comes from trying to do “real” work! I’ll try not to let it happen again.

  30. Scott Says:

    what do you think of quantum logic (with the distributive law out of the window) and its consequences for logic (and science and the S&P500, etc.) in general?

    Koray: I’ve blogged about quantum logic in the past. There are interesting things to say about it mathematically, but

    (1) I don’t think it “challenges the laws of logic,” nor do I think there’s any empirical discovery that could. The fact that one can define and study formal systems that break (say) the distributive law, doesn’t make the slightest difference to the truth of the distributive law as conventionally understood.

    (2) Judging it as a way of reasoning about quantum mechanics, I find that quantum logic leaves an enormous part out: probabilities! Quantum logic is basically what you get by throwing away the probabilistic part of quantum mechanics (i.e., the Born rule), and considering only the lattice of subspaces of Hilbert space. Then, to make the problems more interesting, you tend to go immediately to infinite-dimensional Hilbert spaces, which takes you even further from the conceptual aspects of QM that interest me the most. Thus, I think that quantum information and computing, where you generally care only about achieving some goal with probability 1-ε, and not about whether a given state is or is not in a given subspace, does a better job of capturing what QM is really about.

  31. Koray Says:

    Scott, crap, I should have googled better:

    Staying with your squirrel-behind-bushes analogy, when I read about it I first thought of physical TM’s (paper & pencil or silicon) where bushes stand for tape positions. In an abstract TM we don’t have this limitation, but could a physical machine (including paper & pencil) be more limited?

  32. John Sidles Says:

    Scott says: “going to infinite-dimensional Hilbert spaces … takes you even further from the conceptual aspects of QM that interest me the most.”

    Scott, in your capacity as an professor of engineering, it would be interesting to know what engineering aspects of QM interest you most.

    Is it the practical engineering aspects? Or are your interests more aligned with the post-modern, theorem-proving, academic variety of engineering?

    In these difficult economic times, deans are becoming very fond of theorem-proving faculty … for the pragmatic reason that they require substantially less (expensive) infrastructure than any other variety.

    Does this mean that young engineers who have academic aspirations should focus mainly on theorem-proving?

  33. Scott Says:

    John, people should focus on whatever interests them; as a practical matter, they probably won’t succeed otherwise. I prove theorems, but I’ll also be extremely happy if someone builds a quantum computer. And you knew that. 🙂

  34. MattF Says:

    So,… is ABBA a palindrome or not? I need to know.

  35. John Sidles Says:

    Hmmm … “people should focus on whatever interests them”

    Scott, this strategy works well in mathematics, and yet it is an utter disaster in medicine … where we have to treat the (often confusing and incurable) diseases that patients actually present with, not the (rare, fascinating, and curable) diseases we wish we were seeing.

    Engineering is IMHO a happy middle ground, in which creativity and responsibility mix in (roughly) equal proportion.

    Like rhyming poetry, or tennis with a net.

  36. Scott Says:

    John, “interest” is always a negotiated compromise between what you like and what the rest of the world presents to you. (Theorists have more choice than most people in which problems to work on, but even we don’t get to choose which techniques will be needed to solve the problems, etc.) You don’t have a choice of which diseases patients catch, but you at least have the choice of whether to go to med school in the first place—and to whatever extent you can make choices that are “true to yourself,” I predict (purely as a utilitarian matter, not a spiritual one) that you’ll be more successful than otherwise.

  37. John Sidles Says:

    Scott, I don’t think we’re disagreeing … Especially, it’s delightful that there’s plenty of room for serendipity either way.

    Even the most abstract theorem may have unexpected practical applications, even the most mundane engineering challenge may reveal marvelous mathematical depths, even the most commonplace-seeming medical case may in fact be a rare-and-curable medical condition.

    Thus (as my wife says) “Attitude is everything!” 🙂