3 ms·
The halting problem is only a problem with an infinite amount of RAM. If you limit the amount of state, it's relatively easy (although still exponentially long)
by sp332 11y ago
The halting problem is only a problem with an infinite amount of RAM. If you limit the amount of state, it's relatively easy (although still exponentially long) to solve.
- kazinator 11y agoWell, it's easy to solve then for those instances that fit in your RAM. It remains unsolved for the others!
- sp332 11y agoI mean if the program requires too much RAM then it will either crash & stop or glitch and run forever, but you can always tell which way it will break :)
- paulddraper 11y agoAnd how do you tell (without running forever)?
- sp332 11y agoYou run the program for 2^(bits of state) steps. If it's still running, it will never stop because it must have repeated a state at least once. That means it's in a loop. So it takes a long time, but not an uncomputably long time. By bits of state, I only mean the bits that the program is allowed to change. It doesn't necessarily include OS code or initialization code, as long as they are immutable while the program is running.
- paulddraper 11y agoAh, yep, you're right. Finite state -> solved halting problem
- ckuehne 11y agoIt 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 11y agoIt 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_lower_bounds 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 11y agoI 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_pitfalls https://en.wikipedia.org/wiki/Halting_problem#Common_pitfall...
- deleted 11y ago[deleted]