4 ms·

> The brain cannot simulate a turing machine. It does not have infinite memory, which is a requirement for a turing machine. In practice we call modern compute

by shawnz 6y ago

> The brain cannot simulate a turing machine. It does not have infinite memory, which is a requirement for a turing machine. In practice we call modern computers turing-complete even though they don't have infinite memory. The brain can simulate such a machine. > The brain has no such constraint. It is analog, and therefore infinite in State representation. If this mattered, then it would mean analog computers are more powerful than digital computers and therefore the Church-Turing thesis is wrong

coreyp_1 6y ago
Regarding the Church-Turing thesis, it is exactly that, just a thesis. Again, akin to P vs NP. It seems to hold for most cases, but is not proven. The reason that it's difficult to apply in regards to the brain is that we don't exactly know how the brain is computing... or if it "computes" at all! To my knowledge, we don't have a model of computation for consciousness, emotion, free will, Etc. Perhaps these are better classified as emergent Behavior rather than computation, but if that is the case I still don't know of a model explaining what computations or rules give rise to the emergent Behavior. Perhaps the problem is in our definition of computation and what it means to compute. We do know that the cardinality of the set of possible computational problems is larger than the cardinality of the set of all possible Turing machines. This is provable by simple diagonalization proofs. The question, then, is whether or not the computations of the brain fall Within the set of Turing recognizable languages (computational problems). To my knowledge, this has not been shown.
- supergarfield 6y ago
  As far as I understand, the prevailing opinion is that the brain is a physical object and that its operation does not involve currently-unknown laws of physics (because we have a good understanding of what happens at the scale of an entire atom or above). A Turing machine can run a simulation based on such physical laws to any desired level of precision (which is enough, because as mentioned in TFA, processes in the brain aren't individually very precise). This is true because of the nature of these laws, which are mostly just asking you to integrate differential equations. If you accept this, then it should follow that a Turing machine can in fact simulate a brain: just run a physics sim on a brain's initial state. (I do realize that this is far outside the realm of what's doable today, but it seems to provide a solid justification for why it's conceptually possible).
  - coreyp_1 6y ago
    "any desired level of precision" is actually the issue. The moment you choose a level of precision, you cease being accurate (at that level). If you make the argument that a TM has infinite memory, and can therefore represent an infinite precision, then I would counter that our current defintion of a TM requires a finite tape alphabet (and finite number of states), which is part of the TM's known computational limitations. And, of course, the moment that you use any finite set of symbols to represent an infinitely precise value, you fall into the problem that the set of real numbers has a larger cardinality than the set of possible turing machines (again, simple proof via diagonalization). It is possible that the brain's imprecision (I would argue that "inconsistency" might be a better word) is a requirement of it's computational ability. Again, we haven't defined how the brain computes, nor do we have a model for explaining its computation, encoding or representation of knowledge, or emergent behavior. We have observed phenomena related to some of these things, but we are far from understanding it. It may be that the computational processes are dependent on the surrounding environment. We know that the biological processes are influenceable by the physical world, but we do not know much about how these external forces affect, limit, or are required for, the process of brain computation. The quantum world may play a part in consciousness (or no, we don't know). Non-determinism may play a part. It is possible that, in order to simulate a brain, one would have to simulate the entire universe around it in order to predict the behavior... meaning that it may well require a universe to perform the simulation. Which brings us to a related theory of whether or not we are living in a simulation, but I digress... :)
    - deleted 6y ago
      [deleted]
    - mamon 6y ago
      > It is possible that the brain's imprecision (I would argue that "inconsistency" might be a better word) is a requirement of it's computational ability Is it possible that brain is in fact a quantum computer? I can imagine that under all those neural networks there is a small part where, trapped in some complex protein structure, some qbits exist and are crucial to most advanced brain functions, such as consciousness.
deepnotderp 6y ago
Isn't the recent Google quantum "supremacy" experiment evidence against the extended Church-Turing thesis?
- anchpop 6y ago
  No, quantum computers as we understand them can be simulated by a turing machine
  - deepnotderp 6y ago
    The extended Church-Turing thesis which I specifically referred to concerns efficient simulation, not just whether it can be simulated.
- The_rationalist 6y ago
  Google has not proved quantum supremacy, it is a scam. They have proved the truism that running a physical system is faster than running a simulation of a physical system...
  - lawrenceyan 6y ago
    https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 What part of the experiment in the paper released did you feel like was inadequate?

by shawnz 6y ago

coreyp_1 6y ago

Regarding the Church-Turing thesis, it is exactly that, just a thesis. Again, akin to P vs NP. It seems to hold for most cases, but is not proven. The reason that it's difficult to apply in regards to the brain is that we don't exactly know how the brain is computing... or if it "computes" at all! To my knowledge, we don't have a model of computation for consciousness, emotion, free will, Etc. Perhaps these are better classified as emergent Behavior rather than computation, but if that is the case I still don't know of a model explaining what computations or rules give rise to the emergent Behavior. Perhaps the problem is in our definition of computation and what it means to compute. We do know that the cardinality of the set of possible computational problems is larger than the cardinality of the set of all possible Turing machines. This is provable by simple diagonalization proofs. The question, then, is whether or not the computations of the brain fall Within the set of Turing recognizable languages (computational problems). To my knowledge, this has not been shown.

supergarfield 6y ago
As far as I understand, the prevailing opinion is that the brain is a physical object and that its operation does not involve currently-unknown laws of physics (because we have a good understanding of what happens at the scale of an entire atom or above). A Turing machine can run a simulation based on such physical laws to any desired level of precision (which is enough, because as mentioned in TFA, processes in the brain aren't individually very precise). This is true because of the nature of these laws, which are mostly just asking you to integrate differential equations. If you accept this, then it should follow that a Turing machine can in fact simulate a brain: just run a physics sim on a brain's initial state. (I do realize that this is far outside the realm of what's doable today, but it seems to provide a solid justification for why it's conceptually possible).
- coreyp_1 6y ago
  "any desired level of precision" is actually the issue. The moment you choose a level of precision, you cease being accurate (at that level). If you make the argument that a TM has infinite memory, and can therefore represent an infinite precision, then I would counter that our current defintion of a TM requires a finite tape alphabet (and finite number of states), which is part of the TM's known computational limitations. And, of course, the moment that you use any finite set of symbols to represent an infinitely precise value, you fall into the problem that the set of real numbers has a larger cardinality than the set of possible turing machines (again, simple proof via diagonalization). It is possible that the brain's imprecision (I would argue that "inconsistency" might be a better word) is a requirement of it's computational ability. Again, we haven't defined how the brain computes, nor do we have a model for explaining its computation, encoding or representation of knowledge, or emergent behavior. We have observed phenomena related to some of these things, but we are far from understanding it. It may be that the computational processes are dependent on the surrounding environment. We know that the biological processes are influenceable by the physical world, but we do not know much about how these external forces affect, limit, or are required for, the process of brain computation. The quantum world may play a part in consciousness (or no, we don't know). Non-determinism may play a part. It is possible that, in order to simulate a brain, one would have to simulate the entire universe around it in order to predict the behavior... meaning that it may well require a universe to perform the simulation. Which brings us to a related theory of whether or not we are living in a simulation, but I digress... :)
  - deleted 6y ago
    [deleted]
  - mamon 6y ago
    > It is possible that the brain's imprecision (I would argue that "inconsistency" might be a better word) is a requirement of it's computational ability Is it possible that brain is in fact a quantum computer? I can imagine that under all those neural networks there is a small part where, trapped in some complex protein structure, some qbits exist and are crucial to most advanced brain functions, such as consciousness.

deepnotderp 6y ago

Isn't the recent Google quantum "supremacy" experiment evidence against the extended Church-Turing thesis?

anchpop 6y ago
No, quantum computers as we understand them can be simulated by a turing machine
- deepnotderp 6y ago
  The extended Church-Turing thesis which I specifically referred to concerns efficient simulation, not just whether it can be simulated.
The_rationalist 6y ago
Google has not proved quantum supremacy, it is a scam. They have proved the truism that running a physical system is faster than running a simulation of a physical system...
- lawrenceyan 6y ago
  https://www.nature.com/articles/s41586-019-1666-5 https://www.nature.com/articles/s41586-019-1666-5 What part of the experiment in the paper released did you feel like was inadequate?