39
$\begingroup$

Uncomputable functions: Intro

The last month I have been going down the rabbit hole of googology (mathematical study of large numbers) in my free time. I am still trying to wrap my head around the seeming paradox of the existence of natural numbers that are well-defined but uncomputable (in the sense that it has been proven that they can never be calculated by a human / a Turing machine). Let me give two of the most famous examples:

Busy beaver function $\Sigma(n,m)$

$\Sigma(n,m)$ "is defined as the maximum number of non-blank symbols that can be written (in the finished tape) with an $n$-state, $m$-color halting Turing machine starting from a blank tape before halting." It has been shown that $\Sigma$ grows faster than all computable functions and, thus, is uncomputable. Calculating $\Sigma$ for sufficiently large inputs would require an oracle Turing machine as it would literally be a solution to the halting problem. Thus, it is uncomputable, although the forumlation of $\Sigma$ in set theory is precise and clear. More details here.

Rayo's number $\text{Rayo}\left(10^{100}\right)$

Rayo's number was the record holder in the googology community for a long time and it is defined as "the smallest positive integer bigger than any finite positive integer named by an expression in the language of first-order set theory with googol symbols or less." It is defined in the language of an (unspecified) second-order set theory here. (Its well-definedness is thusly a bit controversial but it would outgrow $\Sigma$ by a huge marigin if resolved.)

My mathematical / existential questions

  • Does a number like $x=\Sigma\left(10^{100},10^{100}\right)$ "exist" in set theory in the same sense like the number $4$? Does it even make sense to include it in a mathematical operation like $(x$ mod $4)$ or $x^x$ if we cannot even write it down in a decimal expansion?

  • I am well aware of Gödel's incompleteness theorems and the existence of unprovable statements like the continuum hypothesis, which can neither be proven nor disproven by ZFC axioms in any finite number of steps. Is there some parallel between that and the existence of numbers that cannot be computed in any finite amount of time?

  • Is there some version of mathematics or system of axioms which resolves this problem? (i.e. where well-definedness of an object is equivalent to computability?)

I would be very happy if anyone could answer or point me in the right direction.

$\endgroup$
13
  • 16
    $\begingroup$ "Does it make sense to include it in a mathematical operation like $(x\text{mod}4)$?" I can tell you that Graham's number ends in a 7. $\endgroup$
    – JMoravitz
    Dec 2, 2021 at 19:24
  • 16
    $\begingroup$ @Andreas take any non-computable integer, multiply it by 10 and add 7. That number will end in a 7 and remains non-computable. $\endgroup$
    – Snaw
    Dec 2, 2021 at 19:29
  • 6
    $\begingroup$ Uncomputable numbers must be transcendental. Usually "computable" means "turing-computable" $\endgroup$
    – Peter
    Dec 2, 2021 at 19:31
  • 4
    $\begingroup$ A function is called uncomputable if there is no algorithm to compute it for every possible input. $\endgroup$
    – Peter
    Dec 2, 2021 at 19:35
  • 11
    $\begingroup$ You may be interested in some work in ultrafinitism, such as Vladimir Yu. Sazonov's "On Feasible Numbers". Here the premise is to show that a system of arithmetic, plus the axiom that "$2^{1000}$ doesn't exist" has a shortest proof of contradiction of a particularly large size (specifically too large to actually write down in the known physical universe). $\endgroup$
    – TomKern
    Dec 2, 2021 at 20:40

6 Answers 6

33
$\begingroup$

Replying to your three mathematical/existential questions in order:

  • Yes. There exists a TM that, when started on a blank tape, eventually halts (after finitely many steps) with the exact decimal expansion of $x=\Sigma\left(10^{100},10^{100}\right)$ on the tape. The same is true for $x\bmod 4$ or $x^x$ or any other natural number.
  • There does not exist a natural number "that cannot be computed in any finite amount of time".
  • There is no such problem for natural numbers.

On the other hand, provability is another kettle o' fish: There is no natural number $n$ such that ZFC proves $\ BB(7918)=n,$ and more recently we have that for any $m\ge 748,$ there is no natural number $n$ such that ZFC proves $BB(m)=n.$ (Here $BB$ is the Busy Beaver function w.r.t. the number of steps taken before halting.)


NB: As your questions (and your entire Intro) seemed to be about natural numbers, that is the context of my replies above. The situation is quite different in the larger context of real numbers. Note that every natural number has a finite representation, which is the basic reason it is computable. In contrast, a real number typically requires an infinite representation, which opens the possibility of not being computable. (It turns out that almost all reals are not computable.)

$\endgroup$
12
  • 1
    $\begingroup$ This answer makes it sound like every number is computable. This is incorrect - every natural number is computable, but uncomputable numbers are a thing. So even though there is an inaccuracy in the question, the core of the question is completely valid and should be answered. $\endgroup$
    – Vincent
    Dec 3, 2021 at 12:52
  • 9
    $\begingroup$ @Andreas No consistent computable axiomatization of $\mathsf{ZFC}$ can assign a value to every formula defining a natural number. However, Turing machines can't do so either! Note that when we say (something like) "The number which is $\Sigma(10^{100},10^{100})$ is computed by Turing machine $T$" we just mean that $T$ produces a number which happens to be the number named by $\Sigma(10^{100},10^{100})$; in no way is $T$ required to "interact with" (or "analyze," or "understand," or etc.) $\Sigma$ at all. $\endgroup$ Dec 3, 2021 at 16:17
  • 11
    $\begingroup$ It might help to consider a less loaded example: let $n=0$ if alien life exists in our galaxy and $n=1$ otherwise. Then $n$ is definitely computable, and I can build a pair of Turing machines one of which computes $n$ - but neither machine is particularly powerful. It's not that (reasonable) theories are less powerful than Turing machines, it's that you're asking for less from machines than theories. E.g. the first sentence of my previous comment is equivalently (roughly, more-or-less, ...) saying that no Turing machine can "reasonably" assign values to all number-defining expressions. $\endgroup$ Dec 3, 2021 at 16:18
  • 5
    $\begingroup$ @EricDuminil Given any $n$ and $m$, there's at least one TM specialized to that specific pair of $n$ and $m$ that outputs the value of $\sum(n,m)$ after finitely many steps. However, the method used to arrive at that number is at best "do some math if $n$ and $m$ are "easy" values, otherwise take a random guess (and get lucky that we picked a TM that guesses right)". What's not possible, is to have one single single TM that you can give any $n$ and $m$ and always get the correct value for $\sum(n,m)$. Nor can you have a TM that tells you which other TM guesses $\sum(n,m)$ correctly. $\endgroup$ Dec 4, 2021 at 19:49
  • 2
    $\begingroup$ @EricDuminil Essentially, yes. Though, there's still things we can do beyond throwing up our hands and admitting defeat. For instance, if we define $A_k$ to be the result of dovetailing together the relevant busy beaver candidates, running them each for $k$ steps, and outputting the length of the longest one that's halted, then $\lim_{k\to\infty} A_k = \sum(n,m)$, even though each individual $A_k$ is computable in finite time. We just can never prove we've picked a large enough $k$ for the limit to have converged. $\endgroup$ Dec 5, 2021 at 16:52
17
$\begingroup$

My view is that questions such as these arise from a failure to distinguish between intension (a description of a thing, an arithmetic expression, program source code, etc.) and extension (the thing described, the result of evaluating the expression, the observable behaviour of the compiled program, etc.). Maybe the following "theorem" will throw the difference into sharp relief.

Theorem. Every natural number is computable.

Proof. We must show that for every natural number $n$, there is a Turing machine whose output is (say) a unary representation of $n$. We proceed by induction. There is certainly a Turing machine whose output is empty, i.e. a representation of $0$. If we have a Turing machine whose output is a unary representation of $n$ it is clear that we can modify it to output just one more unit, so as to obtain a unary representation of $n + 1$. Hence every natural number is indeed computable. ◼

There is nothing wrong with the proof above, but nonetheless you may feel unable to accept the conclusion. The only way out is to conclude that there is a problem with the interpretation of the statement of the theorem. What this is actually proving is that every natural-number-in-extension is computable. This proof has nothing to do with natural-numbers-in-intension.

In order to say anything mathematically rigorous about natural-numbers-in-intension we must first choose a mathematical model for "describing natural numbers". Unfortunately, there is no canonical choice, and different choices have different expressive power. If you choose to define "description of a natural number" as "Turing machine that computes it", then tautologically every natural-number-in-intension is computable. But you could also choose to define it as "formula $\phi$ in the language of set theory with at least one free variable $n$ such that ZFC proves $\exists ! n \in \mathbb{N} . \phi$". In this case it is true that not every natural-number-in-intension is computable – or, to put it another way, there is no procedure (computable or otherwise!) that will convert the formula $\phi$ into a Turing machine that (ZFC proves) computes the unique natural number that $\phi$ describes.

$\endgroup$
9
$\begingroup$

I think this set of questions and direction of inquiry is one of the more interesting in philosophy and foundations of mathematics! I’ll answer your last question first: there are a variety of systems of mathematics which in various ways attempt to address the question of only allowing computable objects to exist. One good example is the subsystem of second order arithmetic $RCA_0$, which stands for the Recursive Comprehension Axiom. This axiom set is much weaker than say, Peano Arithmetic, and is one attempt at capturing the notion of “computable arithmetic”. From a computational perspective, it has many nice properties, such as the fact that any set which can be proven to exist in $RCA_0$ has a membership testing computer program, and indeed such a program can more or less be mechanically reconstructed from the proof of existence (this is more or less the Curry-Howard correspondence, see Wikipedia and this bit of Wikibooks Haskell for more).

You can also do a subset of everyday mathematics in $RCA_0$, such as proving the intermediate value theorem, the existence of algebraic closures of fields, Godel’s soundness theorem for first order logic and (a weak version of the) completeness theorem for the same. However, many mathematical statements of interest turn out not to hold in $RCA_0$, for example it is not the case that every bounded, increasing sequence of real numbers has an upper bound - precisely because there exists computable sequences of real numbers whose upper bounds are uncomputable! One example of such a sequence is a sequence of lower bounds on Chaitin's halting probability. As a result, doing mathematics in $RCA_0$ is not very nice in various ways, or at least it is a very different mathematical world than the one most pure mathematicians are used to.

For more on $RCA_0$, see for example Subsystems of Second Order Arithmetic by Stephen G. Simpson. The project of computable foundations of mathematics, for various definitions of the word computable, is a wide-ranging one, too large to include everything of relevance here. Keywords that might be helpful here include “constructivism”, eg Bishops Foundations of Constructive Analysis, “recursive analysis” and “recursive counterexamples”, and dependent type theory as is used in the programming languages Idris and LEAN.

To your second question, yes, the relation between statements that are independent of a set of axioms and numbers that cannot be computed is strong both intuitively and formally. The classic example of a statement that is independent of, say, ZFC, is that ZFC is consistent, which we’ll denote as $Con(ZFC)$. But $Con(ZFC)$ is equivalent to a statement about a particular computer program: “the computer program which searches over all the proofs in ZFC and halts upon finding a contradiction does not halt”. That in turn, is related to (among other uncomputable functions), the busy beaver function. In particular, suppose “the computer program which searches over all the proofs in ZFC and halts upon finding a contradiction” is a Turing machine with $X$ states. Then any proposition about the value of $\Sigma(X)$ implies either $Con(ZFC)$ or $\neg Con(ZFC)$, but as we know ZFC proves neither of those propositions, ZFC cannot prove $\Sigma(X)$ is equal to some specific finite value.

There is a subtlety here, as is partially addressed by r.e.s.’s answer: ZFC does prove the superficially-related statement “there exists some Turing machine which outputs $\Sigma(X)$”. But this is in some sense trivial, because ZFC proves the statements “there exists a Turing machine which outputs 1” and “there exists a Turing machine which outputs 2” and so forth, which lets it prove “for all natural numbers $n$, there exists a turning machine which outputs n”. Combined with the also-trivial statement “$\Sigma(X)$ is a natural number”, we of course now obtain “there exists some Turing machine which outputs $\Sigma(X)$”, but this sentence can now be seen to be not capturing what it might seem to mean. We don’t just want to know one of the Turing machines in the world outputs the number we’re looking for, we want to know which one, and there ZFC cannot help us. Indeed, any axiom system which is recursively enumerable (there exists a computer program which will print all of the possibly-infinite set of axioms) will eventually not prove $\Sigma(Y)$ for a sufficiently large Y, by the same argument given above.

For Adam Yedidia and Scott Aaronson’s proof that the value for Y in ZFC is at most 8000 (later reduced to 748), see A Relatively Small Turing Machine Whose Behavior Is Independentof Set Theory and Aaronson's blog post about it. For more on the busy beaver function and how it relates to the foundations of mathematics see Aaronson's The Busy Beaver Frontier.

I left your first question last because it is in some sense the thorniest and most philosophical. For example, it’s certainly true that ZFC (and indeed PA, and other quite weak systems of mathematics) prove the statement $$\Sigma(10^{100}, 10^{100}) \in \mathbb{N}$$ But I get the sense that’s not really what you’re asking. There is something philosophically uncomfortable about a number being proven to exist, but not being proven to have any specific value, which is one instance of the broader phenomenon of “non-constructive proofs”.

Different people have different reactions to this philosophical point. For example, the entire field of constructive mathematics is largely predicated on “we shouldn’t have numbers and more generally mathematical objects that are proven to exist, but not actually constructed”, for different formalizations of what exactly “constructed” means. Most mathematicians, on the other hand, either haven’t thought about this, don’t worry about this too much, or accept that they are working with objects that are (sometimes) fundamentally different from the ones which are computable. Two reasons to think that last idea isn’t too crazy: first, mathematics is always about figuring out unknown things. If I defined a number $Q$ via $Q = 1$ if $P \not= NP$ else $Q = 0$, then we also don’t have any good way to prove what the value of $Q$ is, even though most mathematicians think that ZFC proves that $Q=1$, and certainly that the value of $Q$ is not independent of ZFC. Second, this is more fuzzy, but a lot of mathematics relies on objects which at least intuitively aren’t computable, eg real numbers. The idea of an continuum of real numbers, which extends infinitely far in both directions and has no “gaps” is in some sense a very intuitive one, and doesn’t really accord very well with my picture of what things a computer can actually handle! You can encode real numbers as Cauchy sequences, (some of) which are representable as finite computer programs, but I certainly am not thinking most of the time about some computer program shuffling around (finite representations of) Cauchy sequences when I think about theorems like “every monotonically increasing sequence of real numbers has a least upper bound”.

Finally, though this answer has already grown very long, it probably wouldn’t be complete without at least a bit of a mention of one more philosophical point: formalism versus platonism. Briefly, formalism says “everything a mathematician does is encoded in the symbols, math is all about the formal derivation of theorems from axioms via proofs”, while platonism says “"mathematical objects really exist in some sense, there is some 'true actual' thing you mean when you say 'natural number', beyond the fact that your proofs about natural numbers correspond to symbols on a page which follow the mathematical rules of proof". This philosophical divide relates to our discussion above because (as far as I can tell) a formalist would say that there isn’t really a ‘fact of the matter’ about the value of $\Sigma(1000)$, or any other value of $\Sigma$ for that matter. There’s only the fact that ZFC proves $\Sigma(3)=6$, and ZFC doesn’t prove any value for $\Sigma(1000)$. While a platonist would say $\Sigma(3)$ really is 6, when I define a “natural number” and a computer programs and so on there is a real thing that I mean by that, they aren’t just symbols. Similarly, there is some true value of $\Sigma(1000)$, if you give me some particular computer program, if I ran it on my laptop it just would halt or wouldn’t halt, ZFC can’t prove that for all the programs, sure, but that doesn’t mean it isn’t true or false.

One reason to think this latter position makes sense is that there is only one axiom of the form $\Sigma(X)=n$, where $n$ is a decimal expansion of a natural number, that is consistent with ZFC (assuming ZFC is consistent). This is compatible with the fact that the value of $\Sigma(1000)$ is independent of ZFC because that simply guarantees (via Godel’s completeness theorem) there are two axioms that are both consistent with ZFC: $\Sigma(1000)=n$ and $\Sigma(1000) \not = n$, for some explicitly written out natural number $n$. Good luck figuring out what the relevant $n$ is though!

$\endgroup$
6
  • $\begingroup$ Thank you so much for the super detailed answer! This all gives me the idea for a weird metaphysical thought experiment: Suppose Bob lives on Earth and has access to arbitrarily much computing power. Then Bob can create a finite Turing machine $T$ that will calculate a number as specified by $x=\Sigma\left(10^{100},10^{100}\right)$ (even though ZFC cannot prove that this is the natural number named by $\Sigma\left(10^{100},10^{100}\right)$, many people under this post have pointed out that this should be possible as $T$ simply runs an algorithm without "understanding" it). [To be Continued] $\endgroup$
    – Andreas
    Dec 4, 2021 at 8:53
  • $\begingroup$ Then we can use $x$ to run Turing machine $Z$ for $x$ steps from the paper you linked (A Relatively Small Turing Machine Whose Behavior Is Independent of ZFC) and, thus, determine if ZFC is consistent. This does not really prove anything within ZFC of course, but it shows us on a metaphysical level whether we can expect to ever find an inconsistency within ZFC or not. (This does not violate Gödel's second incompleteness theorem as it is not a proof within ZFC, but it still blows my mind and feels kind of "hacky" / unexpected to me.) $\endgroup$
    – Andreas
    Dec 4, 2021 at 8:57
  • 1
    $\begingroup$ +1, very nice answer! One quibble: you write "it is not the case [in RCAₒ] that every increasing sequence of real numbers has an upper bound", but that's also true in the standard reals; and later "theorems like 'every monotonically increasing sequence of real numbers has a least upper bound'", which is not true in the standard reals. I think you mean "it is not the case [in RCAₒ] that every bounded, increasing sequence of real numbers has a least upper bound" and "theorems like 'every bounded, monotonically increasing sequence of real numbers has a least upper bound'". $\endgroup$
    – ruakh
    Dec 4, 2021 at 23:14
  • 1
    $\begingroup$ Thanks for the errata, I fixed that and one other thing ("I left your first question last" originally said "last question"). $\endgroup$
    – zzyxxian
    Dec 5, 2021 at 2:13
  • 1
    $\begingroup$ To @Andreas, unfortunately, no, that's not possible even with unlimited compute. I touched on this in the section "There is a subtlety here", but though there does exist a machine which calculates that number, we have no idea what machine it is! ZFC is completely silent on this question, and I don't think any other person or axiomatic system has any idea what that machine is either. A more powerful axiom system could create such a proof, but that's just saying "if we knew what the value of $Sigma(10000)$ was already so we could assume it as an axiom, we'd be good". $\endgroup$
    – zzyxxian
    Dec 5, 2021 at 2:18
6
$\begingroup$

Is there some version of mathematics or system of axioms which resolves this problem? (i.e. where well-definedness of an object is equivalent to computability?)

There is a philosophy of mathematics known as constructivism which asserts that mathematical objects only exist if they can be constructed explicitly. "Well-defined" isn't really the right term here, we should stick with "exists", but in principle this should be the answer you're looking for. Quoth Wikipedia:

If, for instance, the algorithmic view is taken, then the reals as constructed here are essentially what classically would be called the computable numbers.

$\endgroup$
3
$\begingroup$

For the question you ask, it is simply not the case as long as you have a good definition of "well-defined". If you can write a way of computing the desired number on a piece of paper (and supposing that you prove that your definition imply that it is unique), then you can also write some code that compute it with the desired precision and this defined your turing machine. So actually I would say that well-defined and computable are two synonyms.

$\endgroup$
4
  • $\begingroup$ I see now that my question was ill-formulated. I had previously heard of statements like "ZFC cannot prove $\Sigma(n,m) = x$" for any $x\in\mathbb N$ for sufficiently large $n,m\in\mathbb N$ (see this post linked by r.e.s.) and wrongly concluded that this made certain natural numbers "uncomputable". So my question should rather have been: "In what sense does a number exist if its value is unprovable? And why is ZFC "weaker" in that sense than a TM?" $\endgroup$
    – Andreas
    Dec 3, 2021 at 13:20
  • 2
    $\begingroup$ Regardless of computing model, writing down a number's "definition" on paper will involve a finite (but unbounded) sequence of symbols from a finite alphabet, and thus there are only a countably infinite number of numbers that can be "defined". So almost all real numbers can't be. $\endgroup$
    – Dan
    Dec 3, 2021 at 16:11
  • $\begingroup$ @Dan If we consider that this piece of paper is inside the observable universe, and that this universe is finite, doesn't it mean that the sequence of symbols is bounded, and only a finite (but extremely large) number of reals could be described on a piece of paper? $\endgroup$ Dec 4, 2021 at 20:32
  • 1
    $\begingroup$ @EricDuminil, exactly ! The problem is that you can transform any finite (or even countable infinite actually) set of symbols on a sheet of paper into a natural number and thus there is only a countable number of such descriptions. And there is such only a countable number of computable reals, which is really small given the number of reals. My personal (and more philosophical) problem, is that I suspect that when I try to represent a number in my mind, I only have access to computable numbers, otherwise it is just a shadowy "real number" that I will never think again. $\endgroup$
    – HeMath
    Dec 6, 2021 at 12:13
1
$\begingroup$

I'm going to gently push back on r.e.s's answer and provide an alternative perspective, where these doubts you are having are actually justified.

Indeed, instead of set theory meaning ZFC with classical logic, let's work in Intuitionistic Logic, with IZF rather than ZFC, which is pretty similar, except for Choice, which we don't really need when talking about Turing machines and natural numbers anyways.

Let's take a family of predicates $\Gamma(n, m)$ (say $\Gamma(n, m):=\Sigma(n, n) = m$ for example) and say that $\Gamma$ is a computable number if there is a Turing Machine which takes as input $n$ and returns $m$ such that $\Gamma(n, m)$ holds.

Now let's answer your 3 questions again:

  1. In IZF, the number 4 (and most numbers you can compute) can be proven to exist. However, $\Sigma(n, n)$ in general cannot: indeed you'd need to prove that either an arbitrary TM must run forever, or halts after some definite number of steps. You really need the excluded middle for that.

  2. The existence of any "uncomputable" number in this sense will imply the incompleteness theorem pretty straightforwardly: if arithmetic was complete, you could compute any number by enumerating all the proofs and stopping as soon as you had, say a proof of $\Gamma(\overline{n},\overline{m})$ (which you must eventually find in a complete theory, if such an $m$ exists).

  3. One can show (assuming some standard and necessary consistency statements) that if $IZF \vdash \forall n\exists m, \Gamma(n,m)$ then indeed, there is a computable function $f$ such that for each numeral $k$, $IZF\vdash \Gamma(\overline{k},\overline{f(k)})$, a property which does not hold for ZFC, as you have noted. It's worth noting that the converse cannot possibly hold: there must always be some computable function $g$ such that there is no predicate $P$ with $IZF\vdash \forall n\exists m, P(n, m)$, and $P(k, l)$ holds exactly when $l = g(k)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.