|
|
|
|
|
|
by sp332
3805 days ago
|
|
|
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). |
|
|
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...