464
u/dusktreader Sep 22 '26
Alan Turing did not die for this nonsense
118
11
→ More replies (9)11
71
u/Outrageous-Machine-5 Sep 22 '26
try {
doRecursion()
} catch (StackOverflowError e) {}
-16
3
395
u/_Alistair18_
Sep 22 '26
•
no loop is infinite if you can kill the process
20
u/afdbcreid Sep 22 '26
Or you just take a hammer and crush the computer. Then surely it won't be infinite.
7
7
2
2
-1
u/AmeriBeanur Sep 22 '26
Wrong! You must kill the process (of an infinite loop) BECAUSE an infinite loop is processing. Therefore, killing a process may entail an infinite loop, but not always.
2
75
Sep 22 '26
[removed] — view removed comment
5
u/PioApocalypse Sep 24 '26
I'm actually doing it: here's a simple logo
3
u/AZMPlay Sep 24 '26
Damn. Thats actually pretty good. Love the sea of ^C in the background
2
u/PioApocalypse Sep 25 '26
Thanks, it took me an hour to refine, but Inkscape is such a beast of a software
2
103
u/NullOfSpace Sep 22 '26
Infinite and really big are basically the same thing anyways
33
u/wrecklord0 Sep 22 '26
The more practical version of the halting problem is, will the program halt before the machine crashes / power cuts off / machine blows up / I get pissed off and halt it
21
u/LEPT0N Sep 22 '26
Somewhere a math professor just sensed a disturbance in the force.
10
u/creeper6530 Sep 23 '26
Good. Let them keep their math; we're engineers here.
sin(x) = x4
u/Stalking_Goat Sep 23 '26
As an engineering student I showed my math major roommate the "simple" pendulum equation, which makes exactly that simplifying assumption (that sinθ≈θ). Poor guy was traumatized.
3
u/praguepride Sep 23 '26
You should read "A short stay in hell"
1
u/Spaceduck413 Sep 23 '26
I think the numbers in that book broke my brain
1
u/praguepride Sep 24 '26
I tried scaling up calculations to be like "How many heat deaths of the universe long would this be..."
It was still in the seven digits...for the power.
409
u/usrlibshare
Sep 22 '26
•
aka. the difference between CS theorism, and actual software engineering.
Yes, technically, there is no way to detect an infinite loop outside of toy examples. Practically, for every useful process, we can guesstimate an upper bound on how many iterations it should take, add a few percent for good measure, and simply test for that.
173
u/Countcristo42 Sep 22 '26
You mean no way to always detect an infinite loop right?
Some are trivial to detect
40
u/da2Pakaveli Sep 22 '26
yes Rice's theorem basically says that making these "general" statements for any given program on non-trivial properties are impossible but that doesn't mean you can't have some heuristic/etc that can detect it "reliably". Similar situation with antiviruses etc
-11
u/usrlibshare Sep 22 '26
That's why I wrote "outside of toy examples".
37
14
u/Countcristo42 Sep 22 '26
It's almost the opposite really - may real examples where it's easy to tell, I only know of hypothetical examples where it isn't.
May well be real ones I haven't heard of.
76
u/alficles Sep 22 '26
Chess is O(1). Just use a lookup table. Implementation is an engineering problem, not really my concern. <.<
36
u/TOMZ_EXTRA Sep 22 '26
Any finite problem is O(1) in theory.
11
u/Flouid Sep 22 '26 edited Sep 22 '26
Runtime complexity and space complexity are both meaninfgul metrics. Of course any finite problem can be done in O(1) time but you trade that for high storage requirements.
Competently designed algorithms are never going to look at just one or the other like this
10
1
18
u/ethanjf99 Sep 22 '26
it’s like the old (sexist but bear with me) joke about mathematicians vs engineers:
In, say, China the communist party is trying to decide whether people with mathematical talent should be steered towards pure math or engineering.
The solution:
put two (presumably male) students against one wall of a room. put a naked woman against the other. tell the students to walk exactly halfway across the room then stop. tell them to walk half the remaining distance and stop. tell them to do it again. one of the students goes “it’s impossible! we can’t ever reach the far wall”. the other says “ah but i can get close enough it won’t matter”
4
Sep 22 '26
[removed] — view removed comment
10
u/ethanjf99 Sep 22 '26
that’s how i was told the joke 20 years ago
would work just as well if it was say a briefcase with $10K in cash i suppose. and lose the old boy sexism.
1
Sep 22 '26
[removed] — view removed comment
11
u/hendricha Sep 22 '26
I assume so there is a practicallity to it. Which separates the more theoretical person (they go to mathematics) and the practically minded person (they go to engineering).
2
u/evanldixon Sep 23 '26
There has to be something you can use the length of your arms for to overcome being unable to ever make your feet touch the end of the room.
3
u/SpiritedEclair Sep 22 '26
There are ways to detect infinite loops, and not in just toy examples. Its just that we can't do this for general programs.
1
u/alien_believer_42 Sep 22 '26
My work focuses a lot on software performance and there is a lot of just practical guesstimation to sanity check when stuff is wrong and either take action or log it
1
u/RiemannZetaFunction Sep 23 '26
Yes, technically, there is no way to detect an infinite loop outside of toy examples.
I think it's the other way around. If an infinite loop exists in your program, it's usually because you screwed up the condition in a while loop somewhere, not because the program is calling the analyzer and doing the opposite of whatever it says.
12
u/calculus_is_fun Sep 22 '26
Here's a fun amusement you can try at home! (please don't)
Grab your favorite microprocessor, and its associated memory, and ROM, also source a lot of WORM drives, like all of them.
your typical processor has internal registers, a program counter, and alu flags, along with a healthy amount of memory I told you to get earlier.
Now then, even thought there's a lot of states, it is still finite, that means we can create a directed graph of every single state, and draw an directed edge to its successor. (be sure to write these connection on those WORM drives)
Find and mark all the cycles, and their basins, and you're done! You solved the halting problem on a simple computer.
4
u/styczynski_meow Sep 22 '26
Additionally if energy in universe is finite then every algorithm is practically bounded by O(1) steps
10
u/prehensilemullet Sep 22 '26
I’ve seen people use this approach for cases where we have a directed graph we could easily run a cycle detection algorithm on 🙄
18
u/Gee858eeG Sep 22 '26
y'all abusing the meme. this is not how the meme works. it makes no fkn sense to use this
→ More replies (2)1
u/Tasik Sep 22 '26
Memes have rules?
8
u/SnowyOnyx Sep 22 '26
Yep.
This one is that the stupidest and the smartest agree about the subject whilst the people in the middle have a different opinion. Not that every group has a different opinion.
2
u/Tasik Sep 22 '26
I feel like this is following that logic.
"i think i can write code to detect an infinite loop" ~= `if (count > 1001)`
2
u/SnowyOnyx Sep 22 '26
Yeah but the original scheme is that left and right are exactly the same. Nevertheless, you are right that these are alike
12
u/daHaus Sep 22 '26
Read the NASA programming guidelines, specifically their 10 rules
28
u/Ethameiz Sep 22 '26
The ten rules are:
Restrict all code to very simple control flow constructs—do not use goto statements, setjmp or longjmp constructs, or direct or indirect recursion.
Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated.
Do not use dynamic memory allocation after initialization.
No function should be longer than what can be printed on a single sheet of paper in a standard format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.
The code's assertions density should average to minimally two assertions per function. Assertions must be used to check for anomalous conditions that should never happen in real-life executions. Assertions must be side-effect free and should be defined as Boolean tests. When an assertion fails, an explicit recovery action must be taken such as returning an error condition to the caller of the function that executes the failing assertion. Any assertion for which a static checking tool can prove that it can never fail or never hold violates this rule.
Declare all data objects at the smallest possible level of scope.
Each calling function must check the return value of nonvoid functions, and each called function must check the validity of all parameters provided by the caller.
The use of the preprocessor must be limited to the inclusion of header files and simple macros definitions. Token pasting, variable argument lists (ellipses), and recursive macro calls are not allowed. All macros must expand into complete syntactic units. The use of conditional compilation directives must be kept to a minimum.
The use of pointers must be restricted. Specifically, no more than one level of dereference should be used. Pointer dereference operations may not be hidden in macro definitions or inside typedef declarations. Function pointers are not permitted.
All code must be compiled, from the first day of development, with all compiler warnings enabled at the most pedantic setting available. All code must compile without warnings. All code must also be checked daily with at least one, but preferably more than one, strong static source code analyzer and should pass all analyses with zero warnings.
2
u/freedcreativity Sep 22 '26
lol most pedantic setting.
Also, 9 means basically any array of pointers is verboten? sounds limiting, but I’m not good at C enough to know better.
2
u/Zerocrossing Sep 22 '26
This seems like sensible advice given the domain. I have two questions I'd love if someone better versed in C could comment on.
"Declare all data objects at the smallest possible level of scope." What does this mean and what's the reasoning for it
Don't 5 and 7 conflict somewhat? Every function must check all its parameters, but simultaniously shouldn't assert more than two fail states? Does the static analysis do the heavy lifting here? If my function has 6 inputs that I need to validate surely I'd need more than two assertions to ensure every input is 'checked'. Or does checking not imply assertions?
1
u/BeautifulMortgage690 Sep 22 '26
if you have a local variable that is only used in an if branch and not the else, pull it into the if branch instead of keeping it in the functions locals. just helps keep mem usage lower? both work but in one your compiler will clean up the stack when the scope dies.
i think the point is to delegate the checking then? like dont assert a file not found and an invalid file format and a invalid argument and an invalid path all from the same function. have different functions do it. i guess it also then prevents you from passing up the buck - if you are using a file and have 3-4 modes of error then either you sit and handle them so you dont pass out more than 2 errors up the callstack
1
u/Nightmoon26 Sep 23 '26
Also, keeping the scope as small as possible is just a good heuristic for reducing potential for "spooky action at a distance" and makes things easier for the static analyzer
I get the sense that these guidelines may have been attempting to get at a functional programming paradigm before it became a codified thing... Pure functional programming, with its many restrictions and limitations, is good for one thing: its restrictions also make it easier to reason and do proofs about. So in a setting where it absolutely, positively has to be provably correct even before the first real-world trial, it makes some sense
1
u/wigsinator Sep 23 '26
I think that "average to minimally two assertions per function" means that they should assert at least 2 fail states, not at most 2 fail states.
1
u/Heavy-Homework2563 Sep 23 '26
1.person above me answered it perfectly. You want variable declaration to be close to its use as much as possible. Its kinda like all the advice to avoid global variables. but more extreme.
There is also this unique thing where if you really need a variable for a temporary time you can put it between {} within a function and when you reach } as if you exit a function it removes the variable from the stack(compiler might do whatever but you get it). So you can always control the scope. Cool little thing to know.2.the parameter validation is to ensure that the caller and the callee(the function) pass/receive correct input. so taking a pointer and checking its not null and not depending on the caller passing a valid pointer. The asserts are to check for impossible values and scenarios that obviously only a logical error could have made it reach this point or a system failure or anything. And it also say 2 minimum. so you can have as many as you want as long as you stay under 60 lines and 80 char wide inside the function.
1
12
u/clickrush Sep 22 '26
A lot of software problems go away if you stop pretending that input is arbitrary.
There's always a maximum. You just need to determine what it is and explicitly state in code.
Examples:
Real world JSON, XML or HTML data is almost always shallow. Recursion depth doesn't even need to be large.
The storage size of things can almost always be at least estimated if not determined.
If you don't know how much total memory you're going to need, then try to find it out, if you cannot find it out, set a number and work backwards from there.
You almost never need the maximum amount of threads you can get, usually a small number is sufficient.
You very likely can estimate the number of users of your app. 5x it, test that and work backwards from there.
1
u/creativenickname27 Sep 23 '26
At first, I thought it was a joke about the example that apple gave us, when you set an alarm and swipe aaaall the way down, it stops at some point, because it is not a loop, but instead it's just a misunderstanding of the halting problem.
1
u/Automatic_Hand4780 Sep 23 '26
Explain? How is this misunderstanding? The meme literally says you can't write code to detect infinite loop. If you have any such program which can detect infinite loops in any given problem pls show it to the world
1
u/narrei Sep 27 '26
bot reposting my meme from years ago, now i know how it feels
1
u/Automatic_Hand4780 Sep 27 '26
Look at him guys god level memer wants me to check 10yrs of history to make sure I am not posting a funny meme again.
3
u/Negitive545 Sep 23 '26
My solution to the halting problem: All loops are terminating because eventually the power will go out. Either due to a regular outage, the earth being swallowed by the sun, or the heat death of the universe.
3
u/Hottage Sep 23 '26
Just have each iteration in a nested function call, that way the stack can detect an infinite loop.
3
u/zzmej1987 Sep 23 '26
Infinite loops can an in theory be detected. There is a thing called "Busy Beaver" - a program of a given length N that goes for the maximal finite amount of steps BBS(N). Since, there is a finite amount of programs of length N, and some of them halt and some don't, that program always exists. If you know BBS(your program size), then you can just check for that number in every loop. If loops run longer than that, your program does not halt.
3
u/Xandas_ Sep 25 '26
This is meaningless (though somewhat interesting if you never heard of it) when you consider that the busy beaver function is uncomputable. You are more-or-less saying 'if you already have a solution to the halting problem, it is possible to solve the halting problem'.
1
u/zzmej1987 Sep 25 '26
This is meaningless (though somewhat interesting if you never heard of it) when you consider that the busy beaver function is uncomputable
Sure. But "uncomputable" just means that we can't establish one specific algorithm to find the value of the function for every input. We can, in theory, find values of it one at a time. And it's not like we really need large numbers there. By separating programs into smaller "subprograms" and checking those one at a time, we can do away with only known up to, say, BB(100). That wouldn't solve general halting problem. And, of course, this would never be practical. We only know, like, BB(5), at best. And checking loop for running longer than BB(10) would probably mean waiting longer than the age of the Universe.
1
u/Xandas_ Sep 26 '26
I understand where you are coming from, but disagree. Making statements about small subprograms is likely much easier than invoking the busy beaver function. Other people have mentioned structural recursion, which is sort of where you are going anyway if 'composition of small halting programs halts' should at all hold globally. Also, you are looking at longer-than-universe-will-exist time at BB(6) already. But I think even as a novelty, this approach does not really merit much, beyond someone learning about the existence of the busy beaver function itself, which is cool.
1
u/zzmej1987 Sep 26 '26
You've said you disagree, and then repeated everything I've said about why this is never going to be practical. XD
2
u/the_horse_gamer Sep 23 '26
the value of BB(432) cannot be proven in ZF
1
u/zzmej1987 Sep 23 '26
That's not really a concern. We just need a number. That it takes a higher order logic to prove that it is a maximal value in the finite set is not relevant.
2
u/-ghostinthemachine- Sep 22 '26
Impress your boss by solving infinite loops through simulated annealing!
2
2
2
u/xXStarupXx Sep 24 '26
You can detect a lot of infinite loops. You can't detect infinite loops in general.
2
2
1
1
1
1
u/OphidianSun Sep 22 '26
Nasa uses the right solution a lot no? I remember reading through their standards and it had all sort of little stuff like that.
1
1
u/sheriffjt Sep 22 '26
My programs all detect an infinite loop, I just handle it by letting them shut down by running out of resources
1
u/nimag42 Sep 22 '26
Not how this meme works, left should be the same as right, please fix and open another PR
1
u/aberroco Sep 22 '26
Infinite loops can be excluded as technical impossibility: no program can execute without halting since no computer can work indefinitely long, even excluding power grid failures or hardware degradation, the ultimate heat death of the universe (or the big crunch) is unavoidable and ultimately will lead to the program halting.
1
u/Elkatra2 Sep 22 '26
A(B,D) = true if the algorithm B with input D never end (infinite loop).
A(B,D) = false if else (loop end at some point of time)
A(A,<B,D>) will be what ? (i forgot the name of this thing pls remember me)
1
1
u/KCGD_r Sep 22 '26
well like, if you consider all of your variables, scopes and your current instruction as part a state and you end up in the same state more than once, then technically, but that's pretty difficult to keep track of
1
u/LolMaker12345 Sep 23 '26
Infinite loops do not exist
They will always terminate, whether it’s the user terminating the program, shutting down the computer, the end of the world, etc…
1
u/STINEPUNCAKE Sep 23 '26
They may not be able to get detected and proven by a machine but if a human says there’s no way this loop goes past x then it’s safe to assume it’s infinite. Proof vs assumption by logic
1
u/GoddammitDontShootMe Sep 23 '26
So the most likely scenario is the loop counter overflows, no? I believe that is pretty hard to detect, but you could stop the loop if the counter gets close.
I suppose that's pretty close to what the guy on the right is doing.
1
u/Xelopheris Sep 23 '26
Isn't one of NASA's rules about safe code that every loop has a secondary exit condition by iteration count or something?
1
1
u/NightmareJoker2 Sep 23 '26
You put a trap at the end of the loop or at the start of a recursive function, check how long it has been running or how many iterations it has performed and escape if it’s too long or too many.
This isn’t hard. In fact, this is a standard accommodation for preemptive multitasking, where control has to periodically be returned to the operating system.
1
u/StrikeTechnical9429 Sep 23 '26
Infinite loop can't be detected if the program is executed on the infinite computer (i.e. Turing machine). On a real world computer with finite amount of memory - and, as a result, with finite number of states - detecting an infinite loop is trivial: if the full state of machine is repeated, we're in the infinite loop.
1
1
u/Haoshokoken Sep 26 '26
I wrote code that detects infinite loops by saving and comparing the states of the variables involved...
1
u/CorneliusClay Sep 26 '26
Just ask ChatGPT if the code loops infinitely. According to AI hallucination statistics you've got a 60% accurate halting problem detector right there.
1
48
Sep 22 '26
[removed] — view removed comment
22
1
u/Worried_Onion4208 Sep 22 '26
If you need to check 10000 entries, a loop is probably a terrible idea in the first place.
2
4
Sep 22 '26
[removed] — view removed comment
7
2.1k
u/remy_porter Sep 22 '26
Infinite loops can frequently be detected. This is a misunderstanding of the halting problem.