There is no general solution other than brute force. That's not a terribly difficult extension of the halting problem, it just takes more paperwork to deal with the edge cases, but you'll get to that result. The same basic technique works: Your supposed solution to the problem is itself some finite program, and you can feed it the "I halt only if I don't halt" problem too. The difference is that brute force is a solution, because now instead of an infinite sequence of programs you have a bounded set of programs. So whatever concrete "I halt only if I don't halt" you pass to someone within the specified limits, there is definitely some answer, but your technique won't be able to tell what it is short of just running it.
For the same reason the halting problem doesn't even have a good heuristic, neither does this. Unpredictable chaos is not an exceptional case, it is the exponentially-normal case. You have to go the other way, and construct programs deliberately designed to have the ability to tell if they halt. The term for that if you want to learn more about it is "non-Turing complete programming language", sometimes called a "sub-Turing" programming language: https://increment.com/programming-languages/turing-incomplet...
You can read that as "this is how hard it is to construct code that we can make execution guarantees about". That focuses on code that is deliberately constructed to be finite in scope and may be something that can be strictly bounded in memory use or time or both. You'll note if you spend any time working with them how hard they are to work with. That's a reflection of the limits of generalizing any such proofs of time or space of a given program.
If there is a general algorithm that does what you think, we don't even have a clue what it would look like. And we have a lot of clues there can't be any such thing.
For the finite case, the more relevant question is, can you predict whether or not the computation will halt in less time than 1. executing the algorithm and 2. checking whether or not the algorithm ever loops?
Bear in mind checking whether or not the algorithm ever loops means taking the full state of the system and checking against a database of all previous states of the system. Bear in mind that the Atari 2600, and its whopping 128 bytes of RAM, has with that amount of RAM more states than there are planck volumes * planck time intervals in the known universe... by over sixty orders of magnitude. And every three additional bits you add to the RAM of the system your are looking at adds an order of magnitude (minus a bit) to that, so, nearly 3 orders of magnitude more states per byte... not per megabyte or gigabyte, per byte. Call it 2 orders of magnitude per byte if you want to be conservative.
It can be solved, if by nothing else simply by running it, in the mathematical sense. In the practical sense it's not even close. That's why we use the Turing machine analysis... technically it's an approximation because we don't actually have real Turing machines. However the size of the finite state machines we have is such that it is far more productive to simply say "the halting problem is unsolvable" than to argue about how many orders of magnitude of orders of magnitude of resources it takes to solve the question of whether or a given program terminates.
I think there's an equivocation of "computable" going on here. Mathematicians talk about a lot of things like "uncomputable sequences" but that is usually making a statement about the sequence, not necessarily any individual member. The Busy Beaver sequence is uncomputable. You can, however, quite trivially compute BB(2), even in your head if you're a bit careful. You can set up individual elements of an uncomputable sequence in our universe, and you may be unable to state in advance what the system would do with anything less than simply letting it run and see what happens due to the complexity of the system, but being a member of an uncomputable sequence doesn't mean that you can't in fact set those things up and watch them run. The Universe doesn't throw an "UncomputableCircumstance" exception or anything. It just keeps advancing to the next state. Your inability to make certain statements about that next state or some future state is not its problem.
It is a common accusation. There's a somewhat famous quote I've seen a few times:
"It's interesting to look back through history on this one. Each age has its pinnacle of technology, and each age uses that technology as a metaphor for nature, for the universe. In ancient Greece, the technological marvels were musical instruments and the ruler and compass. The Greek philosophers tried to build an entire cosmology from number, harmony, proportion, form, and so on — from mathematics, basically. Remember the music of the spheres? The Pythagoreans believed that nature was a manifestation of rational mathematics. Later on the pinnacle of technology was the clockwork. Newton wanted a clockwork universe, the entire universe as a gigantic clockwork mechanism, with all the parts interlocking and ticking over with infinite precision. Then in the 19th century along came steam power, and the universe was then depicted as an enormous heat engine, or thermodynamic machine, running down toward its heat death. Today the computer is the pinnacle of technology, so it's now fashionable to talk about nature as a computational process."
While "computer" may give us impressions of something with "a CPU" and "RAM" and "a disk drive", it does at least seem plausible that the universe as computation is a plausible base level, though. Unlike "the music of the spheres", which to the extent that it made predictions of the world, it got them wrong in the most basic way, viewing it through a lens of computation allows us to put some quite subtle and interesting limits on things. "Computation" is a pretty flexible substrate; it is difficult to imagine how the proposition "the universe is a computation and subject to the limitations thereto" could be falsified, and if it could, it is difficult to imagine how we would be able to know it was so falsified. Nevertheless the math of computation allows us to say non-trivial things about the universe as a result; it is not a vacuous generalization, though it is certainly a loose one... being able to say yet more concrete things about the nature of the computation, such as "this is exactly how gravity works", has quite a bit more utility.
For the rest of HN, while that video is from someone who takes the Bible seriously, you can also view it as an interesting examination of the historical time period, even if with a particular lens and slant. Who doesn't have a particular lens and slant anyhow?
It sounds like you think emacs is some sort of basic text editor, I dunno, like Notepad on Windows, that has an adjoined Lisp interpreter?
Admittedly, it doesn't help that there are some sibling comments that implicitly seem to be speaking that way.
However, Emacs is a 42-year-old software program that has been in constant development this entire time. Its git repository has over 180,000 commits right now on its main branch, which is still 20,000 ahead of VSCode. It doesn't just have a Lisp editor attached, it has 1.6 million lines of Lisp in it as well, and that's just the source repo, not all of the extensions you can get for it. Using "cloc" to count the total lines of source it has, it's still pretty close to 2/3rds the lines of code than VSCode has, at 2,613,748 for emacs versus 3,849,521 for VSCode. So that's the scale we're talking here, something on par with an IDE, not something on par with a simple text editor.
Yes, it gives you a lot of capabilities you didn't have before. The joke about it being a decent OS that needs a good text editor comes from the fact it has a large number of things it can do out of the box that aren't just text editing. It isn't just Notepad with a Lisp interpreter attached. It has vast capabilities that have been implemented and then also tested over the course of decades. Considering the set of disadvantages it carries with it, like weird key bindings and the fact that the variant of lisp it uses is more-or-less unique to emacs, somewhat analogously to the handicap principle [1] one should counterintuitively understand that as a sign that it must have extraordinary strengths that are able to offset that.
(I've used it for a long time, but I never really learned Lisp. AIs are making it much easier to customize than ever, though. I've said many times here on HN that I think every line of AI code should be reviewed. So yesterday I prompted Claude to build some Lisp functions so I can declare 1. a base directory 2. a regex of file names to match and produce 3. a function to walk over the entire directory forwards or backwards with CTRL-x CTRL-n or CTRL-x CTRL-p, thus allowing me to easily walk through an entire project for review purposes systematically. Nobody had to give me permission to do that. I didn't need to "create an extension". I don't have to care if anyone else in the world wants it. It's not the only editor that can do this as easily as emacs but it's a short list.)
This whole vulnerability thing is the first time I'm really feeling like AI tech is a shakedown more than a value-add to my job. So I have to take multiple different frontier models, burn tokens constantly scanning all my code bases with complicated harnesses that eat tokens by the hundreds of millions, burn tokens cross-checking the cross-checks of the cross-checks in some eight-phase process made out of non-deterministic agents, to feed them into another multi-stage multi-agent pipeline to try to turn them into actionable vulnerabilities, and if I ever stop or slow down this process I can expect to be explaining why I did that in a court case someday.
That's ridiculous.
And yet, presumably, the vulns are real.
What are businesses supposed to actually do with this?
What happens to the whole AI value proposition when instead of it being a way to pump out lines of code for crazy cheap it becomes a way for each line of code to become vastly more expensive than it was before?
I can't help but notice that in the section headed "What it costs" the $ symbol is conspicuously absent. I would definitely like to hear a much more concrete number on some sort of per-100k-line basis or something. I know that per-line isn't great but at least it would be something.
Maybe if the models get a lot better we wouldn't need all this cross-checking. And maybe they'd write fewer vulnerabilities for the other models to laboriously and expensively figure out in the first place.
But good gracious does this sound like the AI industry just asking for you to hand the a blank check, because it sure would be a shame if something happened to your code base, wouldn't it?
I don't have a solution to this. This is stricly a cri de coeur.
Except maybe to say that if this is going to be the way in the future that it becomes vastly, vastly more important to work out how to write more secure code from the very beginning. We've certainly been trending this way for the last few decades, hand-wringing aside security has gotten a lot better than it used to be, it's just the world has gotten more complicated and harsh as well so it doesn't always look like it. But it takes over a decade for things like "use parameters in your SQL query instead of concatenation" to go from some crazy guy's idea in some obscure open source package somewhere to common practice that can almost be counted on. That loop is going to have to close much faster and there's a lot of things that are barely registering on people's radars, like, the *at APIs for files (openat, etc.) need to be the default much, much sooner than their current trajectory has them on.
I've done two rewrites now with AI. Neither of them particularly large, but still non-trivial; think in the low tens of thousands of lines of code. It's been a bit so I haven't tried it on the very latest models, but I can attest that at least Opus 4.5 does like to sand off the edges and drop use cases without necessarily drawing it to your attention. Based on my other experience with later models I doubt they've changed that much. Partially because in a rewrite, trying to sand off some of the rougher edges is itself a valid move sometimes; if you don't need the crazy complication from 15 years ago maybe you should try dropping it.
In both cases I more-or-less ended up lining up the rewritten code and the original code right next to each other and trying to ensure that I could figure out where every line of code in the original ended up in the rewrite. That's much less of a pain than it sounds since they tend to bunch together. One of the rewrites was much harder because the very reason I wanted the rewrite was that the original was very hard to understand due to a combination of way more indirection than was necessary and the pervasive use of associative maps instead of structures, even though the data was structured. The AIs get confused just as the humans do. I did some work in creating unit tests that drew from a data source that both code bases could test against, since this was an HTTP API there was a relatively clean cut point for both codebases there.
AI makes these rewrites way, way easier than they used to be, but you do need to keep an eye on what they're doing, cross-check the final output by hand or by those shared unit tests, and not just assume you can fire the project off Friday evening and take whatever it made by Monday because that end product is probably missing quite a few of the original features.
When I have a good idea that I can hit what I want in a single query, I still use search engines directly a lot. But I have found AI is pretty decent at automating the process of making a vague search, picking up from the search better search terms, then making a couple of other wrong searches, then refining down to what I really want and potentially pulling together an answer from multiple sources. I know how to do all that, but the AI can do in a minute what may take me 15 minutes.
I'd say I also know I can still do it, but... as the search engines deteriorate it is getting somewhat harder to do this by hand than it used to be. I still do this by hand sometimes for cases where I want the exploration of a topic for myself, rather than a focused answer where I don't really care about what I learn along the way, and it's getting harder. I don't know that it'll converge at "zero value" but the search result pages seem like they're just... harder to use for this than they used to be, though it's hard to put my finger on how.
"Our hypothesis is simple: session logs are now the most important artifact in software development, and should be stored alongside the code itself in the repository."
Wasn't there an article on HN that went by in the last few weeks about someone actually implementing this, and it just made things worse on every metric?
Pre-AI people periodically wanted version control to be tracking every keystroke and I, along with a lot of other people, feel like they never successfully articulated exactly what we're supposed to get out of that. Session history seems like the same thing. A prompt history, maybe. But I don't want every bit of an AI's musing any more than I want every last stray through that passes through a developer's head either, and for the same reason in both cases: A finite mind has room for only so much stuff.
It is not a viable strategy for a finite mind, be it human or AI, to just "stuff everything into it and expect improvement to result". The first thing that finite mind will need to do to get any value out of it is to extract it into some much, much smaller and less detail-rich summarized version. Which is pretty close to what we already have, except without needing to burn AI time on the process. We have spent decades honing techniques for reducing cognitive load. The AIs benefit from them too, and make them more important than ever, not obsoleted.
Sure, it isn't exactly what we have today. But I think this is a case of the exceptions looming too large in our mind, precisely because they are exceptions. Yes, I've had a handful of cases in my career where I've wondered what were they thinking, and not just as a criticism, but as an actual question. But it's rare, and in the end, not necessarily all that valuable compared to questions like "what is the code doing" and "what is passing through the code that gets this thing done to it". In the vast majority of cases, the code is already only and exactly what I need.
The fact we have this code artifact that is a gateway and a checkpoint through which "intention" does not pass is a positive good thing and is one of the subtle reasons that people miss that makes both large-scale human software development and the current trend of AI-based software development possible in the first place. The highly effective process of trimming down all of this stuff into an artifact that has an extremely-precisely specified function and doesn't need external support from humans or process or history is an amazingly wonderful thing. Larding down the codebase with vast, vast quantities of very fluffy data that is only quite rarely useful is a positive step backwards, not forwards.
Properly speaking, that would be a characteristic of the entire production process, including the people, rather than a property of the code itself. (At least for now. Stay tuned with AI for further updates.) Still, you'll see it in the code.
Ask your local fire department about putting fires out in battery-powered cars versus gasoline cars. Yes, there is a qualitative difference and it's not in favor of the battery-powered cars.
That's not to say that it's a stopper for them; it's just part of the cost/benefits analysis. The idea of technologies that are better on all parts of the cost/benefit analysis at once is a science fiction or video game concept. In the real world there's always a mixture of positives and negatives between two different technologies.
I don't know what those four state's goals are, but if they are out to address the nominal issue and not just collect a payday in court from deep pockets, they are correct to not sue all of them all at once. In our system, they want a precedent. To get that precedent, they go after their best target to get it. I would expect they looked at all the possible targets and determined that Facebook is the one they are most likely to win.
They have to make this determination before discovery, but that's life.
If they win this case, even if they don't get the full penalty, you can be sure the other companies will be paying attention and will do something about it. Of course that "something" may not be "immediately stop engineering addiction into their products" and be more like "be sure to obfuscate it better, maybe crank the knob down a bit and prepare to claim in a future lawsuit that the problem was solved even though they haven't really changed anything". Suing the next company is easier with a precedent to go off of.
They are correct to concentrate their fire on what they believe is the most vulnerable part of the line, not to spread their limited resources out over attacking half-a-dozen of the largest and most well-resourced targets on Earth. Once they lose the first case, the resulting precedent weakens them in all of the others as well.
I agree that's what they seem to have been thinking.
I don't entirely understand... well... from a rational perspective anyhow, of course companies are not entirely rational... why it didn't become clear that this was a silly idea and not working. It's easy to make Gamepass stop cannibalizing your main game sales. You don't need a big announcement, you don't need to advertise your plans. You don't need a huge internal political fight. You just... stop. You just stop putting your brand new AAA games on your cheap subscription service plan. You don't even have to remove the old ones, they turn into your old AAA games naturally in the fullness of time. Nobody has to lose face. It's easy. It's like falling off a log.
[email protected] , though be aware that I only really check email every few days now.
Permission for comment republication in HN collections granted, though please do drop a line to [email protected] so I know. :)
my public key: https://keybase.io/jerf; my proof: https://keybase.io/jerf/sigs/vL9FeVDSGtiDMBmXC4f_rCikI0n4jNfB-1PsNgUN-Is