Slashdot Mirror

← Back to Stories (view on slashdot.org)

A Universal Turing Machine In 100 Punchcards

Posted by timothy on from the animation-to-blow-your-mind dept.

New submitter theclockworkcomputer writes "100 years ago tomorrow, Alan Turing was born. To celebrate, I wrote a Universal Turing Machine in 100 Punchcards. I've uploaded a video to explain a small part of the read head (the Jacquard). One needle is shown out of a total of 28. As this is about a program for a Turing Machine and not about a Turing Machine itself, I hope to be excused from the requirement of infinite tape."

14 of 48 comments (clear)

  1. LEGO Turing machine by wisebabo · · Score: 2

    www.youtube.com/watch?v=cYw2ewoO6c4

    I'm not sure if the plans are available anywhere but since (I think) it's built off a standard MindStorms LEGO set anyone should be able to recreate it.

    I understand, however, that LEGO will be unable to provide an infinite number of bricks that are needed for full implementation.

  2. Linear bounded automaton by tepples · · Score: 4, Insightful

    But what is possible is a universal linear bounded automaton, and that's what physically realized Turing machines become.

  3. Wow you couldn't even read the summary? by Anonymous Coward · · Score: 4, Informative

    This is not a universal Turing machine, since those things are impossible in this universe. Not even humans are universal Turing machines.

    Right. And from excessively short summary:

    As this is about a program for a Turing Machine and not about a Turing Machine itself, I hope to be excused from the requirement of infinite tape.

    1. Re:Wow you couldn't even read the summary? by itsdapead · · Score: 2

      Right. And from excessively short summary:

      As this is about a program for a Turing Machine and not about a Turing Machine itself, I hope to be excused from the requirement of infinite tape.

      His finite Turing machine ran out of tape before he got that far. Those things really are bloody useless for web browsing.

      --
      In a survey of 100 programmers, 111111 thought that duck-typing was a good idea.
  4. irony of Alan's death by peter303 · · Score: 4, Interesting

    He was hounded into dangerous therapies because of his sexual orientation. Now the largest computer company in the world is run by a gay man. What would Alan had given us with another 20 years?

    1. Re:irony of Alan's death by Anonymous Coward · · Score: 2, Interesting

      Please don't compare people who have actually done stuff like Alan Turing to management jobs that any idiot is qualified for.

  5. Re:Just to be pedantic by K.+S.+Kyosuke · · Score: 2

    This is not a universal Turing machine, since those things are impossible in this universe. Not even humans are universal Turing machines.

    Unless you require a Turing machine to be infinitely fast, you will never be able to scan the whole physical tape, so an infinite virtual tape should be an adequate replacement, or did I get it wrong?

    --
    Ezekiel 23:20
  6. seems fair by Thud457 · · Score: 2

    He provides the Turing Machine emulator, you provide the infinitely long tape.
    Why exactly is program store considered to be an integral part of the definition? On all practical computers, that's an interchangeable external part.

    --

    the preceding comment is my own and in no way reflects the opinion of the Joint Chiefs of Staff

    1. Re:seems fair by theclockworkcomputer · · Score: 2

      A Turing Machine is comprised of a tape, a wheel, a read/write head and a control. The program on the website is merely the rule table inside the control. The Jacquard and some other parts of the clockwork computer, of which also a schematic exists can be regarded as a the missing parts minus the tape. There is no actual tape, but the program thinks the memory of the computer is the tape and uses that. The memory has only 12 nibbles of storage, but at 12 punchcards per minute, it takes hours before it runs out of memory. By then everyone is already to bed. Reading the comments, I think few get that the animation is really about a mechanical computer, not about a Turing Machine.

  7. Enough! by elsurexiste · · Score: 2

    Can the word "Turing" be mentioned in a Slashdot submission without some random guy bringing up his sexual orientation?

    Everyone knows the story, it has been denounced and publicly acknowledged and an official "I'm sorry" was told. I welcomed those events and moved on. The meme, alas, persists. Even Simon Wiesenthal said something like "We can't pretend there weren't deaths in the holocaust, but we can't think about it all the time".

    Now, can we talk about what's relevant? Like TFA?

    --
    I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!
  8. Re:Just to be pedantic by tendays · · Score: 5, Informative

    Indeed. Turing machines don't require infinite tapes, they require unbounded tapes. In particular the initial state of the tape must contain at most a finite number of non-blank cells. Working with a finite tape is therefore fine as long as you are ready to enlarge it when the head reaches the boundary (so that, to the machine, it appears infinite). In the same sense, a physical computer could act as a Turing machine if, when it runs out of memory, an operator could come and plug in an extra hard drive (and if memory addresses were made in a way that they can be arbitrarily large).

  9. schematic by theclockworkcomputer · · Score: 4, Interesting

    For who is interested here is a schematic of the machine

  10. How beautiful! by Muad'Dave · · Score: 3, Insightful

    Wow. Regardless of the geek cred you get for making such a beast, let me commend you on the sheer artistic beauty of your website and the video. Just wow.

    --
    Tiller's Rule: Never use a word in written form that you've only heard and never read. You will end up looking foolish.
  11. +1 cool by Fubari · · Score: 2

    I wish there was a way to add "Likes" to articles, this one deserves a +1 cool.