Hacker News Reader

Comment by kazinator | Hacker News Reader

Well, it's easy to solve then for those instances that fit in your RAM. It remains unsolved for the others!

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.

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).

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...

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

I 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 :)

And how do you tell (without running forever)?

You 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.

Ah, yep, you're right.

Finite state -> solved halting problem

Reply on news.ycombinator.com