biep@klipper.UUCP (J. A. "Biep" Durieux) (11/01/85)
[] The problem in the discussion in that nobody has stated clearly which equivalence relation he is using. Psycholinguistics has found that humans can search their memory in < log n time, n being the number of items. Turing machines clearly can not do better than order n time. Proof that humans are not Turing machines. (Note I took an equivalence relation which did look at time.) Now take the equivalence relation "true(x, y)", and it is equally clear that anything is equivalent to a Turing machine. The reason math has done so well for the last so many years is, that they have provided us with a set of equivalence relations which left out anything math couldn't deal with. So, using those (normally only implicitly used) relations, any real world pheno- menon turned out to be equivalent to some mathematical model. There are many aspects of reality which are not easily modelled mathematically, and the result has not been that mathematical models have been abandoned, but often that the existence of those aspects has been denied. For those who look at the reality from a mathematical point of view, there will be a mathematical model for the human mind for every equivalence relation they can think of; for those who look at mathematics from reality, there will never be such a model for any equivalence relation *they* can think of. Notes: 1) Before you flame me: yes, I have a masters of mathematics. 2) At the moment a human says he is equivalent to a model he has thought out, he is like a correctness proving program that is saying it has proven itself correct 3) Now first start discussing the form of your equivalence relation, that is much more productive. Mathematicians, don't get angry if the other guy's relation is not mathematizable! Success in learning to understand each other's point of view! -- Biep. {seismo|decvax|philabs|garfield|okstate}!mcvax!vu44!biep Is the difference between a difference of degree and a differ- ence of sorts a difference of degree or a difference of sorts?
ins_apmj@jhunix.UUCP (Patrick M Juola) (11/03/85)
In article <509@klipper.UUCP> biep@klipper.UUCP (J. A. "Biep" Durieux) writes: > Psycholinguistics has > found that humans can search their memory in < log n time, n > being the number of items. Turing machines clearly can not do > better than order n time. Proof that humans are not Turing machines. I'm sure that a Turing machine can search its memory faster than order n : all it would have to do is store the stuff in its memory in some sort of order. I'm thinking specifically of the structure called a binary tree, where everything in the right sub-tree is > the root and the left is < the root. Program the machine to start at some designated root (call it position 1) on the tape. If the item to be searched for is < position n, shift left (for example) to position n*2. If the item is >, shift left to position n*2+1. This, on the average, will find any item in memory in log(base 2)n comparisons, and you've still got an infinite amount of tape to the right for storage of other items. Any EE/CS majors out there, feel free to totally trash my program, but I think a valid algorithm could be designed. Any data structure that would let you perform a binary search would work, and I would be *fascinated* by a proof that no such structure exists. (Yes, J.A., that was a challenge :-) Pat Juola Johns Hopkins Univ. Dept of Maths.
peter@graffiti.UUCP (Peter da Silva) (11/03/85)
> [] > The problem in the discussion in that nobody has stated clearly > which equivalence relation he is using. Psycholinguistics has > found that humans can search their memory in < log n time, n How could they do this? Do you store n items in an otherwise virgin mind and do the search? I can't see how you could possibly prove this, but in any case: > being the number of items. Turing machines clearly can not do > better than order n time. Proof that humans are not Turing machines. > (Note I took an equivalence relation which did look at time.) This does not preclude the possibility that humans are <n> turing machines executing in parallel. If each item has such a machine attached (not unreasonable) then the search can complete in unit time: all that you need is to broadcast the description to all the machines (hey, who has X?). -- Name: Peter da Silva Graphic: `-_-' UUCP: ...!shell!{graffiti,baylor}!peter IAEF: ...!kitty!baylor!peter
mangoe@umcp-cs.UUCP (Charley Wingate) (11/03/85)
In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: >> Psycholinguistics has >> found that humans can search their memory in < log n time, n >> being the number of items. Turing machines clearly can not do >> better than order n time. Proof that humans are not Turing machines. > I'm sure that a Turing machine can search its memory faster than order >n : all it would have to do is store the stuff in its memory in some sort of >order. I'm thinking specifically of the structure called a binary tree, >where everything in the right sub-tree is > the root and the left is < the >root. Program the machine to start at some designated root (call it >position 1) on the tape. If the item to be searched for is < position n, >shift left (for example) to position n*2. If the item is >, shift left to >position n*2+1. This, on the average, will find any item in memory in >log(base 2)n comparisons, and you've still got an infinite amount of tape >to the right for storage of other items. Unfortunately, this fails to work because in Turing machines, it is the number of *steps* which costs you; each step from one cell to the next costs at least on step. Now there are two cases to consider: 1) Suppose we can make the comarison without having to return to a reference value (which is reasonable for a small enough range of values). Then it's clear that the tree search is indeed order(n); since it will take K shifts to get to the Kth position, no matter what. 2) Suppose we do have to return to a reference value that is an extra M units away, and it takes F*(M+K) to make a comparison with an element at position K (i.e., we have to make that many "passes" between the two). For the sequential search this is clearly O(N**2). For the tree version, we get something like FM+F(M+2)+F(M+4)+ ... F(M+K/2) which is FMlogK+FK giving us O(N). The reason why we get these unusual results is that ordinarily the costs of seeking are negligible. In this case, they are quite important. Nevertheless, the original "proof" is still flawed. The brain is quite obviously not a turing machine; on the other hand, neither are current computers. The important question is whether or not it can be modelled by a turing machine. Considering performance, this little "proof" tends one to believe that it can't; but ignoring performance, this "proof" gets us nowhere. Charley Wingate
edwards@uwmacc.UUCP (mark edwards) (11/04/85)
In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: >In article <509@klipper.UUCP> biep@klipper.UUCP (J. A. "Biep" Durieux) writes: >> Psycholinguistics has >> found that humans can search their memory in < log n time, n >> being the number of items. Turing machines clearly can not do >> better than order n time. Proof that humans are not Turing machines. > > I'm sure that a Turing machine can search its memory faster than order >n : all it would have to do is store the stuff in its memory in some sort of >order. I'm thinking specifically of the structure called a binary tree, where >everything in the right sub-tree is > the root and the left is < the root. >Program the machine to start at some designated root (call it position 1) on >the tape. If the item to be searched for is < position n, shift left (for >example) to position n*2. If the item is >, shift left to position n*2+1. >This, on the average, will find any item in memory in log(base 2)n comparisons, >and you've still got an infinite amount of tape to the right for storage of >other items. > Pat Juola While your premise is true for simple data forms, it breaks done as the complexity goes up. Namely semantic concepts vs a simple binary number search. This is not to say that I support the log n vs n search times. There are many other attributes on which to search. One such would be a picture (A picture is worth a thousand words). This is not to say that a turing machine can not do it, only it can not do it today.(tomorrow ?) The brain has a highly parallel interconnected architecture. Each neuron has 100 to 10000 other neurons connected to it. This means after 3 cycles using the low figure 1000000 neurons can be activated (in parallel). While the computer will have only 3 things done (what ever that means). Granted that the computer is much faster (100 to 1000 x ?) th brain still has it beat because of parallelism. Scientific America says that there are 10 to the 10 or 11 neurons in the brain. If only a tenth of these are used the brain still has a large magnitude more memory then a modern processor has. mark =============================================================== Flame away
amb@duke.UUCP (A. Michael Berman) (11/05/85)
In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: >In article <509@klipper.UUCP> biep@klipper.UUCP (J. A. "Biep" Durieux) writes: >> Psycholinguistics has >> found that humans can search their memory in < log n time, n >> being the number of items. Turing machines clearly can not do >> better than order n time. Proof that humans are not Turing machines. > > I'm sure that a Turing machine can search its memory faster than order >n : all it would have to do is store the stuff in its memory in some sort of >order. I'm thinking specifically of the structure called a binary tree, where >everything in the right sub-tree is > the root and the left is < the root. ... >This, on the average, will find any item in memory in log(base 2)n >comparisons, Three comments: 1. re the original comment: the question of whether a Turing machine can compute something is normally separated from its complexity. If we could build a Turing machine that simulated human intelligence at any speed, then the presumption would surely be that we could bring it 'up to speed'. (The suggestion in another note for parallel Turing machines, for example, might be a way to do it.) In fact, a Turing machine tends to be a slow way to do most operations, which leads to the next comment: 2. True, if you count comparisons, a binary search takes log n time (worst case too, not just on average). However, while comparison counting is a reasonable method of analysis on the computation model called a RAM, or Random Access Machine (which more closely models modern computers than does a Turing Machine), it is the wrong metric to use with a TM. Clearly the time for a TM to compute something is proportional to the number of tape squares processed. Thus we can't avoid counting all the work moving back and forth. In fact, the lower bound for searching on a TM is O(n). 3. A RAM can search memory in O(1) expected time, by using hashing. (Can your brain do better?) The question 'can a TM think' could just as well be 'can a RAM think'; since a TM can simulate a RAM and vice versa, the questions are equivalent, modulo the time of computation. The TM is the more traditional formulation. Mike Berman, Duke University
franka@mmintl.UUCP (Frank Adams) (11/05/85)
In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: >In article <509@klipper.UUCP> biep@klipper.UUCP (J. A. "Biep" Durieux) writes: >> Psycholinguistics has >> found that humans can search their memory in < log n time, n >> being the number of items. Turing machines clearly can not do >> better than order n time. Proof that humans are not Turing machines. A human mind has a finite limit on the amount of information it can store. If you put an upper limit on the amount of information, searching only takes a finite amount of time. The behavior of algorithms with small amounts of data does not necessarily resemble their limiting behavior. > I'm sure that a Turing machine can search its memory faster than order >n : all it would have to do is store the stuff in its memory in some sort of >order. I'm thinking specifically of the structure called a binary tree, where >everything in the right sub-tree is > the root and the left is < the root. >Program the machine to start at some designated root (call it position 1) on >the tape. If the item to be searched for is < position n, shift left (for >example) to position n*2. If the item is >, shift left to position n*2+1. >This, on the average, will find any item in memory in log(base 2)n >comparisons, >and you've still got an infinite amount of tape to the right for storage of >other items. By definition, a Turing machine can only move left or right one frame at a time. You can't find the data in less than O(t) time because you can't get to it any faster than that. (To be a little more formal, the total information potentially available in time t is O(t). A binary search requires potential access to O(2**t) information.) >Any data structure that would let >you perform a binary search would work, and I would be *fascinated* by a proof >that no such structure exists. (Yes, J.A., that was a challenge :-) Is that proof fascinating? I thought not. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
franka@mmintl.UUCP (Frank Adams) (11/05/85)
In article <2081@umcp-cs.UUCP> mangoe@umcp-cs.UUCP (Charley Wingate) writes: > 2) Suppose we do have to return to a reference value that is an extra M > units away, and it takes F*(M+K) to make a comparison with an element > at position K (i.e., we have to make that many "passes" between the > two). For the sequential search this is clearly O(N**2). For the tree > version, we get something like > > FM+F(M+2)+F(M+4)+ ... F(M+K/2) which is > > FMlogK+FK giving us O(N). > >The reason why we get these unusual results is that ordinarily the costs of >seeking are negligible. In this case, they are quite important. This would be correct if you really had to return to the orignal value. You don't; you drag it along with you. I.e., you keep a single copy of the search value near the Turing machine head. When you move to the next element, you swap the search value with the last value looked at. This algorithm is technically O(N*K), where K is the size of the objects being searched for; it is customary to ignore this last factor. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
breuel@h-sc1.UUCP (thomas breuel) (11/06/85)
>In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: >>> Psycholinguistics has >>> found that humans can search their memory in < log n time, n >>> being the number of items. Turing machines clearly can not do >>> better than order n time. Proof that humans are not Turing machines. >> I'm sure that a Turing machine can search its memory faster than order >>n : all it would have to do is store the stuff in its memory in some sort of >>order. I'm thinking specifically of the structure called a binary tree, where > While your premise is true for simple data forms, it breaks done as > the complexity goes up. Namely semantic concepts vs a simple binary > number search. This discussion is non-sense. Whether the time complexity of a problem on a Turing machine is equal to the time complexity of a problem on any other (abstract) machine is utterly irrelevant to whether the mind 'is a Turing machine' or not. The comparison of time complexities breaks down even between different kinds of Turing machines (single- vs multitape, although they are polynomially related). What you really want to know is whether the human brain is 'Turing equivalent'. I think with fair certainty it can be said that it is not, in the same sense that a general purpose computer is *not* Turing equivalent: both don't have infinite memory. Both are much more accurately captured by the notion of a finite state machine. (This is, of course, not to say that the use of Turing machines tells us nothing about computation in computers or the brain, just that one has to be careful as to how far the similarities go). Thomas.
hes@ecsvax.UUCP (Henry Schaffer) (11/06/85)
> In article <1096@jhunix.UUCP> ins_apmj@jhunix.ARPA (Patrick M Juola) writes: > > >> Psycholinguistics has > >> found that humans can search their memory in < log n time, n > >> being the number of items. Turing machines clearly can not do > >> better than order n time. Proof that humans are not Turing machines. > > > I'm sure that a Turing machine can search its memory faster than order n > > Unfortunately, this fails to work because in Turing machines, it is the > number of *steps* which costs you; each step from one cell to the next costs > at least on step. > > Nevertheless, the original "proof" is still flawed. The brain is quite > obviously not a turing machine; on the other hand, neither are current > computers. The important question is whether or not it can be modelled by a > turing machine. Considering performance, this little "proof" tends one to > believe that it can't; but ignoring performance, this "proof" gets us > nowhere. > > Charley Wingate The usual concept is the "modelled" aspect, with performance speed quite specifically excepted. Let me quote from a handy reference (Encyclopedia of Computer Science and Engineering 2/e Ralston & Reilly, eds, p. 1542) "... one can show that any computer can be simulated (albeit rather slowly) by a Turing machine." and "Since a Turing machine can simulate any computing device, it follows that anything that cannot be computed on a Turing machine cannot by computer at all. The fact that there are such unsolvable problems motivated Turing to devise his abstract machine." Following this path, the rephrased question is "Can the mind be modelled by a Turing machine?", and it can't be answered by showing speed differences -- but it could by showing that the mind can "compute" something that a Turing machine can't. (Vice-versa isn't possible, because it is evident that the mind can simulate a Turing machine.) --henry schaffer n c state univ
andrews@yale.ARPA (Thomas O. Andrews) (11/07/85)
In article <702@ecsvax.UUCP> hes@ecsvax.UUCP (Henry Schaffer) writes: >Following this path, the rephrased question is "Can the mind be modelled >by a Turing machine?", and it can't be answered by showing speed >differences -- but it could by showing that the mind can "compute" >something that a Turing machine can't. (Vice-versa isn't possible, because >it is evident that the mind can simulate a Turing machine.) >--henry schaffer n c state univ Is it so evident that a mind can emulate a Turing machine? Even a mind with access to paper cannot necessarily emulate a Turing machine. A Turing machine theoretically has perfect, infinite memory. One thing a Turing machine cannot be is interactive in any sane sense of the world. It starts with a fixed set of inputs at time zero. This doesn't allow for a conversation, say. It may be able to respond to a questions, but it cannot ask questions in a simple way, and expect an answer. This would involve changing the values on a tape. What about interactive turing machines? Two turing machines "discussing something." This would involve an entirely new system - one in which each turing machine could write on blank squares of any other turing machine, but could not read the strip of any turing machine but it's own. This would mirror our communications. On the other hand, this pair of turing machines can be computed, and hence can be computed by a single turing machine - in fact whole thousands of "communication turing machines" could be represented in one Turing machine! Scizo-Turing devices! But if we get Billions and Billions of these turing devices together, and have them talk at each other, we could easily get something as complicated as the human brain (er, I think.) For instance, if we have one turing machine that behaves somewhat the way a neuron does, we could create a hoarde of them and set the machine(s) rolling. I'm not making myself clear, am I? I think I'll go to sleep. But first, a brief flame: Someone said something to the effect that "at the moment, Turing machines are not capable of ..." What the hell does 'at the moment' mean when talking about an abstract concept. After define a Turing machine, what it can do and what it can't do is defined, too. "At the moment, we do not know whether a Turing machine can ..." It is mathematically illiterate and bad thinking to interpret our inability as a deficiency in the machine. Since there are things we *know* turing machines can't do, it is best to be careful when talking about "current limits" of our own knowledge. Good night. Oh, and by the way, any more polar bear problems, and I think I'll kill someone. I didn't know there were so many high school students on the net. -- Thomas Andrews "Gosh, I used to know how to do that." Favorite excuse of engineers
biep@klipper.UUCP (J. A. "Biep" Durieux) (11/07/85)
I wrote (in a context which subsequent respondents left out): >>>> Psycholinguistics has >>>> found that humans can search their memory in < log n time, n >>>> being the number of items. Turing machines clearly can not do >>>> better than order n time. Proof that humans are not Turing machines. [some people commented on this, which they shouldn't have done because it was very much besides the point I was making (see below) ] In article <718@h-sc1.UUCP> breuel@h-sc1.UUCP (thomas breuel) writes: >This discussion is non-sense. Whether the time complexity of a problem >on a Turing machine is equal to the time complexity of a problem on any >other (abstract) machine is utterly irrelevant to whether the mind 'is >a Turing machine' or not. What I was pointing out was, that it is nonsense to talk about equivalence without defining the equivalence relation. So, to give an example, I took an equivalence relation which took time complexity into account. Please don't say that is a wrong equivalence relation, please tell me which one is the *right* one. Then we can start to decide whether the two are or are not equivalent. >What you really want to know is whether the human brain is 'Turing >equivalent'. Can you define that? >I think with fair certainty it can be said that it is >not, in the same sense that a general purpose computer is *not* >Turing equivalent: both don't have infinite memory. Can you define "memory"; some people have pointed out that people can write things down, and then you should start to look at the question whether the universe contains infinite mass (to write things down upon) or not... [Just an extreme example again! Please don't pick on me for that!] >(This is, of course, not to say that the use of Turing machines >tells us nothing about computation in computers or the brain, just >that one has to be careful as to how far the similarities go). > > Thomas. Isn't that exactly what I am asking for all the time: Please give your equivalence relation!! [And look at it yourself, whether you are not leaving out of account anything which would make a mind different/equal to a TM, depending on your point of view.] May I suggest to reread my original article, in which I also proved equality? -- Biep. {seismo|decvax|philabs|garfield|okstate}!mcvax!vu44!biep Is the difference between a difference of degree and a differ- ence of sorts a difference of degree or a difference of sorts?
bill@milford.UUCP (bill) (11/07/85)
Henry Schaffer (hes@ecsvax.UUCP) wrote: > Following this path, the rephrased question is "Can the mind be modelled > by a Turing machine?", and it can't be answered by showing speed > differences -- but it could by showing that the mind can "compute" > something that a Turing machine can't. (Vice-versa isn't possible, because > it is evident that the mind can simulate a Turing machine.) ^^^ ^^^^ ^^^ ^^^^^^^^ ^ ^^^^^^ ^^^^^^^ > --henry schaffer n c state univ and Thomas Breuel (breuel@h-sc1.UUCP) wrote: > What you really want to know is whether the human brain is 'Turing > equivalent'. I think with fair certainty it can be said that it is > not, in the same sense that a general purpose computer is *not* > Turing equivalent: both don't have infinite memory. Both are much > more accurately captured by the notion of a finite state machine. ^ ^^^^^^ ^^^^^ ^^^^^^^ I agree with both, the only problem is the old philosophical question of 'mind' =? 'brain' sneaks into the picture (usually called the Mind/Body question.) The brain quite obviously is a finite state machine but through the use of exterior memory media (my desk, my computer files, etc.) the mind can emulate devices requiring arbitrarily large memories and access. A more interesting question here might be "What type of machine can accept an arbitrarily chosen natural language?" I suspect that English is not a regular language nor a context-free language; is it context-sensitive? Is it more?? Sometimes I know my mind is only like a Mealy machine, quite often its only a finite state automata; but ideally I guess its a linear-bounded automata.
michaelm@bcsaic.UUCP (michael b maxwell) (11/07/85)
In article <1637@uwmacc.UUCP> edwards@uwmacc.UUCP (mark edwards) writes: >...Scientific America says that there are 10 to the 10 or 11 neurons in >the brain. If only a tenth of these are used... Wonder where the idea ever came from that we use only 1/10th. of our brain? How could anyone possibly know? And *if* the brain uses holographic storage, does the concept of how much of the brain is used even have meaning? -- Mike Maxwell Boeing Artificial Intelligence Center ...uw-beaver!uw-june!bcsaic!michaelm
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (11/08/85)
> A more interesting question here might be "What type of machine can accept > an arbitrarily chosen natural language?" I suspect that English is not > a regular language nor a context-free language; is it context-sensitive? > Is it more?? The fact that you consider the answers to these questions nonobvious is one of the many reasons why this discussion is stupid. I see that you have dropped net.philosophy and are just posting to net.math; this is EXACTLY BACKWARDS. Please only post discussions about mathematics to net.math. If people want to read discussions like this, they will be subscribers to net.philosophy. Thanks. (I'm about ready to unsubscribe from net.math and maybe net.physics due to all the net.philosophy garbage that is being misposted.)
friesen@psivax.UUCP (Stanley Friesen) (11/08/85)
In article <110@milford.UUCP> bill@milford.UUCP (bill) writes: > >A more interesting question here might be "What type of machine can accept >an arbitrarily chosen natural language?" I suspect that English is not >a regular language nor a context-free language; is it context-sensitive? >Is it more?? > Some answers. No one knows -*yet*. Your suspicion is correct. Yes, it is at least context sensitive. Probably it is mor, I would say that it is "semantics-sensitive", that is the syntax depends on the meaning of the utterence! No formal language system, including context-sensitive languages permit this. -- Sarima (Stanley Friesen) UUCP: {ttidca|ihnp4|sdcrdcf|quad1|nrcvax|bellcore|logico}!psivax!friesen ARPA: ttidca!psivax!friesen@rand-unix.arpa