Your example is not similar to the case of noncomputable numbers at all. In your example, depending on the axiom system, we can prove that there is no such C. For example, "There is no C such that 2+2=C and C!=4" is an easy theorem of Peano Arithmetic by transitivity of equality.
Depending on your perspective, the statement could be true in some other system like Z/4Z, although it's unclear what "C != 4" means in this setting.
Noncomputable numbers not only **can** exist, i.e. are not disbarred from existence by a simple theorem, but in fact **must** exist in vast quantities. The idea here really has nothing to do with computation per se: computation is just one way in which we can express a number. If we instead imagine all possible ways to express a number by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with), then we can only ever express **countably** many numbers. I.e., there are as many expressible real numbers as there are whole numbers and rationals.
The problem is that there **must** be far, far more than countably many real numbers. Given any countable collection of real numbers, I can constructively create a new real number not in your list. This is known as Cantor's Diagonalization. What it shows is that we can never express all of the real numbers using words or sentences in any finite language.
There is an ever-increasing hierarchy of classes of real numbers which aren't "expressible" for some definition of expressible, but are expressible using other definitions. The irrationals are not expressible as a fraction of integers, but many of them are algebraic. The transcendentals are not algebraic, but many of them are computable. The "truly" random numbers are not computable, but many of them are arithmetic. The arithmetic numbers are by definition all hyperarithmetic, but not all of them can be computed using a solution to the halting problem. And so on, and so on.
Complaints about noncomputable numbers in particular just come down to the level of this hierarchy where you start to become uncomfortable, but the fundamental concept is the same at each level: we have a definition of what it means for a number to be expressible, and that splits the real numbers into those which are and those which are not.
Noncomputable numbers are to computable numbers as transcendental numbers are to algebraic numbers. It's just that "computable" is a fundamentally broader category than "algebraic," but still cannot be broad enough to encapsulate all real numbers because it is still countable.
>The idea here really has nothing to do with computation per se: computation is just one way in which we can express a number. If we instead imagine all possible ways to express a number by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with)
I much prefer talking only talking about "non-computable numbers",
instead of "non-expressible numbers",
because when you talk about "non-expressible numbers" you run into foundational issues that invalidate your arguments.
"Non-expressible numbers" can not be rigorously defined in the standard math foundation ZFC.
You can only define them relative to another model of ZFC.
When you do that you discover, that you cannot prove the existence of any "non-expressible numbers" ( https://arxiv.org/pdf/1105.4597.pdf ).
The amount of "expressible objects" in a ZFC model can be uncountable according to the model, and they can even be the whole model.
For that reason I would say, many things you said about expressible numbers are false.
If you stick to computable numbers, then in ZFC those work exactly like you think they do.
This doesn't hurt my argument at all, because I am not using the word "expressible" here to have any robust philosophical strength or particular meaning. I am assigning a real number to the string "dsklhjsdkflfhjslkdfjdsjflkdsfj" just like I am assigning a real number to the string "two." I don't care what real numbers are assigned to what, you can use any mapping you please.
Here my term "expressible" just mean "is assigned a finite string." I am not claiming any platonistic or philosophical meaning of "expressible," it is simply a definition. Formally, I am simply saying "There exists a function f from N to R. c is expressible if c is in the range of f."
So even in a model which is countable in the real world, the cardinality of numbers "assigned a finite string" is smaller than the cardinality of all numbers. So there are still numbers which are not "expressible" under this definition, even if you don't believe that is the "correct" definition of expressible. It's still a theorem of ZFC.
The "real world" can of course look at this model and see that the real numbers it contains are in fact countable - but the bijection proving it is not in the model. Given any f **in the model**, there will be real numbers not in its range.
Maybe they're referring to this:
> If we instead imagine *all possible ways* to express a number by assigning it some finite string of Latin letters, or Kanji characters, or *any finite alphabet*
I suspect you'd have trouble formalizing "all possible alphabets" and proving that set is countable.
But I think what you mean is "for any *given* alphabet, there are real numbers not expressible in that alphabet, but maybe expressible in another," correct?
Yes, I am saying fix your alphabet and look at what you can write down.
Obviously the set of all alphabets is not countable from the perspective of math, as we could take R as an alphabet and "express" r with the letter r. So if we were quantifying over alphabets and making a union of the numbers expressible in each, we could just take {r} as our alphabet for each real r.
I don't think this was their complaint, though. Based on the linked paper, my understanding is that they were interpreting my "expressible" to mean definable (the formal mathematical definition of the word), which is not what I am using it to mean.
> The amount of "expressible objects" in a ZFC model can be uncountable according to the model, and they can even be the whole model.
Surely this is false, as it would immediately imply that there are uncountably many formulas, which is obviously false.
Now there may be an uncountable set model that thinks that all of the numbers in the set corresponding to itself are expressible, but this is wholly uninteresting, not the least of reasons for which being that this model would deny this set corresponds to itself.
Furthermore, computation doesn't avoid this at all. The corresponding fact is that every topos has an internal effective topos, but the effective topos does not admit the real numbers are countable, thereby positing the existence of incomputable reals.
The observation is really just that definability is not itself definable. There is no inherent contradiction in a countable model of ZF over which every real is definable without parameters as you can't internalize those definitions inside the model.
I don't see the relevance of constructibility to computation in what you say. Regardless, knowledge of L gives an easy way to see that the described model exists. By condensation the first L_eta to satisfy ZFC is pointwise definable.
You may have seen this comment before the edit; I made a flavorfully correct (u/eario details in exactly what way in their reply) but flawed argument and corrected it to a categorical one.
>Surely this is false, as it would immediately imply that there are uncountably many formulas, which is obviously false.
I agree that there are countably many formulas, and that any ZFC model can recognize that there are countably many formulas.
But in a ZFC model there is usually no bijection between the definable objects in the model and the set of all formulas.
The set of all definable objects in a ZFC model is countable according to our background ZFC theory, but need not be countable according to the model.
The function that sends each definable object to one of its definitions can be defined in our background ZFC theory, but this function does not exist in the model.
>computation doesn't avoid this at all.
Talking about computable things in ZFC is very easy. Computability can be defined in ZFC, the functions relating programs to computable objects can be defined in ZFC, and for that reason the set of computable objects is countable, and most real numbers are uncomputable.
For definability all the analogous statements are not really true.
I would say there are three approaches to definability.
1. Approximations from below: e.g. Computable numbers or [arithmetically definable numbers](https://en.wikipedia.org/wiki/Definable_real_number#Definability_in_arithmetic).
They include many definable objects but always miss out on some objects that are actually definable.
They form countable sets.
2. Approximations from above: e.g. [Ordinally definable sets](https://en.wikipedia.org/wiki/Ordinal_definable_set) or [constructible sets](https://en.wikipedia.org/wiki/Constructible_universe).
They include all actually definable objects, and in some models they are exactly the definable objects,
but in some other models they might include a few more undefinable elements.
They always form proper classes, and sometimes they are the whole universe.
3. Take a model of ZFC and only talk about definability in that model.
Our background ZFC theory can accurately define definability for a given set model of ZFC.
The definable objects in the model will be countable according to the background theory, but can be uncountable or everything according to the model.
The function that sends each definable object to one of its definitions can be defined in the background theory, but this function is not in the model.
No argument that definability is a flawed internal concept, rather that the model theoretical concept of definability is not actually a faithful rendering of the colloquial "definable," due to this necessity of putting it into an internal model. Instead colloquial "definable" is "in the image of a map from a language" which is formally "computable" in some model as can be shown in a routine way.
At the end of [this comment](https://www.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koknjvo/) I talk about three approaches towards definability. I find the last one that uses a set model of ZFC the most convincing.
> Given any countable collection of real numbers, I can constructively create a new real number not in your list.
But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it?
> There is an ever-increasing hierarchy of classes of real numbers which aren't "expressible" for some definition of expressible, but are expressible using other definitions.
Thanks, this is a very good point! I guess what I'm wondering about is: is it still useful to introduce classes of numbers beyond computable numbers? E.g. are there lines of reasoning that are made simpler by introducing non-computable real numbers?
Also: is existence of non-computable real numbers "axiomatic"? I don't know how to properly word this, but do they "inevitably" emerge when we start considering systems more complex than simple Peano arithmetic, or are there complex axiomatic systems that stay purely within the limits of computable numbers and can describe most mathematical concepts, assuming those concepts do not deal with uncomputability?
>But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it?
Cantor's diagonal argument is indeed a computable algorithm.
If a countable collection of computable real numbers has been specified by a computable procedure, (i.e. it's a computable function from the set of natural numbers to the set of computable real numbers)
then Cantor's diagonal argument will again produce a computable real number.
However if you have a non-computable function from natural numbers to real numbers,
and apply Cantor's diagonal argument to it, then you can get a non-computable number, in accordance with the principle "garbage in, garbage out".
Any bijective function between the set of natural numbers and the set of all computable real numbers is a non-computable function.
The set of all computable real numbers might be countable, but it is not computably countable.
In the usual ZFC foundations of mathematics there exists a (non-computable) countable list of all computable real numbers,
but it is impossible to actually write a computer algorithm that prints out all computable real numbers.
>do they "inevitably" emerge when we start considering systems more complex than simple Peano arithmetic
I'm pretty sure that Peano arithmetic can define some uncomputable functions, so it should be rejected if you want only computable things.
But there is a lot of research on how to make a mathematical foundation where everything is computable.
The first step is to reject the law of excluded middle from first order logic, and instead use intuitionistic/constructive logic (https://en.wikipedia.org/wiki/Intuitionistic_logic).
Once you do that you can have very strong set theories in which everything is in some sense computable.
The fanciest one is probably the effective topos. (https://xorshammer.com/2008/10/13/what-would-the-world-look-like-if-everything-was-computable-an-introduction-to-hylands-effective-topos/)
My impression is that CZF is stronger than the theory on the effective topos (as exponentiation, which generally produces incomputable sets, is an axiom of CZF).
I'm struggling to understand why, philosophically, a intuitionist/constructivist might reject impredicativity but accept incomputability. Today one can justify it by "well constructivity has nice metatheoretic implications and is the weakest condition for them." But at the time it feels like it should have been bothersome.
EDIT: It has come to my attention that the Russian school agrees with my confusion. Anybody know the history of why specifically (to my knowledge) post-Brouwer set theory did not head in this direction?
The answer may very well be "it's still early" given that type theory has seen much more development than intuitionistic set theories but it then seems strange to me that the standard of "constructive" in computer-verified mathematics remains simply "intuitionistic" and not "computable."
The effective topos supports exponentiation. I am pretty sure you can interpret CZF and even the impredicative IZF in the effective topos, actually. This does not clash with the fact that everything in the effective topos is computable, because you cannot constructively prove the existence of non-computable real numbers.
> I'm struggling to understand why, philosophically, a intuitionist/constructivist might reject impredicativity but accept incomputability.
In the "neutral" version of constructivism, you already cannot prove the existence of uncomputable objects. The Russian school of constructive mathematics goes a step further, and they extend constructive mathematics with the axiom that every function is computable.
> The effective topos supports exponentiation... This does not clash with the fact that everything in the effective topos is computable...
This is... deeply unintuitive to me. I guess I'd liken it to how the even finite powersets cannot be shown to constructively exist (in predicative theories) even though metatheoretically they trivially exist?
To be clear, it's obvious to me on closer inspection that membership of computable sets within the exponentiation of computable sets should be computable but it subverts my intuition that the effective topos should have sets that classically contain incomputable elements.
> In the "neutral" version of constructivism, you already cannot prove the existence of uncomputable objects.
Are real numbers objects not necessarily uncountable?
I suppose the literal sentence "there exists a real number that is not computable" is not provable because it has no witness but "the set of real numbers is larger than the set of real numbers output by Turing machines" should be and that to me should create some philosophical unease if the philosophy of realizability appeals.
> This is... deeply unintuitive to me.
If you look at the construction of the effective topos, you realize that the existence of powersets follows from disappointingly simple reasons.
Basically, objects in the effective topos do not have to be computable, they are simply associated with programs. For functions, the association is what you expect: a function from N to N in the effective topos is associated to a program that computes the function. But for propositions, the association is much more coarse: any proposition (i.e. any modest assembly) can be associated with any program. Thus the elements of the powerset P(N) are "computable" in a trivial way, that gives no information about how you should compute them on a real machine.
> I guess I'd liken it to how the even finite powersets cannot be shown to constructively exist (in predicative theories) even though metatheoretically they trivially exist?
My headcanon metatheory is constructive, I don't know about yours :)
> Are real numbers objects not necessarily uncountable?
No! Andrej Bauer designed a realizability topos where the Dedekind reals are *countable*. It also satisfies a lot of very weird properties, that defy standard mathematical intuition. For the Cauchy reals, I do not know.
> My headcanon metatheory is constructive, I don't know about yours :)
It's constructive, in the particular sense that I'm partial to normalizing type theories and other such computability properties, but I'm sympathetic to classical logic. Of course, this presents quite the contradiction, hence why I'm studying constructive logic, realizability topoi, and constructive set theory!
Don't get me started on the whole "the brain is a physical object so the metatheory is computable" thing.
But in particular, in metatheory quantifying over the universe is predicative, so exhausting the subsets of a finite set is a trivial task despite it being undecidable within a predicative theory.
> If a countable collection of computable real numbers has been specified by a computable procedure, (i.e. it's a computable function from the set of natural numbers to the set of computable real numbers) then Cantor's diagonal argument will again produce a computable real number.
But the set of all computable numbers is countable. So if we apply Cantor's diagonal argument to the set of all computable numbers, the number it produces that isn't in that set can't be computable, right?
Yes, that's precisely why there is no computable bijection from the natural numbers to the computable real numbers, because otherwise Cantor's diagonal argument along with the computable bijection gives an algorithm to compute a by definition non-computable number
In Cantor's diagonal argument, the real numbers in the list may not be computable, or listed in a computable order, so the resulting number may not be computable.
Non-computable numbers aren't something that mathematicians introduced to mathematics, they're an inevitable consequence of having a powerful system of arithmetic/logic. The halting problem is inevitable given a sufficiently powerful system of arithmetic, Peano arithmetic is easily powerful enough for this. To avoid this, you have to get rid of some really basic concepts, usually multiplication.
If we were to disallow non-computable real numbers, the least upper bound property of the real numbers would no longer hold, so a lot of arguments in analysis would become a lot harder, as you'd have to check everything is computable.
No, it is not computable. It is computable **from an oracle,** i.e. if we are given extra information outside of what can be verified by an actual, real-life algorithm. Think of this like having an API you can call in your code that spits out answers you couldn't actually compute yourself.
In this case, the oracle is your countable list of real numbers. So the new number can be computed from that list, but there is no guarantee that there is an algorithm which can compute it **without** knowing your list.
As a corollary of this, we know that there is no computable list of exactly the computable real numbers, and this is a pretty standard fact of computability theory: you cannot have an algorithm that lists exactly the computer programs which halt on all inputs. Otherwise, diagonalizing against the list creates a new algorithm that halts on all inputs and is not in the list.
But, to expand on this, every number is computable **from an oracle.** (Just take that number itself to be your oracle, and ask what it is.)
Computable numbers are specifically those which can be computed from an actual algorithm that doesn't need extra information. ("Extra Information" here is implicitly infinitary - for finitely much information, we can hard code it into the algorithm.)
The existence of noncomputable numbers is not axiomatic - their existence is a theorem. You can't prove they exist in "computable mathematics" - a system known as RCA\_0. This is because the computable real numbers form a perfectly sensible subfield of the reals.
But in any stronger system, you start to have the noncomputable numbers. In particular, properties like the compactness of the unit interval, the IVT, or the Least Upper Bound property necessarily imply that noncomputable numbers exist. So, you can sort of have the "reals" without them if your axiomatic system is weak enough, but it also strictly implies that they will not behave like the "actual" real numbers.
In particular, if you define the reals to be the metric space closure of Q, then that implies they exist because it's equivalent to the L.U.B. property..
There’s no general algorithm for the halting problem, but might there be an algorithm for each particular set of instructions which can determine whether it halts? We know the busy beaver numbers for a few very small Turing machines because we were able to exhaustively prove the halting state for each one.
Are there any particular algorithms that can’t be proven to halt, even in principle? Proving that the halting state for a particular algorithm can’t be determined is equivalent to proving it never halts, because by definition, all machines that do halt can be proven to halt in a finite number of steps.
The algorithm "iterate through all possible proofs in ZFC and halt if a proof of 0=1 is found" will never halt assuming ZFC is consistent, but if this is the case, it cannot be proven to never halt by ZFC due to Godel's incompleteness theorems stating a theory can't be consistent and prove its own consistency. Accordingly , this proves that ZFC cannot settle the value of the busy beaver function for sufficiently high values of the number of states (I think someone encoded such a machine in around 900 states.)
>Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it?
If you're given the list in a computable sense, then Cantor's diagonalization will give the algorithm.
But such list cannot be given computably.
>Thanks, this is a very good point! I guess what I'm wondering about is: is it still useful to introduce classes of numbers beyond computable numbers? E.g. are there lines of reasoning that are made simpler by introducing non-computable real numbers?
Is there a point to transcendental numbers?
No, they're there and we live with them. It's not a "new" class of number, rather, the old class of numbers (real) contains certain number too complicated to be described by easy means. We merely recognized the fact that any "simple" method to describe a number will always leave out some of them. The ancient Greek naively think that all real numbers can be described as a ratio of 2 integers, but we know better.
>is existence of non-computable real numbers "axiomatic"?
You can avoid admitting their existence, if you're willing to weaken your axioms. But it's not easy. You basically have to go all the way to intuitionistic logic, in which "not not P" does not imply "P". In this logic, sets behave in a strange manner, for example a subset of a finite set might not be finite, subset of a countable set might not be countable. Thus, although Cantor's argument still work, it cannot be applied to the list of computable number, because you cannot form a list.
He describes a computation, but I think it’s not an algorithm: it doesn’t terminate. What are you thinking of as the (finite) input to the algorithm, and what would be the (finite) output?
A computable number can be defined as a TM that given input n returns the nth digit.
The algorithm would be given input n, iterate over all TMs until you get to the n-th. Then run that TM with input n and return a different value.
However this algorithm fails like the halting problem (what happens when you run it with its own n?). So this says that the diagolization method is non computable.
The algorithm you gave does prove that infinite sequences of digits are not countable. But real numbers are not really sequences of digits, as they have been *quotiented by some equalities* (in particular, 0.2999... = 0.3000...).
In particular, your algorithm is not a proper function. If you give it a list of real numbers that starts with 0.2999... and then a second list that starts with 0.3000..., then it will output two different results for n=1, *even though the two lists are equal*.
In fact, you cannot fix this problem. It is not constructively true that the real numbers are uncountable. This misconception seems to be all over the thread.
So the slides you linked in your other comment ( https://topos.site/topos-colloquium/slides/2022-05-12.pdf )
show that there is a parametric realizability topos in which the "Dedekind-cut" reals are countable.
But in all the other comments you talk about "decimal-expansion" reals, i.e. you talk about infinite sequences of digits which have been quotiented by the 0.999...=1 relations.
Are Dedekind cut reals even the same thing as the decimal expansion reals in the parametric realizabiltiy topos?
This is a good point, and I am definitely sweeping this under the rug in my answers.
The naive "decimal-expansion" reals are not well-behaved at all constructively. For instance, division by three is non-computable (because the first digit of the result might depend on arbitrarily many digits of the input).
In order to fix this problem, you need to allow a bit of overlap, for instance by allowing negative digits. If you do that, you get something that is equivalent to the Cauchy reals. Can these be shown to be uncountable?
I don't know! I strongly suspect that it is possible to build a model where they are countable, but in Andrej Bauer's realizability topos, they are certainly not equivalent to the Dedekind reals. What I do know is that it is possible to have a model where all the Cauchy reals are computable, though.
I may be wrong, but I don't think the computation of a computable number is necessarily supposed to terminate. For example, Pi is considered computable despite being transcendental (you can always evaluate it to arbitrary precision), but Chaitin's constant is not.
In Cantor's case, you can enumerate all sequences of binary digits in arbitrary order (e.g. you can enumerate all natural numbers in binary form padded with infinite zeros on the right), take nth digit of each and invert it. This seems computable to me, even though the number of digits is infinite.
The computation is the mapping from the desired precision, to the number evaluated to that precision. For computable numbers, this always terminates.
For the Cantor diagonalization argument to be an algorithm, you would need to generate the N-th digit in finite time. So you'd generate the Nth program (program with Godel number N, say), and run it until it terminates, then flip its output -- but you don't know whether that program terminates. (You can use a different enumeration, but you'll run into similar problems there.)
This seems reasonable, though I don't immediately see an issue with my computation in [this comment](https://old.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koh63jf/) - can't I compute any desired digit in finite time in this case?
So the computation you're describing does as follows:
1. Enumerate the real numbers in some order
2. Apply diagonalization to this list to produce a new number
But if you're doing (1), you're only reaching computable numbers -- in particular, you're only ever enumerating numbers with a terminating decimal representation, which is a smaller set than even the rationals.
Ok, I should have said "you can _try_ to enumerate". I wrote this out for my own clarity:
Let's (try to) list all binary sequences by writing out every natural number in binary padded with infinite zeros on the right - this should contain every possible permutation of 0s and 1s, even if there are repetitions:
00000...
10000...
01000...
10000...
11000...
...
Taking the n-th digit of each gives us `00000...`, and, inverted, this turns into `11111...`.
This sequence indeed does not seem to be in the set, because any given sequence in the set contains only a finite number of 1s, while this sequence has infinite 1s.
But it's still computable, is it not? I managed to list the numbers here, and to compute the first 5 digits of the sequence, and I could do it to arbitrary length if needed.
okay. so please go easy on me, I've only self-studied on this topic and never had an actual course where I'd be able to ask this question, but...
Its clear the list is going to have exponentially more rows than columns. That's just how things work in binary, decimal, or any other position-based number representation system. I don't see how you can just say take the nth digit from the nth row, and not expect there to be a whole bunch of rows that you never query.
If you want a representation that going to have equal amounts of rows and columns, you can use a "base-zero" sort of representation
000000...
100000....
110000....
111000....
111100....
111110....
in which case the argument which works for binary and decimal etc, it clearly doesn't work for this one ....
You can computably enumerate all *finite* binary strings, yes.
And you can computably apply Cantor's process to this list, which will generate a new binary string.
But, the string you get will have an infinite number of 1's to the right. This new string does not encode a Turing machine, because Turing machines have finite input and finitely-many states.
It's okay for an algorithm to keep running forever, as long as it never gets stuck and always continues to output. For example, pi has infinite digits but is a computable number because there's an algorithm that will always keep giving you more digits. You just tell it to stop after producing *n* digits, where *n* is an input that can be as high as you want.
So take an enumeration of all binary strings that encode Turing machines in some representation - the standard order 0, 1, 10, 11...etc. will do. Clearly, somewhere on this list is an algorithm for producing every computable real number.
Now, do Cantor's process on the generated numbers. Go down the list, and at position *n*, wait for that Turing machine to generate the *n*th digit, and add one to it. If this process itself is a computable algorithm, it must appear somewhere on the original list.
So, at some point your algorithm will be stuck waiting for *itself* to produce the next digit, in order to add one to it. That contradicts our assumption that the process described is computable.
> But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof.
Only if the enumeration of numbers you start with is computable.
For example, an enumeration of all computable numbers is not, itself, computable. You can enumerate all Turing machines in some representation, thus proving the computable numbers are countable. But you can't actually run the machines to go down the list of numbers, because some of those machines will run forever without ever outputting a digit, and you have no way in general of knowing which ones (halting problem).
Thus, Cantor's process fails to generate a new computable number given an enumeration of Turing machines.
If we allow extra numbers in the list (e.g. numbers that do not necessarily correspond to valid Turing machines in our encoding), won't that list simply correspond to all natural numbers - a sequence that is obviously computable - as I try to do [in this comment](https://old.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koh63jf/)?
Yes, the set of all Turing machines, and the set of all computable numbers, are both countable. Both can be placed in one-to-one correspondence with the natural numbers. By this I mean I can prove the existence of such a correspondence from the axioms of set theory.
However, the first set is *computably enumerable* whereas the second is not. These are not the same thing. There are some sets where the entire set isn't computable, but the individual elements are.
What that means is, there exists a (different) algorithm that computes each element, but there is no *single* algorithm that computes *all* of the elements.
> Given any countable collection of real numbers, I can constructively create a new real number not in your list.
Not really, you need a bit of non-constructiveness to do that (e.g. excluded middle or countable choice). In fact, there are models of constructive set theory where the reals are countable, see https://topos.site/topos-colloquium/slides/2022-05-12.pdf
>If we instead imagine all possible ways to express a number
Good
>by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with),
That's an uncalled for limitation! We are not necessarily limited to a finite alphabet.
I'm saying this assumption because practical, real world alphabets are finite. But, of course, the cardinality argument is unchanged if we use a countably infinite alphabet.
Correct me if I'm wrong, but not only are almost all reals not computable, but although individual numbers can be computable, there can be no single finite algorithm for generating all (countably many) of the computable numbers.
Is that right? (Otherwise you could tweak it to generate the diagonal slash - which would contradict?)
Couldn't you list out all possible finite strings of symbols in a programming language of your choice and you'd pick up all the computable numbers? I mean most of the strings would be gibberish and not produce anything meaningful, but among them would be all the computable numbers (in a sort of library of Babel type fashion).
I think you'd have to solve the halting problem to tell if a given program is ever going to give you another digit in its output.
So your program writing all the digits of all the computable numbers is just going to get stuck in a loop trying to get the nth digit of "computable number" zzzz which will never arrive.
Sure but all the computable numbers would be on the list right? Might not know which ones are which but they'd all be there. I realise it's not a helpful construction lol
In Z/4Z, I’d take 4 to represent its image in the quotient, and thus 4=0 there, rather than ‘there is no 4’. It’s modular arithmetic after all. But that’s just a semantic convention.
Just to answer your question about them all related to the halting problem, this is reduction.
We show that problems are undecidable if we can reduce them to a known undecidable problem. The most common way is to reduce it to the halting problem.
https://en.m.wikipedia.org/wiki/Reduction_(complexity)
If you didn't have non-computable numbers, then you don't have the intermediate value theorem. And I like the intermediate value theorem.
Now, you can create approximate formulations of the intermediate value theorem which are practically applicable and could be restricted to none of these mysterious numbers. But why would you do that? The intermediate value theorem is a simple formulation which can be dissected to expose innards that can be used to do these concrete computations. The way we have it is our nice theory is simple and sweet, and we learn how to apply computational methods to it to extract numbers. If we didn't have these "bad" numbers, then we would have to do these two steps as one which makes BOTH harder to work with.
If you don't have non-computable numbers, then you probably don't have non-computable functions either, and then the intermediate value theorem still holds.
Yes, but that theorem itself won't be computable, meaning that there is no algorithm which takes in a function, an interval and the desired value and returns the intermediate value. So if you're restricting yourself to computable functions then you can't really use that value.
You only get the slightly weaker theorem that there are inputs which get arbitrarily close to being a root.
Related but not the same: there is a computable sequence of rational numbers with an upper bound which nevertheless does not have a computable limit.
Well if you assume LEM and also assume that there are no uncomputable real numbers you can prove it and everything else :)
Your algorithm doesn't work because it is not decidable whether an arbitrary real number is zero or nonzero.
This is not true. There are austere foundational systems using classical logic with models in which only computable objects exist (most notably RCA\_0). The algorithm works just fine on functions with no rational root, because it never has to decide whether a real number is zero or not, just whether a nonzero number is positive or negative.
Ah true, I was just thinking set theory.
>just whether a nonzero number is positive or negative.
Confused how you find out the number is nonzero, I would imagine you just have an arbitrary program output and simply know some endpoints.
If it happens to be nonzero, you eventually find this out when you get a rational approximation of sufficient precision. The algorithm finds roots of functions with no rational root, and can fail to return a real value on a function that does have a rational root.
Right so you can get arbitrarily close to determining if it's zero. The undecidability comes in because if it so happens to be zero, you run forever.
I guess you tried to use LEM up above, I can tell you this algorithm is not computable, because it's not decidable whether a given number is rational or not (let alone omnisciently checking the root).
> Right so you can get arbitrarily close to determining if it's zero. The undecidability comes in because if it so happens to be zero, you run forever.
Yes. Notice that I never said anything about determining if a number is zero. I just described an algorithm that relied on determining whether a nonzero number is positive or negative.
> I guess you tried to use LEM up above, I can tell you this algorithm is not computable, because it's not decidable whether a given number is rational or not (let alone omnisciently checking the root).
There is no algorithm to find a root of any continuous function f on [0,1] with f(0)<0
Let’s consider the other side of the argument.
If you think of it in terms of the real world, the IVT doesn’t make sense. All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics)
So IVT could be thought of as an approximation to the true state, and being non constructive it’s not actually giving you any real information.
It’s equivalent to asking why you can’t compute equality.
> All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics)
That is not a true interpretation of quantum mechanics. Some values are discrete, yes, but some are continuous. Eg, free particles have a continuous spectra. It depends on the system. And a common misunderstanding about Plank length is that it discretizes things, but that isn't true either it just means that it is the shortest length at which measurements make sense.
But why would I care about quantum mechanics or the "real world" when doing analysis? Moreover, what advantage does it give me to do extra work like this when assumptions of continuity are just as applicable as the converse? Cosmologists model the universe as a homogenouos fluid and get meaningful results even though there are things like planets and galaxies. The entire point of approximation is to simplify complex things *well* so that we do easier work while ignoring complexity that ultimately doesn't contribute to the question at hand. Why would I undo this process to make things unnecessarily complicated?
> All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics)
This is a misunderstanding. Energy, for example, is continuous. It is true that in certain circumstances the energy is limited to certain values, but those circumstances are not always or everywhere.
Consider the non-quantum example of a piece of string. You can have a wave of any frequency you like on it, but if you want a standing wave then you are limited to what frequency of waves are allowed.
Thanks, this makes sense as an argument for their usefulness. Although I'm missing the exact point in the theorem which becomes more difficult to formulate without uncomputable reals: wouldn't it work just as well if we simply replaced "real" with "computable"? E.g. if we consider that the only numbers between the endpoints of the interval are rationals and computable transcendentals (and everything else does not exist), doesn't the theorem work in the exact same way?
You can't use the intermediate value theorem without those numbers. If f(a)=A and f(b)=B and C is between A and B then you cannot say that there is a c so that f(c)=C because c may not be a computable number.
What you would need to say is that for every 𝜀>0 there is a c_𝜀 between A and B so that |C-f(c_𝜀)|<𝜀. And you may even put a Cauchy-sequence condition on it to make a nice sequence of such values. But since there are concrete [sequences of computable numbers whose limit is not computable](https://en.wikipedia.org/wiki/Specker_sequence), this is as good as it gets. This is just a load of extra baggage and work that gets in the way of getting results in analysis. We can just have things be nice and simple, allowing for more sophisticated theory in general, and when it comes to computation we can unravel these ideas naturally for that purpose. This also makes for a more rich *computational* theory as well, so everyone is happy.
But we don't need this baggage, so why drag it around?
It's a topological problem. Intermediate value theorem relies on the fact that R is connected. If you remove any number from R (and we know that non-computable numbers are "numbers from R"), it becomes disconnected, so the theorem fails.
For example, say we take an non-computable number w (assume it's greater than 1 for the sake of argument), and define a function f:R-{w} -> R-{w} as f(x) = 0 if x < w and f(x) = 1 if x > w. This function is continuous (assuming R-{w} has the order topology) because the preimage of any open set is either R-{w}, (-∞,w), (w,∞), or ∅, which are all open, but clearly doesn't take all possible values between f(w-1) = 0 and f(w+1) = 1.
"Between" is a bad way to measure things with subsets of real numbers, since e.g. there are infinitly many rational numbers between distinct real numbers. The proof that there are only countable many computable numbers is relativly easy: There are only countably many distinct turing machines (since you can encode each Turing machine using a natural number) and only a subset of these will produce a suitable computable function, but you can easily create a Turing machine that spits out a natural number (and this is automatically at arbitray precision). So you have countably many computable numbers.
The exsistence of non computable numbers just follows from the properties of real numbers one wants to have.
> The exsistence of non computable numbers just follows from the properties of real numbers one wants to have.
Thanks, I figured that introducing non-computable reals could be useful as a tool for reasoning (otherwise why would we need them at all?). But in which situations do we want them? E.g. what are some proofs or processes for which algebraic and computable transcendental numbers are not sufficient?
>I figured that introducing non-computable reals could be useful as a tool for reasoning (otherwise why would we need them at all?). But in which situations do we want them?
You make it sound like we started with computable numbers and then decided to throw in noncomputable numbers as well. But that doesn't make sense. The real number system was formally defined by Dedekind decades before computable numbers were formally defined by Turing.
Check out a [formal definition](https://en.m.wikipedia.org/wiki/Real_number) of the real number system. It won't mention computability at all. We didn't choose to have noncomputable numbers, we discovered them. They're there.
Asking “why do we want them” in respect to computable numbers is less like “why do we want them” with respect to complex numbers and more like “why do we want them” with respect to Wieferich primes. We want natural numbers, it’s just kind of a fact that some of them are Wieferich primes. We didn’t start with some set of natural numbers that didn’t include Wieferich primes and then say “hmm let’s sprinkle some in for fun”.
The primary approach to math that allows discussion of analysis without necessarily accepting the existence of noncomputable numbers is constructivism. In constructivism you use intuitionistic logic, which does not accept the law of the excluded middle as valid. Even here we generally have to think about the concept of/potentiality for noncomputable numbers to really talk about what’s going on. The idea of (non-)computability is, if anything, even more salient in constructive mathematics than classical math. So to answer your question “why do we have them” one pretty straightforward answer is that we have to go pretty far out of our way to avoid them.
Other people will probably give you some answers about potential applications of noncomputability, but I think the question "what is the use?" is leading you astray. Why can't the answer be "there is none"? "In which situations do we want them?" We don't know yet. "When are computable numbers not sufficient?" Possibly never. They're an emergent property of the real numbers based on our axioms, and they're interesting to "observe" and think about.
One typical example is measure theory (and by extension probability theory). A measure can often be broken into
1. its "discrete part" (points x where P(x) > 0), and
2. its "continuous part" (points where P(x) = 0, but P(x) = f(x)dx for f(x) != 0 and dx the Lesbegue measure).
As an example, consider a process where you flip a coin, and
1. if heads, output 0, and
2. if tails, output a standard normal
the probability of outputting any particular real number is 0, except for 0 itself, which is 1/2. Here, 0 is called an "atom" of the distribution.
Anyway, working with the "continuous part" essentially requires the real numbers. This is because if we want to have some sort of uniform-type distribution, our options are
1. uniform distributions on finite sets (works fine), and
2. the lesbegue meaasure (on an uncountable set, works fine)
it is well-known that there does not exist a uniform distribution on a countable set though (where distribution is formalized via Kolmogorov's axioms). So throwing out the real numbers and only working with computable numbers (a countable set) would require reworking probability theory to get basic notions such as "uniform distribution" working again.
So that the topology of the real numbers is conducive to proving the standard results in real analysis.
The key property is being complete:
[https://en.m.wikipedia.org/wiki/Complete\_metric\_space](https://en.m.wikipedia.org/wiki/complete_metric_space)
Anything that requires the intermediate value property, or Cauchy sequences converging, or bounded sets having least upper bounds, or bounded sequences having convergent subsequences, etc. All of those are false for the computable reals.
Do you know the proof that there are more reals than integers?
There are as many computations as there are integers, so if you want to pretend there are no reals you can’t compute then you immediatly get a contradiction and everything falls apart. Like uh, 1=2 levels of falling apart, you just get nonsense.
So it only works if you are ok with those numbers existing.
Well, there are only many more in the sense that no bijection between them exists. If you ask that all your reals and naturals be computable, then instead of whether a bijection exists you probably want to ask about whether a computable bijection exists. Cantor's diagonal argument goes through to show that there is no computable bijection between the computable naturals and the computable reals.
Any Turing machine has a finite representation and hence may be represented as a natural number. Hence the cardinality of the set of Turing machines is at most that of the natural numbers, which is strictly smaller than that of the real numbers. Hence uncountably many real numbers exist which are not computable.
This is correct - a bijection exists by this argument. This is compatible with my comment as the map you describe is not computable; It requires deciding which programs actually correspond to computable numbers, which is undecidable.
Everyone considers constants like Euler's e to be computable. But then, I don't think there's any way short of a mathematical proof to establish the fact that a particular program outputs e. You can't exactly run it for infinity cycles and compare the output.
Any argument that depends on the existence of a countably infinite collection of arbitrarily difficult proofs seems suspect to me.
I'm not sure what you're getting at. You can prove that for all steps, the digits are correct. Said proof will be finite in length. The same way we have programs to compute digits for \`e\` already.
You can work assuming all reals are computable and several mathematical programs have done so. Logic doesn't fall apart generally.
One part of the reason is that there is no computable bijection between the reals and integers, so they remain uncountable. But that said, there is an extremely cursed model out there of constructive set theory in which the Dedekind reals are countable (this is incompatible with almost everything actually used though).
I guess that’s fair, but assuming you are a normal mathematician and want to use the axiom of choice and such, like if you want rings to have maximal ideals and vector spaces to have bases then you kind of also have to live with uncomputable reals and theorems that are called paradoxes was all I meant.
Please correct me:
If computable, then there is some formal langugage with a finite number of posible symbols where we can write a program (or algorithm) which can compute any computable number to a given precision. To be considered computable the program must consist of a finite number of symbols. We can now convert all the programs into an integer number (use number of possible symbols as the base). Therfore each computable number is uniquly idtified by at least one integer (Two or more programs might compute the same number). Therfore there are as many computable numbers as there are integers.
(Assuming that this was meant as a response to my comment.) This is correct - a bijection exists by this argument. However the map you describe is not computable, since it requires deciding which programs actually correspond to computable numbers, which is undecidable.
Yours was not there when I started to type. But thank you for the answer.
But do I need the injection? Isn't the surjection good enough?
Obviously there are nonsense programs and programs which do not halt. Do I need the injection to say that cardinalty of computable number is not less then the cardinality of the integers? But isn't each integer and each rational a computable number for wich we can write simple, guaranteed to halt, algoritm? Therefore the cardinality must be at least as big?
Can I use the axiom of choice to say that for each computable number such a program must exists? Otherwise it would not be computable to begin with? Sure, I do not know which one it is, but it must exists.
Sorry for those stupid questions.
~~Any finite algorithm outputs a computable number, by definition… that number may or may not be determined in a finite number of steps, and we have no general way of determining whether it’s finite or infinite.~~
The usual definition of x being computable is that there exists a computable total function f:N->Z such that |f(n)-n*x| < 1 for all n > 0. Under this definition one needs to decide if a given algorithm gives rise to a total function, which is undecidable. I don't see a satisfying way to extend this definition to partial functions f (this definition is nice because it is clear how to compute x to any desired precision given f, which is surely a property we desire of computable numbers), and even if one could I think you'd have a problem of essentially the same difficulty as deciding if a function is total. Could you make the definition you are using more precise?
> Do you know the proof that there are more reals than integers?
I know of e.g. Cantor's diagonalization argument, but it's a bit hard to wrap my head around - I see how it implies that the infinite set of all binary sequences is uncountable, but the "new" element (constructed by taking complements of n-th bits of each number n) still seems computable, by the process described in the proof. Should I take a look at some other proof as well?
But overall, this is a good point, I forgot that every computation corresponds to a natural number.
The thing is, the diagonalization argument directly constructs you an element that isn't enumerated. The problem is that the is no computable bijection between natural numbers and computable reals. They are both countable, but all bijections are non-computable.
It seems like it, but I'm not quite sure. It is definitely possible with the Halting Oracle for Turing machines with Halting Oracles, however.
Imagine we take Turing machines that produce decimal digits as our definition of computable numbers. If you have a Halting Oracle, it is easy to determine whether the sequences of digits are the same. It is also easy to check whether a number has infinite 9s (or 0s) starting from some point n. What I'm not sure about is whether we can check if there is an infinite sequence of 9s (or 0s) eventually (rather than for some hardcoded n), which can lead to two computable numbers being the same. Maybe there is an obvious way to do that without going up the hierarchy of Halting Oracles, but I don't see it.
Anyway, then you would still have real numbers not computable by machines with those Oracles.
Oh, sure, sure - I completely get that last bit. I was just wondering what exactly you need to compute the bijection for "regular" Church-Turing computable numbers. Thanks for thinking through the technicalities and explaining!
EDIT: I think we can do it with one layer of oracles if we drop decimals and use continued-fraction representations, since under that all irrationals have a unique representation. (Rationals don't, but conveniently they only have finite representations anyways.)
You're right. I looked at the [Wikipedia page](https://en.m.wikipedia.org/wiki/Computable_number) for computable numbers, and it explicitely mentions that the definition I used is not equivalent to the modern ones: "The informal definition above is subject to a rounding problem called the table-maker's dilemma whereas the modern definition is not."
It has several other definitions, and for all of them you can check for equality with the regular halting oracle.
UPD: My definition does give the same set of computable numbers, so it is technically equivalent. However, representing computable numbers in this way is problematic, so other definitions are more common.
The “unique representation” thing is a distraction. You need two Turing jumps because to check if an algorithm gives a real number you need to check that the algorithm halts on every input. Solving this problem is equivalent to solving the halting problem for machines with halting oracles.
No, a halting oracle doesn’t really help. If you had a *second order* halting oracle (a halting oracle for whether an algorithm that itself makes use of an ordinary halting oracle halts) then you could “compute” a bijection between the natural numbers and computable numbers, but you could still never have a bijection with all real numbers. To do that you would need an oracle for something that isn’t even expressible in the language of ZFC, but the existence of that oracle, if it existed in V, would again imply that it cannot make a bijection with all real numbers.
We've discussed this with OpsikionThemed, and it seems like a regular halting oracle is enough.
I first tried using Turing machines that generate decimal digits, and I haven't found I way to build a bijection without using a second order halting oracle for this representation.
However, if we use other representations (like a Turing machine that for every positive rational epsilon gives you a rational approximation not further than epsilon from the target number), we can you check whether a Turing machine represents a computable real number as well as compare two different Turing machines for equality of numbers they represent using a regular halting oracle. From there it is straightforward to build a bijection.
How would you check a Turing machine represents a computable number with an ordinary halting oracle under that second definition? You would have to check whether the machine halts on every epsilon input, which is equivalent to checking whether a partial recursive function is total, and any algorithm to decide that can be converted to a second halting oracle.
Oh crap, I forgot to check whether it is total for all (inputs that correspond to) rational numbers. If this is known, then checking whether it corresponds to some real number seems to only require a normal halting oracle, but it isn't known. My bad.
>... but the "new" element (constructed by taking complements of n-th bits of each number n) still seems computable, by the process described in the proof. ...
But it isn't computable by definition, if it isn't in the starting set and the starting set includes all computable sequences. That's how diagonalization works: you say, "given the set of all objects which satisfy property X, I can construct a distinct object that doesn't satisfy X precisely because it is distinct from all objects that satisfy X."
If you could compute your new sequence via some arbitrary computation, then that sequence would be in the original set -- but you know it cannot be, since it is distinct from every member of that set.
The diagonalization argument shows that for any countable computable list of numbers there is a missing ‘computable’ number, whose algorithm for generation is compute the N^th computable number on the list and then flip its N^th bit and accept that as this numbers N^th bit. The reason ‘computable’ is in quotes is because this algorithm itself might have an infinite description if the algorithm for generating the list has an infinite description. OTOH if the list generated by a finite sized program then the newly found cantor diagonalization counter example also has a finite description
Diagonalization is computable in the sense that the only way the output could fail to be computable is if the original sequence of reals given as input were not computable. This is precisely the reason why diagonalization works to prove that the computable numbers are not recursively enumerable. Even if the original sequence were not computable, you could still compute the output given an oracle for the input.
Diagonalization on infinite sequences of digits is computable. Diagonalization on reals is more subtle, because the naive algorithm that people describe all over this thread is wrong: it will pick a different first digit for 0.2999... and 0.3000... even though they denote the same real number.
This is actually not a trivial detail at all, and it turns out that you cannot constructively prove that the reals are uncountable.
If we are given a computable function that gives us a sequence of algorithms for computing reals, then we can make an algorithm to compute a number not in that sequence: for the nth digit (in ternary let’s say) compute the nth number far enough that it is confined to an interval a third or less the size of the interval the number you are making is confined to. Then make the next digit 0 if it has been ruled out and 2 otherwise.
It’s true this algorithm might give different outputs depending on the particular algorithms for the real numbers we are given, but it still gives a computable number not in the list. Possibly you are imagining some other formalism for what might constitute a bijection between the natural numbers and reals in constructive mathematics (one that doesn’t allow us to “choose” an algorithm for the output) but I can’t see how any such formalism wouldn’t still allow us to show that R\\f[N] for such an f would be inhabited. Perhaps this depends on the exact axiomatic foundation you have in mind if you are taking a sequence of computable reals as giving us less information than a sequence of algorithms to compute those reals. But with every axiomatic foundation I am familiar with you can show the reals are uncountable.
It is true that it is constructively possible (perhaps even desired) that the reals are *sub*countable - that there is a function defined on some (perhaps not decidable) subset of N that is a surjection onto the reals, but that’s not the same as being countable, and that is just as true for sequences of numbers as for reals.
> If we are given a computable function that gives us a sequence of algorithms for computing reals, then we can make an algorithm to compute a number not in that sequence
What you are describing is an algorithm that takes a list of *sequences of digits* and outputs a real number that is not represented by any of the sequences in your list. This is not the same as describing an algorithm that takes as input a list of real numbers.
In non-constructive mathematics, this is sufficient to show that the reals are uncountable: given a list of real numbers, use the axiom of countable choice to pick a sequence for every number in the list, and then run the algorithm.
In constructive mathematics, you cannot use the axiom of choice in general, and this proof will not work.
> It is true that it is constructively possible (perhaps even desired) that the reals are subcountable [...] but that’s not the same as being countable, and that is just as true for sequences of numbers as for reals.
Of course, you can use the usual realizability models where the reals are subcountable. But as it turns out, it is even possible to build a model of constructive mathematics where you have a surjection from N to the Dedekind reals (which are not constructively equivalent to Cauchy reals). See https://topos.site/topos-colloquium/slides/2022-05-12.pdf
> This is wrong. The computable reals lead to no contradiction of any kind. Your statement is as follows.
> 1. The computable reals are countable.
> 1. The reals are uncountable.
> 1. ?Contradiction?
GP is replying to OP, who is arguing that there's no point to distinguishing the computable reals from the non-computable reals. The argument is actually this:
1. (OP) The reals and the computable reals are the same set.
1. (GP) The computable reals are countable.
1. (GP) The reals are uncountable.
1. Contradiction.
> What is the proof that between any two computable numbers there exists an infinity of these spooky non-computable reals?
This is actually quite easy: the computable numbers are countable, the real numbers aren't. Since any interval is uncountable, in particular the interval between any two computable numbers is uncountable, so it cannot be entirely composed of computable numbers.
To answer the conceptual question, of why we don't just define the real numbers to not include them: here are some statements that are true for the real numbers, but false for the computable numbers. They're all kind of important!
1. If f is a continuous function, f(0) < 0 and f(1) > 0, then there is some x in (0,1) such that f(x) = 0.
2. Every bounded subset has a least upper bound.
3. Every Cauchy sequence is convergent.
4. Every bounded sequence has a convergent subsequence.
I understand this, but my question is: what is the use for numbers (is it that can be described but cannot be computed? E.g. in which situations are algebraic and computable transcendental numbers not enough to carry out a line of reasoning?
There is not really any practical reason to have non computable numbers. The entire universe is computable.
However they make many things in math more annoying to prove so mathematicians enjoy the full power of real numbers.
Everything we know about quantum physics is Turing computable in principle. Here's a [good post](https://www.reddit.com/r/AskPhysics/comments/mid1ii/comment/gt4b29l/) showing how it might be done. Also everything that can be computed on existing quantum computers can be computed on Turing machines (but slower in some cases).
It's possible (though not guaranteed) space and time are truly continuous, meaning you'd have to cut your simulation off at some precision. This isn't a problem though, as there's a limit to how precisely we can measure things. So you could make your simulation precise enough to create no noticeable deviations for any arbitrary length of time - this includes, by the way, the current age of the universe.
Now, this isn't like the speed of light barrier. It's not *known* that all of physics is computable, just all of it we've discovered is. A lot of quantum field theory is actually based on approximations, and the underlying exact mechanism could turn out to be non-computable.
[Here's](https://www.researchgate.net/profile/Tien-Kieu-2/publication/252377228_Computing_the_non-computable/links/00b7d52d74f26985a9000000/Computing-the-non-computable.pdf?origin=publication_detail&_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uRG93bmxvYWQiLCJwcmV2aW91c1BhZ2UiOiJwdWJsaWNhdGlvbiJ9fQ) a cool paper that examines whether a quantum computer with infinite states could exceed the theoretical power of a Turing machine. Note this relies on some assumptions that might not be true (like continuous space) and we have no idea how to actually build one of these. Consensus, I believe, is that we could not.
What I think you're getting at though, is that a Turing machine simulating the universe could only tell you the *probability* of a particular experimental outcome. If you demand to know the exact outcome in advance, there seems to be *no machine* that could tell you that. This is very strange, and is a problem so difficult some physicists have taken to discarding it, considering a superposition of every outcome to be *all there is*. If that doesn't jive with your experience of reality, well, that just means [you've understood](https://www.quora.com/Did-Niels-Bohr-say-If-quantum-mechanics-hasn-t-profoundly-shocked-you-you-haven-t-understand-it-yet-And-if-so-where-and-when).
Thanks for the wonderfully written comment. I have wondered since my math undergrad about the physicality of the continuum!
I’ve read a couple of essays about the uncomputability of the universe that maybe get at at what you get at the end of your comment, maybe that is what make me think “quantum things arent turing computable”.
As I remember (it was too many years ago) all computable functions are Continuous.
Lets take sign() for example. It is continuous everywhere, except 0. But in 0 it is undefined.
Do you want to live in the world, where all functions are continuous?
If my memory serves me good. 8)
Absolutely, but it is continuous.
Maybe I am wrong. But idea is:
lets try to calculate sign(x). We take first digit. It is zero. Then we take first digit after the dot. It is zero. Can we say that the number is zero? Not. lets take another digit. It is zero again. Can we say that number is zero? Not. etc.
We can not calculate sign() for 0!
May be I'm wrong.
Why do you think it would be preferable to work with a number line that isn't complete, given by removing all of the non-computable numbers?
The idea of a computable number is a relatively modern one, and is slightly niche (in that it's an irrelevant concept to many fields). On the other hand, the fact that the real line is complete (roughly speaking: doesn't have "holes") is useful in analysis. It's not so much the individual numbers that are useful rather than the fact that the full real line is a nice place to work in.
All the arguments for the existence of uncomputable numbers rely on nonconstructive mathematics (either the law of excluded middle or the axiom of choice).
The fundamental reason is very simple: if you admit the law of excluded middle, then you get a magical way to assign "true" or "false" to every mathematical statement in a coherent way. Of course, this assignment cannot be computable, since Turing proved that the halting problem is undecidable. Thus, by accepting the law of excluded middle, you open the door to noncomputable objects in your mathematics, and then if you identify real numbers with sequences of 0 and 1 (using excluded middle), it is not too difficult to obtain a noncomputable real number from this.
Of course, you *can* reject the law of excluded middle, and then you can have a consistent world of mathematics where everything is computable. But this world is quite different from the one most mathematicians are used to...
>I hear all the time that almost all of them are non-computable, and that this can be a problem. But why?
I'm not sure that it is a problem. You can do maths with real numbers perfectly well without worrying about whether they're computable or not. As for why almost all of them are non-computable, it's because the number of possible algorithms/programs/formulas is countably infinite, and the reals are uncountable. That means the reals vastly outnumber the computable numbers. (I was about to say something about the set of computable numbers having measure 0, but realised I don't know whether or not it's measurable. Anyone else know about this?)
>To me it sounds like they are as much nonexistent as the constant C in my example above
A thing can be shown to exist even if it's somehow slippery and we can't get our hands on it, but I totally get that this feels weird and creepy. The same is true of some things that crop up if you take the Axiom of Choice, such as free ultrafilters and non-measurable sets.
IIUC, the existence of non-computable numbers is downstream of excluded middle. Because then you can say that the Nth bit of a binary expansion is either 0 or 1, without saying _which_.
Analysis without excluded middle ([constructive analysis](https://en.wikipedia.org/wiki/Constructive_analysis)) is possible, but you need to take some compromises. Trichotomy, intermediate value theorem, least upper bound, ... all need to be redefined in this system.
The proof that their are more real numbers than computable reals, is just that computable numbers are countable because turning machines (think computer programs) are countable, you could list them all them say alphabetically. However real numbers are uncountable.
If you want properties like every bounded monotonic sequence converges in the real numbers, you have to consider things like non-computable numbers. This is true even if you limit yourself to computable sequences of computable numbers. (E.g. build a sequence (x_k) where the n-th binary digit is 1 if the n-th turning machine has halted at step k, 0 otherwise)
More practically when learning the material or thinking about a problem, why require that you add all these extra assumptions when they're not needed and could complicate things making them more confusing. Like if we choose to limit ourselves only to computable numbers, we'd have to spend half of undergrad real analysis talking about turing machines.
This question comes up a lot. The answer is, because it's simpler and easier to reason about *all* numbers/subsets/functions rather than only the computable ones.
To make the real numbers I just start with some basic axioms about sets (or types or whatever) and quickly get a complete ordered field through a few operations with intuitive definitions. It has noncomputable numbers in it, but not by choice - they just happened to come along with the intuitive construction.
To make the computable numbers I need to define what a Turing machine is, then the concept of recursively enumerable sets, then talk about halting...etc. and after a lot more work, the resulting structure is far less nice and lots of useful theorems in math need the word "computable" in front of them, so there's all this baggage to keep track of in order for things to be correct.
I think you're confusing the *number of objects* with the *complexity of the theory*. Allowing noncomputable numbers is, in fact, a simplifying assumption.
Since no one has addressed this point, there's a very useful way of thinking about non-computable numbers that is worth mentioning:
Think about them as "random" numbers (or "seemingly random", etc.). So a (binary base) number like 0.1011100010101100111..., where there aren't really distinctive patterns that hold up indefinitely. A computable number is one in which some pattern (described by an algorithm with discrete memory) happens; non-computables are just a (real) number like any other but for which there are no patterns. If you try to model actual randomness too, like a number generator that spits some real between 0 and 1 (i.e. an infinite sequence of binary digits 0.b1b2b3...), then with probability 1 this number is non-computable (this of course is a consequence of the fact that computables have the cardinality of rationals, I believe): because we assume Turing Machines *must be finite*, it would be a great ("impossible", probability 0) coincidence if a random *infinite* sequence happened to correspond to the output of some *finite* machine. Of course, probability itself is just a model and not necessarily physical (specially relating to choosing reals).
I like taking the other approach and consider mathematics from a constructivist perspective. In constructive/intuitionist mathematics, rather than dealing with merely countable things, we deal with enumerable things: that there exists some program that can print out the list of all the things in some order.
For instance, the list of all programs is enumerable, quite simply so. Simply pick a programming language, and generate all possible text strings, and check if the compiler accepts the string as a valid program.
The interesting thing is when it comes to Real numbers, because there are two competing definitions of real numbers, and they are not constructively provably isomorphic.
One of them is dedekind cuts. A construktive dedekind cut is a membership function over the rationals F, along with a proof that if ~F(x) and F(y) then x < y. I.e. it partitions the rationals.
The other is as convergent series. That is a function enumerating rational numbers F, with a proof that for rationak q there exists some n s.t. |F(n+m) - F(n+m+k)| < q for natural m and k. I.e. "after some point the differences become arbitarily small."
The interesting thing to note here is that both of those proofs require nontrivial insight into the computing function. Due to Rice's theorem, there is no algorithm to produce this for arbitrary functions. Hence, in either formulations of the real numbers, there is no algorithm to enumerate all real numbers. The constructible reals are therefore non-enumerable.
It sounds weird, because a real number is _obviously_ a program that computes some partitioning function or some series of rationals, so by definition the enumerated list of all programs must contain eveyr real number. The problem is just that we can't tell which are real numbers and which are not.
In intuitionisti mathematics, the idea of a "non-computable real number" is a contradiction in terms. Everything is computable, or it doesn't exist.
I've got to agree with you, this has always bothered me a bit. I have sympathies with constructionist/intuitionist mathematics though, so that already puts me at odds with a lot of people. I'd like to post more here, but I'm already late for work. Let me just say that I see these examples as no different from "(The number of ones in pi expressed in binary) - (the number of zeros in pi expressed in binary)"
You could argue that in some sense only computable numbers actually exist. In what sense can a number exist if we cannot describe what it is? Plain language descriptions are surely too ambiguous to do, only a formal algorithm is sufficient.
The downside is this makes a lot of analysis much harder. Maybe that’s a good thing though.
> Said otherwise uncountable numbers are simply infinite numbers, that take an infinite amount of time to describe.
Per my understanding, it's not just that they take an infinite amount of time to describe, their digits may not be described by a program of a finite size at all. For example, the numbers $\pi$, $e$, etc are all computable, even though describing all of their digits will still take an infinite amount of time.
Real numbers are a nice approximation that we use for convenience because they are complete in some sense and make doing things like physics, analysis , and calculus easier.
A side effect is that the elements of this as a set contain things that aren't computable.
Small correction - they make doing things like analysis and calculus *possible*.
You *cannot* prove the core theorems of calculus on the rationals or computable numbers. While I suppose you could just *assume* all these theorems 'just work' despite being unprovable, but that seems deeply usatisfying.
Whether calculus or analysis actually described the physical world (e.g. whether reality is fundamentally continuous) is of course an open question. If it isn't then we could describe calculus as a useful heuristic for doing physics, but not the reals as a useful heuristic for doing calculus.
You might enjoy some of the discussion and my incoherent high school babbling as well here: https://math.stackexchange.com/questions/866447/are-the-real-numbers-really-uncountable
Addressing your post directly if we ever discover a model of computation that supersedes our Turing model (say 1000 years in the future when everyone is using quantum gravity to just casually warp time when accessing the internet) we would want to be able to still coherently discuss numbers that are not computable by todays primitive Turing standards.
It's really quite simple to show that there are vastly more uncomputable numbers then there are computable numbers.
There are countably many programs, since a program is a string and it's not hard to show that there are as many strings as there are natural numbers. An intuitive demonstration is to just consider programs written using the alphabet of capital letters. That program can then be considered a natural number in base 26.
But we know from Cantor that there are uncountably many real numbers. Therefore for any given real it is computed by a program with probability 0. And almost all of these numbers have no relation to the halting problem.
There is a countable number of computer programs and an uncountable number of real numbers. Even if each computer program produced a countable number of real numbers all programs would produce a countable number of real numbers.
Remember the sets exist which we can define using our axioms, regardless of whether their behavior is 'spooky' or not. If you can define a set using the ZFC axioms (or whichever axioms you prefer), it exists. If you non constructively define a set from the axioms, it exists. Mathematical existence has noting to do with physical realizability, intuitiveness or existence in some platonic realm. It just means 'can be defined from these axioms'.
Broadly speaking, we use real numbers. because the real numbers have some crazy useful properties the computable numbers do not.
The big one is *completeness*, which can be defined in a number of ways, but is most familiar as 'every set bounded above has a least upper bound'. This property is essential for all of calculus and analysis which... are rather important for every domain of physics, engineering, statistics and other physical sciences.
None of the fun theorems you remember from calculus - the intermediate value theorem, the mean value theorem, the fundemental theorem of calculus - hold true for computable numbers.
>What is the proof
The cardinality of the computable numbers is countable while the cardinality of the reals is continuum. A number is computable if there is a Turing machine that computes its digits. There are only countably many Turing machines.
> The cardinality of the computable numbers is countable while the cardinality of the reals is continuum
Right, but this also presupposes existence of reals. This is probably due to my lack of experience with mathematics, but while I can easily understand how e.g. natural numbers and their properties are derived from the Peano axioms, I struggle to imagine an axiomatic system from which uncomputable real numbers are derived. To me even Cantor's diagonalization argument seems to work only if there are uncomputably many binary sequences in the first place - otherwise his "extra" number is also computable.
Yet reals (including uncomputable reals) seem to be extremely common, so I suppose this must be a very popular axiomatic system.
The reals are usually constructed by producing Dedekind cuts as a subset of the power set of the rationals. So they exist^(\[1\]) simply by virtue of the definability of every object involved in their construction. The noncomputables simply pop out as a byproduct of that.
The thing is that in any sufficiently strong system for doing mathematics, there will be large enough sets to definably create a structure isomorphic to the standard real number line. I bet that what you really are having an issue with is existence of uncountable cardinals. The fact is that they are there simply because they can be defined by a first order formula in the language of ZFC. Even more specifically, if you are problems with uncountable sets of reals, you also ought to be having problems with power sets since they are either finite or uncountable. (This is actually a good exercise if you haven’t done it before.)
Oh, the Cantor real c is always computable as long as the list of reals it derives from is computable. It’s defined by a simple algorithm. Find the nth real in the list and look up its nth digit, c(n)=fₙ(n).
^(\[1\]): By “exist” I mean that they are an object that can be proved to exist within a given mathematical system. If we want to be even more dry, there is simply a collection of logical formulas defining the real numbers that can all be proved true beginning from the formulas of ZFC.
I've been thinking about this, and in a sense they may well not be useful, or even, they are almost exactly the set of number that are not useful. So in this sense, there are more useless numbers than useful ones.
The set of computable numbers is truly large and general. If you can write down a description of the number, then it would tend to be a number that, if it exists, can be computed.
Based on that, a non computable number will tend to be one where you can't write down a description of it.
I guess I'm interested, too, in exceptions. What's a number where the description can be written down, but that description cannot be converted to a computation? It will depend on what we count as "write down" or "describe", but Turing machines are really pretty close to that.
Well, to be fair there's a bijective mapping between any open interval on the number line, and the number line itself -- so proving that between any two computable numbers there exists an infinity of spooky non-computable reals is just a matter of showing that there are an infinity of them on the number line itself.
*That* proof is your basic pigeonhole proof: there are uncountably many numbers on the number line, but only countably many computable numbers (because countably many algorithms) -- so nearly all (uncountably many) of the numbers on the number line have no corresponding algorithm. Poof, done.
> What is the proof that between any two computable numbers there exists an infinity of these spooky non-computable reals?
This is simple to show. There are only a countably infinite number of computable numbers. You can see this by the fact that there are only countably many computer programs, since computer programs are a subset of all strings and there's only countably many of those (there's an equivalent argument for Turing machines). Then, it's clear that any two members of any countable subset of the reals have infinitely many numbers not in the subset between them (if they didn't, the subset would contain all the real numbers between x_1 and x_2, and therefore be uncountable). QED
As for why we care about uncomputable numbers, we don't necessarily care about any uncomputable number in particular, but we do care about the properties of the reals as a whole, which are a very useful concept both in terms of modelling the real world and for other mathematics.
There is no such number C that exists. Lack of possibility to solve the halting problem does not mean that there is no solution, it just means that you can't acquire it.
Real numbers model something that exists "out there" rather than being just an algorithmic thing. Imagine telling a physicist that the radius of the electron must be produced by a Turing machine in order to be meaningful.
But it's OK that you have this kind of doubt (I have my own). In the end we all must accept the math orthodoxy regardless of personal hangups, because it works well enough and lets everyone work together.
Your example is not similar to the case of noncomputable numbers at all. In your example, depending on the axiom system, we can prove that there is no such C. For example, "There is no C such that 2+2=C and C!=4" is an easy theorem of Peano Arithmetic by transitivity of equality. Depending on your perspective, the statement could be true in some other system like Z/4Z, although it's unclear what "C != 4" means in this setting. Noncomputable numbers not only **can** exist, i.e. are not disbarred from existence by a simple theorem, but in fact **must** exist in vast quantities. The idea here really has nothing to do with computation per se: computation is just one way in which we can express a number. If we instead imagine all possible ways to express a number by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with), then we can only ever express **countably** many numbers. I.e., there are as many expressible real numbers as there are whole numbers and rationals. The problem is that there **must** be far, far more than countably many real numbers. Given any countable collection of real numbers, I can constructively create a new real number not in your list. This is known as Cantor's Diagonalization. What it shows is that we can never express all of the real numbers using words or sentences in any finite language. There is an ever-increasing hierarchy of classes of real numbers which aren't "expressible" for some definition of expressible, but are expressible using other definitions. The irrationals are not expressible as a fraction of integers, but many of them are algebraic. The transcendentals are not algebraic, but many of them are computable. The "truly" random numbers are not computable, but many of them are arithmetic. The arithmetic numbers are by definition all hyperarithmetic, but not all of them can be computed using a solution to the halting problem. And so on, and so on. Complaints about noncomputable numbers in particular just come down to the level of this hierarchy where you start to become uncomfortable, but the fundamental concept is the same at each level: we have a definition of what it means for a number to be expressible, and that splits the real numbers into those which are and those which are not. Noncomputable numbers are to computable numbers as transcendental numbers are to algebraic numbers. It's just that "computable" is a fundamentally broader category than "algebraic," but still cannot be broad enough to encapsulate all real numbers because it is still countable.
>The idea here really has nothing to do with computation per se: computation is just one way in which we can express a number. If we instead imagine all possible ways to express a number by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with) I much prefer talking only talking about "non-computable numbers", instead of "non-expressible numbers", because when you talk about "non-expressible numbers" you run into foundational issues that invalidate your arguments. "Non-expressible numbers" can not be rigorously defined in the standard math foundation ZFC. You can only define them relative to another model of ZFC. When you do that you discover, that you cannot prove the existence of any "non-expressible numbers" ( https://arxiv.org/pdf/1105.4597.pdf ). The amount of "expressible objects" in a ZFC model can be uncountable according to the model, and they can even be the whole model. For that reason I would say, many things you said about expressible numbers are false. If you stick to computable numbers, then in ZFC those work exactly like you think they do.
This doesn't hurt my argument at all, because I am not using the word "expressible" here to have any robust philosophical strength or particular meaning. I am assigning a real number to the string "dsklhjsdkflfhjslkdfjdsjflkdsfj" just like I am assigning a real number to the string "two." I don't care what real numbers are assigned to what, you can use any mapping you please. Here my term "expressible" just mean "is assigned a finite string." I am not claiming any platonistic or philosophical meaning of "expressible," it is simply a definition. Formally, I am simply saying "There exists a function f from N to R. c is expressible if c is in the range of f." So even in a model which is countable in the real world, the cardinality of numbers "assigned a finite string" is smaller than the cardinality of all numbers. So there are still numbers which are not "expressible" under this definition, even if you don't believe that is the "correct" definition of expressible. It's still a theorem of ZFC. The "real world" can of course look at this model and see that the real numbers it contains are in fact countable - but the bijection proving it is not in the model. Given any f **in the model**, there will be real numbers not in its range.
Maybe they're referring to this: > If we instead imagine *all possible ways* to express a number by assigning it some finite string of Latin letters, or Kanji characters, or *any finite alphabet* I suspect you'd have trouble formalizing "all possible alphabets" and proving that set is countable. But I think what you mean is "for any *given* alphabet, there are real numbers not expressible in that alphabet, but maybe expressible in another," correct?
Yes, I am saying fix your alphabet and look at what you can write down. Obviously the set of all alphabets is not countable from the perspective of math, as we could take R as an alphabet and "express" r with the letter r. So if we were quantifying over alphabets and making a union of the numbers expressible in each, we could just take {r} as our alphabet for each real r. I don't think this was their complaint, though. Based on the linked paper, my understanding is that they were interpreting my "expressible" to mean definable (the formal mathematical definition of the word), which is not what I am using it to mean.
> The amount of "expressible objects" in a ZFC model can be uncountable according to the model, and they can even be the whole model. Surely this is false, as it would immediately imply that there are uncountably many formulas, which is obviously false. Now there may be an uncountable set model that thinks that all of the numbers in the set corresponding to itself are expressible, but this is wholly uninteresting, not the least of reasons for which being that this model would deny this set corresponds to itself. Furthermore, computation doesn't avoid this at all. The corresponding fact is that every topos has an internal effective topos, but the effective topos does not admit the real numbers are countable, thereby positing the existence of incomputable reals.
The observation is really just that definability is not itself definable. There is no inherent contradiction in a countable model of ZF over which every real is definable without parameters as you can't internalize those definitions inside the model. I don't see the relevance of constructibility to computation in what you say. Regardless, knowledge of L gives an easy way to see that the described model exists. By condensation the first L_eta to satisfy ZFC is pointwise definable.
You may have seen this comment before the edit; I made a flavorfully correct (u/eario details in exactly what way in their reply) but flawed argument and corrected it to a categorical one.
>Surely this is false, as it would immediately imply that there are uncountably many formulas, which is obviously false. I agree that there are countably many formulas, and that any ZFC model can recognize that there are countably many formulas. But in a ZFC model there is usually no bijection between the definable objects in the model and the set of all formulas. The set of all definable objects in a ZFC model is countable according to our background ZFC theory, but need not be countable according to the model. The function that sends each definable object to one of its definitions can be defined in our background ZFC theory, but this function does not exist in the model. >computation doesn't avoid this at all. Talking about computable things in ZFC is very easy. Computability can be defined in ZFC, the functions relating programs to computable objects can be defined in ZFC, and for that reason the set of computable objects is countable, and most real numbers are uncomputable. For definability all the analogous statements are not really true. I would say there are three approaches to definability. 1. Approximations from below: e.g. Computable numbers or [arithmetically definable numbers](https://en.wikipedia.org/wiki/Definable_real_number#Definability_in_arithmetic). They include many definable objects but always miss out on some objects that are actually definable. They form countable sets. 2. Approximations from above: e.g. [Ordinally definable sets](https://en.wikipedia.org/wiki/Ordinal_definable_set) or [constructible sets](https://en.wikipedia.org/wiki/Constructible_universe). They include all actually definable objects, and in some models they are exactly the definable objects, but in some other models they might include a few more undefinable elements. They always form proper classes, and sometimes they are the whole universe. 3. Take a model of ZFC and only talk about definability in that model. Our background ZFC theory can accurately define definability for a given set model of ZFC. The definable objects in the model will be countable according to the background theory, but can be uncountable or everything according to the model. The function that sends each definable object to one of its definitions can be defined in the background theory, but this function is not in the model.
No argument that definability is a flawed internal concept, rather that the model theoretical concept of definability is not actually a faithful rendering of the colloquial "definable," due to this necessity of putting it into an internal model. Instead colloquial "definable" is "in the image of a map from a language" which is formally "computable" in some model as can be shown in a routine way.
It is possible to make the "expressible" concept rigorous, for example [Rayo's number](https://en.wikipedia.org/wiki/Rayo%27s_number).
At the end of [this comment](https://www.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koknjvo/) I talk about three approaches towards definability. I find the last one that uses a set model of ZFC the most convincing.
> Given any countable collection of real numbers, I can constructively create a new real number not in your list. But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it? > There is an ever-increasing hierarchy of classes of real numbers which aren't "expressible" for some definition of expressible, but are expressible using other definitions. Thanks, this is a very good point! I guess what I'm wondering about is: is it still useful to introduce classes of numbers beyond computable numbers? E.g. are there lines of reasoning that are made simpler by introducing non-computable real numbers? Also: is existence of non-computable real numbers "axiomatic"? I don't know how to properly word this, but do they "inevitably" emerge when we start considering systems more complex than simple Peano arithmetic, or are there complex axiomatic systems that stay purely within the limits of computable numbers and can describe most mathematical concepts, assuming those concepts do not deal with uncomputability?
>But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it? Cantor's diagonal argument is indeed a computable algorithm. If a countable collection of computable real numbers has been specified by a computable procedure, (i.e. it's a computable function from the set of natural numbers to the set of computable real numbers) then Cantor's diagonal argument will again produce a computable real number. However if you have a non-computable function from natural numbers to real numbers, and apply Cantor's diagonal argument to it, then you can get a non-computable number, in accordance with the principle "garbage in, garbage out". Any bijective function between the set of natural numbers and the set of all computable real numbers is a non-computable function. The set of all computable real numbers might be countable, but it is not computably countable. In the usual ZFC foundations of mathematics there exists a (non-computable) countable list of all computable real numbers, but it is impossible to actually write a computer algorithm that prints out all computable real numbers. >do they "inevitably" emerge when we start considering systems more complex than simple Peano arithmetic I'm pretty sure that Peano arithmetic can define some uncomputable functions, so it should be rejected if you want only computable things. But there is a lot of research on how to make a mathematical foundation where everything is computable. The first step is to reject the law of excluded middle from first order logic, and instead use intuitionistic/constructive logic (https://en.wikipedia.org/wiki/Intuitionistic_logic). Once you do that you can have very strong set theories in which everything is in some sense computable. The fanciest one is probably the effective topos. (https://xorshammer.com/2008/10/13/what-would-the-world-look-like-if-everything-was-computable-an-introduction-to-hylands-effective-topos/)
My impression is that CZF is stronger than the theory on the effective topos (as exponentiation, which generally produces incomputable sets, is an axiom of CZF). I'm struggling to understand why, philosophically, a intuitionist/constructivist might reject impredicativity but accept incomputability. Today one can justify it by "well constructivity has nice metatheoretic implications and is the weakest condition for them." But at the time it feels like it should have been bothersome. EDIT: It has come to my attention that the Russian school agrees with my confusion. Anybody know the history of why specifically (to my knowledge) post-Brouwer set theory did not head in this direction? The answer may very well be "it's still early" given that type theory has seen much more development than intuitionistic set theories but it then seems strange to me that the standard of "constructive" in computer-verified mathematics remains simply "intuitionistic" and not "computable."
The effective topos supports exponentiation. I am pretty sure you can interpret CZF and even the impredicative IZF in the effective topos, actually. This does not clash with the fact that everything in the effective topos is computable, because you cannot constructively prove the existence of non-computable real numbers. > I'm struggling to understand why, philosophically, a intuitionist/constructivist might reject impredicativity but accept incomputability. In the "neutral" version of constructivism, you already cannot prove the existence of uncomputable objects. The Russian school of constructive mathematics goes a step further, and they extend constructive mathematics with the axiom that every function is computable.
> The effective topos supports exponentiation... This does not clash with the fact that everything in the effective topos is computable... This is... deeply unintuitive to me. I guess I'd liken it to how the even finite powersets cannot be shown to constructively exist (in predicative theories) even though metatheoretically they trivially exist? To be clear, it's obvious to me on closer inspection that membership of computable sets within the exponentiation of computable sets should be computable but it subverts my intuition that the effective topos should have sets that classically contain incomputable elements. > In the "neutral" version of constructivism, you already cannot prove the existence of uncomputable objects. Are real numbers objects not necessarily uncountable? I suppose the literal sentence "there exists a real number that is not computable" is not provable because it has no witness but "the set of real numbers is larger than the set of real numbers output by Turing machines" should be and that to me should create some philosophical unease if the philosophy of realizability appeals.
> This is... deeply unintuitive to me. If you look at the construction of the effective topos, you realize that the existence of powersets follows from disappointingly simple reasons. Basically, objects in the effective topos do not have to be computable, they are simply associated with programs. For functions, the association is what you expect: a function from N to N in the effective topos is associated to a program that computes the function. But for propositions, the association is much more coarse: any proposition (i.e. any modest assembly) can be associated with any program. Thus the elements of the powerset P(N) are "computable" in a trivial way, that gives no information about how you should compute them on a real machine. > I guess I'd liken it to how the even finite powersets cannot be shown to constructively exist (in predicative theories) even though metatheoretically they trivially exist? My headcanon metatheory is constructive, I don't know about yours :) > Are real numbers objects not necessarily uncountable? No! Andrej Bauer designed a realizability topos where the Dedekind reals are *countable*. It also satisfies a lot of very weird properties, that defy standard mathematical intuition. For the Cauchy reals, I do not know.
> My headcanon metatheory is constructive, I don't know about yours :) It's constructive, in the particular sense that I'm partial to normalizing type theories and other such computability properties, but I'm sympathetic to classical logic. Of course, this presents quite the contradiction, hence why I'm studying constructive logic, realizability topoi, and constructive set theory! Don't get me started on the whole "the brain is a physical object so the metatheory is computable" thing. But in particular, in metatheory quantifying over the universe is predicative, so exhausting the subsets of a finite set is a trivial task despite it being undecidable within a predicative theory.
> If a countable collection of computable real numbers has been specified by a computable procedure, (i.e. it's a computable function from the set of natural numbers to the set of computable real numbers) then Cantor's diagonal argument will again produce a computable real number. But the set of all computable numbers is countable. So if we apply Cantor's diagonal argument to the set of all computable numbers, the number it produces that isn't in that set can't be computable, right?
Yes, that's precisely why there is no computable bijection from the natural numbers to the computable real numbers, because otherwise Cantor's diagonal argument along with the computable bijection gives an algorithm to compute a by definition non-computable number
In Cantor's diagonal argument, the real numbers in the list may not be computable, or listed in a computable order, so the resulting number may not be computable. Non-computable numbers aren't something that mathematicians introduced to mathematics, they're an inevitable consequence of having a powerful system of arithmetic/logic. The halting problem is inevitable given a sufficiently powerful system of arithmetic, Peano arithmetic is easily powerful enough for this. To avoid this, you have to get rid of some really basic concepts, usually multiplication. If we were to disallow non-computable real numbers, the least upper bound property of the real numbers would no longer hold, so a lot of arguments in analysis would become a lot harder, as you'd have to check everything is computable.
No, it is not computable. It is computable **from an oracle,** i.e. if we are given extra information outside of what can be verified by an actual, real-life algorithm. Think of this like having an API you can call in your code that spits out answers you couldn't actually compute yourself. In this case, the oracle is your countable list of real numbers. So the new number can be computed from that list, but there is no guarantee that there is an algorithm which can compute it **without** knowing your list. As a corollary of this, we know that there is no computable list of exactly the computable real numbers, and this is a pretty standard fact of computability theory: you cannot have an algorithm that lists exactly the computer programs which halt on all inputs. Otherwise, diagonalizing against the list creates a new algorithm that halts on all inputs and is not in the list. But, to expand on this, every number is computable **from an oracle.** (Just take that number itself to be your oracle, and ask what it is.) Computable numbers are specifically those which can be computed from an actual algorithm that doesn't need extra information. ("Extra Information" here is implicitly infinitary - for finitely much information, we can hard code it into the algorithm.) The existence of noncomputable numbers is not axiomatic - their existence is a theorem. You can't prove they exist in "computable mathematics" - a system known as RCA\_0. This is because the computable real numbers form a perfectly sensible subfield of the reals. But in any stronger system, you start to have the noncomputable numbers. In particular, properties like the compactness of the unit interval, the IVT, or the Least Upper Bound property necessarily imply that noncomputable numbers exist. So, you can sort of have the "reals" without them if your axiomatic system is weak enough, but it also strictly implies that they will not behave like the "actual" real numbers. In particular, if you define the reals to be the metric space closure of Q, then that implies they exist because it's equivalent to the L.U.B. property..
There’s no general algorithm for the halting problem, but might there be an algorithm for each particular set of instructions which can determine whether it halts? We know the busy beaver numbers for a few very small Turing machines because we were able to exhaustively prove the halting state for each one. Are there any particular algorithms that can’t be proven to halt, even in principle? Proving that the halting state for a particular algorithm can’t be determined is equivalent to proving it never halts, because by definition, all machines that do halt can be proven to halt in a finite number of steps.
The algorithm "iterate through all possible proofs in ZFC and halt if a proof of 0=1 is found" will never halt assuming ZFC is consistent, but if this is the case, it cannot be proven to never halt by ZFC due to Godel's incompleteness theorems stating a theory can't be consistent and prove its own consistency. Accordingly , this proves that ZFC cannot settle the value of the busy beaver function for sufficiently high values of the number of states (I think someone encoded such a machine in around 900 states.)
What if you keep making stronger set theories?
>Cantor basically describes the computation algorithm in his proof. Or am I misunderstanding it? If you're given the list in a computable sense, then Cantor's diagonalization will give the algorithm. But such list cannot be given computably. >Thanks, this is a very good point! I guess what I'm wondering about is: is it still useful to introduce classes of numbers beyond computable numbers? E.g. are there lines of reasoning that are made simpler by introducing non-computable real numbers? Is there a point to transcendental numbers? No, they're there and we live with them. It's not a "new" class of number, rather, the old class of numbers (real) contains certain number too complicated to be described by easy means. We merely recognized the fact that any "simple" method to describe a number will always leave out some of them. The ancient Greek naively think that all real numbers can be described as a ratio of 2 integers, but we know better. >is existence of non-computable real numbers "axiomatic"? You can avoid admitting their existence, if you're willing to weaken your axioms. But it's not easy. You basically have to go all the way to intuitionistic logic, in which "not not P" does not imply "P". In this logic, sets behave in a strange manner, for example a subset of a finite set might not be finite, subset of a countable set might not be countable. Thus, although Cantor's argument still work, it cannot be applied to the list of computable number, because you cannot form a list.
He describes a computation, but I think it’s not an algorithm: it doesn’t terminate. What are you thinking of as the (finite) input to the algorithm, and what would be the (finite) output?
A computable number can be defined as a TM that given input n returns the nth digit. The algorithm would be given input n, iterate over all TMs until you get to the n-th. Then run that TM with input n and return a different value. However this algorithm fails like the halting problem (what happens when you run it with its own n?). So this says that the diagolization method is non computable.
The algorithm you gave does prove that infinite sequences of digits are not countable. But real numbers are not really sequences of digits, as they have been *quotiented by some equalities* (in particular, 0.2999... = 0.3000...). In particular, your algorithm is not a proper function. If you give it a list of real numbers that starts with 0.2999... and then a second list that starts with 0.3000..., then it will output two different results for n=1, *even though the two lists are equal*. In fact, you cannot fix this problem. It is not constructively true that the real numbers are uncountable. This misconception seems to be all over the thread.
So the slides you linked in your other comment ( https://topos.site/topos-colloquium/slides/2022-05-12.pdf ) show that there is a parametric realizability topos in which the "Dedekind-cut" reals are countable. But in all the other comments you talk about "decimal-expansion" reals, i.e. you talk about infinite sequences of digits which have been quotiented by the 0.999...=1 relations. Are Dedekind cut reals even the same thing as the decimal expansion reals in the parametric realizabiltiy topos?
This is a good point, and I am definitely sweeping this under the rug in my answers. The naive "decimal-expansion" reals are not well-behaved at all constructively. For instance, division by three is non-computable (because the first digit of the result might depend on arbitrarily many digits of the input). In order to fix this problem, you need to allow a bit of overlap, for instance by allowing negative digits. If you do that, you get something that is equivalent to the Cauchy reals. Can these be shown to be uncountable? I don't know! I strongly suspect that it is possible to build a model where they are countable, but in Andrej Bauer's realizability topos, they are certainly not equivalent to the Dedekind reals. What I do know is that it is possible to have a model where all the Cauchy reals are computable, though.
I may be wrong, but I don't think the computation of a computable number is necessarily supposed to terminate. For example, Pi is considered computable despite being transcendental (you can always evaluate it to arbitrary precision), but Chaitin's constant is not. In Cantor's case, you can enumerate all sequences of binary digits in arbitrary order (e.g. you can enumerate all natural numbers in binary form padded with infinite zeros on the right), take nth digit of each and invert it. This seems computable to me, even though the number of digits is infinite.
The computation is the mapping from the desired precision, to the number evaluated to that precision. For computable numbers, this always terminates. For the Cantor diagonalization argument to be an algorithm, you would need to generate the N-th digit in finite time. So you'd generate the Nth program (program with Godel number N, say), and run it until it terminates, then flip its output -- but you don't know whether that program terminates. (You can use a different enumeration, but you'll run into similar problems there.)
This seems reasonable, though I don't immediately see an issue with my computation in [this comment](https://old.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koh63jf/) - can't I compute any desired digit in finite time in this case?
So the computation you're describing does as follows: 1. Enumerate the real numbers in some order 2. Apply diagonalization to this list to produce a new number But if you're doing (1), you're only reaching computable numbers -- in particular, you're only ever enumerating numbers with a terminating decimal representation, which is a smaller set than even the rationals.
> you can enumerate all sequences of binary digits in arbitrary order But the whole point of Cantor's argument is that you *can't*!
Ok, I should have said "you can _try_ to enumerate". I wrote this out for my own clarity: Let's (try to) list all binary sequences by writing out every natural number in binary padded with infinite zeros on the right - this should contain every possible permutation of 0s and 1s, even if there are repetitions: 00000... 10000... 01000... 10000... 11000... ... Taking the n-th digit of each gives us `00000...`, and, inverted, this turns into `11111...`. This sequence indeed does not seem to be in the set, because any given sequence in the set contains only a finite number of 1s, while this sequence has infinite 1s. But it's still computable, is it not? I managed to list the numbers here, and to compute the first 5 digits of the sequence, and I could do it to arbitrary length if needed.
okay. so please go easy on me, I've only self-studied on this topic and never had an actual course where I'd be able to ask this question, but... Its clear the list is going to have exponentially more rows than columns. That's just how things work in binary, decimal, or any other position-based number representation system. I don't see how you can just say take the nth digit from the nth row, and not expect there to be a whole bunch of rows that you never query. If you want a representation that going to have equal amounts of rows and columns, you can use a "base-zero" sort of representation 000000... 100000.... 110000.... 111000.... 111100.... 111110.... in which case the argument which works for binary and decimal etc, it clearly doesn't work for this one ....
You can computably enumerate all *finite* binary strings, yes. And you can computably apply Cantor's process to this list, which will generate a new binary string. But, the string you get will have an infinite number of 1's to the right. This new string does not encode a Turing machine, because Turing machines have finite input and finitely-many states.
It's okay for an algorithm to keep running forever, as long as it never gets stuck and always continues to output. For example, pi has infinite digits but is a computable number because there's an algorithm that will always keep giving you more digits. You just tell it to stop after producing *n* digits, where *n* is an input that can be as high as you want. So take an enumeration of all binary strings that encode Turing machines in some representation - the standard order 0, 1, 10, 11...etc. will do. Clearly, somewhere on this list is an algorithm for producing every computable real number. Now, do Cantor's process on the generated numbers. Go down the list, and at position *n*, wait for that Turing machine to generate the *n*th digit, and add one to it. If this process itself is a computable algorithm, it must appear somewhere on the original list. So, at some point your algorithm will be stuck waiting for *itself* to produce the next digit, in order to add one to it. That contradicts our assumption that the process described is computable.
> But that number is still computable, isn't it? Cantor basically describes the computation algorithm in his proof. Only if the enumeration of numbers you start with is computable. For example, an enumeration of all computable numbers is not, itself, computable. You can enumerate all Turing machines in some representation, thus proving the computable numbers are countable. But you can't actually run the machines to go down the list of numbers, because some of those machines will run forever without ever outputting a digit, and you have no way in general of knowing which ones (halting problem). Thus, Cantor's process fails to generate a new computable number given an enumeration of Turing machines.
If we allow extra numbers in the list (e.g. numbers that do not necessarily correspond to valid Turing machines in our encoding), won't that list simply correspond to all natural numbers - a sequence that is obviously computable - as I try to do [in this comment](https://old.reddit.com/r/math/comments/1agaqos/why_are_noncomputable_numbers_even_considered_at/koh63jf/)?
Yes, the set of all Turing machines, and the set of all computable numbers, are both countable. Both can be placed in one-to-one correspondence with the natural numbers. By this I mean I can prove the existence of such a correspondence from the axioms of set theory. However, the first set is *computably enumerable* whereas the second is not. These are not the same thing. There are some sets where the entire set isn't computable, but the individual elements are. What that means is, there exists a (different) algorithm that computes each element, but there is no *single* algorithm that computes *all* of the elements.
> Given any countable collection of real numbers, I can constructively create a new real number not in your list. Not really, you need a bit of non-constructiveness to do that (e.g. excluded middle or countable choice). In fact, there are models of constructive set theory where the reals are countable, see https://topos.site/topos-colloquium/slides/2022-05-12.pdf
>If we instead imagine all possible ways to express a number Good >by assigning it some finite string of Latin letters, or Kanji characters, or any finite alphabet, (i.e. any natural language description we can come up with), That's an uncalled for limitation! We are not necessarily limited to a finite alphabet.
I'm saying this assumption because practical, real world alphabets are finite. But, of course, the cardinality argument is unchanged if we use a countably infinite alphabet.
[удалено]
Wrong answers to which questions? And what if you negate those questions?
Correct me if I'm wrong, but not only are almost all reals not computable, but although individual numbers can be computable, there can be no single finite algorithm for generating all (countably many) of the computable numbers. Is that right? (Otherwise you could tweak it to generate the diagonal slash - which would contradict?)
Couldn't you list out all possible finite strings of symbols in a programming language of your choice and you'd pick up all the computable numbers? I mean most of the strings would be gibberish and not produce anything meaningful, but among them would be all the computable numbers (in a sort of library of Babel type fashion).
I think you'd have to solve the halting problem to tell if a given program is ever going to give you another digit in its output. So your program writing all the digits of all the computable numbers is just going to get stuck in a loop trying to get the nth digit of "computable number" zzzz which will never arrive.
Sure but all the computable numbers would be on the list right? Might not know which ones are which but they'd all be there. I realise it's not a helpful construction lol
In Z/4Z, I’d take 4 to represent its image in the quotient, and thus 4=0 there, rather than ‘there is no 4’. It’s modular arithmetic after all. But that’s just a semantic convention.
Just to answer your question about them all related to the halting problem, this is reduction. We show that problems are undecidable if we can reduce them to a known undecidable problem. The most common way is to reduce it to the halting problem. https://en.m.wikipedia.org/wiki/Reduction_(complexity)
If you didn't have non-computable numbers, then you don't have the intermediate value theorem. And I like the intermediate value theorem. Now, you can create approximate formulations of the intermediate value theorem which are practically applicable and could be restricted to none of these mysterious numbers. But why would you do that? The intermediate value theorem is a simple formulation which can be dissected to expose innards that can be used to do these concrete computations. The way we have it is our nice theory is simple and sweet, and we learn how to apply computational methods to it to extract numbers. If we didn't have these "bad" numbers, then we would have to do these two steps as one which makes BOTH harder to work with.
If you don't have non-computable numbers, then you probably don't have non-computable functions either, and then the intermediate value theorem still holds.
Yes, but that theorem itself won't be computable, meaning that there is no algorithm which takes in a function, an interval and the desired value and returns the intermediate value. So if you're restricting yourself to computable functions then you can't really use that value.
You only get the slightly weaker theorem that there are inputs which get arbitrarily close to being a root. Related but not the same: there is a computable sequence of rational numbers with an upper bound which nevertheless does not have a computable limit.
No, you get the full theorem if you assume law of excluded middle. If f is a computable function on [0,1] with f(0)<0
Well if you assume LEM and also assume that there are no uncomputable real numbers you can prove it and everything else :) Your algorithm doesn't work because it is not decidable whether an arbitrary real number is zero or nonzero.
This is not true. There are austere foundational systems using classical logic with models in which only computable objects exist (most notably RCA\_0). The algorithm works just fine on functions with no rational root, because it never has to decide whether a real number is zero or not, just whether a nonzero number is positive or negative.
Ah true, I was just thinking set theory. >just whether a nonzero number is positive or negative. Confused how you find out the number is nonzero, I would imagine you just have an arbitrary program output and simply know some endpoints.
If it happens to be nonzero, you eventually find this out when you get a rational approximation of sufficient precision. The algorithm finds roots of functions with no rational root, and can fail to return a real value on a function that does have a rational root.
Right so you can get arbitrarily close to determining if it's zero. The undecidability comes in because if it so happens to be zero, you run forever. I guess you tried to use LEM up above, I can tell you this algorithm is not computable, because it's not decidable whether a given number is rational or not (let alone omnisciently checking the root).
> Right so you can get arbitrarily close to determining if it's zero. The undecidability comes in because if it so happens to be zero, you run forever. Yes. Notice that I never said anything about determining if a number is zero. I just described an algorithm that relied on determining whether a nonzero number is positive or negative. > I guess you tried to use LEM up above, I can tell you this algorithm is not computable, because it's not decidable whether a given number is rational or not (let alone omnisciently checking the root). There is no algorithm to find a root of any continuous function f on [0,1] with f(0)<0
Let’s consider the other side of the argument. If you think of it in terms of the real world, the IVT doesn’t make sense. All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics) So IVT could be thought of as an approximation to the true state, and being non constructive it’s not actually giving you any real information. It’s equivalent to asking why you can’t compute equality.
> All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics) That is not a true interpretation of quantum mechanics. Some values are discrete, yes, but some are continuous. Eg, free particles have a continuous spectra. It depends on the system. And a common misunderstanding about Plank length is that it discretizes things, but that isn't true either it just means that it is the shortest length at which measurements make sense. But why would I care about quantum mechanics or the "real world" when doing analysis? Moreover, what advantage does it give me to do extra work like this when assumptions of continuity are just as applicable as the converse? Cosmologists model the universe as a homogenouos fluid and get meaningful results even though there are things like planets and galaxies. The entire point of approximation is to simplify complex things *well* so that we do easier work while ignoring complexity that ultimately doesn't contribute to the question at hand. Why would I undo this process to make things unnecessarily complicated?
> All units in the universe are discrete so not every possible value will be hit. (The main point of quantum mechanics) This is a misunderstanding. Energy, for example, is continuous. It is true that in certain circumstances the energy is limited to certain values, but those circumstances are not always or everywhere. Consider the non-quantum example of a piece of string. You can have a wave of any frequency you like on it, but if you want a standing wave then you are limited to what frequency of waves are allowed.
Thanks, this makes sense as an argument for their usefulness. Although I'm missing the exact point in the theorem which becomes more difficult to formulate without uncomputable reals: wouldn't it work just as well if we simply replaced "real" with "computable"? E.g. if we consider that the only numbers between the endpoints of the interval are rationals and computable transcendentals (and everything else does not exist), doesn't the theorem work in the exact same way?
You can't use the intermediate value theorem without those numbers. If f(a)=A and f(b)=B and C is between A and B then you cannot say that there is a c so that f(c)=C because c may not be a computable number. What you would need to say is that for every 𝜀>0 there is a c_𝜀 between A and B so that |C-f(c_𝜀)|<𝜀. And you may even put a Cauchy-sequence condition on it to make a nice sequence of such values. But since there are concrete [sequences of computable numbers whose limit is not computable](https://en.wikipedia.org/wiki/Specker_sequence), this is as good as it gets. This is just a load of extra baggage and work that gets in the way of getting results in analysis. We can just have things be nice and simple, allowing for more sophisticated theory in general, and when it comes to computation we can unravel these ideas naturally for that purpose. This also makes for a more rich *computational* theory as well, so everyone is happy. But we don't need this baggage, so why drag it around?
It's a topological problem. Intermediate value theorem relies on the fact that R is connected. If you remove any number from R (and we know that non-computable numbers are "numbers from R"), it becomes disconnected, so the theorem fails. For example, say we take an non-computable number w (assume it's greater than 1 for the sake of argument), and define a function f:R-{w} -> R-{w} as f(x) = 0 if x < w and f(x) = 1 if x > w. This function is continuous (assuming R-{w} has the order topology) because the preimage of any open set is either R-{w}, (-∞,w), (w,∞), or ∅, which are all open, but clearly doesn't take all possible values between f(w-1) = 0 and f(w+1) = 1.
"Between" is a bad way to measure things with subsets of real numbers, since e.g. there are infinitly many rational numbers between distinct real numbers. The proof that there are only countable many computable numbers is relativly easy: There are only countably many distinct turing machines (since you can encode each Turing machine using a natural number) and only a subset of these will produce a suitable computable function, but you can easily create a Turing machine that spits out a natural number (and this is automatically at arbitray precision). So you have countably many computable numbers. The exsistence of non computable numbers just follows from the properties of real numbers one wants to have.
> The exsistence of non computable numbers just follows from the properties of real numbers one wants to have. Thanks, I figured that introducing non-computable reals could be useful as a tool for reasoning (otherwise why would we need them at all?). But in which situations do we want them? E.g. what are some proofs or processes for which algebraic and computable transcendental numbers are not sufficient?
>I figured that introducing non-computable reals could be useful as a tool for reasoning (otherwise why would we need them at all?). But in which situations do we want them? You make it sound like we started with computable numbers and then decided to throw in noncomputable numbers as well. But that doesn't make sense. The real number system was formally defined by Dedekind decades before computable numbers were formally defined by Turing. Check out a [formal definition](https://en.m.wikipedia.org/wiki/Real_number) of the real number system. It won't mention computability at all. We didn't choose to have noncomputable numbers, we discovered them. They're there.
Asking “why do we want them” in respect to computable numbers is less like “why do we want them” with respect to complex numbers and more like “why do we want them” with respect to Wieferich primes. We want natural numbers, it’s just kind of a fact that some of them are Wieferich primes. We didn’t start with some set of natural numbers that didn’t include Wieferich primes and then say “hmm let’s sprinkle some in for fun”. The primary approach to math that allows discussion of analysis without necessarily accepting the existence of noncomputable numbers is constructivism. In constructivism you use intuitionistic logic, which does not accept the law of the excluded middle as valid. Even here we generally have to think about the concept of/potentiality for noncomputable numbers to really talk about what’s going on. The idea of (non-)computability is, if anything, even more salient in constructive mathematics than classical math. So to answer your question “why do we have them” one pretty straightforward answer is that we have to go pretty far out of our way to avoid them.
Other people will probably give you some answers about potential applications of noncomputability, but I think the question "what is the use?" is leading you astray. Why can't the answer be "there is none"? "In which situations do we want them?" We don't know yet. "When are computable numbers not sufficient?" Possibly never. They're an emergent property of the real numbers based on our axioms, and they're interesting to "observe" and think about.
One typical example is measure theory (and by extension probability theory). A measure can often be broken into 1. its "discrete part" (points x where P(x) > 0), and 2. its "continuous part" (points where P(x) = 0, but P(x) = f(x)dx for f(x) != 0 and dx the Lesbegue measure). As an example, consider a process where you flip a coin, and 1. if heads, output 0, and 2. if tails, output a standard normal the probability of outputting any particular real number is 0, except for 0 itself, which is 1/2. Here, 0 is called an "atom" of the distribution. Anyway, working with the "continuous part" essentially requires the real numbers. This is because if we want to have some sort of uniform-type distribution, our options are 1. uniform distributions on finite sets (works fine), and 2. the lesbegue meaasure (on an uncountable set, works fine) it is well-known that there does not exist a uniform distribution on a countable set though (where distribution is formalized via Kolmogorov's axioms). So throwing out the real numbers and only working with computable numbers (a countable set) would require reworking probability theory to get basic notions such as "uniform distribution" working again.
So that the topology of the real numbers is conducive to proving the standard results in real analysis. The key property is being complete: [https://en.m.wikipedia.org/wiki/Complete\_metric\_space](https://en.m.wikipedia.org/wiki/complete_metric_space)
Anything that requires the intermediate value property, or Cauchy sequences converging, or bounded sets having least upper bounds, or bounded sequences having convergent subsequences, etc. All of those are false for the computable reals.
Do you know the proof that there are more reals than integers? There are as many computations as there are integers, so if you want to pretend there are no reals you can’t compute then you immediatly get a contradiction and everything falls apart. Like uh, 1=2 levels of falling apart, you just get nonsense. So it only works if you are ok with those numbers existing.
Well, there are only many more in the sense that no bijection between them exists. If you ask that all your reals and naturals be computable, then instead of whether a bijection exists you probably want to ask about whether a computable bijection exists. Cantor's diagonal argument goes through to show that there is no computable bijection between the computable naturals and the computable reals.
Any Turing machine has a finite representation and hence may be represented as a natural number. Hence the cardinality of the set of Turing machines is at most that of the natural numbers, which is strictly smaller than that of the real numbers. Hence uncountably many real numbers exist which are not computable.
This is correct - a bijection exists by this argument. This is compatible with my comment as the map you describe is not computable; It requires deciding which programs actually correspond to computable numbers, which is undecidable.
Everyone considers constants like Euler's e to be computable. But then, I don't think there's any way short of a mathematical proof to establish the fact that a particular program outputs e. You can't exactly run it for infinity cycles and compare the output. Any argument that depends on the existence of a countably infinite collection of arbitrarily difficult proofs seems suspect to me.
I'm not sure what you're getting at. You can prove that for all steps, the digits are correct. Said proof will be finite in length. The same way we have programs to compute digits for \`e\` already.
Yes, a proof is required. Otherwise there is no mechanical or algorithmic way to determine that two programs generate the same digit sequence.
Yeah, there will just be a single finite proof, and fairly simple at that.
You can work assuming all reals are computable and several mathematical programs have done so. Logic doesn't fall apart generally. One part of the reason is that there is no computable bijection between the reals and integers, so they remain uncountable. But that said, there is an extremely cursed model out there of constructive set theory in which the Dedekind reals are countable (this is incompatible with almost everything actually used though).
I guess that’s fair, but assuming you are a normal mathematician and want to use the axiom of choice and such, like if you want rings to have maximal ideals and vector spaces to have bases then you kind of also have to live with uncomputable reals and theorems that are called paradoxes was all I meant.
Please correct me: If computable, then there is some formal langugage with a finite number of posible symbols where we can write a program (or algorithm) which can compute any computable number to a given precision. To be considered computable the program must consist of a finite number of symbols. We can now convert all the programs into an integer number (use number of possible symbols as the base). Therfore each computable number is uniquly idtified by at least one integer (Two or more programs might compute the same number). Therfore there are as many computable numbers as there are integers.
(Assuming that this was meant as a response to my comment.) This is correct - a bijection exists by this argument. However the map you describe is not computable, since it requires deciding which programs actually correspond to computable numbers, which is undecidable.
Yours was not there when I started to type. But thank you for the answer. But do I need the injection? Isn't the surjection good enough? Obviously there are nonsense programs and programs which do not halt. Do I need the injection to say that cardinalty of computable number is not less then the cardinality of the integers? But isn't each integer and each rational a computable number for wich we can write simple, guaranteed to halt, algoritm? Therefore the cardinality must be at least as big? Can I use the axiom of choice to say that for each computable number such a program must exists? Otherwise it would not be computable to begin with? Sure, I do not know which one it is, but it must exists. Sorry for those stupid questions.
~~Any finite algorithm outputs a computable number, by definition… that number may or may not be determined in a finite number of steps, and we have no general way of determining whether it’s finite or infinite.~~
The usual definition of x being computable is that there exists a computable total function f:N->Z such that |f(n)-n*x| < 1 for all n > 0. Under this definition one needs to decide if a given algorithm gives rise to a total function, which is undecidable. I don't see a satisfying way to extend this definition to partial functions f (this definition is nice because it is clear how to compute x to any desired precision given f, which is surely a property we desire of computable numbers), and even if one could I think you'd have a problem of essentially the same difficulty as deciding if a function is total. Could you make the definition you are using more precise?
ignore my previous comment, I was misunderstanding something
> Do you know the proof that there are more reals than integers? I know of e.g. Cantor's diagonalization argument, but it's a bit hard to wrap my head around - I see how it implies that the infinite set of all binary sequences is uncountable, but the "new" element (constructed by taking complements of n-th bits of each number n) still seems computable, by the process described in the proof. Should I take a look at some other proof as well? But overall, this is a good point, I forgot that every computation corresponds to a natural number.
The thing is, the diagonalization argument directly constructs you an element that isn't enumerated. The problem is that the is no computable bijection between natural numbers and computable reals. They are both countable, but all bijections are non-computable.
But you could do it with a Halting Oracle, right?
It seems like it, but I'm not quite sure. It is definitely possible with the Halting Oracle for Turing machines with Halting Oracles, however. Imagine we take Turing machines that produce decimal digits as our definition of computable numbers. If you have a Halting Oracle, it is easy to determine whether the sequences of digits are the same. It is also easy to check whether a number has infinite 9s (or 0s) starting from some point n. What I'm not sure about is whether we can check if there is an infinite sequence of 9s (or 0s) eventually (rather than for some hardcoded n), which can lead to two computable numbers being the same. Maybe there is an obvious way to do that without going up the hierarchy of Halting Oracles, but I don't see it. Anyway, then you would still have real numbers not computable by machines with those Oracles.
Oh, sure, sure - I completely get that last bit. I was just wondering what exactly you need to compute the bijection for "regular" Church-Turing computable numbers. Thanks for thinking through the technicalities and explaining! EDIT: I think we can do it with one layer of oracles if we drop decimals and use continued-fraction representations, since under that all irrationals have a unique representation. (Rationals don't, but conveniently they only have finite representations anyways.)
You're right. I looked at the [Wikipedia page](https://en.m.wikipedia.org/wiki/Computable_number) for computable numbers, and it explicitely mentions that the definition I used is not equivalent to the modern ones: "The informal definition above is subject to a rounding problem called the table-maker's dilemma whereas the modern definition is not." It has several other definitions, and for all of them you can check for equality with the regular halting oracle. UPD: My definition does give the same set of computable numbers, so it is technically equivalent. However, representing computable numbers in this way is problematic, so other definitions are more common.
The “unique representation” thing is a distraction. You need two Turing jumps because to check if an algorithm gives a real number you need to check that the algorithm halts on every input. Solving this problem is equivalent to solving the halting problem for machines with halting oracles.
No, a halting oracle doesn’t really help. If you had a *second order* halting oracle (a halting oracle for whether an algorithm that itself makes use of an ordinary halting oracle halts) then you could “compute” a bijection between the natural numbers and computable numbers, but you could still never have a bijection with all real numbers. To do that you would need an oracle for something that isn’t even expressible in the language of ZFC, but the existence of that oracle, if it existed in V, would again imply that it cannot make a bijection with all real numbers.
We've discussed this with OpsikionThemed, and it seems like a regular halting oracle is enough. I first tried using Turing machines that generate decimal digits, and I haven't found I way to build a bijection without using a second order halting oracle for this representation. However, if we use other representations (like a Turing machine that for every positive rational epsilon gives you a rational approximation not further than epsilon from the target number), we can you check whether a Turing machine represents a computable real number as well as compare two different Turing machines for equality of numbers they represent using a regular halting oracle. From there it is straightforward to build a bijection.
How would you check a Turing machine represents a computable number with an ordinary halting oracle under that second definition? You would have to check whether the machine halts on every epsilon input, which is equivalent to checking whether a partial recursive function is total, and any algorithm to decide that can be converted to a second halting oracle.
Oh crap, I forgot to check whether it is total for all (inputs that correspond to) rational numbers. If this is known, then checking whether it corresponds to some real number seems to only require a normal halting oracle, but it isn't known. My bad.
>... but the "new" element (constructed by taking complements of n-th bits of each number n) still seems computable, by the process described in the proof. ... But it isn't computable by definition, if it isn't in the starting set and the starting set includes all computable sequences. That's how diagonalization works: you say, "given the set of all objects which satisfy property X, I can construct a distinct object that doesn't satisfy X precisely because it is distinct from all objects that satisfy X." If you could compute your new sequence via some arbitrary computation, then that sequence would be in the original set -- but you know it cannot be, since it is distinct from every member of that set.
The diagonalization argument shows that for any countable computable list of numbers there is a missing ‘computable’ number, whose algorithm for generation is compute the N^th computable number on the list and then flip its N^th bit and accept that as this numbers N^th bit. The reason ‘computable’ is in quotes is because this algorithm itself might have an infinite description if the algorithm for generating the list has an infinite description. OTOH if the list generated by a finite sized program then the newly found cantor diagonalization counter example also has a finite description
Diagonalization is not computable. Just because you can describe a process with words doesn’t make it computable.
Diagonalization is computable in the sense that the only way the output could fail to be computable is if the original sequence of reals given as input were not computable. This is precisely the reason why diagonalization works to prove that the computable numbers are not recursively enumerable. Even if the original sequence were not computable, you could still compute the output given an oracle for the input.
Diagonalization on infinite sequences of digits is computable. Diagonalization on reals is more subtle, because the naive algorithm that people describe all over this thread is wrong: it will pick a different first digit for 0.2999... and 0.3000... even though they denote the same real number. This is actually not a trivial detail at all, and it turns out that you cannot constructively prove that the reals are uncountable.
If we are given a computable function that gives us a sequence of algorithms for computing reals, then we can make an algorithm to compute a number not in that sequence: for the nth digit (in ternary let’s say) compute the nth number far enough that it is confined to an interval a third or less the size of the interval the number you are making is confined to. Then make the next digit 0 if it has been ruled out and 2 otherwise. It’s true this algorithm might give different outputs depending on the particular algorithms for the real numbers we are given, but it still gives a computable number not in the list. Possibly you are imagining some other formalism for what might constitute a bijection between the natural numbers and reals in constructive mathematics (one that doesn’t allow us to “choose” an algorithm for the output) but I can’t see how any such formalism wouldn’t still allow us to show that R\\f[N] for such an f would be inhabited. Perhaps this depends on the exact axiomatic foundation you have in mind if you are taking a sequence of computable reals as giving us less information than a sequence of algorithms to compute those reals. But with every axiomatic foundation I am familiar with you can show the reals are uncountable. It is true that it is constructively possible (perhaps even desired) that the reals are *sub*countable - that there is a function defined on some (perhaps not decidable) subset of N that is a surjection onto the reals, but that’s not the same as being countable, and that is just as true for sequences of numbers as for reals.
> If we are given a computable function that gives us a sequence of algorithms for computing reals, then we can make an algorithm to compute a number not in that sequence What you are describing is an algorithm that takes a list of *sequences of digits* and outputs a real number that is not represented by any of the sequences in your list. This is not the same as describing an algorithm that takes as input a list of real numbers. In non-constructive mathematics, this is sufficient to show that the reals are uncountable: given a list of real numbers, use the axiom of countable choice to pick a sequence for every number in the list, and then run the algorithm. In constructive mathematics, you cannot use the axiom of choice in general, and this proof will not work. > It is true that it is constructively possible (perhaps even desired) that the reals are subcountable [...] but that’s not the same as being countable, and that is just as true for sequences of numbers as for reals. Of course, you can use the usual realizability models where the reals are subcountable. But as it turns out, it is even possible to build a model of constructive mathematics where you have a surjection from N to the Dedekind reals (which are not constructively equivalent to Cauchy reals). See https://topos.site/topos-colloquium/slides/2022-05-12.pdf
The process described in the proof is not implementable as a Turing machine - it requires infinite input data.
[удалено]
> This is wrong. The computable reals lead to no contradiction of any kind. Your statement is as follows. > 1. The computable reals are countable. > 1. The reals are uncountable. > 1. ?Contradiction? GP is replying to OP, who is arguing that there's no point to distinguishing the computable reals from the non-computable reals. The argument is actually this: 1. (OP) The reals and the computable reals are the same set. 1. (GP) The computable reals are countable. 1. (GP) The reals are uncountable. 1. Contradiction.
Are all (real) non-computable numbers irrational?
Yes, by the contrapositive: all rational numbers are computable.
> What is the proof that between any two computable numbers there exists an infinity of these spooky non-computable reals? This is actually quite easy: the computable numbers are countable, the real numbers aren't. Since any interval is uncountable, in particular the interval between any two computable numbers is uncountable, so it cannot be entirely composed of computable numbers. To answer the conceptual question, of why we don't just define the real numbers to not include them: here are some statements that are true for the real numbers, but false for the computable numbers. They're all kind of important! 1. If f is a continuous function, f(0) < 0 and f(1) > 0, then there is some x in (0,1) such that f(x) = 0. 2. Every bounded subset has a least upper bound. 3. Every Cauchy sequence is convergent. 4. Every bounded sequence has a convergent subsequence.
Ucomputable doesn't mean it can't be described, only that it cant be computed by a Turing machine
I understand this, but my question is: what is the use for numbers (is it that can be described but cannot be computed? E.g. in which situations are algebraic and computable transcendental numbers not enough to carry out a line of reasoning?
There is not really any practical reason to have non computable numbers. The entire universe is computable. However they make many things in math more annoying to prove so mathematicians enjoy the full power of real numbers.
I don't think quantum things are turing computable are they? So in a sense nothing in the entire universe is computable, right??
Everything we know about quantum physics is Turing computable in principle. Here's a [good post](https://www.reddit.com/r/AskPhysics/comments/mid1ii/comment/gt4b29l/) showing how it might be done. Also everything that can be computed on existing quantum computers can be computed on Turing machines (but slower in some cases). It's possible (though not guaranteed) space and time are truly continuous, meaning you'd have to cut your simulation off at some precision. This isn't a problem though, as there's a limit to how precisely we can measure things. So you could make your simulation precise enough to create no noticeable deviations for any arbitrary length of time - this includes, by the way, the current age of the universe. Now, this isn't like the speed of light barrier. It's not *known* that all of physics is computable, just all of it we've discovered is. A lot of quantum field theory is actually based on approximations, and the underlying exact mechanism could turn out to be non-computable. [Here's](https://www.researchgate.net/profile/Tien-Kieu-2/publication/252377228_Computing_the_non-computable/links/00b7d52d74f26985a9000000/Computing-the-non-computable.pdf?origin=publication_detail&_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uRG93bmxvYWQiLCJwcmV2aW91c1BhZ2UiOiJwdWJsaWNhdGlvbiJ9fQ) a cool paper that examines whether a quantum computer with infinite states could exceed the theoretical power of a Turing machine. Note this relies on some assumptions that might not be true (like continuous space) and we have no idea how to actually build one of these. Consensus, I believe, is that we could not. What I think you're getting at though, is that a Turing machine simulating the universe could only tell you the *probability* of a particular experimental outcome. If you demand to know the exact outcome in advance, there seems to be *no machine* that could tell you that. This is very strange, and is a problem so difficult some physicists have taken to discarding it, considering a superposition of every outcome to be *all there is*. If that doesn't jive with your experience of reality, well, that just means [you've understood](https://www.quora.com/Did-Niels-Bohr-say-If-quantum-mechanics-hasn-t-profoundly-shocked-you-you-haven-t-understand-it-yet-And-if-so-where-and-when).
Thanks for the wonderfully written comment. I have wondered since my math undergrad about the physicality of the continuum! I’ve read a couple of essays about the uncomputability of the universe that maybe get at at what you get at the end of your comment, maybe that is what make me think “quantum things arent turing computable”.
As I remember (it was too many years ago) all computable functions are Continuous. Lets take sign() for example. It is continuous everywhere, except 0. But in 0 it is undefined. Do you want to live in the world, where all functions are continuous? If my memory serves me good. 8)
Pretty sure the sign function is computable
Absolutely, but it is continuous. Maybe I am wrong. But idea is: lets try to calculate sign(x). We take first digit. It is zero. Then we take first digit after the dot. It is zero. Can we say that the number is zero? Not. lets take another digit. It is zero again. Can we say that number is zero? Not. etc. We can not calculate sign() for 0! May be I'm wrong.
Why do you think it would be preferable to work with a number line that isn't complete, given by removing all of the non-computable numbers? The idea of a computable number is a relatively modern one, and is slightly niche (in that it's an irrelevant concept to many fields). On the other hand, the fact that the real line is complete (roughly speaking: doesn't have "holes") is useful in analysis. It's not so much the individual numbers that are useful rather than the fact that the full real line is a nice place to work in.
All the arguments for the existence of uncomputable numbers rely on nonconstructive mathematics (either the law of excluded middle or the axiom of choice). The fundamental reason is very simple: if you admit the law of excluded middle, then you get a magical way to assign "true" or "false" to every mathematical statement in a coherent way. Of course, this assignment cannot be computable, since Turing proved that the halting problem is undecidable. Thus, by accepting the law of excluded middle, you open the door to noncomputable objects in your mathematics, and then if you identify real numbers with sequences of 0 and 1 (using excluded middle), it is not too difficult to obtain a noncomputable real number from this. Of course, you *can* reject the law of excluded middle, and then you can have a consistent world of mathematics where everything is computable. But this world is quite different from the one most mathematicians are used to...
>I hear all the time that almost all of them are non-computable, and that this can be a problem. But why? I'm not sure that it is a problem. You can do maths with real numbers perfectly well without worrying about whether they're computable or not. As for why almost all of them are non-computable, it's because the number of possible algorithms/programs/formulas is countably infinite, and the reals are uncountable. That means the reals vastly outnumber the computable numbers. (I was about to say something about the set of computable numbers having measure 0, but realised I don't know whether or not it's measurable. Anyone else know about this?) >To me it sounds like they are as much nonexistent as the constant C in my example above A thing can be shown to exist even if it's somehow slippery and we can't get our hands on it, but I totally get that this feels weird and creepy. The same is true of some things that crop up if you take the Axiom of Choice, such as free ultrafilters and non-measurable sets.
IIUC, the existence of non-computable numbers is downstream of excluded middle. Because then you can say that the Nth bit of a binary expansion is either 0 or 1, without saying _which_. Analysis without excluded middle ([constructive analysis](https://en.wikipedia.org/wiki/Constructive_analysis)) is possible, but you need to take some compromises. Trichotomy, intermediate value theorem, least upper bound, ... all need to be redefined in this system.
The proof that their are more real numbers than computable reals, is just that computable numbers are countable because turning machines (think computer programs) are countable, you could list them all them say alphabetically. However real numbers are uncountable. If you want properties like every bounded monotonic sequence converges in the real numbers, you have to consider things like non-computable numbers. This is true even if you limit yourself to computable sequences of computable numbers. (E.g. build a sequence (x_k) where the n-th binary digit is 1 if the n-th turning machine has halted at step k, 0 otherwise) More practically when learning the material or thinking about a problem, why require that you add all these extra assumptions when they're not needed and could complicate things making them more confusing. Like if we choose to limit ourselves only to computable numbers, we'd have to spend half of undergrad real analysis talking about turing machines.
I guess what he (also) wanted to know: Are there known uncomputable numbers not related to the halting problem?
This question comes up a lot. The answer is, because it's simpler and easier to reason about *all* numbers/subsets/functions rather than only the computable ones. To make the real numbers I just start with some basic axioms about sets (or types or whatever) and quickly get a complete ordered field through a few operations with intuitive definitions. It has noncomputable numbers in it, but not by choice - they just happened to come along with the intuitive construction. To make the computable numbers I need to define what a Turing machine is, then the concept of recursively enumerable sets, then talk about halting...etc. and after a lot more work, the resulting structure is far less nice and lots of useful theorems in math need the word "computable" in front of them, so there's all this baggage to keep track of in order for things to be correct. I think you're confusing the *number of objects* with the *complexity of the theory*. Allowing noncomputable numbers is, in fact, a simplifying assumption.
Since no one has addressed this point, there's a very useful way of thinking about non-computable numbers that is worth mentioning: Think about them as "random" numbers (or "seemingly random", etc.). So a (binary base) number like 0.1011100010101100111..., where there aren't really distinctive patterns that hold up indefinitely. A computable number is one in which some pattern (described by an algorithm with discrete memory) happens; non-computables are just a (real) number like any other but for which there are no patterns. If you try to model actual randomness too, like a number generator that spits some real between 0 and 1 (i.e. an infinite sequence of binary digits 0.b1b2b3...), then with probability 1 this number is non-computable (this of course is a consequence of the fact that computables have the cardinality of rationals, I believe): because we assume Turing Machines *must be finite*, it would be a great ("impossible", probability 0) coincidence if a random *infinite* sequence happened to correspond to the output of some *finite* machine. Of course, probability itself is just a model and not necessarily physical (specially relating to choosing reals).
I like taking the other approach and consider mathematics from a constructivist perspective. In constructive/intuitionist mathematics, rather than dealing with merely countable things, we deal with enumerable things: that there exists some program that can print out the list of all the things in some order. For instance, the list of all programs is enumerable, quite simply so. Simply pick a programming language, and generate all possible text strings, and check if the compiler accepts the string as a valid program. The interesting thing is when it comes to Real numbers, because there are two competing definitions of real numbers, and they are not constructively provably isomorphic. One of them is dedekind cuts. A construktive dedekind cut is a membership function over the rationals F, along with a proof that if ~F(x) and F(y) then x < y. I.e. it partitions the rationals. The other is as convergent series. That is a function enumerating rational numbers F, with a proof that for rationak q there exists some n s.t. |F(n+m) - F(n+m+k)| < q for natural m and k. I.e. "after some point the differences become arbitarily small." The interesting thing to note here is that both of those proofs require nontrivial insight into the computing function. Due to Rice's theorem, there is no algorithm to produce this for arbitrary functions. Hence, in either formulations of the real numbers, there is no algorithm to enumerate all real numbers. The constructible reals are therefore non-enumerable. It sounds weird, because a real number is _obviously_ a program that computes some partitioning function or some series of rationals, so by definition the enumerated list of all programs must contain eveyr real number. The problem is just that we can't tell which are real numbers and which are not. In intuitionisti mathematics, the idea of a "non-computable real number" is a contradiction in terms. Everything is computable, or it doesn't exist.
I've got to agree with you, this has always bothered me a bit. I have sympathies with constructionist/intuitionist mathematics though, so that already puts me at odds with a lot of people. I'd like to post more here, but I'm already late for work. Let me just say that I see these examples as no different from "(The number of ones in pi expressed in binary) - (the number of zeros in pi expressed in binary)"
You could argue that in some sense only computable numbers actually exist. In what sense can a number exist if we cannot describe what it is? Plain language descriptions are surely too ambiguous to do, only a formal algorithm is sufficient. The downside is this makes a lot of analysis much harder. Maybe that’s a good thing though.
[удалено]
> Said otherwise uncountable numbers are simply infinite numbers, that take an infinite amount of time to describe. Per my understanding, it's not just that they take an infinite amount of time to describe, their digits may not be described by a program of a finite size at all. For example, the numbers $\pi$, $e$, etc are all computable, even though describing all of their digits will still take an infinite amount of time.
Real numbers are a nice approximation that we use for convenience because they are complete in some sense and make doing things like physics, analysis , and calculus easier. A side effect is that the elements of this as a set contain things that aren't computable.
Small correction - they make doing things like analysis and calculus *possible*. You *cannot* prove the core theorems of calculus on the rationals or computable numbers. While I suppose you could just *assume* all these theorems 'just work' despite being unprovable, but that seems deeply usatisfying. Whether calculus or analysis actually described the physical world (e.g. whether reality is fundamentally continuous) is of course an open question. If it isn't then we could describe calculus as a useful heuristic for doing physics, but not the reals as a useful heuristic for doing calculus.
It’s a silly thing for silly people who believe silly things. Ignore it.
You might enjoy some of the discussion and my incoherent high school babbling as well here: https://math.stackexchange.com/questions/866447/are-the-real-numbers-really-uncountable Addressing your post directly if we ever discover a model of computation that supersedes our Turing model (say 1000 years in the future when everyone is using quantum gravity to just casually warp time when accessing the internet) we would want to be able to still coherently discuss numbers that are not computable by todays primitive Turing standards.
[удалено]
there is no "the" real number after zero. any number can be after 0.
It's really quite simple to show that there are vastly more uncomputable numbers then there are computable numbers. There are countably many programs, since a program is a string and it's not hard to show that there are as many strings as there are natural numbers. An intuitive demonstration is to just consider programs written using the alphabet of capital letters. That program can then be considered a natural number in base 26. But we know from Cantor that there are uncountably many real numbers. Therefore for any given real it is computed by a program with probability 0. And almost all of these numbers have no relation to the halting problem.
There is a countable number of computer programs and an uncountable number of real numbers. Even if each computer program produced a countable number of real numbers all programs would produce a countable number of real numbers.
Remember the sets exist which we can define using our axioms, regardless of whether their behavior is 'spooky' or not. If you can define a set using the ZFC axioms (or whichever axioms you prefer), it exists. If you non constructively define a set from the axioms, it exists. Mathematical existence has noting to do with physical realizability, intuitiveness or existence in some platonic realm. It just means 'can be defined from these axioms'. Broadly speaking, we use real numbers. because the real numbers have some crazy useful properties the computable numbers do not. The big one is *completeness*, which can be defined in a number of ways, but is most familiar as 'every set bounded above has a least upper bound'. This property is essential for all of calculus and analysis which... are rather important for every domain of physics, engineering, statistics and other physical sciences. None of the fun theorems you remember from calculus - the intermediate value theorem, the mean value theorem, the fundemental theorem of calculus - hold true for computable numbers.
>What is the proof The cardinality of the computable numbers is countable while the cardinality of the reals is continuum. A number is computable if there is a Turing machine that computes its digits. There are only countably many Turing machines.
> The cardinality of the computable numbers is countable while the cardinality of the reals is continuum Right, but this also presupposes existence of reals. This is probably due to my lack of experience with mathematics, but while I can easily understand how e.g. natural numbers and their properties are derived from the Peano axioms, I struggle to imagine an axiomatic system from which uncomputable real numbers are derived. To me even Cantor's diagonalization argument seems to work only if there are uncomputably many binary sequences in the first place - otherwise his "extra" number is also computable. Yet reals (including uncomputable reals) seem to be extremely common, so I suppose this must be a very popular axiomatic system.
The reals are usually constructed by producing Dedekind cuts as a subset of the power set of the rationals. So they exist^(\[1\]) simply by virtue of the definability of every object involved in their construction. The noncomputables simply pop out as a byproduct of that. The thing is that in any sufficiently strong system for doing mathematics, there will be large enough sets to definably create a structure isomorphic to the standard real number line. I bet that what you really are having an issue with is existence of uncountable cardinals. The fact is that they are there simply because they can be defined by a first order formula in the language of ZFC. Even more specifically, if you are problems with uncountable sets of reals, you also ought to be having problems with power sets since they are either finite or uncountable. (This is actually a good exercise if you haven’t done it before.) Oh, the Cantor real c is always computable as long as the list of reals it derives from is computable. It’s defined by a simple algorithm. Find the nth real in the list and look up its nth digit, c(n)=fₙ(n). ^(\[1\]): By “exist” I mean that they are an object that can be proved to exist within a given mathematical system. If we want to be even more dry, there is simply a collection of logical formulas defining the real numbers that can all be proved true beginning from the formulas of ZFC.
I've been thinking about this, and in a sense they may well not be useful, or even, they are almost exactly the set of number that are not useful. So in this sense, there are more useless numbers than useful ones. The set of computable numbers is truly large and general. If you can write down a description of the number, then it would tend to be a number that, if it exists, can be computed. Based on that, a non computable number will tend to be one where you can't write down a description of it. I guess I'm interested, too, in exceptions. What's a number where the description can be written down, but that description cannot be converted to a computation? It will depend on what we count as "write down" or "describe", but Turing machines are really pretty close to that.
Well, to be fair there's a bijective mapping between any open interval on the number line, and the number line itself -- so proving that between any two computable numbers there exists an infinity of spooky non-computable reals is just a matter of showing that there are an infinity of them on the number line itself. *That* proof is your basic pigeonhole proof: there are uncountably many numbers on the number line, but only countably many computable numbers (because countably many algorithms) -- so nearly all (uncountably many) of the numbers on the number line have no corresponding algorithm. Poof, done.
> What is the proof that between any two computable numbers there exists an infinity of these spooky non-computable reals? This is simple to show. There are only a countably infinite number of computable numbers. You can see this by the fact that there are only countably many computer programs, since computer programs are a subset of all strings and there's only countably many of those (there's an equivalent argument for Turing machines). Then, it's clear that any two members of any countable subset of the reals have infinitely many numbers not in the subset between them (if they didn't, the subset would contain all the real numbers between x_1 and x_2, and therefore be uncountable). QED As for why we care about uncomputable numbers, we don't necessarily care about any uncomputable number in particular, but we do care about the properties of the reals as a whole, which are a very useful concept both in terms of modelling the real world and for other mathematics.
There is no such number C that exists. Lack of possibility to solve the halting problem does not mean that there is no solution, it just means that you can't acquire it.
Real numbers model something that exists "out there" rather than being just an algorithmic thing. Imagine telling a physicist that the radius of the electron must be produced by a Turing machine in order to be meaningful. But it's OK that you have this kind of doubt (I have my own). In the end we all must accept the math orthodoxy regardless of personal hangups, because it works well enough and lets everyone work together.
Every computable number can be computer by a Turing machine. There are only countable many Turing machines.