A Universal Turing Machine In 100 Punchcards

← Back to Stories (view on slashdot.org)

A Universal Turing Machine In 100 Punchcards

Posted by timothy on Friday June 22, 2012 @02:50AM 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."

48 comments

Just to be pedantic by the_humeister · 2012-06-22 02:56 · Score: 0, Redundant

This is not a universal Turing machine, since those things are impossible in this universe. Not even humans are universal Turing machines.
1. Re:Just to be pedantic by K.+S.+Kyosuke · 2012-06-22 03:11 · 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
2. Re:Just to be pedantic by tendays · 2012-06-22 03:55 · 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).
3. Re:Just to be pedantic by Anonymous Coward · 2012-06-22 04:46 · Score: 0
  
  Sea kelp.
LEGO Turing machine by wisebabo · 2012-06-22 03:01 · 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.
1. Re:LEGO Turing machine by Em+Adespoton · 2012-06-22 07:54 · Score: 1
  
  That means one of the requirements should be a 3D printer... I seem to recall that someone made one out of LEGO.
Linear bounded automaton by tepples · 2012-06-22 03:02 · Score: 4, Insightful

But what is possible is a universal linear bounded automaton, and that's what physically realized Turing machines become.
Wow you couldn't even read the summary? by Anonymous Coward · 2012-06-22 03:04 · 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 · 2012-06-22 04:29 · 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.
irony of Alan's death by peter303 · 2012-06-22 03:07 · 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 · 2012-06-22 03:27 · Score: 0, Flamebait
  
  AIDS?
2. Re:irony of Alan's death by Anonymous Coward · 2012-06-22 03:40 · 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.
3. Re:irony of Alan's death by Anonymous Coward · 2012-06-22 03:52 · Score: 1
  
  Wait a minute ... Balmer's gay?
4. Re:irony of Alan's death by Anonymous Coward · 2012-06-22 04:11 · Score: 0
  
  Please don't compare people who have actually done stuff like Alan Turing to management jobs that any idiot is qualified for.
  Correction: That any idiot believes to be qualified for. If we had less idiots in those places, the world would be a better place.
5. Re:irony of Alan's death by samkass · 2012-06-22 04:16 · Score: 1
  
  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?
  One would hope nothing... didn't the guy deserve a lifelong vacation by that point?
  
  --
  E pluribus unum
6. Re:irony of Alan's death by samkass · 2012-06-22 04:17 · Score: 1
  
  Whoosh... someone utterly misses the point.
  
  --
  E pluribus unum
7. Re:irony of Alan's death by Anonymous Coward · 2012-06-22 04:24 · Score: 0
  
  When robots take over the planet and sink Britain into the sea, a voice will be heard shouting "Turing is avenged!"
8. Re:irony of Alan's death by camperdave · 2012-06-22 06:48 · Score: 1
  
  Wait a minute ... Balmer's gay?
  Explains a lot, doesn't it?
  
  --
  When our name is on the back of your car, we're behind you all the way!
9. Re:irony of Alan's death by DerekLyons · 2012-06-22 06:58 · Score: 1
  
  What would Alan had given us with another 20 years?
  Hard to tell. In his latter years, he went wandering off down all kinds of intellectual paths. He might have produced great things, he might have produced mediocre things, he might have produced nothing of use at all.
10. Re:irony of Alan's death by Em+Adespoton · 2012-06-22 07:58 · Score: 1
  
  Hmm... did Turing really die, or was that a Dalek coverup?
11. Re:irony of Alan's death by Anonymous Coward · 2012-06-22 13:21 · Score: 0
  
  Oh come on, this was funny.
Bravo! Good Job! by LifesABeach · 2012-06-22 03:12 · Score: 1

I would be very interested in how you made what you made.
Just Like on American Dad by eldavojohn · 2012-06-22 03:19 · Score: 1

I would be very interested in how you made what you made.
I as well am very impressed and tip my hat in amazement. However, as I watched the video and then went to his page and started trying to understand how this would communicate with his mechanical bus, I couldn't help but wonder if he had consumed vast amounts of Cougar Boost.

--
My work here is dung.
seems fair by Thud457 · 2012-06-22 03:42 · 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 Immerman · 2012-06-22 08:58 · Score: 1
  
  Probably because until quite recently most computers were single-purpose or hardware-programmable (i.e. you'd need to rewire it to do something different). An orerry, astrolabe, or pocket calculator are all examples of non-programmable computers - they perform useful computations, quite complex ones in the case of a high-quality orerry, but are inherently special-purpose. Turing's insight was that the operation of the machine could itself be controlled by input data, making it a general-purpose machine theoretically capable of performing any arbitrary computational task without hardware modification or human intervention. Remove the program store and it's just a bunch of parts. I challenge you to find any general-purpose computer capable of operating without RAM or external storage, it can't be done. Just because a component is modular and replaceable does not make it any less integral to the whole.
  You have to remember that words haven't always meant what they do now - "computer" for example originally referred to a person employed to perform calculations, and a researcher in the mathematical sciences might employ a roomful of them to perform complex calculations in a reasonable amount of time. However humans occasionally make mistakes, which could be extremely costly if it occurred early in a calculation and/or went undetected, thus the early interest in calculating machines.
  
  --
  --- Most topics have many sides worth arguing, allow me to take one opposite you.
2. Re:seems fair by theclockworkcomputer · 2012-06-22 09:33 · 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.
Enough! by elsurexiste · 2012-06-22 03:52 · 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!
1. Re:Enough! by Anonymous Coward · 2012-06-22 03:55 · Score: 0
  
  Don't be mad just because he was a fanny bandit.
2. Re:Enough! by Anonymous Coward · 2012-06-22 04:04 · Score: 0, Troll
  
  You forget that Alan Turing himself though he was doing something wrong. You might try to rewrite history, extend your imagination to say it was not despicable. But it was and thanks to the pro-gay movement today we have enough STDs and broken families. There is zero - nothing at all - usefull or interesting about this person for today's cryptography. Just move on!
3. Re:Enough! by tool462 · 2012-06-22 04:05 · Score: 1
  
  I thought his problems came about specifically because of his distaste for fannies...
4. Re:Enough! by Anonymous Coward · 2012-06-22 04:20 · Score: 0
  
  Lol. You're dumb.
5. Re:Enough! by Anonymous Coward · 2012-06-22 04:30 · Score: 0
  
  Don't be coming here trying to impress us with your "Queen's English".
6. Re:Enough! by Anonymous Coward · 2012-06-22 04:36 · Score: 0
  
  But it was and thanks to the pro-gay movement today we have enough STDs and broken families. There is zero - nothing at all - usefull or interesting about this person for today's cryptography. Just move on!
  Really? Your that simple minded. Maybe you think, he thought he was doing something wrong because the world was filled with people like you a hundred years ago, much less the stigma religion gives in general. Which BTW he denounced religion so I seriously doubt he believed that.
  As for STDs you have a lot more things in life to blame for that than gays, crack a book sometime. Oh sorry you're probably from Texas where they don't teach things like that anymore.
7. Re:Enough! by Anonymous Coward · 2012-06-22 04:48 · Score: 0
  
  No, he LOOOOOOVED fannies. Just not your Aunt Fanny. Turing was an unabashed pervert.
8. Re:Enough! by dissy · 2012-06-22 11:02 · Score: 1
  
  Now, can we talk about what's relevant? Like TFA?
  You must be new here ;}
  Realizing there is no chance anyone will read TFA, let alone discuss it, personally I would just be happy if the homophobes would crawl back under their rocks and let the important off topic discussions continue!
Infinite Legos - Blame the Cheap Parents by Dareth · 2012-06-22 03:53 · Score: 1

Nah, it is cheap parents who will not pay for them with their infinite incomes.

--

I only look human.
My mother is a halfling and my dad is an ogre, so that makes me an Ogreling
No excuse. by John+Hasler · 2012-06-22 04:05 · Score: 1

Finite tape -> state machine.

--
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
BZZZT! troll harder... by Anonymous Coward · 2012-06-22 04:16 · Score: 0

pro-gay movement...broken families
Why isn't divorce as socially repugnant?
schematic by theclockworkcomputer · 2012-06-22 04:59 · Score: 4, Interesting

For who is interested here is a schematic of the machine
1. Re:schematic by LifesABeach · 2012-06-22 09:41 · Score: 1
  
  I saw the youtube site. My first thought was what software was used to make the "mechanical" visual. Possibly Blender3D?
2. Re:schematic by theclockworkcomputer · 2012-06-22 10:20 · Score: 1
  
  Hi. NX7.5 animation and motion (at work in the weekends). A 2001 version of Rhino to model and animate the leafs. Gimp to past the leafs into the animation. Inkscape to render the titles. Audacity to edit the sound. Blender to convert the stills to avi and add the sound.
How beautiful! by Muad'Dave · 2012-06-22 05:01 · 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.
+1 cool by Fubari · 2012-06-22 06:07 · Score: 2

I wish there was a way to add "Likes" to articles, this one deserves a +1 cool.
Next year the wil be... by Anonymous Coward · 2012-06-23 04:15 · Score: 0

101 years ago, the day after tommorrow, etc etc