Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Home-Built Turing Machine

Soulskill posted more than 4 years ago | from the i'll-order-a-dozen dept.

Hardware Hacking 123

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

cancel ×

123 comments

Sorry! There are no comments related to the filter you selected.

Cool...I think. (2, Insightful)

Anonymous Coward | more than 4 years ago | (#31629206)

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

Why? (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31629294)

I'll tell you why - because the embrace Open Source Software. Nothing is more Open Source Software than building the hardware yourself, and this is *exactly* what terrifies Microsoft. Stuff like this chills them to the bone. All a Microsoftie could build from scratch would be a lightbulb connected to a battery, and even that probably wouldn't work properly and would be encumbered by DRM.

Re:Why? (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31629554)

How could a relatively simple machine like this scare Microsoft? If people want to build their own hardware and write their own software, that's great. But the hardware won't get to the point of being as complex and portable as hardware made by the larger corporations because they have the money and facilities to design new technologies and optimize the older ones.

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

91degrees (207121) | more than 4 years ago | (#31629304)

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

Dogtanian (588974) | more than 4 years ago | (#31632570)

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.

Re:Cool...I think. (2, Interesting)

thrawn_aj (1073100) | more than 4 years ago | (#31632482)

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

hmmm (3, Insightful)

Denihil (1208200) | more than 4 years ago | (#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 (4, Funny)

fuzzyfuzzyfungus (1223518) | more than 4 years ago | (#31629422)

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 (5, Interesting)

FooAtWFU (699187) | more than 4 years ago | (#31631240)

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 [rendell-attic.org] .

Re:hmmm (1)

nomel (244635) | more than 4 years ago | (#31631758)

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 (1)

TangoMargarine (1617195) | more than 4 years ago | (#31631962)

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.

Re:hmmm (1)

severoon (536737) | more than 4 years ago | (#31633308)

Am I the only one that's going to invoke rule 110 [wolframalpha.com] here?

Re:hmmm (1)

thrawn_aj (1073100) | more than 4 years ago | (#31632530)

Somewhere, a thousand geeks just simultaneously orgasm'd. (I would too, but I'm at work and it's generally frowned upon).

Re:hmmm (1, Informative)

Anonymous Coward | more than 4 years ago | (#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:hmmm (1)

shutdown -p now (807394) | more than 4 years ago | (#31631634)

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.

Know what I'm thinking? (4, Funny)

snarfies (115214) | more than 4 years ago | (#31629248)

Hot Tub Turing Machine!

This made me have a major geek moment. (4, Funny)

BlueKitties (1541613) | more than 4 years ago | (#31629358)

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!

Re:This made me have a major geek moment. (1)

The Flymaster (112510) | more than 4 years ago | (#31631490)

Pointless? It can do ANYTHING!

Re:This made me have a major geek moment. (1)

Bugamn (1769722) | more than 4 years ago | (#31631946)

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

"Parallax Propeller chip-based controller" (3, Funny)

John Hasler (414242) | more than 4 years ago | (#31629382)

No relays. How sad.

Re:"Parallax Propeller chip-based controller" (0)

Anonymous Coward | more than 4 years ago | (#31630698)

Yeah, yeah, and no wireless and less space than a Nomad. Turing-based computing will never catch on.

Re:"Parallax Propeller chip-based controller" (1)

Sulphur (1548251) | more than 4 years ago | (#31631370)

No relays. How sad.

Nice use of Spaceley Sprockets though.

I found that no one had ever actually built one (1, Interesting)

Threni (635302) | more than 4 years ago | (#31629392)

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

Re: I found that no one had ever actually built on (5, Insightful)

Corporate Troll (537873) | more than 4 years ago | (#31629432)

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

Re: I found that no one had ever actually built on (3, Insightful)

hoggoth (414195) | more than 4 years ago | (#31629754)

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

Re: I found that no one had ever actually built on (2, Funny)

CannonballHead (842625) | more than 4 years ago | (#31630530)

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 (1, Funny)

Anonymous Coward | more than 4 years ago | (#31630704)

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.

Re: I found that no one had ever actually built on (0)

Anonymous Coward | more than 4 years ago | (#31632424)

My, how apropos!

Re: I found that no one had ever actually built on (0)

Anonymous Coward | more than 4 years ago | (#31630540)

A turing machine has infinite memory.

Re: I found that no one had ever actually built on (0)

Anonymous Coward | more than 4 years ago | (#31630792)

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

Re: I found that no one had ever actually built on (0)

Anonymous Coward | more than 4 years ago | (#31631816)

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 (1)

hoggoth (414195) | more than 4 years ago | (#31632180)

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.

Re: I found that no one had ever actually built on (1)

TangoMargarine (1617195) | more than 4 years ago | (#31632062)

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.

Re: I found that no one had ever actually built on (1)

hoggoth (414195) | more than 4 years ago | (#31632130)

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

Technically... (5, Insightful)

Corporate Troll (537873) | more than 4 years ago | (#31629394)

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... (4, Interesting)

risk one (1013529) | more than 4 years ago | (#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:Technically... (2, Interesting)

FrangoAssado (561740) | more than 4 years ago | (#31630970)

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 [scottaaronson.com] )

Re:Technically... (0)

Anonymous Coward | more than 4 years ago | (#31631220)

So what you're really saying is this is an "Artificial" Mechanical Turk?

No wonder I'm meta-confused.

Re:Technically... (1)

idontgno (624372) | more than 4 years ago | (#31631768)

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

Re:Technically... (1)

eclectro (227083) | more than 4 years ago | (#31630292)

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.

Re:Technically... (1)

ebuck (585470) | more than 4 years ago | (#31632932)

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

just_another_sean (919159) | more than 4 years ago | (#31630336)

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

Re:Technically... (1)

Eowaennor (527108) | more than 4 years ago | (#31630722)

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

itsdapead (734413) | more than 4 years ago | (#31630874)

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!

You're Doing It Wrong (0)

slimjim8094 (941042) | more than 4 years ago | (#31629398)

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

Re:You're Doing It Wrong (3, Interesting)

noidentity (188756) | more than 4 years ago | (#31629544)

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 (5, Informative)

trurl7 (663880) | more than 4 years ago | (#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.

Re:You're Doing It Wrong (0)

slimjim8094 (941042) | more than 4 years ago | (#31629668)

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.

Re:You're Doing It Wrong (1)

xehonk (930376) | more than 4 years ago | (#31629984)

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 (5, Informative)

ircmaxell (1117387) | more than 4 years ago | (#31630028)

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:You're Doing It Wrong (1)

timeOday (582209) | more than 4 years ago | (#31630844)

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 (1)

radtea (464814) | more than 4 years ago | (#31630992)

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.

Re:You're Doing It Wrong (1)

sachamm (924766) | more than 4 years ago | (#31630676)

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.

bad moderation (2, Insightful)

Khashishi (775369) | more than 4 years ago | (#31629808)

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

Re:bad moderation (1)

mcgrew (92797) | more than 4 years ago | (#31631796)

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

Re:You're Doing It Wrong (1, Troll)

spribyl (175893) | more than 4 years ago | (#31629562)

That was my thought as well, shouldn't the program and data be on the tape.

All in the head? (3, Insightful)

s-gen (890660) | more than 4 years ago | (#31629604)

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.

Re:You're Doing It Wrong (2, Informative)

HateBreeder (656491) | more than 4 years ago | (#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.

New Math? (2, Funny)

Jason1729 (561790) | more than 4 years ago | (#31629886)

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

Re:New Math? (1)

ebuck (585470) | more than 4 years ago | (#31633058)

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

Re:You're Doing It Wrong (1)

sachamm (924766) | more than 4 years ago | (#31630538)

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?

How cute. (1)

Beelzebud (1361137) | more than 4 years ago | (#31629722)

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.

Turing Machine=Mathematician Without Insight (4, Funny)

aaaaaaargh! (1150173) | more than 4 years ago | (#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.

Re:Turing Machine=Mathematician Without Insight (1)

tool462 (677306) | more than 4 years ago | (#31630054)

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.

Setting aside the Turing stuff... (5, Insightful)

HotNeedleOfInquiry (598897) | more than 4 years ago | (#31629810)

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

Re:Setting aside the Turing stuff... (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31629908)

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

The circuits wasn't very elegant. BTW, why are we in bold?

Re:Setting aside the Turing stuff... (1)

Y Ddraig Goch (596795) | more than 4 years ago | (#31630672)

+1

Re:Setting aside the Turing stuff... (1)

Iamthecheese (1264298) | more than 4 years ago | (#31631430)

What are the orders of geekhood and who ordains them? and which is the highest? Order of the Strong Pocket Protector? Order of Turing?

Re:Setting aside the Turing stuff... (1)

AliasMarlowe (1042386) | more than 4 years ago | (#31631672)

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.

Re:Setting aside the Turing stuff... (1)

ebuck (585470) | more than 4 years ago | (#31633004)

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

Anonymous Coward | more than 4 years ago | (#31633202)

Not only is he a superb designer, he is a superb director. That video was beautifully made.

Re:Setting aside the Turing stuff... (1)

Danny Rathjens (8471) | more than 4 years ago | (#31633254)

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

Finite State Machine (1)

Jason1729 (561790) | more than 4 years ago | (#31629824)

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

Re:Finite State Machine (1)

vacarul (1624873) | more than 4 years ago | (#31630140)

what about a tape in a loop? would that help?

Re:Finite State Machine (1)

pz (113803) | more than 4 years ago | (#31630220)

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!

Re:Finite State Machine (2, Funny)

nitehawk214 (222219) | more than 4 years ago | (#31631048)

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

Re:Finite State Machine (1)

idontgno (624372) | more than 4 years ago | (#31631800)

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

Re:Finite State Machine (1)

TangoMargarine (1617195) | more than 4 years ago | (#31632196)

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

Re:Finite State Machine (3, Funny)

radtea (464814) | more than 4 years ago | (#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!

So what? (0, Funny)

Anonymous Coward | more than 4 years ago | (#31630072)

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? (0)

Anonymous Coward | more than 4 years ago | (#31630388)

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? (1)

drachenstern (160456) | more than 4 years ago | (#31631104)

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?

Re:Isn't this actually using three states? (2, Insightful)

quadelirus (694946) | more than 4 years ago | (#31631440)

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? (1)

chromas (1085949) | more than 4 years ago | (#31631720)

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

Turing tested and approved? (1)

OzPeter (195038) | more than 4 years ago | (#31630460)

So does this technically pass the Turing test?

The answer to the ultimate question... (0)

Anonymous Coward | more than 4 years ago | (#31630508)

Has it computed 42 yet?

Arrangement (1)

sugarmotor (621907) | more than 4 years ago | (#31630594)

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

Re:Arrangement (1)

slim (1652) | more than 4 years ago | (#31633320)

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

Obligatory (1)

Jeremi (14640) | more than 4 years ago | (#31630720)

Yeah, but does it run Linux?

Re:Obligatory (1)

John Hasler (414242) | more than 4 years ago | (#31631444)

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

Re:Obligatory (1)

AP31R0N (723649) | more than 4 years ago | (#31631566)

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

Re:Obligatory (1)

idontgno (624372) | more than 4 years ago | (#31631858)

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

Non-infinite (1)

AP31R0N (723649) | more than 4 years ago | (#31631426)

Should be finite.

Re:Non-infinite (1, Interesting)

Anonymous Coward | more than 4 years ago | (#31631990)

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 ! (0)

Anonymous Coward | more than 4 years ago | (#31631432)

Really Great Job !

So you haven't seen this? (2, Interesting)

Fjodor42 (181415) | more than 4 years ago | (#31631682)

Re:So you haven't seen this? (0)

Anonymous Coward | more than 4 years ago | (#31632276)

hahaha mod up!!

Beowulf cluster (1)

Conditioner (1405031) | more than 4 years ago | (#31631756)

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

I'm impressed (5, Funny)

the_other_chewey (1119125) | more than 4 years ago | (#31632750)

Im impressed: For an infinite tape, the reels look very compact.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>