The halting problem: Difference between revisions

From Helpful
Jump to navigation Jump to search
mNo edit summary
mNo edit summary
Line 3: Line 3:
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 ever 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)}}


For some code, absolutely.  
 
It would be trivial to make some examples that will always halt.
 
For some specific code, absolutely.  
: It would be trivial to make some examples that will always halt.




Yet, once you introduce programs for which the behaviour depends on the input,  
Yet, once you introduce programs for which the behaviour depends on the input,  
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?




Also, you can figure this out for ''any'' possible code given to you?
Spoilers: Nope.
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.
 
 
 
'''''The''''' halting problem often refers to this question in a general sense.
 
'''''A''''' halting problem can describe the property of a question
: For example, "I want you to discover the fastest possible machine code to compile this to" turns out to be a halting problem.{{verify}}
 
 
 
 
-->
==="Okaaaaay, but why is this ineresting at all?"===
<!--
Or, "So, is the halting problem just a academic exercise?"
 
 
Partly, yes.
 
A lot of the examples don't matter a lot to most programmers,
and mathematicians will probably already know this stuff through Godel and Turing.
 
 
And partly no, for a few reasons.


One, knowing that there are some ''perfectly valid questions'' that ''cannot be answered in reasonable time'',
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 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"




Spoilers: Nope. 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.
Consider asking a compiler for the fastest possible code (or shortest possible, or any such optimum).  


You ''can'' reason about "it will never be faster than this" bounds,
without having to figure out precisely what code that is, so if you can estimate our generated code is close to that, you're fine.


And even saying with certainty "it will never be much faster than this" can be valuable (to compile-time tradeoff and mores).


(Note that this problem addresses correct, deterministic things. Yes, bad thread locking can cause race conditions that deadlock or livelock, but that's not the point of the exercise)


Because it turns out that asking for the best possible answer ''is'' a halting problem.
For any particular case it ''might'' answer, but you cannot know for sure that it does.


So it's really useful to know that something is really close to optimal and go with that.
This is how we tackle optimizing compilers in the real world.




...though arguably that's just [[complexity theory]].


As to software we didn't make, well, a lot of software is written in a relatively straightforward recipe form, and finishes just because what it does doesn't vary, much or at all, with the data you give it.




However, a lot of real-world, practically useful problems do different things with different data.
Usually, this undecidability is because of an search space that is infinite. There are some cases that ''look'' finite and merely intractible, and may or may not be depending on how you ask the question.


This tends to increase the amount of possible states and possible edge cases.
In some cases in a very constrained way, in which case a complete proof it will halt will just be longer and more involved.


In other cases it's so explosively bad, or unconstrained, that a proof is intractible.
Asking a virus scanner 'is this a known virus verbatim' has a linear-time solution (with virus size and amount of data to be scanned).


{{comment|(Asking it whether it might be a permutation on one is usually much slower, because depending on how you define variation it might be, say, exponentially more CPU time (with virus size), but still halt.)}}


And sometimes it's more of a mathematical property.
Asking anti-virus scanner 'is this 100% certainly free of malicious actions at any time in the future', however, is a halting problem.


One example lies in Goldbach's conjecture - "every even integer can be expressed as a sum of two primes".


There's no short proof anyone has thought of,
so people have written program that just starts trying. Once it finds a counterexample, it will halt.


Will it halt?
https://cs.stackexchange.com/questions/32845/why-really-is-the-halting-problem-so-important


If the conjecture is false, which is provable with one counterexample, it will finish.
It also relates somewhat to the limits of machines dealing with logic -- boolean logic, at least.
If the conjecture is true, it will not. And people have run exactly such programs for a looong while, and so far gotten only answers.


Which makes it certainly ''presumable'' the conjecture is true, but is actually an unsolved problem.
And in some ways, with this approach it will remain unsolved ''if'' it is true.


But we cannot know whether that will halt.
Only if and when it does.






'''So, is the halting problem just a academic exercise?'''


Partly, yes.
https://www.quora.com/Why-is-%E2%80%9Cthe-halting-problem%E2%80%9D-a-problem-Why-does-it-exist


A lot of the examples don't matter a lot to most programmers,
and mathematicians will probably already know this stuff through Godel and Turing.




And partly no, for a few reasons.


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






Also, discussions of things like this sometimes puts rough bounds on how hard optimal solutions are, which can matter to complex dynamic problems, in that you can sometimes say
: this is sorta-bad-but-we-can't-do-much better
: or that you probably ''can'' do a lot better




For example, asking a compiler for the fastest possible code (or shortest possible, or any such optimum).


You ''can'' reason about "it will never be faster than this" bounds, without having to figure out precisely what code that is, so if you can estimate our generated code is close to that, you're fine.


Because in fact, asking for the best possible answer ''is'' a halting problem.
For any particular case it ''might'' answer, but you cannot know for sure that it does.


So it's really useful to know that something is really close to optimal and go with that.
This is how we tackle optimizing compilers in the real world.


As to software we didn't make, well, a lot of software is written in a relatively straightforward recipe form, and finishes just because what it does doesn't vary, much or at all, with the data you give it.


...though arguably that's just [[complexity theory]].


However, a lot of real-world, practically useful problems do different things with different data.


This tends to increase the amount of possible states and possible edge cases.
In some cases in a very constrained way, in which case a complete proof it will halt will just be longer and more involved.


Usually, this undecidability is because of an search space that is infinite. There are some cases that ''look'' finite and merely intractible, and may or may not be depending on how you ask the question.
In other cases it's so explosively bad, or unconstrained, that a proof is intractible.




Asking a virus scanner 'is this a known virus verbatim' has a linear-time solution (with virus size and amount of data to be scanned).
And sometimes it's more of a mathematical property.


{{comment|(Asking it whether it might be a permutation on one is usually much slower, because depending on how you define variation it might be, say, exponentially more CPU time (with virus size), but still halt.)}}


Asking anti-virus scanner 'is this 100% certainly free of malicious actions at any time in the future', however, is a halting problem.


One example lies in Goldbach's conjecture - "every even integer can be expressed as a sum of two primes".


There's no short proof anyone has thought of,
so people have written program that just starts trying. Once it finds a counterexample, it will halt.


https://cs.stackexchange.com/questions/32845/why-really-is-the-halting-problem-so-important
Will it halt?


It also relates somewhat to the limits of machines dealing with logic -- boolean logic, at least.
If the conjecture is false, which is provable with one counterexample, it will finish.
If the conjecture is true, it will not. And people have run exactly such programs for a looong while, and so far gotten only answers.


Which makes it certainly ''presumable'' the conjecture is true, but is actually an unsolved problem.
And in some ways, with this approach it will remain unsolved ''if'' it is true.


But we cannot know whether that will halt.
Only if and when it does.








https://www.quora.com/Why-is-%E2%80%9Cthe-halting-problem%E2%80%9D-a-problem-Why-does-it-exist




-->
-->

Revision as of 14:04, 28 November 2023

"Okaaaaay, but why is this ineresting at all?"

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