_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
HTML Visit Hacker News on the Web
COMMENT PAGE FOR:
HTML Unreal Numbers
adrian_b wrote 8 hours 57 min ago:
> Of course, we donât teach about computable numbers in school.
Instead, the most common âupgradeâ from â are reals:
While "computable" numbers are a recent concept, already for a few
centuries, since the early 18th century, mathematics has taught about
another set of numbers intermediate between rational numbers and "real"
numbers: the algebraic numbers, which are a subset of the computable
numbers.
Like the "real" numbers, the "complex" numbers have also been
partitioned since that time into "complex" integer numbers, "complex"
rational numbers, "complex" algebraic numbers, "complex" transcendental
numbers.
Everything that is now discussed in terms of "computable" and
"non-computable" numbers, was previously discussed in terms of
algebraic numbers and transcendental numbers.
While "computable" numbers is a more general concept that more
precisely defines the limit between what is countable and what is not,
the practical importance of this concept is reduced, because 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".
Reubend wrote 10 hours 37 min 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?
moritzwarhier wrote 9 hours 55 min ago:
I'm not a mathematician, but constructivists aim to define
mathematics without uncomputable numbers, see [1] and [2] 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)
HTML [1]: https://en.wikipedia.org/wiki/Computable_analysis
HTML [2]: https://en.wikipedia.org/wiki/Computable_number#Use_in_place...
yorwba wrote 10 hours 19 min 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.
throwaway27448 wrote 10 hours 21 min ago:
I assume this refers to Chaitin's constant:
HTML [1]: https://en.wikipedia.org/wiki/Chaitin%27s_constant
koolala wrote 10 hours 45 min ago:
A number that can predict the future?
emmelaich wrote 10 hours 51 min ago:
Previously:
HTML [1]: https://news.ycombinator.com/item?id=45424648
DIR <- back to front page