10
$\begingroup$

Do all known algorithms that generate infinitely many transcendental numbers like Gelfond-Schneider or Liouville only generate countably many? If uncountably many, is this set of measure zero?

  • 2
    Title needs fixing, all the known things are countable, transcendental or not.2012-12-27

2 Answers 2

19

The Liouville procedure generates continuum-many. As long as the gaps between successive $1$'s grow fast enough, we get a transcendental number.

Take any Liouville-type transcendental number, with $1$'s at positions $p_n$, and $0$'s elsewhere. We can modify this in $2^\omega$ many ways, by deciding for every $n$ whether or not to shift the $1$ at position $p_n$ to position $p_n+1$.

In the above example, a very loose notion of "algorithm" was used. If you mean algorithm in a formal sense, as in a Turing machine algorithm, then there are only countably many Turing machines, and hence only countably many algorithmically specifiable numbers.

  • 0
    Yes, it is of measure $0$. Nifty reason, no, a standard calculation. Robert Israel has given something that could be called a construction of a set of transcendentals that definitely has non-zero measure.2012-12-28
3

Here's a "method" to generate all transcendental numbers in the interval $(0,1)$. Of course such a thing can't be an actual algorithm, it must involve countably many arbitrary choices. Let $\{a_n\}_{n=1}^\infty$ be a sequence that runs through all algebraic numbers in $(0,1)$ (such things are easy enough to generate explicitly, but for brevity I'll just assume it's given). For each $n$ choose a positive integer $m_n$ such that $m_{n+1} > m_n$. Now take any sequence of positive integers $b_n$ with the restriction that if $m_j = n$ for some $j$ and the simple continued fraction representation of $a_j$ is $1/(c_1 + 1/(c_2 + \ldots ))$ (with at least $n$ elements), the n-tuples $[c_1, \ldots, c_n]$ and $[b_1, \ldots, b_n]$ are different. Thus there is at most one possible excluded value for each $b_n$. Finally, take $x$ to be the number with continued fraction representation $1/(b_1 + 1/(b_2 + \ldots)$. It is easy to see that $x$ will be a transcendental number in $(0,1)$ and that any such $x$ can be generated for an appropriate choice of the sequences $m_n$ and $b_n$.

  • 0
    What sort of extra property do you want to your transcendental number to have? That may be possible to enforce by adding further restrictions in the process.2012-12-28