blandy@lakshmi.cs.cornell.edu (Jim Blandy) (08/05/88)
In article <934@netxcom.UUCP> ewiles@netxcom.UUCP (Edwin Wiles) writes: >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. Oh dear. Should this really be discussed here? I'd move this to another newsgroup, but I'm not sure this debate is interesting enough; it's kind of old-hat. Follow-ups through mail, please? Yes, you're right. Because they have infinite memory, Turing machines are more powerful than current computers. Nonetheless, they are still used to model the capabilities of computers. In reality, since any computer has a fixed amount of storage (including disk storage), it has only a finite (big, but finite) number of different states. Thus, it can actually be modeled by a DFA (Deterministic Finite Automaton). But that's not an interesting thing to work with. Why? Because DFAs are incapable of doing things like parsing and type-checking, simple arithmetic, etc. unless you put a fixed limit on the length of the program or the precision of the arithmetic. But one isn't interested in proving things about limited architectures; one wants to be able to prove that no architecture will ever be able to solve a certain problem. A DFA-based argument can prove statements like: "No computer with this particular memory size can solve this problem." So what? Add more memory. With TM-based arguments, we can prove things like: "No computer will ever be able to solve this problem, no matter what the memory size." The latter kind is more interesting; thus, we use TMs. When we reason about what a computer can do, we want a general argument, not one that assumes a certain memory size. >Also, solving certain problems requires the TM to 'fork' (make copies >of itself, which take the alternate path, or paths). Okay. You're talking about non-deterministic algorithms, where one gives the TM a choice of courses to take; the theory is that the TM will always 'guess' the correct path to take. But it's guaranteed that any non-deterministic TM can be simulated by a normal TM. The normal TM may solve the problem much more slowly, but the power is the same. Note that any problem requiring infinite space also requires infinite time. Can a TM requiring infinite space (i.e., taking advantage of its unlimited memory) be truly said to 'solve' the problem? It'll never stop and give you the answer... A computer can do anything a TM can do, if one insists that the TM must halt and that the computer has sufficient memory. My simulation will not handle non-deterministic Turing machines. :-) -- Jim Blandy - blandy@crnlcs.bitnet "And now," cried Max, "let the wild rumpus start!"
harper@oravax.UUCP (Doug Harper) (08/05/88)
In article <19965@cornell.UUCP>, blandy@lakshmi.cs.cornell.edu (Jim Blandy) writes: > A computer can do anything a TM > can do, if one insists that the TM must halt and that the computer has > sufficient memory. Parsing English is always treacherous, but my first reading of the above can be semi-formalized as: (1) There is a computer D, with a large memory, such that for any halting TM computation C, D can perform C. This is a bit too strong to be true. No doubt, the intended parsing corresponds to: (2) For any halting TM computation C, there is a computer D, with a large memory, such that D can perform C. -- arpa: oravax!harper@cu-arpa.cs.cornell.edu uucp: {allegra,rochester}!cornell!oravax!harper Tel: (607) 277-2020 ext. 257 USMail: Odyssey Research Associates/301A Harris B. Dates Dr./Ithaca, NY 14850
smryan@garth.UUCP (Steven Ryan) (08/06/88)
>Oh dear. Should this really be discussed here? I'd move this to >another newsgroup, but I'm not sure this debate is interesting enough; >it's kind of old-hat. Follow-ups through mail, please? > >Yes, you're right. Because they have infinite memory, Turing machines Before you drop it, get the facts straight. Turing machines have unbounded not infinite memory. The only way a Turing machine can write an infinite tape is in infinite time, in which case it is busted. > But it's guaranteed >that any non-deterministic TM can be simulated by a normal TM. The >normal TM may solve the problem much more slowly, but the power is the >same. I'm not so sure, but I don't feel like looking it up. I suspect a nondeterministic machine can navigate through a partial function by making good guesses while a backtracking deterministic machine might blunder into a computational blackhole. Or maybe not.
lee@uhccux.uhcc.hawaii.edu (Greg Lee) (08/06/88)
From article <1164@garth.UUCP>, by smryan@garth.UUCP (Steven Ryan): " " > But it's guaranteed " >that any non-deterministic TM can be simulated by a normal TM. The " >normal TM may solve the problem much more slowly, but the power is the " >same. " " I'm not so sure, but I don't feel like looking it up. I suspect a Any non-deterministic finite automaton can be simulated by a deterministic one... Could we have a reference for the case of TMs? Greg, lee@uhccux.uhcc.hawaii.edu