Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Unreal numbers

lcamtuf.substack.com

Post reply on HN
Print view View original

21–30 of 32 posts

Re: Unreal numbers

#21

Post by LolWolf »

adrian_b wrote: post #17
LolWolf wrote: post #13

Earlier quoted context omitted.

> few of the computable numbers that are not algebraic are interesting, the main exceptions being the numbers that are algebraic expressions containing "2*Pi" and/or "ln 2". I don’t think this is true at all. For example: the solution to a generic PDE that has no closed form solution at some point of import is likely transcendental, not algebraic, but definitely computable. (Think, say, Navier-Stokes being used for w…

True, but with such numbers you will normally not do anything else except computing an approximate value of them. They are not comparable with numbers like 2*Pi or various irrational nth roots that can appear in a lot of relationships and formulae in symbolic computations. That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in n…

> True, but with such numbers you will normally not do anything else except computing an approximate value of them.

That's what I think people do with other numbers like "pi" at the end of the day, no? :)

> That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.

It's very much an encoding problem, I think. Though we probably, on aggregate, use "unnamed computable numbers" implicitly on the order of as much as we use "named computable numbers" the former just has way more of a "tail" of uses where the "encoding of the symbol" is, e.g., "here's the PDE you use to compute this number"!

(It gets a little weird since we're kind of not distinguishing between the approximation that can be used to construct said numbers to arbitrary precision vs the specific program instance that constructs one specific approximation, but the idea is mostly there.)

Re: Unreal numbers

#22

Post by lich_king »

tromp wrote: post #12
lich_king wrote: post #10

Earlier quoted context omitted.

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.

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 th…

"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.

Re: Unreal numbers

#23

Post by [deleted] »

throwaway27448 wrote: post #5
Reubend wrote: post #4

> 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…

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

[deleted]

Re: Unreal numbers

#24

Post by cofunctor »

Reubend wrote: post #4

> 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…

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 :)

Re: Unreal numbers

#25

Post by cofunctor »

lich_king wrote: post #22
tromp wrote: post #12

Earlier quoted context omitted.

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 th…

"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.

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!

Re: Unreal numbers

#26

Post by krackers »

thaumasiotes wrote: post #18
gjm11 wrote: post #11

Earlier quoted context omitted.

Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)

Indeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete. I've read about an actual bijection betwee…

The cantor pairing function is a bijection though between (N, N) -> N so it does establish a bijection in cardinality between positive rationals and N.

The approach you mentioned would be if you used a non-bijective function to map from (N, N) to N like 2^a 3^b which can show that the cardinality of positive rationals is a subset of the cardinality of the naturals, and then you get your version of the proof.

Edit: Wait unless the objection was that actually the bijection from (N, N) -> N is not sufficient since e.g. (1,1) and (2,2) all map to the same rational. You could probably skip duplicates when enumerating, but if you insist on a explicit constructive version I have no idea how you'd find the inversion formula for that.

Re: Unreal numbers

#27

Post by taco9999 »

thaumasiotes wrote: post #18
gjm11 wrote: post #11

Earlier quoted context omitted.

Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)

Indeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete. I've read about an actual bijection betwee…

For bijection, the path through the rationals can just jump over and skip any numbers that have already been visited by the path.

Re: Unreal numbers

#28

Post by kovek »

I was thinking about the ability of representing different kinds of numbers. Imagine that we had a certain CPU that could process algorithms, and the final output of the algorithm is a number. The CPU has a certain number of operations (At least https://en.wikipedia.org/wiki/One-instruction_set_computer). Then, if the algorithm can be described with an integer (since the algorithm can be described with binary), then... can integers describe Real numbers?

Re: Unreal numbers

#29

Post by thaumasiotes »

adrian_b wrote: post #20
thaumasiotes wrote: post #18

Earlier quoted context omitted.

Indeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete. I've read about an actual bijection betwee…

For the construction of a bijection between natural numbers and another set, when you already know that the sets have the same number of elements, it is enough to define an order relation on the other set. There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ... For instance, after reducing the numerator and denominator, so that you have unique rational numbers,…

This doesn't really help you if you want to calculate the index associated with a rational number.

Re: Unreal numbers

#30

Post by tromp »

lich_king wrote: post #22
tromp wrote: post #12

Earlier quoted context omitted.

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 th…

"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.

I did just that for the first 37 BB numbers at 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".

Post reply on HN