What can be computed? A practical guide to the theory of computation (2018) [pdf] | Hacker News Reader

What can be computed? A practical guide to the theory of computation (2018) [pdf]

softouch.on.ca

96 pointsnill025 comments

What a wonderful text. Easy to read, concise, clear, interesting -- and above all, important.

I would add context for 2025 about the fundamental limits this places on what (modern) AI is in principal capable of. Perhaps some "non-computable" features would need to be hard-coded into AI, so that it could at least better approximate the types of incomputable problems we might ask it to do?

Also, a search of the text for "conscious" does not yield anything, which is probably a good thing. This text also reminds me of the questions like, "What does it mean to be conscious?" and, "How are human brains able to reason about (things like) incomputability, which in some sense, computers as we currently understand them could never do?" and, "What specifically beyond pure mathematics does a brain have or need in order to be conscious enough to reason about such things?"

corollary: Numberphile (with Matt Parker of Stand Up Maths) - "All the Numbers". Most are incomputable, of course :)

[0] https://www.youtube.com/watch?v=5TkIe60y2GI&t=1s

Other than Chaitin's constant(s), name a few that aren't computable.

Choose any arbitrarily small segment of the real line, all those numbers will be uncomputable almost everywhere

While there are many (often equivalent) definitions of what a computable number are. And easy to grasp informal explanation is that a number is computable if you can write a function/algorithm f(n) such that it returns the n-th digit in a finite amount of time.

For Pi as an example: f(3) = 4 (from 3.14)

Almost all applies to the elements of an uncountable set except for countable subset.

As the reals have a cardinality of 2^aleph_0 or aleph_1 (uncountable), but the Natural Numbers, Integers and Rationals are aleph_0 (countable), you have to find some many to one reduction.

Chaitin's constant is uncomputable because it is effectively random, and no random problem is decidable, or (co)recursively enumerable)

It gets mapped to the halting problem, because that is the canonical example but you could use the system identification problem, symbol-grounding problem, open frame problem etc....

But to answer your question, in the real interval [0,1], the computable numbers have measure zero, and the uncomputable numbers have measure one.

So right there is an uncountable infinity of non-computable numbers.

Chaitin's constant is uncomputable because of its construction, not because it is "effectively random". Pi is also "effectively random".

π is a transcendental number meaning that it is not algebraic

It is NOT an algorithmically random sequence.

Chatlin's halting probability is normal, transcendental, and non-computable.

https://arxiv.org/pdf/0904.1149 > Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol. 22, pp. 329–340, 1975] introduced Ω number as a concrete example of random real.

Being non-algebraic is not the same as being algorithmicly random in the formal sense.

These are distinct senses of "random". Pi is conjectured (but not proven) to be a so-called normal number, which means that n-grams have uniform frequencies, so if you slide a window of size n over the digits, then every sequence of n digits will come up with equal frequency in the limit.

Chaitin's omega is "random" in a stronger sense. There is no finite algorithm that can produce the digits. There's no compact, finite representation from which you could "unpack" those digits. The digits are what they are, the best way to represent them is simply to list them.

Pi's digits are very "regular", but the pattern is not about repetitions in digits or skewed frequencies of certain digit sequences but that the digits follow from simple rules. A short program can generate those digits to arbitrary length. So in some sense they have redundancy, a kind of pattern to them.

I should've been more clear. The Reals are very unsettling because there are supposed to be so many of them, but nobody has used, named, or described more than a few which aren't computable. They are angels dancing on a pin which we've never seen and probably don't need for any of applied mathematics.

> and probably don't need for any of applied mathematics

Basically everyone who uses mathematics in some applied capacity happily uses the real numbers.

No, all the numbers most anyone actually uses are computable, and it'd say something weird about determinism if they weren't. The word "need" was carrying some weight, as in necessary vs sufficient.

It's not about individual numbers. Most applied maths fields (including physics) use the real numbers and the properties of real numbers as a complete field are implicitly assumed all the time (e.g. for differential equations). It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable.

If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing. That's probably possible although I doubt that it would be very elegant. But it's simply not what people use.

> If you want to argue that one could derive a theory of physics etc. that doesn't rely on the real numbers that's one thing.

That wasn't my original intent, but I think it's a legitimate stance. The Reals are bizarre (Banak Tarski, etc...), and we practically never use the non-computable ones.

> It's only ever some mathematicians, computer scientists and philosophers who care about the fact that most of them aren't computable.

Lol, who else WOULD care? :-)

> That's probably possible although I doubt that it would be very elegant.

That's an aesthetic judgment. Someone else might argue that sticking to the numbers we actually use and can calculate is simpler/cleaner/more elegant/whatever. And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine.

(Although the Computables have plenty of weirdness to them too...)

> And besides, I'm guessing you could replace ℝ with T (for Turing) and most of the proofs would go just fine.

This is wrong. LUB doesn't hold for the computable reals, and this means that a lot of classical proofs straight up don't work anymore.

That's not to say you can't build a different kind of real analysis built only on the computable reals, some mathematicians have tried to do similar things in the past, but it's going to be a different framework with not exactly the same theorems and not exactly the same proofs; for example, there are no discontinuous functions anymore.

There's some more discussion here: https://www.reddit.com/r/math/s/LSL487ncag

Yeah, I'm sure there are some holes (poor attempt at a pun), but you already know you can get arbitrarily close to whatever bound with rationals, much less computables, so it seems like someone better educated than me could shore that up.

Anyways, the computables have unfortunate properties too (not knowing if you'll eventually need to carry for addition, or when to stop testing for equality), so I'm left wondering if some genius in the future will come up with a new way to build the numbers which are more satisfying.

Thank you for the Reddit link.

Gödel's Incompleteness Theorem places a limit on what you can prove within a formal system. Neither humans nor LLMs are a formal system, so it says nothing about them.

Someone's going to think that, since you can formally model computer programs (and thus formally model how an LLMs runs), that means that Gödel's Incompleteness Theorem applies to computer programs and to LLMs. But that's irrelevant; being model-able doesn't make something a formal system!

"Formal system" has a very technical meaning: it has a set of consistent axioms, and the ability to enumerate formal proofs using those axioms. For example, Zermelo-Fraenkel set theory is a formal system [1]. It has nine formal axioms, which you can see listed in its Wikipedia article. Utterly different kind of thing than humans or LLMs. Comparing an LLM to ZFC is like comparing a particular watermelon to the number 4.

[1] https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...

This is unnecessary nitpicking. You can easily derive a logical contradiction of your choice by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system. If a specific theorem doesn't prove that, a simple corollary will.

If you want to escape the limits of computability, you have to assume that the physical Church–Turing thesis is false. That the reality allows mechanisms that cannot be modeled formally or simulated on any currently plausible computer.

> by assuming that a system that can be formally modeled can prove something that cannot be proven within a formal system

Something that cannot be proven within which formal system? Every true statement can be proven by some formal system. No formal system can prove all true statements.

(This is all about Godel incompleteness. Turing incomputability does apply though, see the sibling comments! It's important to keep them separate, they're saying different things.)

While it's true that LLMs are not strictly a formal system, they do operate on Turing-complete hardware and software, and thus they are still subject to the broader limitations of computability theory, meaning they cannot escape fundamental constraints like undecidability or incompleteness when attempting formal reasoning.

LLMs don't do formal reasoning. Not in any sense. They don't do any kind of reasoning - they replay combinatorics of the reasoning that was encoded in their training data via "finding" the patterns in the relationships of the tokens at different scales and then applying those to the generation of some output triggered by the input.

That's irrelevant. They have an "input tape" and an "output tape" and whatever goes on inside the LLM could in principle be implemented in a TM (of course that wouldn't be efficient but that's besides the point).

I'm confused by this. Why are you talking about Gödel?

LLMs, like any model of computation, are subject to the limits of Turing Machines, so they cannot for example solve the halting problem.

Oof, I pattern matched OP to a different argument I've seen a lot. That's embarrassing.

Yes, that's correct, it's provably impossible to construct an LLM that, if you ask it "Will this program halt? <program>", answers correctly for all programs. Likewise humans, under the assumption that you can accurately simulate physics with a computer. (Note that QM isn't an obstacle, as you can emulate QM just fine with a classical computer with a mere exponential slowdown.)

Another excellent book is Tom Stuart's Understanding Computation : From Simple Machines to Impossible Programs - https://computationbook.com/

they never ran the program they claimed couldn’t exist ??

Also, why directly run the programs? What about running them with a wrapper program that crashes em if they invert the output of their input?

All this undecidability stuff reads like regurgitated hokum to justify giving up on a problem just because a single oversimplified case can’t be solved for all pathological inputs in a particular way (without bothering to look for a workaround)

I don't at all understand where your confusion lies, but be assured that undecidability/noncomputability isn't "hokum". It's probably "regurgitated" in the sense that this is covered in about every "intro CS" textbook, lecture, etc. because it forms the basis of theoretical CS.

Reply on news.ycombinator.com