Feeds

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 den …

COMMENTS

This topic is closed for new posts.
Bronze badge

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.)

4
0
Paris Hilton

Re: Cool.

Didnt the Reg send the Playmonaught into space onboard PARIS?

Must be similar to a Lego man

1
0
Bronze badge

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?

1
0
Bronze badge
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.

0
0
Bronze 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.

10
0

What a job

To get paid to build things like that!

Almost as good as being Quality Controller in a brewery.

3
0
Silver badge
Pint

Re: What a job

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

7
0
Anonymous Coward

Re: What a job

"Foster's brewery?" = Oxymoron?

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

1
0
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.

0
0
Bronze badge

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.

0
0
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.

6
1
Bronze badge
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

13
0

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...

1
0

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.

3
0
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

0
0

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.

1
0
Bronze badge

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...

0
0
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!

0
0

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.

0
0
Facepalm

Re: Not really a LEGO Turing Machine!

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

0
2
Bronze badge
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.

0
0
Bronze badge
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.

0
0

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.

0
0
Silver badge

Sir

"letter from the Queen"

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

4
1
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.

3
0
Silver badge

Haase and Bennett

were pardoned after conviction - and those laws still stand.

1
0
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.

0
0

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

0
0

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.

0
0

Playmobile Reconstuction Please

Thanks.

0
0
Silver badge
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.

0
0

Serious failure in taste

Why the appalling noise???

P.

0
0
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.

3
0
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.

0
0
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'

0
0
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?

0
0

Re: Binary?

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

i.e. not binary

0
0

Floating point?

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

0
0
This topic is closed for new posts.