Binary expansions associated with languages

Question

Let $\mathbf{L}$ be the set of all languages over $\Sigma=\{0,1\}$ and $E(\Sigma)$ be a lexicographic enumeration of $\Sigma^*$. Then there exists a bijection from $f:\mathbf{L} \rightarrow [0,1)$ where $f(L)$ has its $i$-th bit (to the right of the binary point) set to 1 iff the $i$-th string in $E(\Sigma)$ belongs to $L$. For simplicity, ignore languages that have a binary expansion consisting entirely of ones after a finite number of positions (such as .001001111111.....).

Questions

(1) Conjecture: If $L_{u}$ is an unrecognizable language, $f(L_u)$ must be an irrational , possibly transcendental number.

The intuition is that rational expansions are finite or periodic, hence must be trivially decidable, and algebraic numbers are expanded by solving the corresponding polynomial equation. Is there a proof/counterexample for this? Admittedly, this is only an intuition.

(2) What kind of numbers do the undecidable-but-recognizable languages map to?

Answer 1

I was just reading a relevant paper yesterday. The paper is "On the computational complexity of algorithms" by J. Hartmanis and E. Stearns. How numbers are related to complexity is just the last section of the paper. It uses a different definition, that of a sequence where the i-th term is 1 if the i-th string is in the language. It seems to me like the two definitions are equivalent or can be with slight modifications.

The paper proves that:

• All rational numbers are in $DTIME(n)$
• All algebraic numbers are in $DTIME(n^{2}$
• There are transcendental numbers in $DTIME(n)$

Note that this paper is from 1965, therefore a search is possible to provide better results.

Answer 2

regarding the first question, I think you are correct. For every rational number you can build a Turing machine that tells you exactly what is the n-th digit in the binary expansion. You only need to know the finite string of digits that repeats itself , and the finite string of digits before the periodicity begins.

now given a word, you can find exactly where it is in the enumeration, and then check if the corresponding digit is one or not.

In similar way, given a polynomial for an algebraic number, you can calculate the binary expansion of its roots up to any digit, so given a word, you can always check its place in the enumeration and then find whether or not it is in the language. This same reasoning is true for every number that you have some way to calculate its first n digits for every n (for example you can use Taylor expansion to calculate $e$ and more generally $e^x$ if you can find x's first n digits). Therefore all such numbers correspond to decidable languages.

Answer 3

As the comment alluded to, all irrational and transcendental numbers are in some sense computable, so those that are not computable cannot even be transcendental. An unrecognizable language would correspond to $f$ not being -total-. That is, you could have a language that corresponds to 1/3 in binary but with the first bit (corresponding to $\epsilon$?) not decided. Is that number rational? It's not equal to 1/3, but it's not irrational or transcendental either. It's just incomputable.