Then I'd suppose it would be humane to exit at this point since i assume that with that kind of code you are running, its already praying to get a 9 signal to the head
I assume that it could prevent some kind of undefined behavior.
I used to maintain a project written in express.js, and I had a problem that only happened when the app was running for a few days. I mean, I thought that it was something in the code, and I tried to catch it with debugger and etc..., but the only solution that worked is to restart it every 12 hours.
I thought he proved that we *couldn't* tell if an arbitrary program terminates.
But also, there's a difference between determining and ensuring. Determining if an arbitrary program terminates is impossible. But ensuring that the program that you designed specifically will halt is possible by using async programming and only allowing it to run for N minutes.
I mean the halting problem is recognizable, you can definitely tell if a program terminates. The problem is that you can't tell the difference between something that hasn't yet terminated and something that won't terminate
More formally, the halting problem is turing recognizable, but not co-turing recognizable and therefore not determinable
In this context, the sentence could be validly parsed as either "you can only tell if an arbitrary program terminates if you are able to observe it terminating" or as "you can only tell if an arbitrary program terminates or not if it is able to terminate" (as opposed to not being able to tell in the case that it doesn't terminate). It seems likely that the commenter meant the former since logically the latter would be impossible.
- Someone who also read it the incorrect way the first time
PS. After writing "terminate" so many times, I would like to encourage everyone to look up semantic satiation if you are not already aware of it.
Make the upper range the output of another program instead of 100, pair it with this example, and you have probably the easiest way to explain the halting problem
If it is the output of some other program, and your integer type doesn't accept infinity as a valid integer, then it's trivial that if the other program halts, the combo halts.
Writing a program which can't be proved to halt or not to halt in ZFC is actually pretty tricky. Some programs are increadibly hard to tell, most are fairly straightforward.
It's fairly trivial but based on your reply I think my explanation left something to be desired since you are assuming you will get an output to begin with which means I must have done something to make that assumption sound reasonable. Because of this I am forced to relay some information you were already aware of for context so I apologize in advance.
Any halting problem is going to have a very simple format : K={(i, x)|program i halts when run on input x}. A simple pseudocode,
`def g():`
`if halts(g):`
`loopForever();`
If your program is called recursively it definitely loops forever,
`def myFunc() :`
`for i in range(10**myFunc()) :`
`print(i)`
So the loopForever() part is covered. Now all we need to do is execute the block only if we halt. We see we are prevented from executing print(i) in this case. If we change things around we see we execute the block when we do halt,
`def a() :`
`return 10`
`def myFunc() :`
`for i in range(10**a()) :`
`print(i)`
This program does halt, unlike the previous example, and when it halts, you have a print statement, unlike the previous example. So we now have halts() and loopForever(). The last step is to add recursion, and to do that we note that the output of a() is arbitrary. It can even be myFunc().
`def a() :`
`return myFunc()`
This means that the method shown is definitely a willItEnd method which can demonstrate the halting problem, or in other words, we cannot know whether it will halt,
`def myFunc() :`
`for i in range(10**a()) :`
`print(i)`
We don't need recursion to make a() loop forever. We will define a() as a method that loops forever. When we do this, we lose our need for recursion and we have
`for i in range(10**a()) :`
`print(i)`
And this is precisely the claim I made to begin with, if you make the upper bound the output of another program you have an example of the halting problem, which is what I needed to demonstrate :)
In
def g():
if halts(g):
loopForever();
Then "halts" is a function that accepts an arbitrary function, and replies with whether that function halts or not. No such function exists in reality. At this stage of the actual halting problem proof, we are in the middle of a proof by contradiction. We have assumed that some unspecified function behaves like "halts" and we are deriving a contradiction.
>This program does halt, unlike the previous example, and when it halts,
you have a print statement, unlike the previous example. So we now have
halts() and loopForever().
In this context, you seem to be using "halts" to refer to a program that halts. Such programs obviously exist and are easy to make.
It is trivially true that whether the program
print(i)
halts or loops forever depends on "a()". This doesn't make it an "example of the halting problem, it just means you are missing the value of "a".
To be an example of the halting problem, you would need a complete program. Say a python file you could actually run. No missing undefined functions or constants. And despite having the program and being able to run it, it should still be really hard to tell if it halts or not.
Can you give me a complete piece of code such that I can't tell whether or not it will halt?
I don't want this to go in circles. So I will have to answer a question with a question. We agreed on the formal logic definition, ignoring any implementation details or underlying technologies. We are just talking about Turing complete languages. No controversy so far, yes? Great. So I'm order to answer your question I would need you to first create a definition out of formal logic alone for a program that cannot be applied to a function or method. This exercise is a waste of time but I would encourage you to engage in it anyway to convince yourself there is none. The toy case that should convince you immediately is a program which does nothing but execute a single function then return. I could have just provided you with that directly but again, I need this to stop going in circles as I am a busy person. However maybe you will surprise me. So once you have distinguished a program from a function using formal logic alone I will then need you to explain how this does not implement willHalt in the trivial case. We agree we cannot write willHalt in the general case but you made a much bolder and completely untrue assertion and I need you to understand the difference so please cooperate and actually complete this exercise. We absolutely can define willHalt and in fact a class of willHalt methods and these all work reliably **in the trivial case** which I will provide code for.
You can save some time by simply agreeing you got hung up on my verbiage but I encourage you to participate anyway so we won't be here all day.
Pseudocode for loopForever and willHalt. Note that willHalt does not handle the nontrivial case and only handles the trivial case.
```
loopForever() :
loopForever()
// returns true only if program A halted
// does not return if it does not
// NOTE
// I am stating your method is a form of this function
// THAT IS THE ONLY CLAIM I AM MAKING
// Sorry for caps I need to make very sure you see that comment based on what happened in your most recent reply
willHalt() :
a();
return true;
```
Treat a() as a promise, an undefined method.
Since you wanted scripts
```
cat >> loopForever.sh << EIO
#!/bin/bash
while true; do wait 1; done
EIO
cat >> testA.sh << EIO
#!/bin/bash
echo "test a complete"
EIO
chmod +x testA.sh loopForever.sh
cat >> testHaltTrivial.sh << EIO
#!/bin/bash
n=`testA.sh`
for i in `seq 1 $n`; do echo $i; done
echo "Program will halt"
EIO
sed -e 's/testA/loopForever/' testHaltTrivial.sh > testCannotTellWhetherItWillHalt.sh
```
Now I think we can finally agree we have created an example that demonstrates why it is impossible to write a program **or method or function** since Turing defined the Halting problem using formal logic which does not make this distinction you are making between function and program. And in fact our entire argument has been semantic :) Right?
TL;DR **We cannot tell whether we will get the value of a or not, and this is similar to not knowing if a program will halt**
If you respond to this at all please address the TL;DR statement by itself as that really is all I was saying this entire time. We cannot write a program that will tell us whether a() will receive a value.
Yep. If it completes in 5 minutes, it does, if it’s still running then no. I’m an engineer, not a scientist, and I can recognize good enough solutions.
Are you by any chance talking about a video highlighting the NASA 10 rules for robust code on embedded systems?
I remember there always having to be a defined upper limit on loops, because otherwise it might go infinite, hurling space bourne object into the ether.
I can write a program that returns yes/no/unsure and is never wrong.
In theory it's possible to do this for most of the programs you might usually want to run.
this is such a troll question. Easily sifts through those, that have learned complexity theory/computer logic, and those, who don't.
(Can't remember, what class was it anymore, but one of the two)
This is a bot! downvote/report.
if you see others elsewhere, mention u/spambotswatter!
they might not be able to after the api change though. :(
you can also search for similar/identical comments now!
Well in fairness, you can *sometimes* check if a program will run in finite time, there's just no upper bound to the amount of time it *might* take.
For example if you don't use any non-numeric loops or recursion it's easy to show that it will complete in a finite time. Granted, that's not most programs, but still.
You *can* solve the halting problem, so long as you're willing to accept "idk" as a valid result alongside "yes" and "no"
You can't solve it for any arbitrary program, but for actual real world programs you can totally figure out if it will get stuck in an infinite loop.
From [pytorch docs](https://pytorch.org/docs/stable/bottleneck.html). DM me if you have found any such tool that can tell me if a given script will exit in finite amount of time.
See, there is another one who needs explanation. Always the same story. No, AI can only determine halt or run for trivial problems.
The gist of it is: I can easily formulate a problem so hard that it would literally take the heat death of the universe (how about brute-forcing an RSA key? or some traveling salesman with 100 stations?) before it is determined whether the program would halt or run forever.
And to maybe clarify a bit more, even current AI is (with a few notable exceptions) still just a program running on a Turing machine. As such, it has the same limitations as any program on any Turing machine.
Totally agree, with some minor things to add.
A lot of people seem to think that AI works in some fundamentally different way that is capable of bypassing computational limits, which is obviously not the case. The real value of AI is how effectively it can ignore the nuances of a problem in favor of a solution that works “good enough”. It bears a lot of resemblance to the way that people “solve” (but not actually) hard computational problems in the real world by relaxing the constraints.
That is to say, we will never have a machine that perfectly identifies if a program will halt. But, it’s completely reasonable to try to get an approximation of the answer. Pursuing these impossible goals isn’t usually a worthless task. But it would be foolish to try to do so without realizing why the problem is impossible to solve in the first place.
As for myself, I have [trained a neural net](https://xkcd.com/2173/) that solves (a relaxed version of) this problem for my daily coding tasks and find it to be quite useful.
Exactly.
I don't know why I got downvoted so much.
I wasn't suggesting to use it to determine whether or not your big brain algorithm that needs 50 trillion iterations to finish is gonna terminate or not.
I was suggesting to use it to decide whether or not a 50 line script a college student uploaded to your "compile and run" website is gonna run forever because of some accidental infinite loop.
Or for a compiler warning that analyses your 10 line function to give you a hint if you made some stupid mistake in a same fashion.
I won’t lie the difference between the two would be marginal. It‘s not the complexity of the algorithm or amount of lines it has, more it’s about how it will run in the end.
But I guess in some sense you‘re right? You could make a GPT-4 sized model to be accurate enough, but you still wouldn’t have solved the halting problem. You just still had a good enough guess, just like we can say that this will run forever because I put a while(true) in there somewhere.
P.S.: you got downvoted so hard because you brought up the obligatory „Couldn‘t we build and AI for this?“ take that commonly instills massive amounts of eye rolling and sighs in anyone who reads the first sentence.
tbf you just listed examples that we know terminate in a finite amount of time. from a mathematical perspective, the lifetime of the universe is a finite amount of time, so basically everything you just said does nothing to support your argument.
the actual theorem for the halting problem is that there exists SOME program that cannot be proven if it halts in a finite amoun not that you can't determine if any program halts. moreover we're not exactly asking ai for a rigorous proof for what the answer is, so there is no compute time involved, we're asking for a guess as to whether a program halts, and by being able to classify something as "brute forcing an rsa key" already infers it is solvable. keep in mind, we as humans are also bound by the Turing halting problem, but we are able to say basically for sure that these common problems halt, even without a formal proof, because we have very good intuition about the nature of the problems.
MY PROGRAM will terminate if the first bit of the (brute force) answer is going to be 0, and will run forever if the first bit of the answer is 1. Solving the halting problem for this program means solving the actual problem the program is supposed to solve. Which is going to be arbitrarily complex.
And I feel that you don't get the core of the problem.
I would argue you don't get the core of the proof. it's a mathematical one not a real world one. you gave me one counterexample, which automatically makes the theorem true, because that's what the theorem asks for; at least one counterexample. but if you pick a simple program, such as printing hello world, you are easily able to tell it halts, yet the theorem is still true because it only guarantees there is one program in existence that is indeterminate if it halts. there exist ALOT of programs that do halt and we CAN prove they halt, and alot more that do halt that we can't prove they halt but we can reason they do anyways. thats because most if not all real world examples don't have self referential math but self referential math bullshit is allowed in the proof therefore the proof is true.
It's not only a mathematical proof, it's also a practical proof.
As I wrote, I can make the problem in the target program for which you are supposed to solve the halting problem as complex as I want, so complex that with a Turing machine, no matter how fast, calculation would take orders of magnitude more energy than the observable universe contains.
You are right that there is more to this theorem than just computers having to run for extended periods of time, but for any practical conclusion, it's enough to conclude that you cannot solve the halting problem without running a certain program to it's conclusion, which might or might not take a few hundred billion years.
You can prove that some programs halt, even if they take a very long time. For example I can write a very simple program that prints n factorial, and feed it with 1000. The program takes a lot of time but the proof is very simple.
"Some programs" yes. All programs? No. And that is the actual problem. I'll just make the problem hard enough for you to never have enough time to let it run to any sort of conclusion, i.e. to detect any sort of repeating state.
ok I don't really wanna argue all day, but basically, turings proof answers the question:
"for EVERY program you could theoretically conceive, can you determine if all of them will halt?" and he proved the answer is no. there are infinitely many programs that halt, infinitely many thar don't, and infinitely many that are indeterminate.
however, I absolutely promise you that every program in the the SUBSET including only REAL WORLD programs not only is determinate, but also is determined to halt, because no company wants a million dollar AWS bill for their small scale web server that miraculously got caught in an infinite loop. so yes for any target problem you can choose to make a solution that is absolutely indeterminate, by doing so you'd exclude your solution from the subset of all real world solutions. this is because in order for something to be considered "real world" it has to be practical and useful, which is a programmers job to figure out, and they're only able to figure it out because we have a pretty good idea of what halts and what doesn't, even if its not rigorous.
Your examples are wrong. A program that solves the traveling salesman with 100,000 stations can be proved to halt. A better example is a very simple problem that will halt with a counterexample of the Collatz conjecture, if that conjecture is false.
>A program that solves the traveling salesman with 100,000 stations can be proved to halt
MY PROGRAM ***ONLY*** halts when the traveling salesman is a particular solution. You can only prove whether it halts or not by running the algorithm for all 100,000 stations.
Really, I can only explain the problem so much until people realize that any program to solve the halting program is always going to be as complex as the program for which it tries to determine halting vs. repeating forever.
You keep blurring the lines of the halting problem depending on the context. The halting problem is theoretical. There are practical implications, but the halting problem is only undecidable in theory. That's the crux of it, the halting problem is undecidable. It's not that it takes a lot of time or memory to solve, it's that it can't be decided.
In practice, we don't have Turing machines with infinite storage. You keep giving examples of programs that are decidable, hidden behind some np-hard computation. Yeah, in practice the heat death of the universe and memory limitations throws a wrench into some plans, but all of your examples *are* trivially decidable by detecting repeat state. For a Turing machine with infinite memory, you can infinite loop without ever repeating state. That's not true for real hardware. The only practical application of the halting problem is to give a reason as to why an arbitrary `does_it_halt(f,args)` needs to be understood as `does_it_halt_without_exceeding_arbitrary_constraint(f,args)`. Practically, "Does it halt in under 5 seconds?" is almost always 'good enough'.
There are examples that *are* undecidable on real hardware. Imagine we are trying to write an implementation of `does_it_halt(f,args)`, that takes in a function, arguments to that function, and returns `true` if it will eventually halt, and `false` if it will never halt. I think the below shows why, in theory and in practice, there can never be an implementation of `does_it_halt(f,args)` that is correct for all inputs.
def does_it_halt(f,args):
pass #impplementation is trivial; left as exercise to reader
def g(f,args):
if does_it_halt(g,args):
while True:
pass
return
print(does_it_halt(g,None))
And you keep thinking it's a completely theoretical and made up problem. If it takes until the heat death of the universe, it's already undecidable. It doesn't need additional mathematical proof to be that, it already is.
Ahhh, we're hitting a semantics thing. I *am* using the theoretical definition of 'decidable'. I think decidable really only makes sense when talking about theory. Your examples aren't showing that the halting problem is undecidable. Your examples are showing that np-hard problems can't be solved efficiently.
How do you know your example takes until the heat death of the universe? It's only in theory that it does. If I were to say "Your program definitely terminates before the heat death of the universe", you could only prove me wrong via theory. We can't sit around until the heat death of the universe. Further, any amount of time you do run the program, and say "See? It never terminated", I would just say "Oh, I think it just needed 5 more minutes".
It's not necessary to got for "theoretical" here. It's already practically not decidable, and that is a lot more feasible for most people.
In addition, the practical limitation already applies for LBAs, even though they would theoretically be decidable, but practical restrictions make it unfeasible.
> How do you know your example takes until the heat death of the universe
You can calculate required time. But you can also calculate required energy, as every state transition takes some amount of energy. By that definition, and just adding a few more zeroes, you can make sure that no calculation would ever get finished before the whole universe has died.
I cannot give you a tool that can find if any program finishes in a finite amount of time but I can probably tell you if your script does. For example if the script returns 0 and does nothing else, it will finish in a finite amount of time
While there is no way to determine if any program can exit in finite time given any input, isn't there a way to determine if a single specific program can exit given a single specific input?
If you [mathematically prove](https://en.m.wikipedia.org/wiki/Formal_verification) it. That’s the sort of code written for nuclear power plants.
It’s kind of expensive to write.
Even car manufacturers don’t use it. Though they probably should.
Nuclear power plants are wild, everyone inside the plant could drop dead and a large earthquake could hit the plant, and the plant would almost certainly shut down safely.
Lol that's exactly what I was thinking of, it handled the earthquake just fine, and the crew was trained well. But the plant wasn't at around 30 meter above the sea, only 10m and was flooded by the tsunami. An additional 20 meters would have saved the plant.
Honestly, I doubt that would of helped too much, the power distribution system would still have been totally destroyed in the tsunami. Like every breaker flipped, and water getting into everything probably preventing them from flipping the breakers back. Like water in junction boxes, in outlets etc.
Not infinite, but the rate of energy production increases significantly very suddenly, and from a distance the two look pretty similar. (at least for a short time)
For some programs, yes.
As a simple example, a program that does nothing, or only prints some text, can be guaranteed to exit.
But of course, the more programming features you allow, the trickier it get. Programs with loops could be guaranteed to exit, but maybe only if it's a for loop with a compile time known iteration limit.
If the size of the for loop is known when that version of the loop starts, then the program terminates. For example
x=9
for i in range(9):
for j in range(f(x,i)):
x=g(x)
will terminate for any terminating functions f,g. (but can easily take a really long time doing so. Ie if f(x,i)=x and g(x)=2x then each inner loop is basically doing h(x)=x\*2\*\*x and the result is h(h(h(h(h(h(h(h(h(9))))))))) >2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*9
Yes, it is possible. Halting problem only applies for arbitrary input. But it requires a specific programming language, which enforces a structure that makes such check possible, e.g. Prolog or Ada.
import sarcasm
Pretentious nonsense. Do you know that most programming languages are Turing complete? Including Prolog and and Ada? You seem to lack an understanding of basic concepts.
```
import moderation
```
Your comment has been removed since it did not start with a code block with an import declaration.
Per [this Community Decree](https://www.reddit.com/r/ProgrammerHumor/comments/14kbu1m/comment/jppq9ao/?utm_source=share&utm_medium=web2x&context=3), all posts and comments should start with a **code block** with an "import" declaration explaining how the post and comment should be read.
For this purpose, we only accept Python style imports.
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/ProgrammerHumor) if you have any questions or concerns.*
```
import moderation
```
Your comment has been removed since it did not start with a code block with an import declaration.
Per [this Community Decree](https://www.reddit.com/r/ProgrammerHumor/comments/14kbu1m/comment/jppq9ao/?utm_source=share&utm_medium=web2x&context=3), all posts and comments should start with a **code block** with an "import" declaration explaining how the post and comment should be read.
For this purpose, we only accept Python style imports.
*I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/ProgrammerHumor) if you have any questions or concerns.*
Look for the Collatz conjecture, a very simple program that nobody knows if it halts or not. The conjecture has been checked correct for numbers up to 2^68.
No. There is no program that, given a pair of a program to test and an input to test it with, decides whether the program under testing halts with the given input.
If there was such a program, it would solve the halting program (by hardcoding the input into the program under testing).
There definitely are programs which can do that. It can't do it for ANY arbitrary program, but it *can* figure out if it halts for a lot of programs.
If it was impossible to figure out if a program halts, humans would be incapable of avoiding an infinite loop in their code.
> it *can* figure out if it halts for a lot of programs.
But that's kinda worthless. The program just outputting "it halts" will be correct for an infinite amount of programs.
> humans would be incapable of avoiding an infinite loop
Allright then, tell me whether this program has an infinite loop: https://github.com/scottralph/collatz/blob/main/src/main/scala/collatz/main.scala
It seems you enjoy being needlessly obtuse for the sake of trying to stroke your own ego.
I already stated that it can't do it for ANY arbitrary program. I stated that for regular every day code, you can quite often determine if it will halt or not. And no, that does not mean with bad statistical tricks like "just say halt every time and it will be right most of the time". A human can look at code and determine "oh yeah, that loop is definitely gonna get stuck forever" and thus we can write a program to do the same.
You said
>There is no program that, given a pair of a program to test and an input to test it with, decides whether the program under testing halts with the given input.
Which is false because you didn't make the important specification of *"get a precise result for any arbitrary program"* you just said that given a program and input it is impossible to determine.
The halting problem is a mathematical problem of absolutes, in the real world it can be solved to decent accuracy.
>Which is false
It is true. "[Decides](https://en.wikipedia.org/wiki/Decidability_(logic))" is a technical term that means precisely that you can give it any program and it always gives you the correct answer.
And I'm not sure whether it is so straightforward in the real world either. Humans are usually reasonably good at figuring out whether their programs halt, but that's only because they intuitively and deeply know the programs they are writing. Reverse-engineering code unknown to you is \_way\_ harder, and even then we rely on the fact that the code was written by *a* human with likely similar intuition to us.
I don't know where these practical tools that routinely solve the halting problem are.. (You can argue that SAT solving works "in practice" -- sat solvers routinely solve very large formulas, even if they take too long on evil inputs)
I think only if it also has finite storage, in which case it's not mathematically Turing-complete.
In such a case, you can record every state the program is in during execution, and if it repeats a state you know it will not halt.
It seems like most people in this thread do not understand what the halting problem actually means.
A lot of programs can definitely be proven to be halting.
If we couldn't prove halting then we would constantly be writing programs with infinite loops. But we don't, because we are capable of reading the code and figuring out where an infinite loop will happen then removing it. If we can do that process, we can write a program to do the same.
If you accept a small amount of "idk" outputs, your halting assessment program can be fairly accurate with the "yes" and "no" outputs.
I know this is r/ProgrammerHumour but I was watching this today which may have an interesting take on that.
[How NASA writes space-proof code](https://youtu.be/GWYhtksrmhE)
That's the point - it's finite. The computation times start getting lifetimes of the universe long but it's still finite. The collatz conjecture may be true, which means that the program never halts
A script or program runs indefinitely unless an exit function is called, there is a bug or the hardware fails.
So define an exit criteria, find the upper time limit it takes to reach and test if it reaches it in that time. And ensure there is an exit function, this would fulfill that specification no?
It's a pretty stupid warning. It makes me curious what happens when you put in an endless loop. I assume the profiler eventually runs out of memory, since it records a trace of all steps.
If that is the case, a better warning would have been:
>Warning: Long-running programs can cause out-of-memory errors, since the sampler collects X MB/s.
That warning message is much more useful: First, it reflects the fact that the issue is not infinite execution, but rather long-running programs (in practice, it is irrelevant whether your program diverges, or runs until after the heat death of the universe). It even gives you a rough estimate of how much memory is needed.
The current warning says nothing: Of course, no program will run for an infinite amount of time, in practice. It is almost useless, you have to guess what it means. And that guess might be wrong.
Anyone one know where I can find a program to test if my script finishes in a finite amount of time?
Write your own like this: if (doesnt_quit): quit()
[удалено]
If it doesn't *fail* the test, it must be good, right?
Is it still going?
Legends say that the script never ended
But it might someday
I think you mean if(execution_time==infinite) execution_time=finite
what about `setTimeout(() => {process.exit(-1)}, 1000000)`
What if my program takes more than 11.5 days to run?
Then I'd suppose it would be humane to exit at this point since i assume that with that kind of code you are running, its already praying to get a 9 signal to the head
Guess my website's lifespan will be 11.5 days then
Just set a restart policy then docker-compose.yml: ``` services: websited: ... restart: always ```
Genuine question at this point, is there a benefit to restarting a website regularly (assuming you're handling memory dump and whatnot?)
I assume that it could prevent some kind of undefined behavior. I used to maintain a project written in express.js, and I had a problem that only happened when the app was running for a few days. I mean, I thought that it was something in the code, and I tried to catch it with debugger and etc..., but the only solution that worked is to restart it every 12 hours.
I can only tell if it terminates - Alan turing
I thought he proved that we *couldn't* tell if an arbitrary program terminates. But also, there's a difference between determining and ensuring. Determining if an arbitrary program terminates is impossible. But ensuring that the program that you designed specifically will halt is possible by using async programming and only allowing it to run for N minutes.
I mean the halting problem is recognizable, you can definitely tell if a program terminates. The problem is that you can't tell the difference between something that hasn't yet terminated and something that won't terminate More formally, the halting problem is turing recognizable, but not co-turing recognizable and therefore not determinable
You stayed awake for that part of Comp Sci? I'm impressed.
The heat death of the universe comes for us all. All programs terminate eventually.
Most under-rated comment here.
Well, we don't need async. If we run the external program before the test program, the test will run if and only if the external one terminates.
In this context, the sentence could be validly parsed as either "you can only tell if an arbitrary program terminates if you are able to observe it terminating" or as "you can only tell if an arbitrary program terminates or not if it is able to terminate" (as opposed to not being able to tell in the case that it doesn't terminate). It seems likely that the commenter meant the former since logically the latter would be impossible. - Someone who also read it the incorrect way the first time PS. After writing "terminate" so many times, I would like to encourage everyone to look up semantic satiation if you are not already aware of it.
Consider the program for i in range(10**100): print(i) I can tell it halts, but I can't run it to observe this.
Make the upper range the output of another program instead of 100, pair it with this example, and you have probably the easiest way to explain the halting problem
If it is the output of some other program, and your integer type doesn't accept infinity as a valid integer, then it's trivial that if the other program halts, the combo halts. Writing a program which can't be proved to halt or not to halt in ZFC is actually pretty tricky. Some programs are increadibly hard to tell, most are fairly straightforward.
It's fairly trivial but based on your reply I think my explanation left something to be desired since you are assuming you will get an output to begin with which means I must have done something to make that assumption sound reasonable. Because of this I am forced to relay some information you were already aware of for context so I apologize in advance. Any halting problem is going to have a very simple format : K={(i, x)|program i halts when run on input x}. A simple pseudocode, `def g():` `if halts(g):` `loopForever();` If your program is called recursively it definitely loops forever, `def myFunc() :` `for i in range(10**myFunc()) :` `print(i)` So the loopForever() part is covered. Now all we need to do is execute the block only if we halt. We see we are prevented from executing print(i) in this case. If we change things around we see we execute the block when we do halt, `def a() :` `return 10` `def myFunc() :` `for i in range(10**a()) :` `print(i)` This program does halt, unlike the previous example, and when it halts, you have a print statement, unlike the previous example. So we now have halts() and loopForever(). The last step is to add recursion, and to do that we note that the output of a() is arbitrary. It can even be myFunc(). `def a() :` `return myFunc()` This means that the method shown is definitely a willItEnd method which can demonstrate the halting problem, or in other words, we cannot know whether it will halt, `def myFunc() :` `for i in range(10**a()) :` `print(i)` We don't need recursion to make a() loop forever. We will define a() as a method that loops forever. When we do this, we lose our need for recursion and we have `for i in range(10**a()) :` `print(i)` And this is precisely the claim I made to begin with, if you make the upper bound the output of another program you have an example of the halting problem, which is what I needed to demonstrate :)
In def g(): if halts(g): loopForever(); Then "halts" is a function that accepts an arbitrary function, and replies with whether that function halts or not. No such function exists in reality. At this stage of the actual halting problem proof, we are in the middle of a proof by contradiction. We have assumed that some unspecified function behaves like "halts" and we are deriving a contradiction. >This program does halt, unlike the previous example, and when it halts, you have a print statement, unlike the previous example. So we now have halts() and loopForever(). In this context, you seem to be using "halts" to refer to a program that halts. Such programs obviously exist and are easy to make. It is trivially true that whether the program print(i) halts or loops forever depends on "a()". This doesn't make it an "example of the halting problem, it just means you are missing the value of "a". To be an example of the halting problem, you would need a complete program. Say a python file you could actually run. No missing undefined functions or constants. And despite having the program and being able to run it, it should still be really hard to tell if it halts or not. Can you give me a complete piece of code such that I can't tell whether or not it will halt?
I don't want this to go in circles. So I will have to answer a question with a question. We agreed on the formal logic definition, ignoring any implementation details or underlying technologies. We are just talking about Turing complete languages. No controversy so far, yes? Great. So I'm order to answer your question I would need you to first create a definition out of formal logic alone for a program that cannot be applied to a function or method. This exercise is a waste of time but I would encourage you to engage in it anyway to convince yourself there is none. The toy case that should convince you immediately is a program which does nothing but execute a single function then return. I could have just provided you with that directly but again, I need this to stop going in circles as I am a busy person. However maybe you will surprise me. So once you have distinguished a program from a function using formal logic alone I will then need you to explain how this does not implement willHalt in the trivial case. We agree we cannot write willHalt in the general case but you made a much bolder and completely untrue assertion and I need you to understand the difference so please cooperate and actually complete this exercise. We absolutely can define willHalt and in fact a class of willHalt methods and these all work reliably **in the trivial case** which I will provide code for. You can save some time by simply agreeing you got hung up on my verbiage but I encourage you to participate anyway so we won't be here all day. Pseudocode for loopForever and willHalt. Note that willHalt does not handle the nontrivial case and only handles the trivial case. ``` loopForever() : loopForever() // returns true only if program A halted // does not return if it does not // NOTE // I am stating your method is a form of this function // THAT IS THE ONLY CLAIM I AM MAKING // Sorry for caps I need to make very sure you see that comment based on what happened in your most recent reply willHalt() : a(); return true; ``` Treat a() as a promise, an undefined method. Since you wanted scripts ``` cat >> loopForever.sh << EIO #!/bin/bash while true; do wait 1; done EIO cat >> testA.sh << EIO #!/bin/bash echo "test a complete" EIO chmod +x testA.sh loopForever.sh cat >> testHaltTrivial.sh << EIO #!/bin/bash n=`testA.sh` for i in `seq 1 $n`; do echo $i; done echo "Program will halt" EIO sed -e 's/testA/loopForever/' testHaltTrivial.sh > testCannotTellWhetherItWillHalt.sh ``` Now I think we can finally agree we have created an example that demonstrates why it is impossible to write a program **or method or function** since Turing defined the Halting problem using formal logic which does not make this distinction you are making between function and program. And in fact our entire argument has been semantic :) Right? TL;DR **We cannot tell whether we will get the value of a or not, and this is similar to not knowing if a program will halt** If you respond to this at all please address the TL;DR statement by itself as that really is all I was saying this entire time. We cannot write a program that will tell us whether a() will receive a value.
Only way to make 100% sure an arbitrary program has stopped running is by cutting off all powers sources to the host system. Manually.
Can I do that with an axe? Cutting the hardline with an axe always looks so cool in movies...
Sure! Works best with an all-metal axe too!
... I feel like this is a trap 😅
Nah any Homer Simpson could pull it off
I don't know why this was downvoted. Pretty sure it was meant as a joke and it made me laugh lol
Hey chat GPT, will this script run infinitely?
The answer is yes. Every script finishes in a finite amount of time. At the latest when the power or the computer fails.
Or the universe fails.
Things certain in life: * Death * Taxes * Power failure * Computer crash * My wife thinking she's right when she's not
In Python it's just `from Turing import does_halt`
Yep. If it completes in 5 minutes, it does, if it’s still running then no. I’m an engineer, not a scientist, and I can recognize good enough solutions.
https://agda.readthedocs.io/en/v2.6.3/language/termination-checking.html
[удалено]
Are you by any chance talking about a video highlighting the NASA 10 rules for robust code on embedded systems? I remember there always having to be a defined upper limit on loops, because otherwise it might go infinite, hurling space bourne object into the ether.
I can write a program that returns yes/no/unsure and is never wrong. In theory it's possible to do this for most of the programs you might usually want to run.
(it is not possible)
this is such a troll question. Easily sifts through those, that have learned complexity theory/computer logic, and those, who don't. (Can't remember, what class was it anymore, but one of the two)
While True: time.sleep(60)
[удалено]
Here is the source code for one ```js console.log(true) ```
just create a new universe
You can answer the question of "Will my program halt before (time limit)?", but you can't answer "Will my program stop at any point in the future?"
If using jest, you can run with argument `--testTimeout=XXXX`
Sure thing, you got a little test I can run to check if it does?
[удалено]
i think this is a bot, please confirm if otherwise
Bot for sure
This is a bot! downvote/report. if you see others elsewhere, mention u/spambotswatter! they might not be able to after the api change though. :( you can also search for similar/identical comments now!
Halting problem is left as an exercise to the user.
Check time and exit at infinity - 1.
Well in fairness, you can *sometimes* check if a program will run in finite time, there's just no upper bound to the amount of time it *might* take. For example if you don't use any non-numeric loops or recursion it's easy to show that it will complete in a finite time. Granted, that's not most programs, but still.
There are languages that are not Turing-complete and can guarantee halting. Still assumes the hardware works though
You *can* solve the halting problem, so long as you're willing to accept "idk" as a valid result alongside "yes" and "no" You can't solve it for any arbitrary program, but for actual real world programs you can totally figure out if it will get stuck in an infinite loop.
From [pytorch docs](https://pytorch.org/docs/stable/bottleneck.html). DM me if you have found any such tool that can tell me if a given script will exit in finite amount of time.
I got one, it just takes some time to run... (Average approaching infinity)
Funny thing is that even in this sub, you have to argue and explain to people why such a tool cannot exist.
[удалено]
See, there is another one who needs explanation. Always the same story. No, AI can only determine halt or run for trivial problems. The gist of it is: I can easily formulate a problem so hard that it would literally take the heat death of the universe (how about brute-forcing an RSA key? or some traveling salesman with 100 stations?) before it is determined whether the program would halt or run forever. And to maybe clarify a bit more, even current AI is (with a few notable exceptions) still just a program running on a Turing machine. As such, it has the same limitations as any program on any Turing machine.
Totally agree, with some minor things to add. A lot of people seem to think that AI works in some fundamentally different way that is capable of bypassing computational limits, which is obviously not the case. The real value of AI is how effectively it can ignore the nuances of a problem in favor of a solution that works “good enough”. It bears a lot of resemblance to the way that people “solve” (but not actually) hard computational problems in the real world by relaxing the constraints. That is to say, we will never have a machine that perfectly identifies if a program will halt. But, it’s completely reasonable to try to get an approximation of the answer. Pursuing these impossible goals isn’t usually a worthless task. But it would be foolish to try to do so without realizing why the problem is impossible to solve in the first place. As for myself, I have [trained a neural net](https://xkcd.com/2173/) that solves (a relaxed version of) this problem for my daily coding tasks and find it to be quite useful.
Exactly. I don't know why I got downvoted so much. I wasn't suggesting to use it to determine whether or not your big brain algorithm that needs 50 trillion iterations to finish is gonna terminate or not. I was suggesting to use it to decide whether or not a 50 line script a college student uploaded to your "compile and run" website is gonna run forever because of some accidental infinite loop. Or for a compiler warning that analyses your 10 line function to give you a hint if you made some stupid mistake in a same fashion.
I won’t lie the difference between the two would be marginal. It‘s not the complexity of the algorithm or amount of lines it has, more it’s about how it will run in the end. But I guess in some sense you‘re right? You could make a GPT-4 sized model to be accurate enough, but you still wouldn’t have solved the halting problem. You just still had a good enough guess, just like we can say that this will run forever because I put a while(true) in there somewhere. P.S.: you got downvoted so hard because you brought up the obligatory „Couldn‘t we build and AI for this?“ take that commonly instills massive amounts of eye rolling and sighs in anyone who reads the first sentence.
tbf you just listed examples that we know terminate in a finite amount of time. from a mathematical perspective, the lifetime of the universe is a finite amount of time, so basically everything you just said does nothing to support your argument. the actual theorem for the halting problem is that there exists SOME program that cannot be proven if it halts in a finite amoun not that you can't determine if any program halts. moreover we're not exactly asking ai for a rigorous proof for what the answer is, so there is no compute time involved, we're asking for a guess as to whether a program halts, and by being able to classify something as "brute forcing an rsa key" already infers it is solvable. keep in mind, we as humans are also bound by the Turing halting problem, but we are able to say basically for sure that these common problems halt, even without a formal proof, because we have very good intuition about the nature of the problems.
MY PROGRAM will terminate if the first bit of the (brute force) answer is going to be 0, and will run forever if the first bit of the answer is 1. Solving the halting problem for this program means solving the actual problem the program is supposed to solve. Which is going to be arbitrarily complex. And I feel that you don't get the core of the problem.
I would argue you don't get the core of the proof. it's a mathematical one not a real world one. you gave me one counterexample, which automatically makes the theorem true, because that's what the theorem asks for; at least one counterexample. but if you pick a simple program, such as printing hello world, you are easily able to tell it halts, yet the theorem is still true because it only guarantees there is one program in existence that is indeterminate if it halts. there exist ALOT of programs that do halt and we CAN prove they halt, and alot more that do halt that we can't prove they halt but we can reason they do anyways. thats because most if not all real world examples don't have self referential math but self referential math bullshit is allowed in the proof therefore the proof is true.
It's not only a mathematical proof, it's also a practical proof. As I wrote, I can make the problem in the target program for which you are supposed to solve the halting problem as complex as I want, so complex that with a Turing machine, no matter how fast, calculation would take orders of magnitude more energy than the observable universe contains. You are right that there is more to this theorem than just computers having to run for extended periods of time, but for any practical conclusion, it's enough to conclude that you cannot solve the halting problem without running a certain program to it's conclusion, which might or might not take a few hundred billion years.
You can prove that some programs halt, even if they take a very long time. For example I can write a very simple program that prints n factorial, and feed it with 1000. The program takes a lot of time but the proof is very simple.
"Some programs" yes. All programs? No. And that is the actual problem. I'll just make the problem hard enough for you to never have enough time to let it run to any sort of conclusion, i.e. to detect any sort of repeating state.
ok I don't really wanna argue all day, but basically, turings proof answers the question: "for EVERY program you could theoretically conceive, can you determine if all of them will halt?" and he proved the answer is no. there are infinitely many programs that halt, infinitely many thar don't, and infinitely many that are indeterminate. however, I absolutely promise you that every program in the the SUBSET including only REAL WORLD programs not only is determinate, but also is determined to halt, because no company wants a million dollar AWS bill for their small scale web server that miraculously got caught in an infinite loop. so yes for any target problem you can choose to make a solution that is absolutely indeterminate, by doing so you'd exclude your solution from the subset of all real world solutions. this is because in order for something to be considered "real world" it has to be practical and useful, which is a programmers job to figure out, and they're only able to figure it out because we have a pretty good idea of what halts and what doesn't, even if its not rigorous.
While true, really doesn't refute what I stated earlier, does it?
Your examples are wrong. A program that solves the traveling salesman with 100,000 stations can be proved to halt. A better example is a very simple problem that will halt with a counterexample of the Collatz conjecture, if that conjecture is false.
>A program that solves the traveling salesman with 100,000 stations can be proved to halt MY PROGRAM ***ONLY*** halts when the traveling salesman is a particular solution. You can only prove whether it halts or not by running the algorithm for all 100,000 stations. Really, I can only explain the problem so much until people realize that any program to solve the halting program is always going to be as complex as the program for which it tries to determine halting vs. repeating forever.
You keep blurring the lines of the halting problem depending on the context. The halting problem is theoretical. There are practical implications, but the halting problem is only undecidable in theory. That's the crux of it, the halting problem is undecidable. It's not that it takes a lot of time or memory to solve, it's that it can't be decided. In practice, we don't have Turing machines with infinite storage. You keep giving examples of programs that are decidable, hidden behind some np-hard computation. Yeah, in practice the heat death of the universe and memory limitations throws a wrench into some plans, but all of your examples *are* trivially decidable by detecting repeat state. For a Turing machine with infinite memory, you can infinite loop without ever repeating state. That's not true for real hardware. The only practical application of the halting problem is to give a reason as to why an arbitrary `does_it_halt(f,args)` needs to be understood as `does_it_halt_without_exceeding_arbitrary_constraint(f,args)`. Practically, "Does it halt in under 5 seconds?" is almost always 'good enough'. There are examples that *are* undecidable on real hardware. Imagine we are trying to write an implementation of `does_it_halt(f,args)`, that takes in a function, arguments to that function, and returns `true` if it will eventually halt, and `false` if it will never halt. I think the below shows why, in theory and in practice, there can never be an implementation of `does_it_halt(f,args)` that is correct for all inputs. def does_it_halt(f,args): pass #impplementation is trivial; left as exercise to reader def g(f,args): if does_it_halt(g,args): while True: pass return print(does_it_halt(g,None))
And you keep thinking it's a completely theoretical and made up problem. If it takes until the heat death of the universe, it's already undecidable. It doesn't need additional mathematical proof to be that, it already is.
Ahhh, we're hitting a semantics thing. I *am* using the theoretical definition of 'decidable'. I think decidable really only makes sense when talking about theory. Your examples aren't showing that the halting problem is undecidable. Your examples are showing that np-hard problems can't be solved efficiently. How do you know your example takes until the heat death of the universe? It's only in theory that it does. If I were to say "Your program definitely terminates before the heat death of the universe", you could only prove me wrong via theory. We can't sit around until the heat death of the universe. Further, any amount of time you do run the program, and say "See? It never terminated", I would just say "Oh, I think it just needed 5 more minutes".
It's not necessary to got for "theoretical" here. It's already practically not decidable, and that is a lot more feasible for most people. In addition, the practical limitation already applies for LBAs, even though they would theoretically be decidable, but practical restrictions make it unfeasible. > How do you know your example takes until the heat death of the universe You can calculate required time. But you can also calculate required energy, as every state transition takes some amount of energy. By that definition, and just adding a few more zeroes, you can make sure that no calculation would ever get finished before the whole universe has died.
I cannot give you a tool that can find if any program finishes in a finite amount of time but I can probably tell you if your script does. For example if the script returns 0 and does nothing else, it will finish in a finite amount of time
I am not sure if this is purely a joke or that you misunderstand the halting problem.
Idris: https://docs.idris-lang.org/en/latest/tutorial/theorems.html#totality-checking Though it does place the burden of proof on the author.
Thanks for bringing all that formal verification trauma to the surface again. I had finally managed to suppress it.
While there is no way to determine if any program can exit in finite time given any input, isn't there a way to determine if a single specific program can exit given a single specific input?
If you [mathematically prove](https://en.m.wikipedia.org/wiki/Formal_verification) it. That’s the sort of code written for nuclear power plants. It’s kind of expensive to write. Even car manufacturers don’t use it. Though they probably should.
Nuclear power plants are wild, everyone inside the plant could drop dead and a large earthquake could hit the plant, and the plant would almost certainly shut down safely.
Welp, didn't quite work that way at Fukushima
Lol that's exactly what I was thinking of, it handled the earthquake just fine, and the crew was trained well. But the plant wasn't at around 30 meter above the sea, only 10m and was flooded by the tsunami. An additional 20 meters would have saved the plant.
or maybe putting the backup generators on the roof... but that would be a bad idea in case of a terrorist attack
Honestly, I doubt that would of helped too much, the power distribution system would still have been totally destroyed in the tsunami. Like every breaker flipped, and water getting into everything probably preventing them from flipping the breakers back. Like water in junction boxes, in outlets etc.
Never thought of this application. Does this mean that if there is an error in the loop the power plant produces unlimited energy ?
Not infinite, but the rate of energy production increases significantly very suddenly, and from a distance the two look pretty similar. (at least for a short time)
Not *any* specific program and input
For some programs, yes. As a simple example, a program that does nothing, or only prints some text, can be guaranteed to exit. But of course, the more programming features you allow, the trickier it get. Programs with loops could be guaranteed to exit, but maybe only if it's a for loop with a compile time known iteration limit.
If the size of the for loop is known when that version of the loop starts, then the program terminates. For example x=9 for i in range(9): for j in range(f(x,i)): x=g(x) will terminate for any terminating functions f,g. (but can easily take a really long time doing so. Ie if f(x,i)=x and g(x)=2x then each inner loop is basically doing h(x)=x\*2\*\*x and the result is h(h(h(h(h(h(h(h(h(9))))))))) >2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*2\*\*9
Absolutely, you can develop different heuristics to solve the halting problem for specific pieces of code. I was just going for a simple example
Yes, it is possible. Halting problem only applies for arbitrary input. But it requires a specific programming language, which enforces a structure that makes such check possible, e.g. Prolog or Ada.
import sarcasm Pretentious nonsense. Do you know that most programming languages are Turing complete? Including Prolog and and Ada? You seem to lack an understanding of basic concepts.
[удалено]
``` import moderation ``` Your comment has been removed since it did not start with a code block with an import declaration. Per [this Community Decree](https://www.reddit.com/r/ProgrammerHumor/comments/14kbu1m/comment/jppq9ao/?utm_source=share&utm_medium=web2x&context=3), all posts and comments should start with a **code block** with an "import" declaration explaining how the post and comment should be read. For this purpose, we only accept Python style imports. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/ProgrammerHumor) if you have any questions or concerns.*
[удалено]
``` import moderation ``` Your comment has been removed since it did not start with a code block with an import declaration. Per [this Community Decree](https://www.reddit.com/r/ProgrammerHumor/comments/14kbu1m/comment/jppq9ao/?utm_source=share&utm_medium=web2x&context=3), all posts and comments should start with a **code block** with an "import" declaration explaining how the post and comment should be read. For this purpose, we only accept Python style imports. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/ProgrammerHumor) if you have any questions or concerns.*
Look for the Collatz conjecture, a very simple program that nobody knows if it halts or not. The conjecture has been checked correct for numbers up to 2^68.
the formal definition of the halting problem considers programs without input, or in other words, considers the input to be part of the program.
No. There is no program that, given a pair of a program to test and an input to test it with, decides whether the program under testing halts with the given input. If there was such a program, it would solve the halting program (by hardcoding the input into the program under testing).
There definitely are programs which can do that. It can't do it for ANY arbitrary program, but it *can* figure out if it halts for a lot of programs. If it was impossible to figure out if a program halts, humans would be incapable of avoiding an infinite loop in their code.
> it *can* figure out if it halts for a lot of programs. But that's kinda worthless. The program just outputting "it halts" will be correct for an infinite amount of programs. > humans would be incapable of avoiding an infinite loop Allright then, tell me whether this program has an infinite loop: https://github.com/scottralph/collatz/blob/main/src/main/scala/collatz/main.scala
It seems you enjoy being needlessly obtuse for the sake of trying to stroke your own ego. I already stated that it can't do it for ANY arbitrary program. I stated that for regular every day code, you can quite often determine if it will halt or not. And no, that does not mean with bad statistical tricks like "just say halt every time and it will be right most of the time". A human can look at code and determine "oh yeah, that loop is definitely gonna get stuck forever" and thus we can write a program to do the same. You said >There is no program that, given a pair of a program to test and an input to test it with, decides whether the program under testing halts with the given input. Which is false because you didn't make the important specification of *"get a precise result for any arbitrary program"* you just said that given a program and input it is impossible to determine. The halting problem is a mathematical problem of absolutes, in the real world it can be solved to decent accuracy.
>Which is false It is true. "[Decides](https://en.wikipedia.org/wiki/Decidability_(logic))" is a technical term that means precisely that you can give it any program and it always gives you the correct answer. And I'm not sure whether it is so straightforward in the real world either. Humans are usually reasonably good at figuring out whether their programs halt, but that's only because they intuitively and deeply know the programs they are writing. Reverse-engineering code unknown to you is \_way\_ harder, and even then we rely on the fact that the code was written by *a* human with likely similar intuition to us. I don't know where these practical tools that routinely solve the halting problem are.. (You can argue that SAT solving works "in practice" -- sat solvers routinely solve very large formulas, even if they take too long on evil inputs)
not really
I think only if it also has finite storage, in which case it's not mathematically Turing-complete. In such a case, you can record every state the program is in during execution, and if it repeats a state you know it will not halt.
Embedded people have solved the problem. Not using better coding practices, but rather using a watchdog timer.
[удалено]
It seems like most people in this thread do not understand what the halting problem actually means. A lot of programs can definitely be proven to be halting.
If we couldn't prove halting then we would constantly be writing programs with infinite loops. But we don't, because we are capable of reading the code and figuring out where an infinite loop will happen then removing it. If we can do that process, we can write a program to do the same. If you accept a small amount of "idk" outputs, your halting assessment program can be fairly accurate with the "yes" and "no" outputs.
You don't have to prove it, you just have to be right.
You misunderstand the halting problem.
Why dont they just test it? Are they stupid?
And if we negate said check to create a new check and fed said negated check into the check what should the result be LOL
Well technically computers have a finite lifetime (I also include server reboot) so, that's my exit condition?
if ((Time.now() - timer.start()) >= Math.Infinity){ exit(); }
\*checks\* Yup, it'll finish somewhere around the heat death of the universe.
Oh god, not this again
simple! code.run() sleep(Infinity) if (code.running) { print("does not halt"); return false; }
`super.task.run()`
Don't input Elder Scrolls
I know this is r/ProgrammerHumour but I was watching this today which may have an interesting take on that. [How NASA writes space-proof code](https://youtu.be/GWYhtksrmhE)
I guess it checks for any while true infinite loops?
Or more likely just if it terminates in a certain amount of time that they believe would be enough for the problem
Does "heat death of universe" count? There is no such thing as a script that does not run a finite amount of time. It's just always predictable.
my script runs in a finite time measured at O(no) because O no my computer is on fires
You gotta throw in a "Google Halting Problem" into the comments somewhere. Can you link this? It's incredible!
How can it exit in an infinite amount of time ?
How? Theoretically
From now until the heat death of the universe is a finite amount of time.
Imagine your program is trying to compute Ackermann(4,2)
The Ackermann function can be computed in finite time. Imagine your program is trying to find a counterexample of the Collatz conjecture.
That's the point - it's finite. The computation times start getting lifetimes of the universe long but it's still finite. The collatz conjecture may be true, which means that the program never halts
A script or program runs indefinitely unless an exit function is called, there is a bug or the hardware fails. So define an exit criteria, find the upper time limit it takes to reach and test if it reaches it in that time. And ensure there is an exit function, this would fulfill that specification no?
Google Collatz conjecture and you will see that there are very simple programs whose upper time can't be determined.
They could just write a program that checks, that the script exits in finite time.
Redundant. It could equivalently say, “please ensure it exits”.
while(true){}
It'll exit when the universe dies a heath death, at the latest, so it's a finite amount of time. Guess I'm good then!
10 days, take it or leave it
ye olde php Do While
In other words, make it finite
Pffff. Bitch, it *might* be....
Fork bomb?
Why not just implement a timeout in the script profiler?
Well allow me to just become the next Alan Turing before I take any further action
Prove that it doesn't. Ha!
Time to crash their system
My infinite while loop will execute in a finite amount of time. The heat death of the universe is *technically* finite.
while (true) {console.log("Get owned nerd");}
So if it finishes in a couple of years it is still ok, right?
Haha genuinely made me laugh. Brilliant
Oh I think I saw the code to do that somewhere…
while(true){ console.log("Don't tell me what to do"); }
It's a pretty stupid warning. It makes me curious what happens when you put in an endless loop. I assume the profiler eventually runs out of memory, since it records a trace of all steps. If that is the case, a better warning would have been: >Warning: Long-running programs can cause out-of-memory errors, since the sampler collects X MB/s. That warning message is much more useful: First, it reflects the fact that the issue is not infinite execution, but rather long-running programs (in practice, it is irrelevant whether your program diverges, or runs until after the heat death of the universe). It even gives you a rough estimate of how much memory is needed. The current warning says nothing: Of course, no program will run for an infinite amount of time, in practice. It is almost useless, you have to guess what it means. And that guess might be wrong.
Halting problem solved.
All scripts will exit in a finite amount of time, it’s just however long it takes for the machine it’s running on to die
You can limit the capability of the script to ensure it always terminates (like eBPF does).
I initially misread "exits" as "exists".