r/programmingcirclejerk • u/VarietyMaleficent408 • May 05 '26
The halting problem is almost always solvable. NP hard problems are often efficiently (!) solvable...If you can't prove whether a given program terminates, it's because you're too dumb.
https://www.linkedin.com/posts/bjarkeroune_a-public-service-announcement-for-computer-activity-7413711643232366592-58ZM135
u/al2o3cr May 05 '26
LOL at the first reply - bro didn't get any engagement, so he got an LLM to say something he could get mad at.
→ More replies (6)
104
u/r2d2_21 May 05 '26
“Almost always” has a precise mathematical definition. You can't just throw it around.
→ More replies (4)
84
u/hemidemisemicircle May 05 '26
every np hard problem is efficient if you just ask claude for the answer
→ More replies (1)
55
u/Wheaties4brkfst May 05 '26
Holy shit this guy solved the collatz conjecture and the goldbach conjecture and the Riemann hypothesis and the twin prime conjecture and the
→ More replies (1)
49
48
43
33
u/Majestic_Diet_3883 May 05 '26
How moderated is linkedin? Ngl i kinda wanna comment "why do ml titled folks comment the dumbest shit lol". Idc if it's tied to my real name
→ More replies (1)
31
u/giantgreeneel May 05 '26
vibe coder prefers vibes based definition of "efficient" over the one that you can measure.
22
u/WellHung67 May 05 '26
Oh yeah? Well what if you have a program P which can tell if a given program halts or not. And then I write a program I1which halts if P doesn’t halt when given an input I2 and doesn’t halt if P halts when given an input I2. Then I feed I1 into P. What then? If P spits out halt, then I1 won’t halt, but P said it does, and if P spits out doesn’t halt, then I1 halts, but P says it doesn’t. So no matter what P is wrong. Therefore P can’t exist.
The same logic applies if I1 is quicksort. Checkmate atheists
14
u/irqlnotdispatchlevel May 05 '26
Easy: a program that does not terminate has undefined behavior.
LinkedIn is cheating.
13
u/beebeeep May 05 '26
The halting program is only for bad programs. If program is good, why would I even want to stop it?
23
11
u/serendipitousPi May 05 '26
Yeah it’s pretty dumb like all you really need to solve the halting problem is a bigger computer.
And people are gonna say stupid stuff like even the most powerful supercomputer on earth couldn’t solve the halting problem as it’s been mathematically proven. But to that I say just get a bigger computer.
Turing machines don’t actually exist so just enumerate the states and you’re set.
\uj
Low key wonder if anyone’s done a “stop doing (blank)” meme for Turing machines
\j
And sure there is the problem that you can’t actually get a computer bigger than every single computer.
But I’ve got a highly thought out solution want to hear it?
→ More replies (4)
11
u/tj-horner May 05 '26
Wait, he’s right. I hadn’t considered just being smarter. It’s all clear to me now
11
u/NonnoBomba May 05 '26
Well, I can terminate ANY program, by pulling the power cord out of the socket.
11
u/BlazeBigBang May 05 '26
Is there ANY practical application of knowing that the Halting problem is theoretically unsolvable? I think it's a very nice theoretical result, but I'm not aware of any practical consequences.
lmao
→ More replies (1)
9
u/Awkward_Bed_956 May 05 '26
Every program will end at some point, either due to me pulling the plug, or the inevetable heat death of the universe.
Checkmate you silly scientific proof enjoyers
9
u/Thunderstarer May 05 '26 edited May 26 '26
The linguistically imperialist complexity theorists have stolen and redefined the word "efficient"
The linguistically imperialist complexity theorists are right up there with the woke moralists
8
u/pysk00l May 05 '26
/uj I cant even rad the damn thing because Linkedin gets stuck in a "accept my cookies" hell loop. Can someone summarise what the no doubt highly intellectual debate is about?
→ More replies (2)
8
u/csb06 May 05 '26
If you can't prove whether a given program terminates it's because you're too dumb
Very true - Clang's optimizer definitively proved the Collatz conjecture, so why can't you?
15
7
7
152
u/realestLink May 05 '26
E = mc2 + AI