Home-Built Turing Machine

stronghawk writes "The creator of the Nickel-O-Matic is back at it and has now built a Turing Machine from a Parallax Propeller chip-based controller, motors, a dry-erase marker and a non-infinite supply of shiny 35mm leader film. From his FAQ: 'While thinking about Turing machines I found that no one had ever actually built one, at least not one that looked like Turing's original concept (if someone does know of one, please let me know). There have been a few other physical Turing machines like the Logo of Doom, but none were immediately recognizable as Turing machines. As I am always looking for a new challenge, I set out to build what you see here.'"

I found that no one had ever actually built one

[Threni]

I think you'll find that every single computer ever made has been a Turing machine.

Re:You're Doing It Wrong

[noidentity]

As far as I can see, he's using a microcontroller which is, itself, Turing-complete. So it's still only emulating a Turing machine (just with physical tape, instead of an emulator on your computer).

Couldn't that be said of any Turing machine? Whatever you build it out of is Turing-complete, I think.

Re:You're Doing It Wrong

[ircmaxell]

The program would only ever be on the tape in the case of a Universal Turing Machine: http://en.wikipedia.org/wiki/Universal_Turing_machine [wikipedia.org]...

Re:Technically...

[risk one]

Actually, in a sense, you can. The Turing machine doesn't require an infinite tape, just a tape of arbitrary length. Basically, you need to be able to always add more tape. Eventually, of course, the universe will run out of mass for you to make tape out of, but the machine is still a proper Turing machine. The distinction may seem meaningless, but consider the set of all finite bitstrings. This set will not contain any infinitely long strings, but it will contain arbitrarily long string. However long you want your string, there's one in the set, and a longer one, but no infinitely long ones. There's a definite difference between arbitrary finite length and infinite length. I've always found that this realization makes the Turing Machine just a little bit more real.

Re:Technically...

[FrangoAssado]

Well, if you want to split hairs, at least split them to the end...

Eventually, of course, the universe will run out of mass for you to make tape out of, but the machine is still a proper Turing machine.

How is this "still a proper Turing machine"? There are programs that would work on a theoretical Turing machine (with arbitrary amount of tape), but would run out of memory in your scheme.

The OP point stands: we will never actually be able to build a real Turing machine[1]. Still, computers are very good approximations (for programs that require up to a certain amount of memory).

[1] Assuming the universe is actually expanding and that the theory of relativity is right (a good discussion can be found here: http://www.scottaaronson.com/democritus/lec20.html [scottaaronson.com])

Re:hmmm

[FooAtWFU]

Well, if you're going to make a Turing machine run something equivalent to Conway's Game of Life, forget the random: have the simulation be A Turing Machine in Conway's Game of Life [rendell-attic.org].

So you haven't seen this?

[Fjodor42]

http://www.youtube.com/watch?v=cYw2ewoO6c4&feature=fvst [youtube.com]

Re:Non-infinite

[Anonymous Coward]

A default Turing machine tape is infinite, it's an important part of the concept. Thus it has to be accented that this one isn't infinite. Saying it's a "finite tape" would suggest that it's a choice as arbitrary as "shiny" and "35mm".

Re:Cool...I think.

[thrawn_aj]

Who modded this 'troll'? Are people not allowed to muse wonderingly anymore? Sheesh, some people need to unclench.

Personally, having been entirely fascinated with Turing and his work during my college years (from a mathematical point of view - the Entscheidungsproblem [wikipedia.org] rather than CS), seeing an actual Turing machine sends shivers up my spine. Kudos!

For anyone interested in knowing more about this fascinating scientist, I recommend the book by Andrew Hodges [amazon.com].

Re: I found that no one had ever actually built on

[LandruBek]

No, actually he was correct. Having an unlimited amount of input (over a finite alphabet) does not promote a finite state machine to being a (classical) Turing machine. If you want to have a real Turing machine, then you must have unlimited writable memory (as well as a few other things). Finite state machines handle unlimited input just fine. Actual desktop computers have "only" a finite (gigantic) number of possible states, assuming you don't let people swap in an unlimited number of new hard drives.