The overall point feels strained to me.
Yes, formal mathematics has such limits. We can't expect machines to be perfect and provably perfect. But the industry isn't assuming that. Why would it? Natural intelligence is not perfect or provably perfect, either.
Rather than certainty, measurement is often enough. We can't prove a program will always halt, but we can check it halts in a specific execution.
Approximation is also often all we need. Even if we can't prove that we can train a network with more than 50% success, if we can get multiple shots at that (using different data, or initial random weights, or training techniques, or something else), then we can reduce that danger exponentially. (I don't know that we have a guarantee of succeeding there, but this would be the hope, and I am not aware of anything showing it is impossible, unlike perfect provability.)
Finally, it is possible that perfect provability does work on the problems we care about. Godel and Turing etc.'s proofs rely on finding rare situations where we can't prove things - cleverly-constructed pathological cases - but perhaps human behavior does not fall into that set. Human behavior may not be a pathological case for proofs or learnability.
> The overall point feels strained to me.
It is. This happens to some people who discover undecidability is a thing. Then they get carried away and try to generalize to other areas. Branches of this line of thinking include the concept that intelligence must be analog with infinite precision, (this is the same line of thinking as the argument against digital audio) or intelligence must be "quantum". (Penrose).
The formal answer to the halting problem is that deterministic systems with finite memory must repeat a previous state or halt. Undecidability requires unbounded memory. Finite memory systems may have so many states and be so complex that decidability is computationally infeasible. But that's not impossibility. I used to get this objection when I was working on proof of correctness systems. We now know that some programs are hard to decide, but many useful ones are not.
If your program is anywhere near undecidable, it's probably broken. Microsoft's position with their Static Driver Verifier was that if 45 minutes of symbolic execution hadn't found a way out, you failed driver verification. This is one of those problems, like linear programming, where part of the problem space is really hard in a computational sense, but most of it isn't.
(I sometimes wonder if Penrose was on to something with his idea that the brain uses quantum effects in microtubules.[1] Penrose is a first-rate physicist. His philosophy is not as good. It's become clear that we can do artificial intelligence with acres of transistors and gigawatts of power, but the efficiency is terrible. We need either a more efficient algorithm or better hardware elements. LLM training now is like a Newcomen steam engine, where something the size of a house had the power output of a modern motorcycle engine.)
[1] https://en.wikipedia.org/wiki/Orchestrated_objective_reducti...
> We can't prove a program will always halt, but we can check it halts in a specific execution.
The computer scientist says “The halting problem cannot be solved, I have proven it” and the software engineer goes “30 second timeout, if the answer’s not ready by then we don’t need it”
I think this comparison is interesting because it shows the difference between theory & practice, but it's a little inaccurate. The halting problem being undecidable just implies there is no single universal algorithm that can tell you whether any program at all will halt. In practice we are working in specific domains and can come up with heuristics which are "good enough" for a specific codebase / module, like the timeouts you mention. So the halting problem can be solved for some subsets of programs but not all of them, and the computer scientist would hopefully have realized this instead of treating the codebase generically as "any program".
I don't understand the point at all. Mathematical theorems like godel's incompleteness theorem or the halting problem are applicable to everything including the human brain. If they were a limitation to developing general intelligence then human beings wouldn't have existed.
> Godel's incompleteness theorem or the halting problem are applicable to everything including the human brain.
Maybe. That's if you assume that the universe is a conventional computer. Far from settled and the alternative isn't necessarily just "God does it" - it might be that the universe is a "computer-plus", with some processes that produce results not computable by Turing means. It would be strange, but so is quantum mechanics, so...
This line of thinking doesn’t really go anywhere. You can say “but what if <something outside of an axiomatic system>? Then <axiomatic system> doesn’t apply!”
Well great. Then where are you? You are precisely nowhere. You haven’t disproved the results in the system and you haven’t proved anything else.
As of yet we have no such evidence of physical systems that are more powerful than Turing machines. We will consider if ever such evidence arises.
Turing machines can't operate on arbitrary real-numbered values because they require infinite precision.
If the universe indeed uses real values, it's possible that it's more powerful than Turing machines.
The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers are non-computable (the set of computable numbers is countable, so it has the same "size" as the Naturals, while the Reals are not countable - so they are much larger).
However, this doesn't mean that TMs can't operate on such numbers. You can compute the fact that pi + pi = 2 * pi even if you can't enumerate all of pi's decimals.
That's why I added the word "arbitrary" :)
> However, this doesn't mean that TMs can't operate on such numbers.
Well, it kinda does. For example, you can't compute the sum of two arbitrary real values in a finite number of steps.
That being said, it's possible that the universe actually is not "running" on real numbers. This would also mean that our physics built on top of calculus is just an approximation.
This has always fascinated me. You can't really construct a meaningful amount of calculus without having real-valued variables. The intermediate value theorem depends on it, and it's one of the foundational parts.
I tried to construct something like "bounded error rational calculus", by trying to use rational ranges instead of real values and then constraining the range size. I was able to recover _some_ calculus, but I really have not studied it in enough details.
I find this topic of precision and of the computation that happens in the universe to be pretty interesting, but also very hard to pin down.
For example, let's take two arbitrary real numbers, call them x and y. They're almost certainly irrational uncomputable numbers, of course. Now, what is their sum? It's x + y, of course - I can tell you that without doing an infinity of computational work. Now, is this a useful representation? It very much depends on the use you have for it. For two unrelated uncomputable numbers, their sum is almost certainly uncomputable anyway, so there's not going to be any meaningful representation of it either. However, we can still derive useful properties about it, and use it in physical simulations as we need. For example, if both x and y are positive, I can tell you that x+y is greater than either of them, so I can also tell you that the electromagnetic force between two particles that are at distance x+y will be weaker than the force between two particles at distances of just x or just y.
So, what would it mean for the universe to "compute the exact value" of these two, or of their sum? What can physics do, assuming that some aspects are indeed continuous, that a simulation running on a TM actually can't?
Yep, a possibility that has found support with Roger Penrose, who wrote two books about it.
Are they? Are there any actual Turing machines? Doesn’t that require infinite memory? I don’t know of a single thing which actually has that, nor one that comes close.
That just means even more limitations, then. (Though the grandparent comment is correct that literally everything is subject to the same Gödel-style limitation on its ability to make negative claims about its own behavior, whether computers, humans, or any other system at all.)
Not infinite memory, a Turing machine only requires "unbounded" memory, which is a way of saying that it will not run out of memory while running its program with the given input. In other words it just needs to have enough memory to run the program with whatever inputs it was given, which is much less than infinity. And this situation is quite common in the real world -- the programs I use on a daily basis have all the memory / RAM they need to do what I want (almost by definition). So in practice I might as well view them as Turing machines.
Finite machines such as FSMs (finite state machines) are a subset of TMs, so yes they are actual Turing Machines. What they aren't is UTMs ... universal Turing Machines that can emulate every TM.
The court system is the system built for dealing with this indeterminism in human affairs. The question is not whether imperfect systems are useful, or whether there are ways to construct a system to accommodate those imperfections - both of those have been answered again and again in human history (yes, and yes, with the same caveats as the first systems - turtles all the way down). The questions are how much effort does it take to reduce those imperfections to a level that renders the system a net improvement, what is the total cost of the system given those required efforts, and who pays the cost of the inevitable failures that still emerge from the system? As sits, the AI industry seems unwilling to put real effort into calculating the first, is certain the answer to the second is minimal, and is absolutely uninterested in being the answer to the third. The basic point here is, given that we know for a mathematical fact that the answer to the first is larger than we want it to be (that’s this whole article), how do we want to address the second and the third?