Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Programming Toys

A Turing Machine Built With Lego, And a Place To Put It 74

Posted by timothy from the try-that-with-lincoln-logs dept.
New submitter Otis_INF writes "To honor Alan Turing, two researchers at the CWI built a simple LEGO Turing Machine, to show everyone how simple a computer actually is. Primary goals were to make every operation as visible as possible and to make it using just a single LEGO MINDSTORMS NXT set." And if a simple Turing machine gets old, Reader miller60 adds a link to this Lego data center "that recreates all the major features of an IT facility, assembled from 5,772 pieces, 28 figures, and 1 meter of fiber optic cable. The builder, Tanaka, has uploaded details to the Lego Digital Designer Gallery so others can build and adapt their own."
This discussion has been archived. No new comments can be posted.

A Turing Machine Built With Lego, And a Place To Put It More

A Turing Machine Built With Lego, And a Place To Put It

Comments Filter:
  • It's a Turing machine dammit, not a web server!

  • Hmm... (Score:3)

    by Antony T Curtis ( 89990 ) on Tuesday June 19, 2012 @12:09PM (#40372207) Homepage Journal

    My personal opinion: I don't like their implementation.

    I would prefer to see a version which uses a long "tape" which is covered in a thin film and the data recorded using different coloured dots from whiteboard markers.

    Just my 2.

    • Re: (Score:2)

      by vlm ( 69642 )

      whiteboard markers will dry out too quickly. Been there, thought of that.

      • Well what about those round one post Lego dots. That might be doable.

        • Re: (Score:2)

          by vlm ( 69642 )

          Might work, might be a bit fumbly. The closest "solution" I could come up with involved something that looks like a magnetic chess piece with a little neo-magnet on the bottom and a gripper on top. Given a decent gripper/mover I could implement something like that on my milling machine table right now. This brings up my really weird idea of a robot arm making QR codes using black square magnets on a steel sheet. But this is getting pretty far off from the original "mostly-electromechanical" design.

  • It's an LBA, not a TM (Score:5, Insightful)

    by Prune ( 557140 ) on Tuesday June 19, 2012 @12:13PM (#40372261)
    At Turing machine has infinite tape (memory). You cannot build one in the real world**. This is a deterministic LBA (linearly bounded automaton). **for two reasons preventing infinite storage: 1. a real world automaton is limited in extent by its light cone, and you cannot rely on this growing forever since accelerating expansion of the universe eventually will prevent outer parts of the device from communicating back with lightspeed signals 2. the Bekenstein bound limits information density: you can only store a finite information in a finite space--so no arbitrary precision real numbers
  • Modular design is certainly the way most new data centers are going!! And who is more modular than Lego????????

  • Turing machine emulation using physical memory (Score:5, Informative)

    by vlm ( 69642 ) on Tuesday June 19, 2012 @12:17PM (#40372333)

    As has been (kinda harshly) hashed out on hackernews, this is really a turing machine emulated on a NXT using lego as a physical memory display. This is still cool, but its not "turing machine built out of lego" except by the extreme interpretation that a NXT computer is sold by the lego corporation.

    There have been some genuine mechanical turing machines built with varying level of success.

    Its pretty easy to make an electromechanical relay based turing machine if for no reason other than price (well, price compared to when I was a kid, its still gonna be a chunk of change)

    When I was a teenage kid a simple DPDT 12 volt relay at radio shack cost me something like two HOURS of labor income, and now as a "highly" paid jack(-ass) of all computational trades I can buy a simple DPDT from Mouser for something like two MINUTES of labor income. I've got a bitslice ALU design (admittedly not a turing machine) down to about 22 relays per bit. Latching relays are about 50% more money than non-latching. Also QPDT relays are "cheap" and commercially available.

    large PCBs are expensive. Yet sockets and hand wiring is not cheap either (although it looks cool)

    I'm stuck on (electro-)mechanical memory storage devices. There was a single bit core memory design from a 1970s electronics magazine that used simple steel washers as cores, terrible magnetic properties but cheaply and widely available. However I don't want an electronic design. Latching relays are cheap enough for registers and ... surprisingly enough ... latches ... but they're a bit expensive for main memory. For example an Altair size of memory made of latching relays would cost me about 256 bytes * 8 bits * 3 bucks per latching relay equals $6.1K just for storage not to mention decode logic. Until I can figure out a way to get below $1/bit purely electromechanically I think I'm stuck.

    The history of computation, since the 1940s (before even my time) has always been "computation is cheap, memory is expensive"

    • Re: (Score:2)

      by kasperd ( 592156 )

      this is really a turing machine emulated on a NXT using lego as a physical memory display. This is still cool, but its not "turing machine built out of lego" except by the extreme interpretation that a NXT computer is sold by the lego corporation.

      According to the video (which is now working) it reads the state of those lego pieces using an optic sensor. So they are not just used for display, they are used as actual memory. There is no requirement as to how you implement the state machine of a turing machine

    • The history of computation, since the 1940s (before even my time) has always been "computation is cheap, memory is expensive"

      That may have changed now with 2TB for $99....

      I/O bandwidth on the memory is still a little more expensive than the CPUs it connects to, but 2TB is a pretty infinite storage pool if you've got the patience to wait for it.

      Hell, even 2GB of DRAM, or 256MB of cache feels infinite in terms of pre-1980s computers.

  • In theory it actually can run Linux (if you are really really patient)

    • Re: (Score:2)

      by Belial6 ( 794905 )
      I think it would be funnier to run LOGO on it.
      • For a truly perverse experience it needs to be a Lego Turing machine to emulate an Apple ][ running LOGO to control the Lego Turing machine. I some how feel I have now stumbled upon some weird edge case of the halting problem related to my childhood and that I need to go dig out my computational theory book.

  • Otherwise, how the heck did they come up with an infinitely long tape?

  • If Professor Turing patented a TM these days, he could sue for royalties on every computer, big and small. I almost wish he had as revenge for the crappy way the British gov't treated him.

  • ...but I'd like to see how they'd implement the lambda calculus in Lego.

    Maybe this is how one finally proves, after decades of bickering and argument, which model of computation is better- by seeing which one looks prettier when you make a visualiser for it out of brightly coloured snappable bricks.

  • A Turing machine is defined by a tape and a manipulator, and a state machine defining how those tape symbols are manipulated. The former is visible in the video. The latter is not. It appears they're using a mindstorm (itself a microcomputer) to perform the function of the state machine. I think this is cheating.

    In fact, the whole state machine part of the Turing machine has always been rather nebulous to me. Yes, I understand the state transitions, but no physical mechanism is described (in CS theory

    • The implementation of the state machine is of less interest because it is finite. The aim of the exercise is to reduce the the notion of computability to a machine-like process. The most simple conception is that only one part of the machine is infinite and variable. That is why Turing needed to show how to implement a Universal Machine as a single Turing Machine, so that the transition table could be made fixed in size (and after that point, uninteresting in implementation). It would have been sufficient t

      • Besides, you don't need a fully mechanical state machine and an infinite tape to show the interested public some of Turing's highly important computer science work (as opposed to impressing the Slashdot crowd, or showcasing the Engima code breaking work, which seems to be what most 'normal' people associate with him these days).

        With that goal in mind, I think the project has been highly successful – it has been reported in major Dutch newspapers and generated a lot of interest in the Netherlands.

    • The mindscrew is that every physical machine, including the microcomputer (as well as this "Turing machine" itself, with its finite tape), is technically a finite state machine. The theoretical model of a true Turing machine requires the availability of infinite memory.

      You could say that the deterministic finite state machine can be any (deterministic) physical device conceivable, while the infinite tape is the one part that cannot be built in reality.

  • The only reason it's "simple" is that one of its parts is a full computing device.

    I'd have preferred a "hardware" implementation...

  • I do love legos though..

Slashdot Top Deals

A consultant is a person who borrows your watch, tells you what time it is, pockets the watch, and sends you a bill for it.

Close