There are really few problems that are “impossible.” That is, if you count those customers/managers are interested in. All the rest is just “I’ll need 10 years, 230 million Dollars and a research team”
XKCD 1425 by Randall Munroe. License: CC BY-NC 2.5
“The other programmers keep accidentally writing code that ends up in an infinite loop. I’d like you to make a program that can reliably detect that.”
You may joke, but if I had a penny for every time someone asked me to solve a problem, that basically boils down to the halting problem, I’d be rich.
Yeah, accidentally running into the halting problem is common in automatic code analysis.
It’d be nice if we wrote something to detect it running into the halting problem.
I have always wondered why the answer to the halting problem isn’t: “If no output has been returned in X time, BREAK, restart program from beginning.”
what if it needed just one more second to complete?
Damn Vogons.
Because that will fail to detect a program that halts in X+1 time. The problem isn’t to detect if a program that halts halts, the problem is to generally create an algorithm that will guarantee that the analyzed program will always halt given an infinite time running on an infinite computer.
But you could also do a mean time analysis on specific tasks and have it cut off at a standard deviation or two (90-98% of task times covered), and have a checkbox or something for when the user expects longer times.
You could probably even make this adaptive, with a cutoff at 2x the standard time, and updating the median estimate after each run.
I was recently tasked with the traveling salesman problem on a project. My first pass was quick but produced sloppy inefficient results. Well boss didn’t like it so he had me go back at it again so it would be far more accurate. Well now it slogs through figuring out an optimal solution of several thousand points.
Just check the git blame.
A full solution to the halting problem can’t exist. But you can definitely write a program that will “reliably” detect them to a certain percentage.
And many applications do exactly that. Firefox asked me today if I wanted to stop a tab because it was processing for too long.
That’s not even close to solving the halting problem. FF doesn’t check if the program has been in its current state before. It literally just checks if 10 seconds have passed without JS emptying its event loop.
Right. There is no solution to the halting problem, that’s been proven. But you just showed you can very easily create a way of practically solving it. Just waiting for 10 seconds does it. That will catch every infinite loop while also having some false positives. And that will be fine in most applications.
My point is that even if a solution to the halting problem is impossible, there is often a very possible solution that will get you close enough for a real world scenario. And there are definitely more sophisticated methods of catching non-halting programs with fewer false positives.
And that will be fine in most applications.
Have you never written a useful program that took more than 10 seconds to complete?
I fully agree with your sentiment. But just in case: If you’re blocking the main thread of a browser for seconds at a time, you should look into that.
I’m not talking about web applications.
My loop isn’t infinite, just longer than the heat death of the universe.
For JavaScript apps, stopping them when they consume too much resources is definitely a good idea. But if you work on some project where it’s common to run computionally intensive tasks, it can be harder to detect non-halting.
Just because it’s not possible on a Turing Machine doesn’t mean it’s impossible on a PC with finite memory. You just have to track all the memory that is available to the algorithm and once you detect a state you’ve seen already, you know it’s not halting ever. The detection algorithm will need an insane amount of memory though.
Edit: think about the amount of memory that would need. It’s crazy but theoretically possible. In real world use cases only if the algorithm you’re watching has access to a tiny amount of memory.
Easy.
If( loop == inf) {
End;
}
Pay check please?
Here you go:
Woah! This is worthless!
There have been genuine efforts to do that. Obviously (well, for a very niche use of “obviously”) it’s not always possible, but detecting infinite loops isn’t like the uncertainty principle.
It’s called The Terminator.
This. Very few problems are truly impossible to solve, they arem in fact, just wildly impractical to solve. So don’t try to tell the PM/client/coworker-with-a-‘brilliant’-idea it can’t be done, tell them what it’ll take to work out what it’ll take to do it. Either they go away, or you end up in charge of a project with an astronomical budget and no clearly defined deliverables.
I mean, now a days, I can upload the image into stable diffusion automatic1111 and click interrogate CLIP and then see if it outputs “bird” as a reverse promopt, but this comic WAS from 4 and a half years ago, so the programmer was right on the time-frame.
It always depends on which existing tools you have access to. Go back some more years and there is no GPS. Detecting the bird will be the easier problem then.
Funny thing is, since that comic was originally published bird detection has gotten a lot easier
About 5 years after, and there was a research team behind it.
Several teams actually
I bet it’s because the camera now also scans for the 5G radio waves that are used to control the “birds” instead of just recording waves in the visible spectrum
respect for uploading the image, linking the page, and crediting the author :)
What is a bird!?
a miserable little pile of secrets
Diogenes bursts into Dracula’s throne room while holding a chicken.
Plato bursts into Dracula’s throne room holding a lantern and a mirror
Throws water bowl
insert “bird isn’t real” meme
Bird watching goes both ways
Customer: Why is there so much latency over my tunnel from us-east to us-west?
Me: checks latency seems pretty normal, what’s the issue?
Customer: The latency is too much. Why is it not as fast as us-east-1 to us-east-2?
Me: They are near each other. Us-West is across the entire United States
Customer: Make faster
Me: This is the speed of light. And over copper it’s about 2/3 that
Customer: hmm are you sure that’s as fast as it can go?
Me: Well, unless we change the laws of physics your not going to get any better latency
Customer: So… can we do that? Change the laws of physics? What congressman do we need to email?
That’s cause they always have money in the lobbying budget to fix things.
For the low price of billions and a decade of work they could build out hollow core fiber coast to coast to get the last 1/3 c.
that would really help with playing video games
What’s hollow core fibre.
Its a type of fiber optic cable where the center of the cable is literally hollow. Normal fiber uses a glass core. Light passing through glass also travels about 2/3 the speed of the light since the speed of light is only constant in an empty vacuum. With hollow core, light is no longer passing through glass so its speed is much closer to the actual speed of light.
… wait, how does that work? Total internal reflection happens at the boundary to a lower index of refraction.
I don’t know the physics well enough, but here is some general information.
https://en.m.wikipedia.org/wiki/Photonic-crystal_fiber
https://www.rp-photonics.com/hollow_core_fibers.html
High Group Velocity, Low Latency Signal Transmission
The group velocity of guided light is usually close to the vacuum velocity of light. This implies substantially lower latency for signal transmission through hollow-core fibers.
My dumb person guess is that it needs to be in a perfectly straight line.
There’s probably more to it.
Looks like it comes in spools.
https://www.ixblue.com/store/ixf-hcf-10-100-950/
I don’t know the physics of it. I posted some info for the parent you responded to. My understanding is the applied physics is different from traditional fiber.
The main physical principle behind propagation of light in conventional optical fibers is total internal reflection (TIR). However, engineering of optical materials with features on the scale of the wavelength of light offers many new possibilities for manipulating light. In particular, some microstructured fibres make it possible to guide light by a mechanism different from total internal reflection. In these fibres, light is trapped in the core by an out-of-plane band-gap, which appears over a range of axial wavevectors and prevents propagation of light in the microstructured cladding [Cregan (1999)], allowing guided modes to form in the central hollow core.
https://mpl.mpg.de/research-at-mpl/russell-emeritus-group/research/about-pcf/hollow-core-pcf
How do you get internal reflectance with a hollow core?
You can’t have total internal reflection within a hollow core, but that’s not how they function.
That’s fair.
Then you find out the real reason they need faster latency is because they’re pinging the server for new data every 1ms
So can you give me an estimate for when you can solve that?
Anytime I run into that question I tell them if I could manage FTL comms I wouldn’t be working here.
Eh, sometimes they’re right about this one though. It’s true that a request traveling near light speed is as fast as it can possibly be, but what if it’s 17 requests? Sometimes you can fix latency by doing fewer transactions.
edit: love a downvote with no reply. Just “No!” [stomps feet]
what if we made a new type of blockchain? one that was powered by generative AI and the metaverse? oh! and could we make it so that it Empowers Business Solutions?
This can certainly be done as long as we stick to the five core values - take ownership, take the leap, act with integrity, put the customer first, and dare to innovate.
This whole comment chain is making me feel sad. And angry. And sangry.
Only if we have 3 red lines, 2 blue lines, and one transparent line. And have all of them perpendicular to each other.
Can a line be a cat? I love kittens.
Can the cat be drawn in red?
that’s some nice 6-dimensional thinking! very well suited to the new blockchain project
Thanks, i had a stroke while reading that
Shut up shut up shut up!
Please don’t give people stupid ideas
What we need is a paradigm shift in how we empower synergy between product lines through utilization of emerging technologies and strategic acquisitions to improve our KPIs across the platform.
Your anus is moving but I don’t get a thing of what you speak.
Ever heard of justified homicide? :)
Unionize, people. It’s terrifying how few IT workers are unionized.
It’s because of big pay, highly mobile employees, hiding the real role of the HR and this false sense of security compared to the rest of the workplaces despite all these lay-offs from the big companies. Also, whenever a unionizing attempt happens, the companies go into crackdown mode and have their multitude of ways to either fire you with a bogus reason, remove your post citing “restructuring” or pulling you on a dead career track and demonize you in front of your colleagues with the usual “we care about our employees and everything can already be resolved through HR” speech. And moreover, many of these issues have a direct cause the Work Laws of the respective countries
It’s because we can just leave for better positions.
As a junior product, hell no.
okay, do that then and stop complaining i guess?
There has been chatter on Blind for the devs and engineering at my company unionizing. It’s a long shot. But I’m all for it.
While I completely agree, the meme would not really be different with a unionised workplace
Unions only make sense when you are easily replaceable as a worker so you don’t have any barganing power on your own. As an individual IT worker you can usually tell your boss to fuck off if things get bad and just look for a new better job…
Corp IT when the team gets ready for production
Hah, yes, I was a few times between these two sides. My role was to understand both and doing something you could call “translating.”
Well–well look. I already told you: I deal with the god damn customers so the engineers don’t have to. I have people skills; I am good at dealing with people. Can’t you understand that? What the hell is wrong with you people?
And if you convince the project manager that it won’t work by telling them all the reasons why they come back a few days or weeks later asking why it won’t work.
You forgot sales
this is where the art of bullshit … managing expectations, comes in handy
Piped Link: The Expert (Short Comedy Sketch) aka “7 Red Lines”
The Expert!
This lives in my head. Any time I talk to/about sales or customers. ajklsdhflkasjdgfloaui
Why do you have a project manager discussing technical solutions? That’s kind of… very wrong. Most PMs nowadays have a just a slightly better technical background than a secretary…
A project manager has responsibility for delivery of a project but they typically lack domain specific knowledge. As a result they can’t directly deliver something, merely ask subject matter experts for advice and facilitate a team to deliver.
Most PM’s cope with the stress of this position poorly.
This cartoon is an example of micro management (a common coping mechanisim), the manager has involved themselves in the low level decisions because that gives a sense of control. If a technical team then tell them its a bad decison the team are effectively attacking their coping mechanisim.
The solution isn’t to tell them their technical idea is terrible, when you’ve fallen down this rabbit hole you have to treat the PM as a stakeholder. They are someone you have to manage, so a common solution is to give them confidence there is a path to delivery, a way to track and understand it.
Best practice is to clearly state that PM here is not competent for its job, either he finds a solution himself (e.g. he manages expectations of clients without admitting he fucked up) or he has to be replaced.
This kind of situation is very dangerous. PM shouldn’t take similar decisions, nor promising anything
This advice isn’t grounded in reality.
Management normally defines ways to track and judge itself, these are typically called Key Performance Indicators.
KPI’s are normally things like contract value growth, new contracts signed, profit margin, etc…
So if the project manager is meeting or exceeding their KPI’s and you walk up to their boss telling them the PM is failing as basic job functions, the boss won’t care.
This is because the boss might have set the KPI’s or the boss might also be judged on them. In either situation its to the bosses advantage to ignore you.
The boss will only care if there is a KPI you can demonstrate the PM failing to meet.
Every person/group will have various incentives and motivations. To affect change you have to understand what they are.
Too real