Remix.run Logo
▲ adamddev1 an hour ago

People keep believing that the big LLM players with somehow disprove Rice's Theorem. "Somehow we'll be able to get AI to check if a program does X or Y." "We'll be able to have the machines verify things automatically." But this is is of course as hopeless as solving the Halting Problem. Theoretically, we know this is impossible.

Empirically, we can observe the breaking effects of this broken thinking. Code quality goes down, and apps go from being 99% to 95% reliable. But that's not a big deal, they say, that's good enough... But when the quality of all the building blocks further down get degraded in the same way, you can't keep track of which parts are broken, and which parts are dependable, and the whole thing comes crumbling down.

People keep saying, "I can build an app with AI, therefore we can build everything with AI." This article talks about some potential anecdotes that could help to show that doesn't work.

▲marcosdumay 14 minutes ago | parent | next [-]

As the sibling says, the problem is not really Rice's Theorem. We were doing some great progress into software reliability before the LLM-crazy destroyed the industry.

The problem for LLMs is less formal and way more wicked. We don't have any good theory of software reliability. At all. All the reliability we have is artisanal and designed ad-hock.

▲habitue an hour ago | parent | prev | next [-]

Rice's theorem is across arbitrary turing machines. We intentionally limit the kinds of programs we emit with type systems, knowing they will prevent us from writing some programs, but we'll be able to analyze the ones we can write much better.

We prove properties of programs all the time, that's what a type system is for.

Can we prove all properties about our program that we're interested in? Maybe, maybe not. But Rice's theorem is not the tool for that argument.

▲adamddev1 an hour ago | parent [-]

Are vibe-coded apps being being written in Rocq programs that perfectly match dependent types to every possible behavior? Is anyone anywhere writing software with type theory at the level where it perfectly limits things and saves our programs from semantic mistakes?

▲vouwfietsman 31 minutes ago | parent | next [-]

> every possible behavior > semantic mistakes

Of course the point is not whether we can now do this with AI, but whether AI can help us get the same quality we used to get, faster.

Also, consider that it should rarely be the goal to enumerate and judge every possible behavior of a program, with exceptions for life-saving or otherwise critical software.

▲d0mine 28 minutes ago | parent | prev [-]

Many of the recent maths solutions are just a lot of Lean code (types + guarantees).

▲ginthian 36 minutes ago | parent | prev [-]

[flagged]