3 ms·

The idea that humans are physical systems with Turing-computable behavior would mean that any problem not solvable by Turing machines is also not solvable by hu

by kd0amg 6y ago

The idea that humans are physical systems with Turing-computable behavior would mean that any problem not solvable by Turing machines is also not solvable by humans. That is, there are programs whose halting behavior no human will ever determine, theorems of Peano arithmetic whose proof no human will ever find, etc., no matter how much humans work at it.

qayxc 6y ago
> The idea that humans are physical systems with Turing-computable behavior would mean that any problem not solvable by Turing machines is also not solvable by humans. But there are real-world instances that contradict this hypothesis already. Humans don't exhibit Turing-computable behaviour because they did indeed solve problems that aren't solvable by Turing Machines. I can give a very concrete example as well. Consider the following program (in Python for simplicity's sake): def nat(x): yield x yield from nat(x+1) for a in nat(2): for b in nat(2): for c in nat(2): if a*a*a + b*b*b == c*c*c: print(f"{a}^3 * {b}^3 = {c}^3") exit() There is no Turing Machine capable of proving that this program won't halt (technically it will, due to practical limitations). Yet it has has been proven centuries ago that the above program won't halt. The mathematicians couldn't have used a Turing Machine-compliant computation, so something else must be involved. Now this of course doesn't mean that humans are generally capable of solving every problem that's not solvable by an algorithm, but it means that they can solve problems that algorithms can't solve.
- kd0amg 6y ago
  > There is no Turing Machine capable of proving that this program won't halt Yes, there is. There's a machine which does nothing but print that exact proof. You seem to have conflated solving an instance of a problem with solving the entire problem. Turing's theorem states that no one Turing machine will get the answer right for every instance of the halting problem, but for any instance that one specific machine gets wrong, there's another machine that also gets that instance right (in addition to everything else the original machine gets right).

by kd0amg 6y ago

qayxc 6y ago

> The idea that humans are physical systems with Turing-computable behavior would mean that any problem not solvable by Turing machines is also not solvable by humans. But there are real-world instances that contradict this hypothesis already. Humans don't exhibit Turing-computable behaviour because they did indeed solve problems that aren't solvable by Turing Machines. I can give a very concrete example as well. Consider the following program (in Python for simplicity's sake): def nat(x): yield x yield from nat(x+1) for a in nat(2): for b in nat(2): for c in nat(2): if a*a*a + b*b*b == c*c*c: print(f"{a}^3 * {b}^3 = {c}^3") exit() There is no Turing Machine capable of proving that this program won't halt (technically it will, due to practical limitations). Yet it has has been proven centuries ago that the above program won't halt. The mathematicians couldn't have used a Turing Machine-compliant computation, so something else must be involved. Now this of course doesn't mean that humans are generally capable of solving every problem that's not solvable by an algorithm, but it means that they can solve problems that algorithms can't solve.

kd0amg 6y ago
> There is no Turing Machine capable of proving that this program won't halt Yes, there is. There's a machine which does nothing but print that exact proof. You seem to have conflated solving an instance of a problem with solving the entire problem. Turing's theorem states that no one Turing machine will get the answer right for every instance of the halting problem, but for any instance that one specific machine gets wrong, there's another machine that also gets that instance right (in addition to everything else the original machine gets right).