6 ms·

How is the brain not a universal turing machine? Is there a task that turing machines can do that brains can't? It has been shown that rnns are turing complete

How is the brain not a universal turing machine? Is there a task that turing machines can do that brains can't? It has been shown that rnns are turing complete [1] so it is certainly believable that brains are [1] http://stats.stackexchange.com/questions/220907/meaning-of-and-proof-of-rnn-can-approximate-any-algorithm http://stats.stackexchange.com/questions/220907/meaning-of-a...

roywiggins 10y ago
You can calculate rule 110 by pen and paper, so at least the brain-pen-paper system is Turing complete. However, the brain is not a Turing machine, probably. There aren't discrete states, no transition table, no tape, etc. We probably don't store information remotely like a Turing machine does (with arbitrary symbols). There's a remote chance that the opposite is true, and there are functions humans can calculate that Turing machines can't.
- Immortalin 10y ago
  Lambda calculus aren't turing machines either but they are turing complete
jamesblonde 10y ago
I won't go into details on why the brain isn't a UTC - this is useful: https://www.quora.com/Is-the-brain-a-turing-machine https://www.quora.com/Is-the-brain-a-turing-machine
- barrkel 10y ago
  Care to mention which reply you think is insightful? I didn't find much of interest at the end of that link; some say yes, some say no, and some answer the inverse but related question (can a Turing machine emulate the brain - because obviously people can laboriously emulate Turing machines). If you think the brain can compute something a Turing machine can't, it would be interesting to link to something that justifies the position (I personally think a TM is enough).
  - jamesblonde 10y ago
    I don't think a brain can compute something a TM can compute. The brain, however, is not a simple universal turing machine in the sense that it doesn't have a finite set of instructions and an infinite tape-band. I don't subscribe to the Penrose school of thought on this matter.
    - barrkel 10y ago
      Well clearly the brain isn't infinite, but nor is any Turing Machine we implement. When we say something like C is Turing complete, we don't mean that any correct implementation can compute what a TM can compute, because no implementation is finite. Eventually both the stack will be exhausted and malloc() will fail; there's a finite amount of state available on any concrete hardware. My point being that that seems to be such a trivially true statement - conveying no information - so that we must understand the sentence to mean something else; that it can compute what a TM can compute, up to some arbitrary limit related to available state. So, would you say that the brain isn't Turing complete either?
yjftsjthsd-h 10y ago
I think the key detail is that the brain is actually more powerful than a turing machine, as demonstrated by our ability to solve halting problems
- DiThi 10y ago
  > our ability to solve halting problems Is that true? Do you have a source?
- muricula 10y ago
  I'm not sure this is correct at all. Turing machines can solve certain subsets of the halting problem (i.e does a given program without recursion and with only certain types of loops halt?), but it's impossible to create an algorithm which will say whether any program halts. I see no reason why the Human brain would be able to solve the halting problem, or even any problem a Turing machine can't.

roywiggins 10y ago

You can calculate rule 110 by pen and paper, so at least the brain-pen-paper system is Turing complete. However, the brain is not a Turing machine, probably. There aren't discrete states, no transition table, no tape, etc. We probably don't store information remotely like a Turing machine does (with arbitrary symbols). There's a remote chance that the opposite is true, and there are functions humans can calculate that Turing machines can't.

Immortalin 10y ago
Lambda calculus aren't turing machines either but they are turing complete

jamesblonde 10y ago

I won't go into details on why the brain isn't a UTC - this is useful: https://www.quora.com/Is-the-brain-a-turing-machine https://www.quora.com/Is-the-brain-a-turing-machine

barrkel 10y ago
Care to mention which reply you think is insightful? I didn't find much of interest at the end of that link; some say yes, some say no, and some answer the inverse but related question (can a Turing machine emulate the brain - because obviously people can laboriously emulate Turing machines). If you think the brain can compute something a Turing machine can't, it would be interesting to link to something that justifies the position (I personally think a TM is enough).
- jamesblonde 10y ago
  I don't think a brain can compute something a TM can compute. The brain, however, is not a simple universal turing machine in the sense that it doesn't have a finite set of instructions and an infinite tape-band. I don't subscribe to the Penrose school of thought on this matter.
  - barrkel 10y ago
    Well clearly the brain isn't infinite, but nor is any Turing Machine we implement. When we say something like C is Turing complete, we don't mean that any correct implementation can compute what a TM can compute, because no implementation is finite. Eventually both the stack will be exhausted and malloc() will fail; there's a finite amount of state available on any concrete hardware. My point being that that seems to be such a trivially true statement - conveying no information - so that we must understand the sentence to mean something else; that it can compute what a TM can compute, up to some arbitrary limit related to available state. So, would you say that the brain isn't Turing complete either?

yjftsjthsd-h 10y ago

I think the key detail is that the brain is actually more powerful than a turing machine, as demonstrated by our ability to solve halting problems

DiThi 10y ago
> our ability to solve halting problems Is that true? Do you have a source?
muricula 10y ago
I'm not sure this is correct at all. Turing machines can solve certain subsets of the halting problem (i.e does a given program without recursion and with only certain types of loops halt?), but it's impossible to create an algorithm which will say whether any program halts. I see no reason why the Human brain would be able to solve the halting problem, or even any problem a Turing machine can't.