4 ms·

> To me, whether it's NP-complete is of little concern, since humans have been allocating registers (and beating compilers) with little difficulty. Following t

> To me, whether it's NP-complete is of little concern, since humans have been allocating registers (and beating compilers) with little difficulty. Following that logic, one would conclude that writing an AI for Go is trivial as well [1]. > if I can describe the algorithm that I, as a human, take ... then a machine can probably do it just as well if not faster This is pretty easy to disprove. You can probably look at a program's source code and tell whether or not it halts. But it's been proven that a Turing machine cannot [2]. The halting problem is one of many undecidable problems in computer science [3]. If any one of the undecidable problems can be solved by a human, that proves that the human brain is not Turing equivalent. [1] https://en.wikipedia.org/wiki/Computer_Go https://en.wikipedia.org/wiki/Computer_Go [2] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem [3] https://en.wikipedia.org/wiki/Undecidable_problem https://en.wikipedia.org/wiki/Undecidable_problem

yongjik 12y ago
I think you misunderstand what is the halting problem. It's being able to tell whether a program will halt or not, for all conceivable programs. A human brain certainly can't do that. For example, does this program halt? (Let's assume infinite-precision numbers, for simplicity. After all, a Turing machine can access an infinitely long tape.) for (int n = 3; ; n++) for (int a = 1; a < n; a++) for (int b = 1; b < n; b++) for (int c = 1; c < n; c++) for (int m = 3; m < n; m++) if (pow(a, m) + pow(b, m) == pow(c, m)) exit(1); Show me that this program never halts, and you just proved Fermat's last theorem. Edit: added one missing loop
Houshalter 12y ago
AIs have been made for Go and they aren't extraordinarily complicated. They can beat most humans. It's pretty widely believed that humans are Turing equivalent, and there is no evidence at all to suggest we aren't. Certainly humans can't determine halting for all possible programs and inputs. And we run on physics which as far as I know is Turing equivalent.

yongjik 12y ago

I think you misunderstand what is the halting problem. It's being able to tell whether a program will halt or not, for all conceivable programs. A human brain certainly can't do that. For example, does this program halt? (Let's assume infinite-precision numbers, for simplicity. After all, a Turing machine can access an infinitely long tape.) for (int n = 3; ; n++) for (int a = 1; a < n; a++) for (int b = 1; b < n; b++) for (int c = 1; c < n; c++) for (int m = 3; m < n; m++) if (pow(a, m) + pow(b, m) == pow(c, m)) exit(1); Show me that this program never halts, and you just proved Fermat's last theorem. Edit: added one missing loop

Houshalter 12y ago

AIs have been made for Go and they aren't extraordinarily complicated. They can beat most humans. It's pretty widely believed that humans are Turing equivalent, and there is no evidence at all to suggest we aren't. Certainly humans can't determine halting for all possible programs and inputs. And we run on physics which as far as I know is Turing equivalent.