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.
pnp@ihnp1.UUCP (Peter Prokopowicz) (11/07/85)
Even if it is presumed that the brain has a finite memory capacity, that one fact does not make it appropriate to compare it to a finite state machine, or Turing machine, for that matter. That's like comparing apples and dogs, or trying to decide if the workings of our kidneys best be described by a context free or regular grammar.
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?
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.)