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.)
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 …
-
Thursday 21st June 2012 12:43 GMT Mage
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.
-
Thursday 21st June 2012 15:18 GMT 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.
-
-
-
Thursday 21st June 2012 13:34 GMT Anonymous Coward
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
-
-
Thursday 21st June 2012 15:06 GMT 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...
-
Thursday 21st June 2012 17:50 GMT 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.
-
Friday 22nd June 2012 09:44 GMT Anonymous Coward
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.
-
-
-
-
-
Thursday 21st June 2012 13:35 GMT 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...
-
-
Thursday 21st June 2012 14:38 GMT 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.
-
-
Friday 22nd June 2012 09:51 GMT Anonymous Coward
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.
-
-
-
-
Thursday 21st June 2012 13:43 GMT John H Woods
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.
-
-
-
Friday 22nd June 2012 17:47 GMT 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.
-
-
-
-
-
-
Thursday 21st June 2012 16:26 GMT 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.
-
Friday 22nd June 2012 06:38 GMT Anonymous Coward
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.
-
This topic is closed for new posts.
Biting the hand that feeds IT
