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)}}
{{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 specific code, absolutely.  
For some specific code running on some specific data, absolutely.
: It would be trivial to make some examples that will always halt.
 
It would be trivial to make some code-and-data examples that will always halt, and some others that run forever.




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?
That's suddenly some hard proofy math problem.


Spoilers: Nope, you cannot. 


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.
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.
'''''The''''' halting problem often refers to this question in a general sense.
: i.e. the concept being discussed here


'''''A''''' halting problem can describe the property of a question  
'''''A''''' halting problem can describe this property of a particular 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}}
: For example, "I want you to discover the fastest possible machine code to compile this to" turns out to be a halting problem.{{verify}}




-->




-->
==="I suppose, but um, why is that interesting ''at all''?"===
==="Okaaaaay, but why is that interesting at all?"===
<!--
<!--
Or, "So, is the halting problem just a academic exercise?"
Or, "So, is the halting problem just a academic exercise?"
Partly, yes.




Partly, yes.
Mathematicians like this sort of thing, though will probably already seen this stuff through Godel and Turing.


A lot of the examples don't matter a lot to most programmers,
Programmers may care in theory, but a lot of the examples you will see in discussions do not matter  
and mathematicians will probably already know this stuff through Godel and Turing.
to ''most'' programmers.




And partly no, for a few reasons.
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 answered in reasonable time'',
Line 52: Line 60:
: "this is suboptimal, but we know that we can't necessarily do much better"
: "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"
: 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)




Consider asking a compiler for the fastest possible code (or shortest possible, or any such optimum).  
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,  
You ''can'' reason about "it will never be faster than this" style 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 determine those bounds ''without'' having to figure out precisely what code that is.


And even saying with certainty "it will never be much faster than this" can be valuable (to compile-time tradeoff and mores).
Because it turns out that asking for ''the'' best possible answer ''is'' a halting problem.


Knowing that, it suddenly becomes really useful that,
if we can say with certainty code can fundamentally never be more than (roughly) 10% faster than it is now,
that is valuable, e.g. to tradeoffs made at compile time - it makes cost ''and'' benefit (roughly) quantifiable,
and makes it easier to decide ''when'' we are happy with the result.


Because it turns out that asking for the best possible answer ''is'' a halting problem.
(...though arguably that's crossing over into [[complexity theory]]).
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.  
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.




...though arguably that's just [[complexity theory]].
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.




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.)}}
Usually, this undecidability is because of an search space that is or becomes infinite.


Asking anti-virus scanner 'is this 100% certainly free of malicious actions at any time in the future', however, is a halting problem.
There are some cases that ''look'' finite and merely intractible.




Sometimes that difference depending on the precise wording of the question.


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


It also relates somewhat to the limits of machines dealing with logic -- boolean logic, at least.
Asking a virus scanner "do you have a ''known'' virus, verbatim" has a linear-time solution (that is, linear with virus size, and amount of data to be scanned).


Asking anti-virus scanner "is this PC 100% certainly free of code that may have malicious actions at any time in the future", however, is a halting problem.


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.






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


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




It also relates somewhat to the limits of machines dealing with logic -- boolean logic, at least.






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.




 
A lot of real-world data varies may take different approaches with different data. That may be the ''point''.
 
 
 
 
 
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.


This tends to increase the amount of possible states and possible edge cases.
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 some cases in a very constrained way, in which case a complete proof it will halt will is only more work.


In other cases it's so explosively bad, or unconstrained, that a proof is intractible.
In other cases it's so explosively bad, or unconstrained, that a proof is intractible.




And sometimes it's more of a mathematical property.


And sometimes it's more of a mathematical property. That may be hard to ''know'',
but often things have all the earmarks of 'timesink/insanity awaits those who try'.




One example lies in Goldbach's conjecture - "every even integer can be expressed as a sum of two primes".
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,  
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.
so people have written program that just starts finding an answer for every integer.  
Once it finds a counterexample, it will halt.


Will it halt?
Will it halt?


If the conjecture is false, which is provable with one counterexample, it will finish.
If the conjecture is false, which is provable with any 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.
If the conjecture is true, it will never finish.  


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.
There are heuristics that suggest it might be true and never halt.
Only if and when it does.


People have run exactly such programs for a long while, and so far gotten only answers (up to 4E18 so far).


Which makes it certainly ''presumable'' the conjecture is true, but is actually an unsolved problem.


And in some ways, ''if'' the conjecture is true,
''that means'' it will be impossible to solve in this exhaustive-search way.




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


-->
-->

Latest revision as of 14:32, 25 March 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=94583"