back to article Turing Machine brought to life with Lego

Check out this badass Turing Machine made from a single Lego Mindstorms Nxt kit, an impressive reincarnation of the classic concept conceived by maths boffin Alan Turing in 1936. While Turing's idea had an infinite tape, the researchers that built this particular machine were limited to just 32. Put together by Jereon van …

COMMENTS

This topic is closed for new posts.
  1. Anomynous Coward

    Cool.

    Really cool.

    Let's send one into space.

    (What happens to Lego in space? Does anyone know? Does the air in the brick cavities break the model up? I think someone should be finding this sort of thing out.)

    1. 1Rafayal
      Paris Hilton

      Re: Cool.

      Didnt the Reg send the Playmonaught into space onboard PARIS?

      Must be similar to a Lego man

      1. Anomynous Coward

        Playmonaut

        Did we ever get a report on his / her / its well-being following the trip?

        Is it now a bearded Playmomystic convinced it saw a god in the fragments of the bursting launch balloon?

    2. Anonymous Coward
      Happy

      Re: Cool.

      A recent mission, as part of its educational programme, included an astronaut on the ISS building a LEGO model of the ISS in a glove-box before taking it out and letting it float around.

  2. graeme leggett Silver badge

    I must get some Mindstorms kit

    it looks like great fun

    Err, I mean I'm sure it would be a useful educational resource for my son.

  3. Roger Varley

    What a job

    To get paid to build things like that!

    Almost as good as being Quality Controller in a brewery.

    1. Piro Silver badge
      Pint

      Re: What a job

      What happens if that was the Carling or Foster's brewery?

      1. Anonymous Coward
        Anonymous Coward

        Re: What a job

        "Foster's brewery?" = Oxymoron?

        Foster's urin treatment and recycling plant, would be more accurate.

  4. Mage Silver badge
    Boffin

    Impressive

    But either all Programmable Digital Computers are Turing Machines, or none are (lack of infinitely long "tape").

    The tape doesn't have to be a tape. It's all a mind game, a concept. See if you can build Hilbert's Hotel out of lego. For an encore build the coaches for Hilbert's Hotel.

    Mathematicians were quite happy with Turing's paper, they had had over 10 years to get used to infinite stuff. Hilbert really upset them about 10 years earlier. I'd guess they were relieved there was only ONE infinite tape and the headaches had worn off.

    1. Anonymous Coward
      Anonymous Coward

      Re: Impressive

      Big difference. You only need an infinite tape to emulate every other Turing machine, but that's only because you've allowed that other machine an infinite tape. Oddly you could make the same claim regarding the machine having an infinite number of states, symbols, and entries in its state transition table, but these always seem to be deemed finite.

      Actually given a finite tape Turing Machine you would only need another finite machine to emulate it (but with a degree more in both its tape length and state transition table size). A Turing Machine machine is still capable of a defined set of finite operations with a finite tape, as all these models demonstrate. Why an infinite tape is critical to the definition is honestly beyond me.

      Hilbert's Hotel is something of a joke about struggling to understand the mathematics of infinity. No part of it works in finite space at all.

  5. GettinSadda
    Unhappy

    Not really a LEGO Turing Machine!

    Yes it includes physical LEGO as a very small and insignificant part of the system, but all the real work is done inside an actual electronic computer.

    1. Anonymous Coward
      Meh

      Re: Not really a LEGO Turing Machine!

      True - Whilst a lovely demonstration, it would be more impressive were it a purely mechanical device.

      Of course we'll both be downvoted for such an opinion by pseudo-fanbois who will then spluff all over the place when they actually see a purely mechanical LEGO one.

      You know, like this:

      http://www.turing2012.fr/?p=530&lang=en

      1. Rob Carriere

        Re: Not really a LEGO Turing Machine!

        Thank you for that link!

        Wow. Cancel my earlier remark about the sufficiency of LEGO. Cancel it with prejudice. That's one heck of a machine.

        1. Anonymous Coward
          Anonymous Coward

          Re: Not really a LEGO Turing Machine!

          Well, it's an unwritten rule that someone has to say you could do it better in Meccano...

          But I laboured for a while under the misconception that the Turing Machine reads a program of discrete operations. It doesn't - it's pre-configured with a state machine that acts as the program, which in itself could be huge. I gather the linear program concept only came about with Von Neumann Architecture (for shared memory) or Harvard Architecture (for separate program and memory). Either of which is possibly easier to implement mechanically, but certainly easier to program in...

          1. Francis Vaughan

            Re: Not really a LEGO Turing Machine!

            There is nothing stopping you writing a state control table that implements a program that can use the tape to hold both data and program code for a new automata implemented by the Turing machine. That is after all just unified code and data. And a nice exercise in showing how a Turning machine encompasses all other automata. In principle you could code an x86 interpreter on a Turning machine. All the CPU state still lives on the tape, an you could put x86 code and ordinary data elsewhere on the tape. What matters is that the ONLY mutable data lives on the tape. The table is fixed.

            1. Anonymous Coward
              Paris Hilton

              Re: Not really a LEGO Turing Machine!

              True, but here again is the issue I have with the definition of a Turing machine. To mix code and data on the tape requires a state machine that can remember position, i.e. it implements the equivalent of at least a program counter, address register and accumulator - though addresses will always be relative on the tape. Though since the definition allows for infinite tape, it follows that those addressing registers will also tend towards the infinite, such that a finite state machine is insufficient.

              1. Francis Vaughan

                Re: Not really a LEGO Turing Machine!

                Different infinities. Try Cantor's diagonalisation mechanism to show that the Turing machine can still cover things. So long as there are Aleph null places on the tape, it is big enough.

      2. Chris Sake
        Thumb Up

        Re: Not really a LEGO Turing Machine!

        Joefish, thank you for that link. The article's video was like watching a goldfish swim around in its bowl and calling it a Turing Machine. The French one was amazing. Now let's see that be part of the curriculum in an ICT course!

    2. Rob Carriere

      Re: Not really a LEGO Turing Machine!

      That's actually not quite true. The part inside the electronic computer simulates a finite state machine; the LEGO bits are what transforms the FSM into a Turing machine. You could reasonably argue that the bulk of the compute power is in the LEGO part of the construction.

      That said, I was a bit disappointed at the electronic fudging myself. A fully mechanical TM would have been more impressive as well as of more educational value.

      But, I think LEGO is probably an insufficient medium for that. Old-style Meccano, on the other hand...

    3. Wemb
      Thumb Up

      All the real work....

      Need a 'real computer'? Fine - attach it to one of these

      http://www.youtube.com/watch?v=KL_wy-CxBP8

    4. Francis Vaughan

      Re: Not really a LEGO Turing Machine!

      Yup. It isn't a Turning machine at all. Sorry, but it isn't.

      A Turing machine only holds machine state on the tape. The programme, that is the state transition table is fixed and cannot hold mutable state. That is the definition. This model device only used the tape to provide I/O. There was mutable state inside the simulating engine - the engine internally did the calculation 2+2=4. It was not calculated on the tape, which is what a real Turning machine must do.

      So, sorry, nice bit of Lego, but it is NOT a Turing Machine.

    5. 20legend
      Facepalm

      Re: Not really a LEGO Turing Machine!

      ITS MADE FROM A SINGLE LEGO KIT - what the fuck do you expect ?????

      1. Anonymous Coward
        Devil

        Re: ITS MADE FROM A SINGLE LEGO KIT

        No it's not, as you only get 12 of those right-angled axle joints in the kit and there are 32 of them used for the memory tape. And as someone has already pointed out, a programmable switch-flipper is not a Turing Machine. At best, it's a Brainfuck parser with mechanical memory.

  6. Sir Runcible Spoon

    Sir

    "letter from the Queen"

    How about a posthumous pardon and an apology to his family instead?

    1. John H Woods Silver badge

      Re: Sir

      Officially a 'posthumous pardon' is not applicable - he was convicted under the (bad) laws of the time, and pardons are reserved for people whose convictions are found to have been wrong, rather than whose prosecution is.

      But I can't see why they can't find some official form in which they could apologize for ruining his life, and prematurely depriving us of a genius who played no small part in ensuring the continuity of our own state.

      1. Tom 7

        Haase and Bennett

        were pardoned after conviction - and those laws still stand.

        1. Anonymous Coward
          Anonymous Coward

          Re: Haase and Bennett

          and then got 42 years (nearly double the original sentence) between them once their means of getting the pardon was uncovered.

          1. Francis Vaughan

            Re: Haase and Bennett

            Still proves the point, no matter how duplicitously obtained. If a pair of convicted drug dealers can get the "exercise the Royal Prerogative of mercy" call, and be pardoned of a crime, there is no logical argument the British government can reasonably stand on to deny Turing. The process clearly exists, and has been used recently.

      2. Aqua Marina

        Re: Sir

        You can't get much more official than a written public apology from a serving Prime Minister and published in a national newspaper.

        http://www.telegraph.co.uk/news/politics/gordon-brown/6170112/Gordon-Brown-Im-proud-to-say-sorry-to-a-real-war-hero.html

  7. drunk.smile

    Playmobile Reconstuction Please

    Thanks.

  8. M Gale
    Thumb Up

    Hm.

    So were the creators thinking "let's build a Turing machine?"

    Or were they thinking "Can we make Brainfuck out of Lego?"

    Lovely, either way.

  9. Cyberelic

    Serious failure in taste

    Why the appalling noise???

    P.

  10. Anonymous Coward
    Anonymous Coward

    Oh, yeah?

    Well, I made a really very excellent sculpture of the red 'Angry Bird' the other day.

    Hey, my son asked me to.

    Yeah, I waited with bated breath for the day my kid was old enough to play with legos. It was such a rush to get back into it that I spent a few nights up until 3am working on making a truck thing with no bumps at all on any part of the surface. It's tougher than you might think, with a limited block set.

    Right now I have to hold myself back from scooping heaps of Lego sets off shelves into my shopping card wherever I go; the main saving grace is that most of the retail stuff is fucking 'Cars' advertising that has four huge plastic chunks with 'lego' written on them. What a load of bullshit. A block with only one purpose isn't a fucking lego, you miserable cock goblins! And can we PLEASE, PLEASE have at least SOME toys that aren't tie ins for movies or TV shows? Fuck's sake, people, I'd like to be able to get something that (a) doesn't talk and (b) doesn't have a 'Cars' character on it and (c) isn't sold in a quaint boutique and made by a bearded craftsman in Vermont, out of lacquered maple (that has undergone at least three hours of foreplay), and which costs $90 for a little car which really is pretty awesome but 90 fucking dollars? I can't afford that shit!

    Ahem.

    Still, at least they're still making the real ones - you can even get a biggish box full of normal blocks for 30 bucks or so at your favorite huge-box retailer.

    The worst part is that since my son is just coming up on four, his ambition outweighs his skill, and he keeps trying to do impossible things (holding a half pound blob of legos cantilevered out six inches and hooked on a tower by one bump) and then freaking the FUCK out when it doesn't work. Still, he's getting better and better, and it's tough to beat doing something like cross-bracing a car chassis and seeing him do it the next day.

    1. Anonymous Coward
      Thumb Up

      Re: Oh, yeah?

      Complete agreement on everything...

      Have only bought the generic Bricks & More buckets and boxes, especially love the vehicles one, er... I mean my SON loves it of course. He's made a bunch of vehicles and a small pump/ repair station on one of them big grey baseplates...

      A little expensive but better than 3 sets of 'Cars' branded Lego boxes.

    2. Captain TickTock
      Headmaster

      Every time someone says LEGOs...

      a mini figure dies.

      LEGO the company itself does not use the term LEGOs.

      LEGO is a system of components.

      You can make hings out of Lego. You might have 'a piece of Lego', but not 'a Lego'

  11. Richard 1
    FAIL

    Binary?

    Are the right-angled logo pieces meant to denote binary? I'm assuming that they are. If so, how does two pieces flipped up mean '2' and four flipped up mean '4'. That's not how they would be represented in binary...

    3 + 3 = 15?

    1. peter 45

      Re: Binary?

      I think you answered your own question.For this 2 bits flipped = 2 and 4=4

      i.e. not binary

  12. A_Flat_Minor

    Floating point?

    To me this looks just like HMS Hermes from the side.

This topic is closed for new posts.