Comment by kazinator | Hacker News Reader

Comment by kazinator | Hacker News Reader

Parent Full thread

Okay, I won't tell you that your browser can't calculate, for every possible Javascript function, and every possible input to that function, the Boolean value indicating whether or not that function will halt. Don't mind me at all!

> HTML and CSS both are fault tolerant. If something goes wrong in HTML, browsers either display the content of the element or try to fix minor issues like unclosed elements for you. CSS skips lines of code it can’t understand and merrily goes on its way to show the rest of it. JavaScript breaks on errors and tells you that something went wrong. It will not execute the rest of the script, but throws in the towel and tells you to get your house in order first.

HTML (or rather, processing thereof) being fault tolerant is a complete misfeature. It's the result of browser in the 1990's trying to out-do each other in handling broken web pages in order to look more functional. Broken HTML should be loudly rejected (at least in pages which declare strict conformance to a modern dialect).

CSS skipping stuff it doesn't understand is harmless because a declarative language for assigning style properties. It doesn't have permanent effects, like making a call to a server to update a database record.

A program in a general purpose language cannot reliably continue after an error (without logic to handle that situation). Later steps depend on the earlier ones having executed correctly in every detail.

>A program in a general purpose language cannot reliably continue after an error (without logic to handle that situation). Later steps depend on the earlier ones having executed correctly in every detail.

I don't understand this statement. Obviously, the program cannot preform correctly, but that may not matter. For example, if a web page caches content on disk for the future, but there is an error. It may not matter that the particular disk write failed without any additional logic. The error would just cause a slightly longer load time next time.

> It may not matter that the particular disk write failed without any additional logic.

Only if the disk write completely failed, leaving no traces of a half-broken cache entry.

If you have a half-written cache entry and don't deal with that situation somehow, you end up serving the user broken content from the cache.

It usually behooves us to have our code react to write errors.

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.

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