What does “Undecidable” mean, anyway

IMHO what just referring to uncountability misses is that not only most functions are unexpressable, many __useful ones__ are not. Most ℝ→ℝ functions (and even most real numbers) are so unremarkable there is no way to uniquely name them. The fact that some useful functions are undecidable is quite a bit less trivial than "there are more functions than there are programs to evaluate them".

Isn't this related to why the busy beaver is the fastest growing program, given that at some N states it would be able to emulate any closed form function and then at some greater number N + M states be able to use that function in more complex functions (as a lower bounds, the actual busy beaver of N + M states given size would likely be an even larger output than the same sized Turing machine emulating whichever fast growing function is used for comparison)?

`S = {str -> bool}` is actually uncountable. `S` is isomorphic to the power set (set of all subsets) of `str`, and `2^str` is at least as big as the set of real numbers, as any real number (like π) can be mapped to the set of string prefixes (like `{"3", "3.1", "3.14", ...}`). Since the reals are uncountable, so is `2^str` and `S`.

> It's better to say that some functions like "does this program halt?" simply don't exist.

Let f : (p: String) -> Boolean equal the function that returns True if p is a halting program, and False otherwise

I think you are experiencing the same confusion I felt when I first started thinking about the difference between a program and a function.

The set of all possible mapping from all possible finite strings to booleans is definitely *not* countable.

What I (and the article) mean by a "function" `f : string -> boolean` here is any arbitrary assignment of a single boolean value to every possible string. Let's consider two examples:

1. Some "expressible" function like "f(s) returns True if the length of s is odd, and returns False otherwise".

2. Some "random" function where some magical process has listed out every possible string and then, for each string, flipped a coin and assigned that string True if the coin came up heads, and False if it came up tails and wrote down all the results in a infinite table and called that the function f.

The first type of "expressible" function is the type that we most commonly encounter and that we can implement as programs (i.e., a list of finitely many instructions to go from string to boolean).

Nearly all of the second type of function -- the "random" ones -- cannot be expressible using a program. The only way to capture the function's behavior is to write down the infinite look-up table that assigns each string a boolean value.

Now you are probably asking, "How do you know that the infinite tables cannot be expressed using some program?" and the answer is because there are too many possible infinite tables.

To give you an intuition for this, consider all the way we can assign boolean values to the strings "a", "b", and "c": there are 2^3 = 8. For any finite set X of n strings there will be 2^n possible tables that assign a boolean value to each string in X. The critical thing here is that 2^n is always strictly larger than n for all n >= 1.

This fact that there are more tables mapping strings to boolean than strings still holds even when there are infinitely many strings. What exactly we mean by "more" here is what Cantor and others developed. They said that a set A has more things than a set B if you consider all possible ways you can pair a thing from A with a thing from B there will always be things in A that are left over (i.e., not paired with anything from B).

Cantor's diagonalization argument applied here is the following: let S be the set of all finite strings and F be the set of all functions/tables that assigns a boolean to each element in S (this is sometimes written F = 2^S). Now suppose F was countable. By definition, that would mean that there is a pairing that assigns each natural number to exactly one function from F with none left over. The set S of finite strings is also countable so there is also a pairing from natural numbers to all elements of S. This means we can pair each element of S with exactly one element of F by looking up the natural number n assigned to s \in S and pairing s with the element f \in F that was also assigned to n. Crucially, what assuming the countability of F means is that if you give me a string s then there is always single f_s that is paired with s. Conversely, if you give me an f \in F there must be exactly one string s_f that is paired with that f.

We are going to construct a new function f' that is not in F. The way we do this is by defining f'(s) = not f_s(s). That is, f'(s) takes the input string s, looks up the function f_s that is paired with s, calculates the value of f_s(s) then flips its output.

Now we can argue that f' cannot be in F since it is different to every other function in F. Why? Well, suppose f' was actually some f \in F then since F is countable we know it must have some paired string s, that is, f' = f_s for some string s. Now if we look at the value of f'(s) it must be the same as f_s(s) since f' = f_s. But also f'(s) = not f_s(s) by the way we defined f' so we get that f_s(s) = not f_s(s) which is a contradiction. Therefore f' cannot be in F and thus our premise that F was countable must be wrong.

Another way to see this is that, by construction, f' is different to every other function f in F, specifically on the input value s that is paired with f.

Thus, the set F of all functions from strings to boolean must be uncountable.

Having a decision algorithm does not make a computation free. It may take exponential time in the input size, doubly exponential time, some time involving Graham's number, ... etc. It may also take up an unreasonable amount of space. Indeed, some problems have such complex algorithms that you should expect the universe to end before the answer is determined and/or the computing device is doomed to collapse into a black hole, making the answer irretrievable.

So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive.

That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.

I don’t think finite-but-unbounded and infinite makes any difference in this setting, since at most finitely many cells of the memory tape may be used at any stage of computation.

> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at!

> (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop)

I think what makes Animats's distinction worth stressing is that a lot of people miss this and fall into the trap of making false/misleading claims about the impact of the halting problem on actual computers/software.

For instance, claiming that the halting problem proves there are problems humans can solve that computers fundamentally can't, giving "the halting problem makes this impossible" as reason against adding a halt/loop detector to a chip emulator, making all sorts of weird claims about AI[0][1], or arguably even this author's claim that a halt detector would make bcrypt cracking trivial.

[0]: https://mindmatters.ai/2025/02/agi-the-halting-problem-and-t...

[1]: https://arxiv.org/pdf/2407.16890

Yes, I thought the article was really good until it got to that point.

> a halt detector can be trivially repurposed as a program optimizer / theorem-prover / bcrypt cracker / chess engine. It's too powerful, so we should expect it to be impossible.)

A Turing machine can be trivially repurposed as a bcrypt cracker or chess engine (for the same definition of trivial the author is using), so if it's not intuitive that a computer can do this, then your intuition is wrong.

Program optimizers and theorem provers also exist, of course, but in those cases the problems really are undecidable so no Turing machine is guaranteed to work on any given program or theorem.

I meant more as how to mentally model it in a way that can get someone across the line. My assertion is that caring about undecidability is almost certainly a waste of time for most people. That said, the reason we work in small chunks is often so that we can more easily answer questions about programs.

Moving the graphical drawing and constraints over to a symbolic system also helps see how many symbols it can take to cover a simple system.

Of course, the real reason for me thinking on this is that I'm playing with FreeCAD for the first time in a long time. :D

I don't either philosophical conceptions of consciousness or theories of computational complexity count as even "efforts to formalize intelligence". They are each focused on something significantly different.

The closest effort I know of as far characterizing intelligence as such is Steven Smale's 18th problem.

https://en.wikipedia.org/wiki/Smale%27s_problems

I think this is more about levels or classifications of intelligence.

If you've ever interacted with a very smart animal, it's easy to recognize that their reasoning abilities are on par with a human child in a very subjective and vague way. We can also say with extreme confidence that humans have wildly different levels of intelligence and intellectual ability.

The question is, how do we define what we mean by "Alice is smarter than Bob". Or more pertinently, how do we effectively compare the intelligence and ability of an AI to that of another intelligent entity?

Is ChatGPT on par with a human child? A smart dog? Crows? A college professor? PhD level?

Of course we can test specific skills. Riddles, critical thinking, that sort of thing. Problem is that the results from a PhD will be indistinguishable from the results of a child with the answer key. You can't examine the mental state of others, so there's no way to know if they've synthesized the answer themselves or are simply parroting. (This is also a problem philosophers have been thinking about for millenia)

Personally, I doubt we'll answer these questions any time soon. Unless we do actually develop a science of consciousness, we'll probably still be asking these questions in a century or two.

The known laws of physics are computable, so if you believe that human intelligence is purely physical (and the known laws of physics are sufficient to explain it) then that means that human intelligence is in principle no more powerful than a Turing machine, since the Turing machine can emulate human intelligence by simulating physics.

If there's a nonphysical aspect to human intelligence and it's not computable, then that means computers can never match human intelligence even in theory.

I was thinking the same thing, maybe a level above in the Chomsky Hierarchy…

>More likely we’re just going to max out around human levels of intelligence, and we may never find a higher level than that.

I've seen people state this before, but I don't think I've seen anyone make a scientific statement on why this could be the case. The human body has a rather tight power and cooling envelope itself. On top of that we'd have to ask how and why our neural algorithm somehow found the global maxima of intelligence when we can see that other animals can have higher local maxima of sensory processing.

Moreso machine intelligence has more exploration room to search the problem space of survival (aka Mickey7) that the death any attached sensoring/external network isn't the death of the AI itself. How does 'restore from backup' affect the evolution of intelligence?

Granted there are limits somewhere, and maybe those limits are just a few times what a human can do. Traversing the problem space in networks much larger than human sized capabilities might explode in time and memory complexity, or something weird like that.

For that definition, including the phrase "ad infinitum", then it's pretty unlikely.

But a lack of infinities won't prevent the basic scenario of tech improving tech until things are advancing too fast for humans to comprehend.

The CPU is an implementation of theory. It just happens that the realization of several axioms in the Turing machine is realizable physically. And the rest hold true. The nice thing with notation is that they're more flexible than building/creating/executing the thing they describe.

Turing machine works going left or right writing/reading on a tape of 1s and 0s. Your CPU works on RAM writing and reading 1s and 0s.

CPU in principle isn't that different and is largely just using a more sophisticated instruction set. Move 5 vs right right righy right right. swap vs read, write, right, write. etc

Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo.

Moreover what's really interesting to me is that Turing came up with the idea from following what he himself was doing as he did computation on graph paper

I completely disagree. For example understanding the theory gives me a very powerful bullshit detector because entire categories of problem which might sound merely difficult are in fact Undecidable.

Knowing that the actual regular expressions can be recognised by a finite automaton but PCRE and similar "LOL, just whatever neat string matching" extensions cannot means you can clearly draw the line and not accidentally make a product which promises arbitrary computation for $1 per million queries.

I agree that understanding something of how the CPU works is also useful, but it's no substitute for a grounding in theory. The CPU is after all obliged to only do things which are theoretically possible, so it's not even a real difference of kind.

Introduction to the Theory of Computation by Michael Sipser. There's also his course based on the book on YouTube[0].

Language Implementation Patterns by Terence Parr. It avoids the theory in other books, going for a more practical approach.

Then it was just trying a lot of programming paradigms like functional programming with Common Lisp and Clojure, logic programming with Prolog, array and stack programming with Uiua. And reading snippets of books and papers. It was chaotic.

But the most enlightening lesson was: Formalism is the key. You define axioms, specify rules and as long as you stay consistent, it's ok. The important thing is to remember the axioms and understanding the rules.

[0]: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3...

Might be hard to approach but my favorite is Pierce's "Types and Programing Languages": https://www.cis.upenn.edu/~bcpierce/tapl/ (known as TAPL). Was grateful to take a graduate level class using it in college.

Mertens Theory of Computation

It's the recursive nature of it.

Almost any program can be written in a DSL that solves the class of problem that the program solves. So if you consider the user stories of your project as that class of problem, you can come up with with a DSL (mostly in form of pseudocode) that can describe the solution. But first you need to refine the terms down to some primitives (context free grammar). You then need to think about the implementation of the execution machine. which will be a graph of states (automata). The transition between the states will be driven by an execution machine. The latter needs not be as basic as the Turing machine.

But often, you do not need to do all these stuff. You can just use common abstractions like design patterns, data structures, and basic algorithms to have a ready made solution. But you still have to compose them and if you understand how everything works, it's easier to do so.

it depends what you're working on, if you do any form of program analysis (security, compiler stuff) you bump into undecidability everyday

Could I say that 'P is Undecidable' is defined as: It is False that {There exists T such that [(T and P) and (T and not P) are both consistent]}?

I still think what I said was correct.

> On the other hand, undecidable has a sharper meaning in computation contexts as well as constructive logics without excluded middle. In these cases we can comprehend the “reachability” of propositions. A proposition is not true or false, but may instead be “constructively true”, “constructively false”, or “undecidable”.

Yes, but that just means that independence/undecidability depend on the proof system, as I said before. So when using a constructive proof system, more statements will turn out to be undecidable/independent of a theory than with a classical one, since the constructive proof system doesn't allow non-constructive proofs, but the classical one does.