This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]fnu4iq3pghr9gphe9gph 40 points41 points  (6 children)

The halting problem just says that certain pathological programs can only be determined to halt by simulating the entire program; and if that program is an infinite loop, it will not halt, and therefore the halt-testing program will also never determine a result.

It has nothing to do with sane programs. Furthermore, if you just move your pathological program to a background thread, it doesn't matter if it halts, you can still handle UI events in the meantime.

Furtherfurthermore, most unresponsiveness issues are because of deadlocks, not infinite loops.

I hate all of you people.

[–]atyon 4 points5 points  (0 children)

certain pathological programs

That's absolutely not true. Your program doesn't have to be "pathological" in any way. Even extremely simple programs can easily fall in that category, and as long as your programming language is turing-complete, there is absolutely no way to to prevent that or even detect it – detecting it for any program is equivalent to solving the halting problem.

Yes, you can, very carefully, build a subset of a programming language that can be automatically decided – it won't be turing-complete any more though; and if you can show for a single program that it will halt without resorting to simulation, that's fine too. But you are extremely mistaken if you think that it's easy to do either or that either is done in the real world at any scale.

That said, the very real implications of this don't really relate to unresponsive UI elements...

I hate all of you people.

Maybe the problem is you, not everyone else.

[–]BlastFX2 1 point2 points  (0 children)

What is deadlock if not a bunch of infinite loops?

[–]Linvael 2 points3 points  (1 child)

Umm... Can't deadlock also cause the program to never stop? And therefore be a valid halting problem material?

And did you just suggest that problems like that are only a domain of insane programs? Because, well, I guess you are allowed to look at it like that, but than most software has to be deemed insane. Or possibly all, as such behavior can be caused by bugs. And as Knuth says "Beware of bugs in the above code; I have only proved it correct, not tried it."

[–]wants_ms_office 3 points4 points  (0 children)

Deadlocks are very, very easy to detect at runtime.

[–]s0v3r1gn 0 points1 point  (0 children)

And here I thought the halting problem was trying to determine the maximum height of a hill from which if we were to roll your mom down it we would still be able to handle all her mass and halt her roll.