Forgot your password?
typodupeerror
Hardware Hacking Robotics Build

Home-Built Turing Machine 123

Posted by Soulskill
from the i'll-order-a-dozen dept.
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.'"
This discussion has been archived. No new comments can be posted.

Home-Built Turing Machine

Comments Filter:
  • by trurl7 (663880) on Friday March 26, 2010 @01:56PM (#31629550)

    RTFA. I know that's a sin, but seriously, do. You'll discover you are wrong.

    The microcontroller loads the program as written in ascii on an SD card. It also can write the initial data onto the tape. After that, the computation is, indeed, performed by the "machine". Hence the optical reader for the characters on the tape.

  • by HateBreeder (656491) on Friday March 26, 2010 @02:00PM (#31629626)

    Actually, if you'd bother reading the article, you'd find that the micro-controller is being used to do drive the electric motors, image process and maintain the turing machine's "state" [wikipedia.org]. that's it.

  • by ircmaxell (1117387) on Friday March 26, 2010 @02:23PM (#31630028) Homepage
    Actually, sorry but you're wrong. Alan Turing himself described a Turing Machine as a "Logical Computing Machine" which consisted of:

    an infinite memory capacity obtained in the form of an infinite tape marked out into squares on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine.

    Now, let's look at how this works. It reads a symbol from the tape using the camera. Then it checks its internal state, and sees what it should do with that symbol (should it change the symbol, change the state, and/or how should it move). Then it does that action and moves on to the next symbol as instructed by the last "rule". Considering that the only thing that the machine keeps track of from position to position is the state, it is indeed a Turing machine. The microprocessor's job (as he states) is to act as the read/write head for the machine. Turing never described HOW the head worked, just WHAT it did. And this head performs EXACTLY what Turing described. And that's why this is a Turing machine. If you wrote a program on your computer that did this, it too would be a Turing machine. The delineation is in how it handles and stores states, not the method in which it "processes" data... And Turing's original work described a Turing machine as using a person to perform the actions (but strictly following the ruleset). So I fail to see how this could possibly NOT be a Turing machine...

  • Re:hmmm (Score:1, Informative)

    by Anonymous Coward on Friday March 26, 2010 @03:53PM (#31631374)

    A "Turing machine" is what you see in the video—or at least it would be, if it were an ideal abstraction with an infinite supply of tape and the ability to remember an unlimited number of states (although the number of states would be finite in any given program). A "Turing-complete" machine/language is one that is capable of simulating a Turing machine—again, adjusting for finite memory within the bounds of common sense.

    The significance is that Turing proved that a Turing machine can execute anything at all that we would intuitively call an "algorithm". So, if you have a new programming language, all you have to do is prove that it can simulate a Turing machine like the one in the video—a very easy task in most cases, doable even with a perversely simple language like Whitespace or Brainfuck—and bang, you've proven that you have a language capable of executing any algorithm at all, a "Turing-complete" language.

  • Re:Cool...I think. (Score:3, Informative)

    by epee1221 (873140) on Friday March 26, 2010 @07:25PM (#31634094)

    Well, infinite tape is the optimal design.

    Strictly speaking, limiting a Turing machine to a finite tape makes it something other than a Turing machine (e.g. a linear bounded automaton).

The world is moving so fast these days that the man who says it can't be done is generally interrupted by someone doing it. -- E. Hubbard

Working...