David Brown wrote:
I can definitively declare that this is unsolvable, just because of magnitude. In fact solving the halting problem this way only works for trivially small computer system (a handfull of bits).
Not at all. Solve it on a Turing machine. That's kind of the point I'm making. Before you say "the brain can (or cannot) solve the halting problem," you have to understand what the halting problem is and what makes it unsolvable.
First, as others have mentioned, it's 2^(8*2^16) different states. 8*2^16 is the number of bits of memory, each of which can be in a different state.
OK. No biggie. You're either unbounded, or you're not.
This is approximately 2.6 x 10^157826 different states that you would have to store. The magnitude of this number is just numbing.
That doesn't make it any less mathematically intractable. People work with the set of real numbers all the time. Between any two real numbers are more real numbers than all the integers put together. Let alone a paultry 10^157826.
The halting problem only is true for unbounded computers. Otherwise, I can write a Turing machine program for any program on a finite size computer that will check in finite time whether that program halts or not. That's the definition of the halting problem.
That you can't actually *run* the Turing machine program I provide on a machine you can actually build doesn't really say much about whether the brain can solve the halting problem. Any more than if I give you a physical machine which always breaks down after 5000 instructions, you can claim you can solve the halting problem for that machine.
-- Darren New / San Diego, CA, USA (PST) It's not feature creep if you put it at the end and adjust the release date. -- KPLUG-LPSG@kernel-panic.org http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg