The halting problem: Difference between revisions

From Helpful
Jump to navigation Jump to search
mNo edit summary
 
mNo edit summary
 
Line 1: Line 1:
<!--
<!--


Given the code of a program, can you say that it will ever stop, as in, not continue running forever?
Given the code of a program, can you say that it will stop, as in, not continue running forever?


{{comment|(Note that this problem addresses correct, deterministic problems and solutions.  Yes, bad thread locking can cause race conditions that [[deadlock]] or [[livelock]], but that's not the point of the exercise.)}}
{{comment|(Yes, badly designed things, like parallelism that can [[deadlock]] or [[livelock]] or otherwise mess up, but that's not the point of the exercise. This problem addresses correct, deterministic problems and solutions.  )}}






For some specific code running on some specific data, absolutely.
For some specific code regardless of data, yes.  


It would be trivial to make some code-and-data examples that will always halt, and some others that run forever.
1+1 will always halt.
 
Simple.




Line 15: Line 17:
can you prove any given code will halt ''for all possible input''?
can you prove any given code will halt ''for all possible input''?


Also, you can figure this out for ''any'' possible code given to you?
For some code on some specific data, absolutely.
That's suddenly some hard proofy math problem.
 
Adding any finite list of integers will also still halt.
 
 
It would be trivial to make some code-and-data examples that will always halt.


It is often also easy enough find some fragment of code ''might'' have cases where it runs forever, and then find an example that does.


Spoilers: Nope, you cannot.
 
More interestingly, figure this out for ''any'' possible code given to you?
 
That's suddenly feels like some hard proofy math problem that other people should do.
 
 
Spoilers: Nope, you cannot.


This problem is [https://en.wikipedia.org/wiki/Undecidable_problem undecidable], meaning it is ''proven'' to be impossible to give a correct yes-or-no answer.
This problem is [https://en.wikipedia.org/wiki/Undecidable_problem undecidable], meaning it is ''proven'' to be impossible to give a correct yes-or-no answer.




Line 52: Line 64:
But partly no, it's not ''just'' a thought experiment, it has some uses.
But partly no, it's not ''just'' a thought experiment, it has some uses.


One, knowing that there are some ''perfectly valid questions'' that ''cannot be answered in reasonable time'',
One, knowing that there are some ''perfectly valid questions'' that ''cannot be perfectly answered in reasonable time'',
can save you a lot of time trying to do so, by recognizing the earmarks of such problems.  
can save you a lot of time trying to do so, by recognizing the earmarks of such problems.  


It's related to recognizing [[NP-complete]] and [[NP-hard]] problems.
It's related to recognizing [[NP-complete]] and [[NP-hard]] problems.


It's related to saying
: "this is suboptimal, but we know that we can't necessarily do much better"
: or, sometimes "this is a dirty quick fix, we ''do'' know of a much better solution but just haven't gotten to it"


(mathematicians will also care for this sort of concept, to not waste too much time)


As already mentioned, consider asking a compiler for the fastest possible code (or shortest possible, or any such absolute optimum).


Consider asking a compiler for the fastest possible code (or shortest possible, or any such optimum).
(This runs into [[optimality theory]] -- which is an entirely different topic)


You ''can'' reason about "it will never be faster than this" style bounds,
You ''can'' reason about "it will never be faster than this" style bounds,
Line 80: Line 89:
In other words: So it's really useful to know when something is really close to optimal, and go with that.  
In other words: So it's really useful to know when something is really close to optimal, and go with that.  
This is how we tackle optimizing compilers in the real world.
This is how we tackle optimizing compilers in the real world.




Line 98: Line 108:


Asking a virus scanner "do you have something that looks sort of like a known virus", leaving it up to it what 'looks like' means, makes it look for certain means of variation. This ''may'' take [[exponentially]] more CPU time (with virus size), catches more cases, and but still halts.
Asking a virus scanner "do you have something that looks sort of like a known virus", leaving it up to it what 'looks like' means, makes it look for certain means of variation. This ''may'' take [[exponentially]] more CPU time (with virus size), catches more cases, and but still halts.
It's related to saying
: "this is suboptimal, but we know that we can't necessarily do much better"
: or, sometimes "this is a dirty quick fix, we ''do'' know of a much better solution - but just haven't gotten to it"




Latest revision as of 00:49, 26 June 2024


"I suppose, but um, why is that interesting at all?"

Retrieved from "https://helpful.knobs-dials.com/index.php?title=The_halting_problem&oldid=97563"