[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!