blandy@awamore.cs.cornell.edu (Jim Blandy) (08/03/88)
I see now that I should have shar'ed them together. Sorry. Next time. Since a certain well-known Amiga hacker has told me he doesn't know what a Turing machine is, I guess they're not as well-known as I thought they were. I thought that maybe a short explanation would help make my other posting that much more interesting. Saving bandwidth by making it useful, or something... This is an explanation of Turing machines to accompany my DME Turing machine simulator. Suppose you wanted to prove a theorem about what kind of calculations an Amiga could or could not do. The Amiga's a complicated machine, a real pain in the neck to prove anything about. Even if you succeeded, you would only have proved it about your Amiga with your hardware running your software. You'd have to do it all over again for a VAX. So a TM is a VERY SIMPLE computer, simple enough to write proofs about, but powerful enough to do anything any computer can do. It's been proven already that anything a TM can do, a computer can do, and vice versa. A TM reads from and writes to a tape; depending on what state it's in and what character is under its read/write head, it 1) writes a new character, 2) moves the tape head right or left one space, and 3) goes into a new state. This repeats until the TM hits a character it doesn't know what to do with. Programming a TM consists of telling it what it should do in a particular state on a particular character; you tell it when to stop by letting it crash, as described above. Note that the tape has a left end, but is infinitely long to the right; everything to the right of the characters on the tape is filled with blanks. For example, suppose you wanted your TM to evaluate an expression. You'd program the TM, put the expression on the tape, and start it up. Most likely the TM would use the blank tape after the expression for intermediate results. The TM would work back and forth for a while, and when it finished, it would leave the answer on the tape. The two sample TMs included with the program show typical strategies for solving simple problems; some approaches are more complicated... Have fun. I thought enough people might find it amusing to make it of general interest. -- Jim Blandy - blandy@crnlcs.bitnet "And now," cried Max, "let the wild rumpus start!"
ewiles@netxcom.UUCP (Edwin Wiles) (08/03/88)
In article <19918@cornell.UUCP> blandy@cs.cornell.edu (Jim Blandy) writes: > >So a TM is a VERY SIMPLE computer, simple enough to write proofs >about, but powerful enough to do anything any computer can do. It's >been proven already that anything a TM can do, a computer can do, and >vice versa. HOLD IT! I'm not that far out of college (3 yrs), but I remember quite clearly that TM's are a *super-set* of current computing technology. i.e. If a computer can do it, a TM can do it. But it is not necessarily true that if a TM can do it, a computer can do it. (Quite often it is true, but not always.) As 'proof' for this: If a problem requires infinite memory, or infinite processors, it *can* be solved by a TM, but not by any existant computer. (I know I'm stating this poorly, but that's the gist of it.) The idea being that the 'tape' a TM uses stretches into infinity, and there is no way for a computer to "stretch into infinity". Also, solving certain problems requires the TM to 'fork' (make a copies of itself, which take the alternate path, or paths). Since a TM is purely imaginary, it can do this indefinitely. Standard hardware, even the heavy-duty parallel processors, have a *finite* number of processors. And before you start talking about virtual memory, and other such tricks, let me remind you that you will still run into limits. Like how much addressing space do you have? And, How much disk space do you have to store the virtual machines that don't happen to be running right now? And where do you store the results of all this computation? On paper created from all the trees now in existence? :-) If anyone is heavily interested, I'll dig out my textbook and produce a more detailed/correct answer. Or, at the very least, tell you the title of the text so that you can study it yourself. Enjoy! -- ...!hadron\ "Who?... Me?... WHAT opinions?!?" | Edwin Wiles ...!sundc\ Schedule: (n.) An ever changing | NetExpress Comm., Inc. ...!pyrdc\ nightmare. | 1953 Gallows Rd. Suite 300 ...!uunet!netxcom!ewiles | Vienna, VA 22180
david@ms.uky.edu (David Herron -- One of the vertebrae) (08/04/88)
In article <19918@cornell.UUCP> blandy@cs.cornell.edu (Jim Blandy) writes: >So a TM is a VERY SIMPLE computer, simple enough to write proofs >about, but powerful enough to do anything any computer can do. It's >been proven already that anything a TM can do, a computer can do, and >vice versa. The equivalence doesn't work in both directions. TM's have an infinite amount of memory available to them whereas physical computers do not. Therefore there is a significant class of problems which can only be solved by TM's, or rather by theoretical machines as opposed to physical machines. Other than this little point everything you said is true enough. If I wanted to be that picky I'd point out that TM's halt when they halt, not when they "see a character they don't know how to deal with". That is, they reach an accepting state ... but this is a minor technical point unlike the point in the previous paragraph. Ok, now you've proved that DME is no more powerful than vi. You need to send this TM simulator off to comp.sources.misc so that it will be able to keep the TM simulator for vi company :-). -- <---- David Herron -- The E-Mail guy <david@ms.uky.edu> <---- ska: David le casse\*' {rutgers,uunet}!ukma!david, david@UKMA.BITNET <---- <---- Looking forward to a particularly blatant, talkative and period bikini ...