[ckuehne]

It is not "relatively easy" to solve. It is exponentially hard. For example, 16 GB RAM means you have about 10^(3*10^10) possible states. That is a 1 followed by 30 million zeroes.

So I guess I'll pick you up in about 10^10^9 years and you tell me how it goes. That is of course assuming that your program does not load new functions from your hard disk at some point which would add more state to you program thus stretching the waiting time even longer.

[sp332]

It is relatively easy, because it's relative to uncomputable numbers. The most famous of which is the Busy Beaver problem which grows much, much faster than 2^x https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_l... For example, 2^5 = 16, but BB(5) has never been computed and has a lower bound of 1.9 × 10^704. You can see that BB(16,000,000,000) is relatively difficult to compute compared to 10^(3*10^10).

[ckuehne]

I think you are confusing things.

The problem is not to compute S=10^(3 * 10^10). In fact, we have already computed it. The problem that you originally discussed was waiting (at most) S steps until we can be sure that the finite state-machine either stops or runs forever. I assumed 10^9 steps per second. Thus, the waiting time would be approx. 10^10^9 years.

Wikipedia has a nice discussion on the topic with a quote by Marvin Minsky [1]:

"Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least 2^1,000,000 possible states: 'This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle'"

[1] https://en.wikipedia.org/wiki/Halting_problem#Common_pitfall...

[sp332]

Yes, it will take a very long time. But it will take much less time than solving the halting problem!