5 ms·

> But what would be an example of an uncomputable number? That’s a good question. Most obviously, we could be talking about numbers that encode the solution to

by Reubend 8mo ago

> But what would be an example of an uncomputable number? That’s a good question. Most obviously, we could be talking about numbers that encode the solution to the halting problem. It would lead to a paradox to have a computer program that allows us to decide, in the general case, whether a given computer program halts. So, if a procedure to approximate a particular real requires solving the halting problem, we can’t have that. This doesn’t make sense to me. Given that there’s no generic way to compute halting, how would we make the leap to saying that there’s a specific number which represents the solution to that problem?

throwaway27448 8mo ago
I assume this refers to Chaitin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
- deleted 8mo ago
  [deleted]
yorwba 8mo ago
Any given computation either halts or it doesn't. You can encode that information in a single bit, as a specific number. Since there is a countably infinite number of possible computations, you'd need a countably infinite number of bits. So you can never find enough storage to hold the full solution of the halting problem in the real world. But you can find enough storage in a real number. Because real numbers can have a countably infinite number of digits after the decimal point. So you can stuff your countably infinite number of bits representing the solution of the halting problem in there. Which specific real number you get depends on the details of the encoding, but it's definitely some real number. And it cannot be computed, because if it could, you could read the solution to the halting problem off its digits, but the halting problem is known to be uncomputable.
moritzwarhier 8mo ago
I'm not a mathematician, but constructivists aim to define mathematics without uncomputable numbers, see https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis and https://en.wikipedia.org/wiki/Computable_number#Use_in_place_of_the_reals https://en.wikipedia.org/wiki/Computable_number#Use_in_place... As far as I can understand, the set of all computable numbers (including all algebraic numbers and many transcendental numbers, such as Pi), even has the same cardinality as the rationals, and thus the natural numbers. The reason we consider uncomputable numbers "numbers" include some definitions about infinite series and analysis that would need to have stricter requirements for convergence when looking only at the computable numbers, not the real numbers. And defining a concrete bijection between the natural numbers and the computable numbers would also solve the halting problem and is impossible, we only know that such a bijection exists: defining it would mean to have an algorithm that can prove for a specific Turing machine that it is the minimal one computing it's output, among a given set of universal Turing machines / UTM encoding. (please take this with a grain of salt as I'm stepping outside the bounds of my knowledge here)
lich_king 8mo ago
Busy beavers are a classic example. They're mostly-hypothetical numbers that tell you "if any Turing machine of size s runs for longer than this, it doesn't halt." There's a link to that in the sentence you quoted.
- tromp 8mo ago
  Individual busy beavers BB(n) are finite natural numbers and thus quite computable. A related uncomputable number is the halting probability Omega of a universal prefix machine (whose programs form a prefix free set). By collecting enough halting programs to accumulate a probability of at least the first n bits of Omega (as a binary fraction), you will have determined all programs of length at most n that halt and thus also the busy beavers up to that size.
  - lich_king 8mo ago
    "A real number in which each decimal digit at position n is equal to the first digit of BB(n)." Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.
    - cofunctor 8mo ago
      Such an algorithm would be computing the (uncomputable) function BB : Nat -> Nat, and not the computability of a given BB(n). Every fixed natural number is computable: just print out the number. This is a subtlety of doing computability theory in classical foundations. It’s akin to how every concrete instance P(x) of a decision problem P is decidable: just use excluded middle to figure out if P(x) is true or false, and then use the Turing machine that immediately accepts or rejects regardless of input. This is very different from writing a machine that has to decide P(x) when given x as an input!
    - tromp 8mo ago
      I did just that for the first 37 BB numbers at https://oeis.org/A333479 https://oeis.org/A333479 I could write a few more given enough time, but writing later ones will take someone more omnipotent than me. You may be confusing the true statement "for each n, BB(n) is computable" with the false statement "\n -> BB(n) is computable".
leni536 8mo ago
Enumerate all well formed programs in order. For programs that halt assign the digit 0, and for the ones that don't, the digit 1. Put the digits after a decimal point and interpret in binary.
- Reubend 7mo ago
  Very interesting! Thank you for explaining this.
deleted 8mo ago
[deleted]
cofunctor 8mo ago
Here’s a nice concrete construction. To start, fix some enumeration ϕ of Turing machines. Let’s define a sequence of rational numbers x_k as $\sum_{i=0}^k 2^{-(i+1)} * halts(ϕ(i),k)$, where $halts(M,k)$ returns 1 if the machine M halts before taking k steps when fed the empty tape, and 0 otherwise. This is perfectly computable, as we only ever need to run a finite number of machines a finite number of steps for each k. This sequence of rationals is monotonic and is upper-bounded by 1, but does not have a computable least upper bound. If such an upper bound existed, then it would encode solutions to the halting problem for every program. However, the reals have least upper bounds of all upper bounded subsets under mild classical assumptions, so we’ve made ourselves an uncomputable real out of computable data. Sequences of this form are called Specker sequences, and are how you cook up most uncomputable numbers. There are models of constructive logic that do not admit any Specker sequences and admit only computable reals, but that is beyond the scope of a single comment :)

by Reubend 8mo ago

throwaway27448 8mo ago

I assume this refers to Chaitin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

deleted 8mo ago
[deleted]

yorwba 8mo ago

Any given computation either halts or it doesn't. You can encode that information in a single bit, as a specific number. Since there is a countably infinite number of possible computations, you'd need a countably infinite number of bits. So you can never find enough storage to hold the full solution of the halting problem in the real world. But you can find enough storage in a real number. Because real numbers can have a countably infinite number of digits after the decimal point. So you can stuff your countably infinite number of bits representing the solution of the halting problem in there. Which specific real number you get depends on the details of the encoding, but it's definitely some real number. And it cannot be computed, because if it could, you could read the solution to the halting problem off its digits, but the halting problem is known to be uncomputable.

moritzwarhier 8mo ago

I'm not a mathematician, but constructivists aim to define mathematics without uncomputable numbers, see https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis and https://en.wikipedia.org/wiki/Computable_number#Use_in_place_of_the_reals https://en.wikipedia.org/wiki/Computable_number#Use_in_place... As far as I can understand, the set of all computable numbers (including all algebraic numbers and many transcendental numbers, such as Pi), even has the same cardinality as the rationals, and thus the natural numbers. The reason we consider uncomputable numbers "numbers" include some definitions about infinite series and analysis that would need to have stricter requirements for convergence when looking only at the computable numbers, not the real numbers. And defining a concrete bijection between the natural numbers and the computable numbers would also solve the halting problem and is impossible, we only know that such a bijection exists: defining it would mean to have an algorithm that can prove for a specific Turing machine that it is the minimal one computing it's output, among a given set of universal Turing machines / UTM encoding. (please take this with a grain of salt as I'm stepping outside the bounds of my knowledge here)

lich_king 8mo ago

Busy beavers are a classic example. They're mostly-hypothetical numbers that tell you "if any Turing machine of size s runs for longer than this, it doesn't halt." There's a link to that in the sentence you quoted.

tromp 8mo ago
Individual busy beavers BB(n) are finite natural numbers and thus quite computable. A related uncomputable number is the halting probability Omega of a universal prefix machine (whose programs form a prefix free set). By collecting enough halting programs to accumulate a probability of at least the first n bits of Omega (as a binary fraction), you will have determined all programs of length at most n that halt and thus also the busy beavers up to that size.
- lich_king 8mo ago
  "A real number in which each decimal digit at position n is equal to the first digit of BB(n)." Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.
  - cofunctor 8mo ago
    Such an algorithm would be computing the (uncomputable) function BB : Nat -> Nat, and not the computability of a given BB(n). Every fixed natural number is computable: just print out the number. This is a subtlety of doing computability theory in classical foundations. It’s akin to how every concrete instance P(x) of a decision problem P is decidable: just use excluded middle to figure out if P(x) is true or false, and then use the Turing machine that immediately accepts or rejects regardless of input. This is very different from writing a machine that has to decide P(x) when given x as an input!
  - tromp 8mo ago
    I did just that for the first 37 BB numbers at https://oeis.org/A333479 https://oeis.org/A333479 I could write a few more given enough time, but writing later ones will take someone more omnipotent than me. You may be confusing the true statement "for each n, BB(n) is computable" with the false statement "\n -> BB(n) is computable".

leni536 8mo ago

Enumerate all well formed programs in order. For programs that halt assign the digit 0, and for the ones that don't, the digit 1. Put the digits after a decimal point and interpret in binary.

Reubend 7mo ago
Very interesting! Thank you for explaining this.

deleted 8mo ago

[deleted]

cofunctor 8mo ago

Here’s a nice concrete construction. To start, fix some enumeration ϕ of Turing machines. Let’s define a sequence of rational numbers x_k as $\sum_{i=0}^k 2^{-(i+1)} * halts(ϕ(i),k)$, where $halts(M,k)$ returns 1 if the machine M halts before taking k steps when fed the empty tape, and 0 otherwise. This is perfectly computable, as we only ever need to run a finite number of machines a finite number of steps for each k. This sequence of rationals is monotonic and is upper-bounded by 1, but does not have a computable least upper bound. If such an upper bound existed, then it would encode solutions to the halting problem for every program. However, the reals have least upper bounds of all upper bounded subsets under mild classical assumptions, so we’ve made ourselves an uncomputable real out of computable data. Sequences of this form are called Specker sequences, and are how you cook up most uncomputable numbers. There are models of constructive logic that do not admit any Specker sequences and admit only computable reals, but that is beyond the scope of a single comment :)