We prove that a real number a greater than or equal to 2 is the irrationality exponent of some computable real number if and only if a is the upper limit of a computable sequence of rational numbers. Thus, there are computable real numbers whose irrationality exponent is not computable.
We show that the set of absolutely normal numbers is $mathbf Pi^0_3$-complete in the Borel hierarchy of subsets of real numbers. Similarly, the set of absolutely normal numbers is $Pi^0_3$-complete in the effective Borel hierarchy.
We prove independence of normality to different bases We show that the set of real numbers that are normal to some base is Sigma^0_4 complete in the Borel hierarchy of subsets of real numbers. This was an open problem, initiated by Alexander Kechris, and conjectured by Ditzen 20 years ago.
Let s be an integer greater than or equal to 2. A real number is simply normal to base s if in its base-s expansion every digit 0, 1, ..., s-1 occurs with the same frequency 1/s. Let X be the set of positive integers that are not perfect powers, henc
e X is the set {2,3, 5,6,7,10,11,...} . Let M be a function from X to sets of positive integers such that, for each s in X, if m is in M(s) then each divisor of m is in M(s) and if M(s) is infinite then it is equal to the set of all positive integers. These conditions on M are necessary for there to be a real number which is simply normal to exactly the bases s^m such that s is in X and m is in M(s). We show these conditions are also sufficient and further establish that the set of real numbers that satisfy them has full Hausdorff dimension. This extends a result of W. M. Schmidt (1961/1962) on normal numbers to different bases.
We solve the problem of finding interspersed maximal repeats using a suffix array construction. As it is well known, all the functionality of suffix trees can be handled by suffix arrays, gaining practicality. Our solution improves the suffix tree ba
sed approaches for the repeat finding problem, being particularly well suited for very large inputs. We prove the corrrectness and complexity of the algorithms.
