On Thu, Jan 24, 2008 at 08:13:30AM -0800, Darren New wrote:
The Z80 has 2^16 bytes of address space (add the appropriate amount of space for registers). That means the processor can only be in one of 8*2^16 different states (again, modulo register content, which is just more memory, and ignoring external stuff like removable media, interrupts, keyboards, etc).
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). 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. This is approximately 2.6 x 10^157826 different states that you would have to store. The magnitude of this number is just numbing. Let's look at it another way. John Allen Pauls estimates that if the known universe were filled with just quarks and nothing else, there would be about 10^143 of them. A computer with 60 bytes of memory can exist in more states than this. So it isn't even possible to store a bitmap of what states you've visited. It doesn't help to not store the states, and run two computers at different speeds to detect the loop. It just moves the problem from absurd memory requirements to absurd time requirements, things that make the universe seem quite young. Dave -- KPLUG-LPSG@kernel-panic.org http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
