Remix.run Logo
ogogmad 2 days ago

> We can't even represent all the natural numbers

We can represent all real numbers to the same extent that we can represent all natural numbers. They're just infinite strings, with each additional letter in the string mattering less and less as it goes along. The "Type Two Effectivity" model for modelling computations with infinite strings doesn't limit you to using just the computable real numbers. An uncomputable real number can be produced by outputting an infinite string letter by letter with each letter getting picked at random. The TTE model does OTOH limit you to computing only with the computable functions on those real numbers.

The TTE model basically uses (Python-like) generators to output an endless sequence of interval approximations to a real number.

kccqzy 2 days ago | parent | next [-]

Let's just assume we have infinite memory and can represent real numbers using infinitely long strings. How do you compare two such numbers for equality? You can check that the first 1000 digits are the same but what about the 1001st digit? Suddenly you need infinite time to determine equality. That's not an effective representation.

Y_Y 2 days ago | parent | prev | next [-]

Georg Cantor would like a word.

Representable numbers are countable, they have measure zero in the reals.

zahlman 2 days ago | parent | prev [-]

> An uncomputable real number can be produced by outputting an infinite string letter by letter with each letter getting picked at random.

This certainly outputs an uncomputable real number, given that you have true random input and not a PRNG.

But random numbers from a seed and an algorithm are by definition computable.

And if you can't compute the number, you have no basis for the claim that it's the right number.

Also, good luck computing with arbitrarily long, computed-on-demand digit strings. Consider: how do you know how many digits you need from the input in order to be sure of N correct digits in the output? This might be possible in general, but it certainly doesn't sound like my idea of fun.