4 ms·
No it isn't unsound, it is an application of the pigeonhole principle. A finite memory and finite set of states implies that there are some finite number of con
by knappa 8y ago
No it isn't unsound, it is an application of the pigeonhole principle. A finite memory and finite set of states implies that there are some finite number of configurations (call it N) that the computer can be in. Once you let the computer go N+1 steps, there must be at least one repeated configuration; which might be halting or not.