Home-Built Turing Machine

Cool...I think. by Anonymous Coward · 2010-03-26 05:37 · Score: 2, Insightful

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. by 91degrees · 2010-03-26 05:42 · Score: 4, Insightful

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
Re:Cool...I think. by thrawn_aj · 2010-03-26 09:07 · Score: 2, Interesting

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 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.
Re:Cool...I think. by Dogtanian · 2010-03-26 09:13 · Score: 1

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.

--
"Slashdot - News and Chat Sites Deviant". (Click "homepage" link above for details).
Re:Cool...I think. by 91degrees · 2010-03-26 11:01 · Score: 1

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:Cool...I think. by epee1221 · 2010-03-26 11:25 · Score: 2, Informative

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 use-mention distinction" is not "enforced here."
Re:Cool...I think. by ricosalomar · 2010-03-29 01:28 · Score: 1

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..
Re:Cool...I think. by thrawn_aj · 2010-03-29 09:04 · Score: 1

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) - it's just under 7 pounds (not lbs. right? lol). The used hardcover (US site - another marketplace seller) is from $15 (go figure) here - http://www.amazon.com/gp/offer-listing/0671492071/ref=dp_olp_1

Happy reads!
Re:Cool...I think. by ricosalomar · 2010-03-29 09:29 · Score: 1

Thx
Re:Cool...I think. by ricosalomar · 2010-03-29 09:32 · Score: 1

Thanks for the info!
Never saw the movie, though I doubt a love story between Turing and Winslet would work out so well ;)

hmmm by Denihil · 2010-03-26 05:38 · Score: 3, Insightful

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.

--
WÌÌfÍ--ÍSÌÒÍ...Í...ÌHÌÍfÍÍÍ--ÍÍÍ

Re:hmmm by fuzzyfuzzyfungus · 2010-03-26 05:49 · Score: 4, Funny

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:hmmm by FooAtWFU · 2010-03-26 07:44 · Score: 5, Interesting

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.

--
The World Wide Web is dying. Soon, we shall have only the Internet.
Re:hmmm by Anonymous Coward · 2010-03-26 07:53 · Score: 1, Informative

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:hmmm by shutdown+-p+now · 2010-03-26 08:10 · Score: 1

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.
Re:hmmm by nomel · 2010-03-26 08:18 · Score: 1

There really needs to be some sort of mod point emergency reserve...I would break the hermetic seal for you, kind sir.
Also, your comment, for some reason, reminds me of most Javascript code that I've seen...
Re:hmmm by TangoMargarine · 2010-03-26 08:33 · Score: 1

We just had a talk about Turing machines at my university, and I just have to say that that looks flippin' awesome, especially considering that it allegedly actually computes something! Unfortunately I have no mod points.

--
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
Re:hmmm by thrawn_aj · 2010-03-26 09:10 · Score: 1

Somewhere, a thousand geeks just simultaneously orgasm'd. (I would too, but I'm at work and it's generally frowned upon).
Re:hmmm by severoon · 2010-03-26 10:11 · Score: 1

Am I the only one that's going to invoke rule 110 here?

--
but have you considered the following argument: shut up.

Know what I'm thinking? by snarfies · 2010-03-26 05:39 · Score: 4, Funny

Hot Tub Turing Machine!

Re:Know what I'm thinking? by Anonymous Coward · 2010-03-26 10:39 · Score: 0

You win. Good day sir.
Re:Know what I'm thinking? by Anonymous Coward · 2010-03-26 11:35 · Score: 0

Turing himself would have approved! The then British government didn't so much..

This made me have a major geek moment. by BlueKitties · 2010-03-26 05:46 · Score: 4, Funny

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!

--
"Sorrow is better than laughter, for by sadness of face the heart is made glad." [Ecclesiastes 7:3]

Re:This made me have a major geek moment. by The+Flymaster · 2010-03-26 08:00 · Score: 1

Pointless? It can do ANYTHING!
Re:This made me have a major geek moment. by Bugamn · 2010-03-26 08:32 · Score: 1

It can do anything that is computable. It can not compute if something is computable, however.

"Parallax Propeller chip-based controller" by John+Hasler · 2010-03-26 05:47 · Score: 3, Funny

No relays. How sad.

--
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.

Re:"Parallax Propeller chip-based controller" by Anonymous Coward · 2010-03-26 07:07 · Score: 0

Yeah, yeah, and no wireless and less space than a Nomad. Turing-based computing will never catch on.
Re:"Parallax Propeller chip-based controller" by Sulphur · 2010-03-26 07:53 · Score: 1

No relays. How sad.
Nice use of Spaceley Sprockets though.
Re:"Parallax Propeller chip-based controller" by 517714 · 2010-03-26 10:41 · Score: 1

No relays Hell! I want steam!

--
The US government have made it clear that we have no inalienable rights; any we do not defend vigorously will be taken.

I found that no one had ever actually built one by Threni · 2010-03-26 05:48 · Score: 1, Interesting

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

Technically... by Corporate+Troll · 2010-03-26 05:48 · Score: 5, Insightful

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... by risk+one · 2010-03-26 06:29 · Score: 4, Interesting

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... by eclectro · 2010-03-26 06:40 · Score: 1

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 machine is that the machine is not made to look like a cute furry beaver.

--
Take the cheese to sickbay, the doctor should see it as soon as possible - B'Elanna Torres, "Learning Curve"
Re:Technically... by just_another_sean · 2010-03-26 06:42 · Score: 1

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

--
Creationist Textbook Stickers Declared Unconstitutional by CowboyNeal
Re:Technically... by Eowaennor · 2010-03-26 07:09 · Score: 1

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!"
Re:Technically... by itsdapead · 2010-03-26 07:20 · Score: 1

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 algorithm "to completion" in order to prove that it used infinite tape or infinite steps (of course, with an abstract Turing machine you'd do it analytically, in the same way that you can use math to add up all the numbers in an infinite series, rather than empirically).
Notwithstanding: hail the Ubergeek. This is sooooooo cool! Pointlessness only adds to its coolness!

--
In a survey of 100 programmers, 111111 thought that duck-typing was a good idea.
Re:Technically... by FrangoAssado · 2010-03-26 07:26 · Score: 2, Interesting

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)
Re:Technically... by Anonymous Coward · 2010-03-26 07:42 · Score: 0

So what you're really saying is this is an "Artificial" Mechanical Turk?
No wonder I'm meta-confused.
Re:Technically... by idontgno · 2010-03-26 08:19 · Score: 1

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

--
Welcome to the Panopticon. Used to be a prison, now it's your home.
Re:Technically... by ebuck · 2010-03-26 09:39 · Score: 1

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.
Re:Technically... by Anonymous Coward · 2010-03-26 10:32 · Score: 0

'The statistical likelihood,' continued the autopilot primly, 'is that other civilizations will arise. There will one day be lemon-soaked paper napkins. Till then there will be a short delay. Please return to your seat.'

You're Doing It Wrong by slimjim8094 · 2010-03-26 05:48 · Score: 0

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

The point of a real Turing machine is that the logic is emergent from the individually-useless instructions on the tape. This is interesting from a hardware perspective, but in this instance the tape itself isn't the program - it's all the microcontroller

--
I have developed a truly marvelous proof of this comment, which this signature is too narrow to contain.

Re:You're Doing It Wrong by noidentity · 2010-03-26 05:56 · Score: 3, Interesting

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 by trurl7 · 2010-03-26 05:56 · Score: 5, Informative

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.
Re:You're Doing It Wrong by spribyl · 2010-03-26 05:57 · Score: 1, Troll

That was my thought as well, shouldn't the program and data be on the tape.
Re:You're Doing It Wrong by HateBreeder · 2010-03-26 06:00 · Score: 2, Informative

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". that's it.

--
Sigs are for the weak.
Re:You're Doing It Wrong by slimjim8094 · 2010-03-26 06:02 · Score: 0

No, I'm right. He says the micro's job is to read and write to the tape, and perform the simple steps as instructed by the tape.
That's fine, and that's cool. But it's not a Turing machine; it's a Turing machine emulator. I could write a program on my computer, feed it a virtual "tape" and do the same thing. It'd only be following the directions on the 'tape', but it'd be an interpreter.
This is a very cool interpreter. But it's not a Turing machine.

--
I have developed a truly marvelous proof of this comment, which this signature is too narrow to contain.
Re:You're Doing It Wrong by xehonk · 2010-03-26 06:20 · Score: 1

The microcontroller is used to implement the action table of the turing machine. Nowhere in the description of a turing machine does it say how those transition rules are to be implemented.
Re:You're Doing It Wrong by ircmaxell · 2010-03-26 06:23 · Score: 5, Informative

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

--
If a man isn't willing to take some risk for his opinions, either his opinions are no good or he's no good
Re:You're Doing It Wrong by ircmaxell · 2010-03-26 06:25 · Score: 3, Interesting

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

--
If a man isn't willing to take some risk for his opinions, either his opinions are no good or he's no good
Re:You're Doing It Wrong by sachamm · 2010-03-26 06:56 · Score: 1

The duality between data and program is one of the fundamental concepts of computer science. The Turing machine is a program that runs another program. The outer program encodes the (simple, encodable) rules of the Turing machine, and was originally intended to be a human with unlimited paper and pencil. The inner program is the tape. Ask yourself this: what would this machine do without a tape?
Re:You're Doing It Wrong by sachamm · 2010-03-26 07:06 · Score: 1

This is a very cool interpreter. But it's not a Turing machine.
A Turing machine is an interpreter. It interprets the code on the tape.
Imagine it was a human instead. This human is given a list of rules (a program) to follow. Then we give the human the tape (a program) and we tell him to follow the rules. That is a Turing machine, and that is what we have here, encoded into an actual machine instead of a list of rules. I think what you are missing is that the list of rules that the human is given is encoded as a program on the microcontroller. This is exactly what one expects from a Turing machine made into an actual machine.
Re:You're Doing It Wrong by timeOday · 2010-03-26 07:18 · Score: 1

I agree, although for the sake of appearances, it would be cool if the finite state machine portion were hard-coded to implement a universal turing machine, and the only programmability was the starting contents of the tape.
Re:You're Doing It Wrong by radtea · 2010-03-26 07:28 · Score: 1

I agree, although for the sake of appearances, it would be cool if the finite state machine portion were hard-coded to implement a universal turing machine, and the only programmability was the starting contents of the tape.
It would be more than cool--it would be actually demonstrate Turing's remarkable core insight. As it is, this a very clever micro-controller implementation of a programmable finite state machine that uses a long tape as an book-keeping device. He says in the description, "In a way the tape is the computer" but this is false. The programmable finite state machine in the micro-controller is a the computer.
The tape in this machine isn't doing any computing at all. It is just helping the finite state machine along. Turing's core insight was that you can get rid of the finite state machine and just have the tape, and a very simple set of universal rules. Implement those on a non-programable finite state machine and you've have, as you point out, a universal Turing machine where all the programability is in the initial number written on the tape. That would be mind-blowingly cool.
This is cool, but falls well short of mind-blowingly so.

--
Blasphemy is a human right. Blasphemophobia kills.
Re:You're Doing It Wrong by jwdb · 2010-03-26 11:30 · Score: 1

Turing's core insight was that you can get rid of the finite state machine and just have the tape, and a very simple set of universal rules.

Do you mean to say that a true universal turing machine has a fixed state transition table regardless of what the desired program was, and that programming is done solely by setting the initial tape? Having the program contained solely in the tape and manipulated with a fixed universal rule set, and still be able to program anything so to speak, would indeed be amazing.
Did Turing ever specify that simple set of universal rules?

Re: I found that no one had ever actually built on by Corporate+Troll · 2010-03-26 05:50 · Score: 5, Insightful

And you'd be wrong.... Computers are Finite State Machines with an insane number of states.

All in the head? by s-gen · 2010-03-26 05:59 · Score: 3, Insightful

A turing machine isn't just the head and the tape, its those things plus a state transition table. The microcontroller is doing the state transition table part.

How cute. by Beelzebud · 2010-03-26 06:05 · Score: 1

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.

Re: I found that no one had ever actually built on by hoggoth · 2010-03-26 06:07 · Score: 3, Insightful

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

--
- For the complete works of Shakespeare: cat /dev/random (may take some time)

Turing Machine=Mathematician Without Insight by aaaaaaargh! · 2010-03-26 06:09 · Score: 4, Funny

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.

Re:Turing Machine=Mathematician Without Insight by tool462 · 2010-03-26 06:25 · Score: 1

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.

bad moderation by Khashishi · 2010-03-26 06:09 · Score: 2, Insightful

It looks like some berserk moderators got in here. Why all the troll mods?

Re:bad moderation by mcgrew · 2010-03-26 08:21 · Score: 1

It's OK, the sane mods overruled the idiots. He's at +5 now. The system works!

--
Free Martian Whores!

Setting aside the Turing stuff... by HotNeedleOfInquiry · 2010-03-26 06:09 · Score: 5, Insightful

The hardware is very elegant and well-done. The guy is a multi-talented geek of the highest order.

--
"Eve of Destruction", it's not just for old hippies anymore...

Re:Setting aside the Turing stuff... by Y+Ddraig+Goch · 2010-03-26 07:06 · Score: 1

+1

--
Meddle thou not in the affairs of Dragons, for thou art crunchy and with most anything.
Re:Setting aside the Turing stuff... by Iamthecheese · 2010-03-26 07:57 · Score: 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?

--
If video games influenced behavior the Pac Man generation would be eating pills and running away from their problems.
Re:Setting aside the Turing stuff... by AliasMarlowe · 2010-03-26 08:13 · Score: 1

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.

--
Those who can make you believe absurdities can make you commit atrocities. - Voltaire
Re:Setting aside the Turing stuff... by ebuck · 2010-03-26 09:43 · Score: 1

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.
Re:Setting aside the Turing stuff... by Anonymous Coward · 2010-03-26 09:59 · Score: 0

Not only is he a superb designer, he is a superb director. That video was beautifully made.
Re:Setting aside the Turing stuff... by Danny+Rathjens · 2010-03-26 10:04 · Score: 1

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. ;)
Re:Setting aside the Turing stuff... by FrankDrebin · 2010-03-27 10:23 · Score: 1

True dat.

--
Anybody want a peanut?

Finite State Machine by Jason1729 · 2010-03-26 06:10 · Score: 1

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

Re:Finite State Machine by vacarul · 2010-03-26 06:31 · Score: 1

what about a tape in a loop? would that help?
Re:Finite State Machine by pz · 2010-03-26 06:35 · Score: 1

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 much more complicated portions of the FSM that perform optical character recognition, or actuate the marker to draw a zero or one symbol (too cool!). Still, a very, very nifty machine, and quite a creative solution to the problem of an erasable tape that is human and machine readable at the same time!

--

Put my fist through my alarm clock with its ding-dong death inside my ear. - The Blackjacks.
Re:Finite State Machine by nitehawk214 · 2010-03-26 07:33 · Score: 2, Funny

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

--
I'm a good cook. I'm a fantastic eater. - Steven Brust
Re:Finite State Machine by radtea · 2010-03-26 07:38 · Score: 3, Funny

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!

--
Blasphemy is a human right. Blasphemophobia kills.
Re:Finite State Machine by idontgno · 2010-03-26 08:22 · Score: 1

The Truth is written by His Noodly Appendage. Holding a black dry-erase marker.

--
Welcome to the Panopticon. Used to be a prison, now it's your home.
Re:Finite State Machine by TangoMargarine · 2010-03-26 08:47 · Score: 1

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

--
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF
Re:Finite State Machine by epine · 2010-03-26 10:14 · Score: 1

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 one, since it takes an infinite amount of time to observe that the tape in infinite in length.
Even if the universe had formed with a doubly-infinite tape stretching across the cosmic vastness, cosmic expansion will eventually stretch your tape faster than you can read it.
It's an interesting physics problem what happens if you have an infinite string at constant tension (with a uniform mass of so many grams/meter) what happens when you severe it into a pair of singly-infinite tapes. Hmmm, you probably have to work with tension in N/m^2 (cross section) and you still get problems with infinite acceleration at the end points until you make some assumptions about the force structure and take relativistic force propagation into account.
Of course, you don't want to hang around when a pair of Vogon infinite-tape splice ships converge with the severed ends in tow, especially if you cut between syllables of their favourite Vogon haiku. Your hang-time margin of survival is determined by the unknown universal constant Vogons/linear parsec.

New Math? by Jason1729 · 2010-03-26 06:14 · Score: 2, Funny

Wow...where can I buy a Turing-complete microcontroller?

Re:New Math? by ebuck · 2010-03-26 09:46 · Score: 1

Skeptical look.... Is this micro-controller made with real bits of Turing?

So what? by Anonymous Coward · 2010-03-26 06:26 · Score: 0, Funny

I'm using a Turing machine to make this post right now. What's the big deal?

Mine's faster, too.

Isn't this actually using three states? by Anonymous Coward · 2010-03-26 06:46 · Score: 0

Isn't this actually using three states? 1, 0, and blank tape? It should put a 1 for 1 and leave a blank for 0...

Re:Isn't this actually using three states? by drachenstern · 2010-03-26 07:36 · Score: 1

Actually that's a great question, and I'm curious about that too, except I think that the answer is if we consider voltage states. Technically there's three states that a signal could be in, which are {off, on, neither} where the third state is easier to illustrate if I can use voltages instead. Let's say that instead of off and on we consider nearly zero (demonstrated as 0) volts for off (makes sense, right?), five volts for on and then a third state where we're neither at 5V or 0V, say 2.5V.
Surely it's reasonable that there might exist a 2.5V in this pattern, right? For instance, if we're traveling from 0V to 5V, we must pass through 2.5V. I forget now the cases where a digital circuit can easily have 2.5V when it seems like it must have only either 0 or 5, but I recall it's quite normal. I think it has something to do with not having a direct ground always attached, the floating ground moves into 2.5V range.
So because of this, it's possible for a gate to exist in any of three states. That's the blank slot indicated on the tape. Think of it as a Heisenberg spot.
Now, who can tell me what I got wrong here?

--
2^3 * 31 * 647
Re:Isn't this actually using three states? by quadelirus · 2010-03-26 07:58 · Score: 2, Insightful

I believe the 1, 0 and blank are the characters of the TM's alphabet, not the states. The states are internal to the machine and there can be quite a lot of them depending on what the program is to accept the TM's language.
Re:Isn't this actually using three states? by chromas · 2010-03-26 08:16 · Score: 1

Blank tape is unformatted media. Please run mkfs.tm first.

Turing tested and approved? by OzPeter · 2010-03-26 06:51 · Score: 1

So does this technically pass the Turing test?

--
I am Slashdot. Are you Slashdot as well?

Re:Turing tested and approved? by slim · 2010-03-26 19:04 · Score: 1

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.

The answer to the ultimate question... by Anonymous Coward · 2010-03-26 06:53 · Score: 0

Has it computed 42 yet?

Re: I found that no one had ever actually built on by CannonballHead · 2010-03-26 06:55 · Score: 2, Funny

Ensure. Unless you mean those input devices actually insure your computer. Maybe that was part of the health care bill?

Re: I found that no one had ever actually built on by Anonymous Coward · 2010-03-26 06:56 · Score: 0

A turing machine has infinite memory.

Arrangement by sugarmotor · 2010-03-26 06:59 · Score: 1

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

--
http://stephan.sugarmotor.org

Re:Arrangement by slim · 2010-03-26 10:11 · Score: 1

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

Re: I found that no one had ever actually built on by Anonymous Coward · 2010-03-26 07:08 · Score: 1, Funny

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.

Obligatory by Jeremi · 2010-03-26 07:09 · Score: 1

Yeah, but does it run Linux?

--

I don't care if it's 90,000 hectares. That lake was not my doing.

Re:Obligatory by John+Hasler · 2010-03-26 07:58 · Score: 1

Not until someone writes a Gcc backend that produces tapes for it.

--
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
Re:Obligatory by AP31R0N · 2010-03-26 08:06 · Score: 1

Yes, but only on a Beowulf cluster of them in Soviet Russia. YMMV.

--
Utilizing the synergization of benchmark e-solutions to pre-workaround action items!
Re:Obligatory by idontgno · 2010-03-26 08:27 · Score: 1

In Soviet South Korea, only Beowulf clusters of electromechanical Turing Machines use old people.

--
Welcome to the Panopticon. Used to be a prison, now it's your home.

Re: I found that no one had ever actually built on by Anonymous Coward · 2010-03-26 07:13 · Score: 0

wtf. A turing machine doesn't need infinite input, just infinite memory.

Non-infinite by AP31R0N · 2010-03-26 07:57 · Score: 1

Should be finite.

--
Utilizing the synergization of benchmark e-solutions to pre-workaround action items!

Re:Non-infinite by Anonymous Coward · 2010-03-26 08:34 · Score: 1, Interesting

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

Great Job ! by Anonymous Coward · 2010-03-26 07:58 · Score: 0

Really Great Job !

So you haven't seen this? by Fjodor42 · 2010-03-26 08:13 · Score: 2, Interesting

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

--
"The number you have dialed is imaginary. Please rotate your phone 90 degrees and try again."

Re:So you haven't seen this? by Anonymous Coward · 2010-03-26 08:52 · Score: 0

hahaha mod up!!

Beowulf cluster by Conditioner · 2010-03-26 08:18 · Score: 0

Imagine a Beowulf cluster of there... it wouldn't amount to much =/

Re: I found that no one had ever actually built on by Anonymous Coward · 2010-03-26 08:23 · Score: 0

Well. Your are very optimistic about the life expectancy of your hardware, including yourself.

I offer you an experiment. Stay below your computer, manipulating the keyboard and the mouse, and listening to your favorite music. Me or my successors will come back in 80 years to check if the input is still "infinite".

Agreed? Lets begin.

Re: I found that no one had ever actually built on by TangoMargarine · 2010-03-26 08:39 · Score: 1

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.

--
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF

Re: I found that no one had ever actually built on by hoggoth · 2010-03-26 08:44 · Score: 1

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

--
- For the complete works of Shakespeare: cat /dev/random (may take some time)

Re: I found that no one had ever actually built on by hoggoth · 2010-03-26 08:46 · Score: 1

I will bequeath my computer to my heirs along with instructions to enter new data every... let's say 108 minutes.
As parts break they will have to replace them in time for the next input.
See you in 80 years.

--
- For the complete works of Shakespeare: cat /dev/random (may take some time)

Re: I found that no one had ever actually built on by Anonymous Coward · 2010-03-26 09:04 · Score: 0

My, how apropos!

I'm impressed by the_other_chewey · 2010-03-26 09:24 · Score: 5, Funny

Im impressed: For an infinite tape, the reels look very compact.

Re: I found that no one had ever actually built on by LandruBek · 2010-03-26 11:55 · Score: 2, Interesting

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.

--
$META_SIG_JOKE

Turing on using human computer as 'Paper Machine': by D4C5CE · 2010-03-26 19:57 · Score: 1

As Alan M. Turing himself wrote in his 1948 National Physical Laboratory report on Intelligent Machinery (transcript 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.

Re: I found that no one had ever actually built on by TangoMargarine · 2010-03-26 20:43 · Score: 1

...which still gives you a finite number of combinations as you could always have more combinations if you had one extra key.

--
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF

His next project? by Arterion · 2010-03-27 13:19 · Score: 1

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.

--
"That which does not kill us makes us stranger." -Trevor Goodchild

Did anyone else read that as: by Hurricane78 · 2010-03-27 17:30 · Score: 1

“Home-Built Time Machine”?

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

--
Any sufficiently advanced intelligence is indistinguishable from stupidity.

Calculate anythihng? by Modern+Primate · 2010-03-28 19:20 · Score: 1

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

Re: I found that no one had ever actually built on by hoggoth · 2010-03-29 02:02 · Score: 1

You have a flawed understanding of 'infinity'.

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

--
- For the complete works of Shakespeare: cat /dev/random (may take some time)

Re: I found that no one had ever actually built on by TangoMargarine · 2010-03-29 05:50 · Score: 1

Exactly my point. I've been saying all along that it is NOT infinity. You aren't listening.

--
Unity? Screw that: XFCE. Slashdot Beta? Screw that: SoylentNews. Australis? Screw that: Pale Moon. UX developers DIAF

Re: I found that no one had ever actually built on by elfprince13 · 2010-03-30 00:49 · Score: 1

It needs neither. It needs finite, but unbounded, memory.

123 comments