Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You should probably look into the computable numbers. –  JSchlather Apr 1 '11 at 11:53

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
No, the comment and chazisop don't say that transcendentals are computable- only a few special cases are computable. And since transcendentals are all non-algebraic numbers, it stands to reason that an infinite number of them are incomputable too. A good example is Chaitin's constant. Your example of 1/3 doesn't apply, as I spoke only of languages whose binary expansions are fully known. –  Ganesh Apr 1 '11 at 18:28
    
@Ganesh: OK, so I think what I was saying is mostly just wrong or incoherent. But at least what you say answers the conjecture partly, that uncomputable numbers are not rational. Is that right? –  Mitch Apr 1 '11 at 18:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.