3 ms·

Our brains are Turing complete. Anything that is computable/ understandable, can be understood by humans.

21 10y ago
Fully homomorphic encryption is also turing complete. Yet it's not possible to understand what such an algorithm is doing by design.
- drdeca 10y ago
  Not efficiently possible, But given enough time and memory, shouldn't it be possible? Although maybe that would require more than the universe has available, in which case I suppose it would be impossible in that sense I guess.
goatlover 10y ago
What is the proof for our brains being Turing complete? That we can in principle compute any algorithm, given writing tools and enough time? I'm not sure a human can compute any algorithm beyond a certain complexity. But maybe if that human never aged or got bored and had an endless supply of paper. But then you're not dealing with a real human being anymore. Even if you had a super patient, super long lived human, what's to say they wouldn't get indefinitely stuck with really involved calculations?
- throwaway87423 10y ago
  I think the proof is fairly simple: i) Tell a person how a Turing machine works, ii) Give her reams of paper iii) Make her miserable by running some instruction. iv) ? v) Profit! Seriously though. I don't think Turing completeness means anything at all; we're increasingly beginning to understand how important representations are. As hackers I'm sure we understand what this means in terms of PLs, but this is no coincidence IMO.
deleted 10y ago
[deleted]
throwaway87423 10y ago
"Understandable" is not necessary computable. Understanding an algorithm is equivalent to the Halting problem in my books.
dragonwriter 10y ago
> Our brains are Turing complete. Anything that is computable/ understandable, can be understood by humans. Our brains are fallible, and so only approximately equivalent to Turing machines; and even ignoring that can only compute every computable thing given both infinite error-free storage capacity (which they don't have internally or externally) and sufficient time to execute the necessary steps of the computation. Realistically, there are computable functions which no human brain will be ever be capable of computing. Whether being able to compute a thing is sufficient, necessary, or tangential to understanding it is also a question.
- charles-salvia 10y ago
  >> Our brains are fallible, and so only approximately equivalent to Turing machines; and even ignoring that can only compute every computable thing given both infinite error-free storage capacity (which they don't have internally or externally) and sufficient time to execute the necessary steps of the computation. So are actual computers. They're just "less fallible" and closer to a Universal Turing Machine than human brains in certain ways. A Commodore 64 is also incapable, in practice, of computing certain computable functions, due to memory limitations and what have you, but nobody would really claim a Commodore 64 is not Turing complete.
  - dragonwriter 10y ago
    > So are actual computers Sure, but no one was making claims about actual computers other than the human brain that requires pointing that out. > but nobody would really claim a Commodore 64 is not Turing complete. Actually, it's a rather common observation that real-world computers are not Turing complete (languages, considered independent of the limitations of concrete machines, may be) and particularly that concrete machines with limited storage space and operating with finite time constraints may not be able to compute all computable results, even though the abstract model they approximate, without those limitations, can.

21 10y ago

Fully homomorphic encryption is also turing complete. Yet it's not possible to understand what such an algorithm is doing by design.

drdeca 10y ago
Not efficiently possible, But given enough time and memory, shouldn't it be possible? Although maybe that would require more than the universe has available, in which case I suppose it would be impossible in that sense I guess.

goatlover 10y ago

What is the proof for our brains being Turing complete? That we can in principle compute any algorithm, given writing tools and enough time? I'm not sure a human can compute any algorithm beyond a certain complexity. But maybe if that human never aged or got bored and had an endless supply of paper. But then you're not dealing with a real human being anymore. Even if you had a super patient, super long lived human, what's to say they wouldn't get indefinitely stuck with really involved calculations?

throwaway87423 10y ago
I think the proof is fairly simple: i) Tell a person how a Turing machine works, ii) Give her reams of paper iii) Make her miserable by running some instruction. iv) ? v) Profit! Seriously though. I don't think Turing completeness means anything at all; we're increasingly beginning to understand how important representations are. As hackers I'm sure we understand what this means in terms of PLs, but this is no coincidence IMO.

deleted 10y ago

[deleted]

throwaway87423 10y ago

"Understandable" is not necessary computable. Understanding an algorithm is equivalent to the Halting problem in my books.

dragonwriter 10y ago

> Our brains are Turing complete. Anything that is computable/ understandable, can be understood by humans. Our brains are fallible, and so only approximately equivalent to Turing machines; and even ignoring that can only compute every computable thing given both infinite error-free storage capacity (which they don't have internally or externally) and sufficient time to execute the necessary steps of the computation. Realistically, there are computable functions which no human brain will be ever be capable of computing. Whether being able to compute a thing is sufficient, necessary, or tangential to understanding it is also a question.

charles-salvia 10y ago
>> Our brains are fallible, and so only approximately equivalent to Turing machines; and even ignoring that can only compute every computable thing given both infinite error-free storage capacity (which they don't have internally or externally) and sufficient time to execute the necessary steps of the computation. So are actual computers. They're just "less fallible" and closer to a Universal Turing Machine than human brains in certain ways. A Commodore 64 is also incapable, in practice, of computing certain computable functions, due to memory limitations and what have you, but nobody would really claim a Commodore 64 is not Turing complete.
- dragonwriter 10y ago
  > So are actual computers Sure, but no one was making claims about actual computers other than the human brain that requires pointing that out. > but nobody would really claim a Commodore 64 is not Turing complete. Actually, it's a rather common observation that real-world computers are not Turing complete (languages, considered independent of the limitations of concrete machines, may be) and particularly that concrete machines with limited storage space and operating with finite time constraints may not be able to compute all computable results, even though the abstract model they approximate, without those limitations, can.