On Sat, 5 Apr 2025 01:27:54 -0500, olcott wrote:
I know nothing about computable numbers.
“A number which can be computed to any number of digits desired by a
Turing machine.”
<
https://mathworld.wolfram.com/ComputableNumber.html>
The concept is very simple: consider the number π. It is irrational, with
no (known) patterns of repetitions among its digits, but it is computable: there are any number of algorithms known for computing it to any desired
degree of accuracy. Computing the exact value of π would take infinite computation steps, but you can get as close as you like, without ever
quite reaching it -- that is, the numerical computations “converge” to the right answer.
Since a computable number is computed by an algorithm, the possible number
of computable numbers cannot be greater than the number of possible
algorithms.
If an algorithm is expressed as a computer program, you can encode each
symbol of the program as an integer, and end up with a huge integer that represents the program as whole -- this encoding is called “Gödel numbering”.
What this means is that the cardinality of the set of possible computer programs, while infinite, cannot be greater than the cardinality of the
set of integers.
The cardinality of the set of integers (and therefore also the set of
computer programs, and of the set of computable numbers) is conventionally written as ℵ₀. The cardinality of the set of reals is written as ℵ₁. Both
are infinite, but ℵ₁ is supposed to be a larger infinity than ℵ₀ -- at least, that’s what the Cantor diagonal construction is supposed to prove.
In this thread I am trying to point out why the proof doesn’t work. For a start, in general, the diagonal construction never converges to an answer.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)