lhamey@mqccsunb.mqcc.mq.oz.au (Len Hamey) (08/13/90)
This discussion of real computers vs TMs is becoming a little convoluted. Am I missing something obvious or is Ken Preston? What is it about Turing Machines that says that they cannot be run for a long period of time performing many computations just like real computers? Clearly, the "input tape" of the Turing Machine is an abstraction of various components of a real computer. Thus, the output terminal (or the output port) may be viewed as a portion of the tape - writing to that portion of the tape causes the written characters to appear on the screen. SImilarly, the keyboard input corresponds to a portion of the tape (if time is not of importance, then the entire input stream can be collected and stored on tape in advance, else the input stream must be considered to be 'creating' the end of the tape as the computation progresses). Note that all real computers have physically limited storage, hence a mathematical limit on their states, so the actual compute engine is a finite state automaton -- the only thing that may be of unlimited size is the input stream and the output stream, and it is easy to see how these two streams can be stored on the TM tape in an interleaved form so that both streams may be infinite. Len Hamey len@mqcomp.mqcs.mq.oz.au
kenp@ntpdvp1.UUCP (Ken Presting) (08/31/90)
(This article is in reply to a posting received while I was on vacation) > kohout@cme.nist.gov (Robert Kohout) writes: >In article <620@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes: >>. . . when there is something on the >>tape besides "input", then the "output" is not a function of the "input". >>I hope that you can now agree that this is both obvious and trivial. >> >Imagine I have a non-deterministic TM that begins its computation by >writing a random string of data on its tape. It then uses this data , >along with its input to compute whatever its output will be. Since the >TM is non-deterministic, we can assume that this "random" number is, >in fact, whatever happens to be on the tape of your machine at the "start". >This TM will then compute whatever your machine computes. This is true, but notice that no deterministic TM can simulate the operation of writing a string of arbitrary length on a blank tape. The familiar equivalence between D and ND machines is stated in terms of the *functions* they can compute. If you wish, you may think of my claim as referring to non-deterministic TM's which do not compute functions. I defined "|=" as a relation between deterministic computations, but that does not imply that an equally useful concept cannot be defined in other terms. Recall that my intention was to define a formal concept with which to model systems whose output is not a function of their input. Non- deterministic TM's can have this property, so your suggestion is at least in the ball park. I would argue that my relational concept has a technical advantage, because it makes the weaker assumption that the content of the database is *arbitrary*, while you are assuming that the database is *random*. (This is perhaps a mere quibble) The important point is the non-equivalence of DTM's and NTM's, IN THIS CONTEXT. In the more familiar context of computing a function, there are no advantages in the use of non-determinism. But we are discussing a different context. We are concerned with devices which can generate new outputs for the same inputs (perhaps as a result of learning from experience). Finally, don't overlook the issue of cardinality. The set of paths defined for Determinstic machines by "|-", the state-change relation, is countable. For Non-deterministic machines, the set of paths is UNcountable. Similarly for the set of "chains" defined by "|=". There can be no isomorphism between sets of differing cardinality, so the concept of "|=" cannot be reduced to any deterministically definable relation. >4. What the sequence of input value is, I do not know, and I do not care. This is our main source of difficulty. The output of real computers is dependent on the past sequence of inputs, and this is exactly the phenomenon which concerns me. If it does not interest you, then we have no disagreement. One reason that change in output over time is important is simply, learning. I do not see any hope of defining "learning" in terms of machines which always produce the same output from a given input. So we have now two reasons for believing the "|=" relation to represent a useful concept, distinct from Turing computability: (1) it defines a set of non-denumerable cardinality, and (2) it can be used to represent a sequence of inputs (and thereby represent learning). >If you are saying that a real machine can accept its inputs in little >chunks, while a TM requires its input up front I maintain that this adds >nothing to the computing ability of the machine. Obviously, one could take >the entire input over the life of a real machine and encode it in some >fashion that could suffice to be the single, "initial" input of a TM. I agree that this is obvious, but it is relevant only in the context of machines which are used to compute functions. >I don't see how you can have it both ways. Either Church's thesis is incorrect, >or a RAM machine cannot do anything that a TM cannot do. Which is it? Let me immediately quash the idea that I am talking about RAM machines vs. TM's. I defined the "|=" relation entirely in terms of TM's. RAM machines are strictly irrelevant. >Perhaps it IS my reading, but you seem to be saying that no, you do not >dispute Church's Thesis, and here is a list of things that a computer can >do and a TM cannot. I have once claimed that nothing in your list is >beyond the capacity of a TM, and now you ask for me to substantiate this >claim. Is this not questioning my statement? And in questioning my assertion, >are you not also implying that you believe that a RAM machine has certain >capabilities which a TM does not? And does that not violate Church's Thesis? If by "Church's Thesis" we mean: Every effective procedure is representable as the operation of a deterministic TM then my proposal has no relationship to Church's thesis at all, because the |= relation does not represent an "effective procedure". For that matter, neither does your (isomorphic) suggestion of allowing an NTM to "guess" an arbitrarily long input string. "Waiting for input" and "guessing" are not finitary, effective, or reliable operations. Let me recal how we got into this issue. I said that Searle's main premise is a consequence of Tarski's theorem on the undefinability of truth. This theorem entails (via Church's thesis) that no effective procedure can be interpreted unambiguously as understanding the symbols it uses. "No problem" I say. Real computers are not always instances of effective procedures. So far, that is the whole story - a very short story. Searle's argument is sound if by computation we mean "effective procedure", and unsound otherwise. All that I am saying is that we each have, at our fingertips, a counter-example to Searle's assumption that all computation is reducible to effective procedures. Ken Presting ("Are we acquiring information yet?")
forbis@milton.u.washington.edu (Gary Forbis) (08/31/90)
I've been following this line for some time. Ken Presting made me think of an important difference between formal TMs and the day to day computation machines actually do. In article <628@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes: >> kohout@cme.nist.gov (Robert Kohout) writes: >... The output of real computers is >dependent on the past sequence of inputs, and this is exactly the >phenomenon which concerns me. ... >One reason that change in output over time is important is simply, learning. >I do not see any hope of defining "learning" in terms of machines which >always produce the same output from a given input. > >>If you are saying that a real machine can accept its inputs in little >>chunks, while a TM requires its input up front I maintain that this adds >>nothing to the computing ability of the machine. Obviously, one could take >>the entire input over the life of a real machine and encode it in some >>fashion that could suffice to be the single, "initial" input of a TM. (I am sorry if any feel I have condenced too much. I am trying to keep this article short and pnews requires and equal or greater amount of new text when compared to old text. This lengthens what would otherwise be a short reply to the context setting quoted material.) There is more to real machines than accepting input and producing output. In many cases there is a causal link between previous output and subsequent input. This is an additional reason that no real machine is equivalent to a single TM whose input stream is predetermined. If "the entire input over the life of a real machine" were encoded "in some fashion that could suffice to be the single, 'initial' input of a TM" it would not represent the causal link and as such would require some oracle to be defined. An example. A normal online application session involves separate create, inquiry, update, and delete functions. Unless the imput oracle knows the results of the create prior to actually doing it it cannot encode input for update which relies upon the output of the inquiry. Now I could chop the input into little chunks for each function but then carry some information as input to subsequent calls that are not normally considered part of the input stream (the part Ken is calling remembered.) --gary forbis@milton.u.washington.edu
weigand@kub.nl (Hans Weigand) (09/12/90)
Another difference between TMs and actual computers is in the real time constraints of the latter. For TMs, no speed is specified (it abstracts away from it). Hence for *practical* purposes, Turing equivalence is not very helpful. It is often overlooked that Church Thesis talks about effective functions, which is a mathematical idea (not a concept, it is not rigorously defined). It does not apply to biological processes such as eating or thinking. --- Hans Weigand Tilburg University (NL)