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:
  • Cool...I think. (Score:2, Insightful)

    by Anonymous Coward

    I admire people who build things like this, but at the same time I also wonder just why the heck they do it.

    I guess that's the difference between people, I'd rather build something new than re-create something that's been done before. (Honestly not trying to sound like an ass, just find it interesting.)

    • Re:Cool...I think. (Score:4, Insightful)

      by 91degrees (207121) on Friday March 26, 2010 @12:42PM (#31629304) Journal
      I don't think it has been done before though. At least not as a hardware implementation. The reason being that while it's an interesting hypohetical machine, it's extremely inefficient means of computing anything. But it is very nice to actually see a visualisation of such a machine
      • by Dogtanian (588974)

        I don't think it has been done before though. At least not as a hardware implementation.

        The requirement for an infinite length of tape may have been a minor problem, IMHO.

        • by 91degrees (207121)
          Well, infinite tape is the optimal design. In practice you only need a tape of adequate length for the calculation you're performing. If you want to print every number then yes, you will need an infinitely long tape. But it will take forever to actually complete that task. And of course, if you had an infinitely long tape the machine would be able to cope with it.
          • Re: (Score:3, Informative)

            by epee1221 (873140)

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

    • Re: (Score:3, Interesting)

      by thrawn_aj (1073100)
      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].
      • This is o.t., I guess. But that amazon link lists a paperback new version of the book for $147.78 !!!. Is this a slashdot price spike of some sort? I love old and rare books, and I am a great admirer of Turing (he did save the world, after all). Just wondering when the price for that particular paperback went through the roof..
        • It's not really the Amazon price - they don't have it in stock. It's a marketplace seller who says the following: "New - Out-of-Print and VERY rare title to find in new condition".

          I didn't think it was all that rare but the last time I read it was in 2000 and borrowed from the university library so I might be mistaken. I guess if you really can't find a lower price, I'd just check out the movie with Kate Winslet ;-).

          Here's the link to the UK version (if you don't mind paying international shipping)
  • hmmm (Score:3, Insightful)

    by Denihil (1208200) on Friday March 26, 2010 @12:38PM (#31629232)
    maybe i'm missing something but i'm used to people talking about "turing machines" as a machine that is "turing-complete", not looking like a hypothetical turing machine he described in his paper. Is this aesthetics over the principle he meant it to be taken by? Cool hardhack though btw, love to have one of those on my coffee table.
    • Re:hmmm (Score:5, Funny)

      by fuzzyfuzzyfungus (1223518) on Friday March 26, 2010 @12:49PM (#31629422) Journal
      For the ultimate in coffee table extravagance, you need this turing machine running an implementation of Conway's game of life, ideally using a chessboard as the display device for that: full cells would rise slightly above the board, moving back down when declared empty.

      To provide randomized starting positions for your game of life simulations, without sinning against Von Neumann, a vintage mahogany-clad Geiger-Müller counter would of course be included...
    • Re: (Score:1, Informative)

      by Anonymous Coward

      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 an

    • I'd imagine that, when you explain the concept of a Turing machine to someone, having a physical implementation like that, where all operations are explicit and obvious, might help.

  • by snarfies (115214) on Friday March 26, 2010 @12:39PM (#31629248) Homepage

    Hot Tub Turing Machine!

  • For social reasons I will refrain from mentioning this to my friends (which I have) later tonight. Baaaah, I want one! This is so pointless but nifty, my inner collector is crying out. Damn fiscal responsibilities in life tell me it's a waste of money, but oh, the geeky child inside cries out!
  • by John Hasler (414242) on Friday March 26, 2010 @12:47PM (#31629382) Homepage

    No relays. How sad.

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

    • And you'd be wrong.... Computers are Finite State Machines with an insane number of states.
      • by hoggoth (414195) on Friday March 26, 2010 @01:07PM (#31629754) Journal

        Incorrect. The keyboard, mouse, and audio input insure it is indeed a Turing machine with infinite input.

        • Re: (Score:3, Funny)

          Ensure. Unless you mean those input devices actually insure your computer. Maybe that was part of the health care bill?
          • Re: (Score:1, Funny)

            by Anonymous Coward

            From http://www.askoxford.com/concise_oed/insure

            insure

                  verb 1 arrange for compensation in the event of damage to or loss of (property, life, or a person), in exchange for regular payments to a company. 2 secure the payment of (a sum) in this way. 3 (insure against) protect (someone) against (a possible eventuality). 4 another term for ENSURE.

            You might want to pay attention to definition #4.

        • I would sure like to see your keyboard that has an infinite number of keys. There's a very important distinction between "practically infinite" and really infinite. A standard computer keyboard, not counting shift/ctrl/alt would have n! / (k! (n - k) !) or whatever the formula is, where ~105 is the number of keys on the keyboard.
          • by hoggoth (414195)

            Apparently my keyboard is a better model than yours. I can hit keys multiple times in any combination I like.

            • ...which still gives you a finite number of combinations as you could always have more combinations if you had one extra key.
              • by hoggoth (414195)

                You have a flawed understanding of 'infinity'.

                Infinity plus one is not greater than infinity.
                Neither is 'infinity and beyond'.

        • Re: (Score:3, Interesting)

          by LandruBek (792512)
          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.
  • Technically... (Score:5, Insightful)

    by Corporate Troll (537873) on Friday March 26, 2010 @12:48PM (#31629394) Homepage Journal
    Purely technically, a Turing Machine that hasn't infinite tapes is simply a Finite State Machine. You cannot build a "real" Turing Machine. Doesn't make his creation less interesting though :-)
    • Re:Technically... (Score:5, Interesting)

      by risk one (1013529) on Friday March 26, 2010 @01:29PM (#31630118)
      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: (Score:3, Interesting)

        by FrangoAssado (561740)

        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 th

        • by idontgno (624372)

          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.

          "Good news, guys, we've solved the halting problem [wikipedia.org]... only wrinkle is, it requires all the matter in the universe, and complete entropic heat death. Oh, and it doesn't really come up with a solution, it just halts."

    • by eclectro (227083)

      Purely technically, a Turing Machine that hasn't infinite tapes is simply a Finite State Machine.

      Then by extension, you could not program one either. So essentially all those Turing machines programmed in computers really aren't. The fact is, from the busy beaver's point of view, the Turing machine is real as long as you don't run out of tape. It perhaps would help this Turing machine if the reels of tape were larger (so it would not run out of tape before it halted). Of course, the more complex Turing machines will run out of tape (or exceed the limits of the computer!).

      I think the bigger flaw to this

      • by ebuck (585470)

        A Turing Machine is a mathematical model of computation. In any math model there may be an impedance mismatch between the model and it's translation to physical representation. The key is to make sure the mismatch only affects items which are not critical to the usefulness of the model.

        I agree that from a physical and practical point of view, this is a Turning Machine, because it is the best approximation of the model in physical form that anyone will be able to build.

    • Bureaucrat Corporate_Troll you are technically correct, the best kind of correct.

    • by Eowaennor (527108)
      Was anyone else reminded of this quote? "If, he thought to himself, such amachine is a virtual impossibility, then it must logically be a finite improbability. So all I have to do in order to make one, is to work out exactly how improbable it is, feed that figure into the finite improbability generator, give it a fresh cup of really hot tea ... and turn it on!"
    • by itsdapead (734413)

      I think what we have here is something that can implement a large subset of Turing machines (i.e. specific initial tape/state table combinations) but falls short of being a universal Turing machine because there will always be computable algorithms that it can't run because of (a) lack of tape or (b) tape melting due to the sun leaving the main sequence.

      My call would be that you can't have a physical implementation of a true universal Turing machine - because you need to be able to "run" a non-computable

  • A troll with mod points...

    As for the article though, this is really cool stuff. This machine would have fit right in on the set of Terry Gilliam's Brazil.
  • by aaaaaaargh! (1150173) on Friday March 26, 2010 @01:09PM (#31629792)

    A Turing machine is supposed to represent what an infinitely patient mathematician with no insight can achieve when he has an infinite amount of paper and pencils. Obviously, the infinity here poses some problems, but you can build a finite Turing machine by finding a mathematician that has no insights,giving him tranquilizers to make him more patient, and locking him into your basement with some food and papers and pencils.

    • by tool462 (677306)

      a mathematician that has no insights,giving him tranquilizers to make him more patient, and locking him into your basement with some food and papers and pencils.

      You just described every elementary school math class.

  • by HotNeedleOfInquiry (598897) on Friday March 26, 2010 @01:09PM (#31629810)
    The hardware is very elegant and well-done. The guy is a multi-talented geek of the highest order.
    • +1
    • What are the orders of geekhood and who ordains them? and which is the highest? Order of the Strong Pocket Protector? Order of Turing?
      • What are the orders of geekhood and who ordains them? and which is the highest?

        The Order of the Circular Slide Rule. I take it you haven't even got a straight one.
        Unkempt facial hair and dodgy personal hygiene just don't confer the same authority.

        • by ebuck (585470)
          You're getting into the upper ranks. Once you earn your first Circular Slide Rule, doors you never even knew existed start opening up for you. Try the Transcendental Hyper-Sphere Squared Quantum State Slide Rule. It's the same model used by Nuclear Scientists and NASA Physicists. Of course, immediately prior to use you need to calibrate it with three independent agencies to be dead on balls accurate. It's an industry term.
    • The video was very well done, too. I thought I was watching an episode of "How It's Made." It almost made me want to turn off adblock to give him some revenue... almost. ;)
    • True dat.
  • Until he installs an infitite tape, this is computationaly equivalent to a Finite Automata.
    • by vacarul (1624873)
      what about a tape in a loop? would that help?
    • by pz (113803)

      Until he installs an infitite tape, this is computationaly equivalent to a Finite Automata.

      If you're going to be pedantic, then get it right --- the machine is computationally equivalent to a finite automaton.

      What I find tickling about this implementation is the clear evidence of an embedded FSM emulating the programmed TM. Since the erase, write, and read portions of the head are physically displaced, the interpreter needs to shift the tape back and forth to execute a simple TM operation like "read symbol at current location" or "write a 1 at current location". Then, of course, there are the m

      • Re: (Score:3, Funny)

        by nitehawk214 (222219)

        If you replace every instance of "Finite State Machine" with "Flying Spaghetti Monster", the post sounds more like a religious discussion.

        • by idontgno (624372)
          The Truth is written by His Noodly Appendage. Holding a black dry-erase marker.
        • Nice to see religion come up on Slashdot and not be the topic of vociferous argument for once :) Like that one quote in a Hitchhiker's book about the religion of Everybody Should Stop Taking This Religion Thing So Seriously And Have A Pizza, or however it came out...I can't find it by a quick googling...
      • by radtea (464814) on Friday March 26, 2010 @02:38PM (#31631158)

        What I find tickling about this implementation is the clear evidence of an embedded FSM emulating the programmed TM.

        The Flying Spaghetti Monster is embedded in the programmed Transcendental Meditation?

        Proof of Intelligent Design!

    • by epine (68316)

      Until he installs an infinite tape, this is computationally equivalent to a Finite Automata.

      Welcome to theoretic physics. Hope you enjoy your career computing landscape probabilities over the 10^500 purported vacuum states. Bring lots of sharp pencils, you'll need them.

      Experimentally, this machine is indistinguishable from a real Turing machine until it whumps up against the end of the tape and the tape daemon refuses to splice a continuation tape. This is known as Fermat's procurement failure.

      Then again, there is no such thing as an observable distinction of a real Turing machine from a fake o

  • So does this technically pass the Turing test?
    • by slim (1652)

      I guess you were joking, but just for the benefit of any passing geek wannabes:

      The Turing Test (an "hard AI" concept) and the Turing Machine (a conceptual computer) are related only in that they were conceived by the same man. You don't need a Turing Machine to pass the Turing Test.

  • Having worked in recursion theory, my (mental) picture of a Turing Machine is a little different.

    The tape is vertical, and the head writes and reads from the side. The "state-transition table" is next

    O__________O
         ^
         !
    [          ]

    Stephan
    • by slim (1652)

      I'm sure with effort you could draw an ASCII art Turing machine that looks like goatse...

  • Yeah, but does it run Linux?

  • Should be finite.

    • Re: (Score:1, Interesting)

      by 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".
  • by the_other_chewey (1119125) on Friday March 26, 2010 @04:24PM (#31632750)
    Im impressed: For an infinite tape, the reels look very compact.
  • As Alan M. Turing himself wrote [alanturing.net] in his 1948 National Physical Laboratory report on Intelligent Machinery (transcript [oxfordjournals.org] from a law journal, of all places):

    It is possible to produce the effect of a computing machine by writing down a set of rules of procedure and asking a man to carry them out. Such a combination of a man with written instructions will be called a ‘Paper Machine.’ A man provided with paper, pencil and rubber, and subject to strict discipline is in effect a universal machine.

  • Maybe he can put my friend's annoying cat in a box that's rigged up to release a hammer that will shattering a vial of acid if a radioactive isotope decays. Though in practice, nothing will change. It seems like it simultaneously may or may not claw me at any given point. I can't see how it simultaneously being dead or alive will be any more or less predictable than its own capricious nature, with respect to being clawed.

  • “Home-Built Time Machine”?

    For a tiny moment there, my heart jumped. :/

  • A machine that can calculate anything, regardless of complexity? I, for one, welcome our new garage-built overlords.

It's a poor workman who blames his tools.

Working...