Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Infinities, impossibilities, and the man in the white linen suit

iain.so

Post reply on HN
Print view View original

31–40 of 65 posts

Re: Infinities, impossibilities, and the man in the white linen suit

#31

Post by jibal »

iainharper wrote: post #2

I wrote this partly because nobody seems to know about Gödel who is arguably a more important figure than Turing. The piece follows four threads where formal limits show up in AI practice today: learnable problems that mathematics cannot sort, neural networks that exist but cannot be trained, self-improving systems that dropped their safety proofs for benchmark scores, and the fact that “will this AI cause harm” is,…

> the fact that “will this AI cause harm” is, mathematically, an unanswerable question.

No it isn't -- this is a fundamental misunderstanding. What is unanswerable is "For all x where x is an AI, will x cause harm?" ... but there is an infinity of specific AIs that provably will or won't cause harm.

Likewise this a very common misunderstanding of the Halting Problem -- Turing proved that there is no TM that can prove whether m will halt for all possible TMs m ... but there are myriad TMs that provably do halt or provably don't halt.

Re: Infinities, impossibilities, and the man in the white linen suit

#32

Post by jason_s »

iainharper wrote: post #2

I wrote this partly because nobody seems to know about Gödel who is arguably a more important figure than Turing. The piece follows four threads where formal limits show up in AI practice today: learnable problems that mathematics cannot sort, neural networks that exist but cannot be trained, self-improving systems that dropped their safety proofs for benchmark scores, and the fact that “will this AI cause harm” is,…

I think there is a loose connection. Hofstadter's 1979 masterpiece, Gödel Escher Bach (https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach --- mentioned in an earlier reply), has a chapter called Contracrostipuntus (https://genius.com/Douglas-hofstadter-contracrostipunctus-an...) which describes an arms-race tension between Crab's "perfect" record player and Tortoise's mischievous records designed to be unplayable on that record player, with titles such as "I Cannot Be Played on Record Player X". Crab's then invents a "Record Player Omega" which includes an ahead-of-time "scanning" step to reconfigure itself based on the record it scans...

All of which reminds me of virus-scanning on computers, and AI efforts for "safety".

Making the connection between GEB and AI isn't new, apparently: https://matthodges.com/posts/2025-08-26-music-to-break-model...

Re: Infinities, impossibilities, and the man in the white linen suit

#33

Post by jsrozner »

cubefox wrote: post #18

Is it just me or does this article have a lot of LLM-isms?

Yes, it is very clearly AI written or substantially AI assisted. "Claude, write about Godel's incompleteness thms with respect to AI"

And it's annoying that comments like yours get downvoted. Maybe HN should have a "vote that this is undisclosed AI writing" button for every post now.

Re: Infinities, impossibilities, and the man in the white linen suit

#34

Post by Chinjut »

moi2388 wrote: post #26
hardbass wrote: post #20

Earlier quoted context omitted.

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.

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.)

Re: Infinities, impossibilities, and the man in the white linen suit

#35

Post by roughly »

azakai wrote: post #9

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 i…

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?

Re: Infinities, impossibilities, and the man in the white linen suit

#37

Post by jsrozner »

Has anyone here actually looked at the Shai Ben David (SBD) result? I did a final grad project on it recently for a class on incompleteness. In my view it's not really that interesting. For learnability to be undecidable, the cardinality of the continuum (size of the reals) must exceed \aleph_k for all finite k. ZFC does not bear upon this (CH is independent of ZFC), so this is a possible setting of the world, and therefore learnability can be undecidable.

But say the size of the continuum is, e.g., \aleph_3, (in this case CH is false, but it's not "horribly false"), then SBD shows how to build a compression scheme, and thus their EMX -- estimating the maximum problem -- is "learnable". But the compression scheme whose existence they show (it's just a function whose existence they prove) can't actually be encoded, since it requires identifying a maximal element by invoking the well-ordering theorem. So there's no algorithm that enables solving the problem (though a function solving the problem exists).

This result, without further work, does not immediately say anything about the sorts of problems for which abstractions can be learned. And abstraction is at the heart of understanding and problem solving.

See e.g., https://arxiv.org/pdf/1909.08410 (§5)

Re: Infinities, impossibilities, and the man in the white linen suit

#38

Post by hardbass »

skippyfish wrote: post #25
hardbass wrote: post #20

Earlier quoted context omitted.

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 qu…

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.

Re: Infinities, impossibilities, and the man in the white linen suit

#39

Post by cyberax »

hardbass wrote: post #38
skippyfish wrote: post #25

Earlier quoted context omitted.

> 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 qu…

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.

Re: Infinities, impossibilities, and the man in the white linen suit

#40

Post by Animats »

azakai wrote: post #9

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 i…

> 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...

Post reply on HN