0

I can't find an example of number that is not computable but it is left computable. In general is already difficult to give example of non computable numbers, but I can't even find any number which is not left computable.

Any help is appreciated.

P.S: A real number $x$, is said to be left computable number if the set $\{q\in\mathbb{Q}\vert q<x\}$ is recursively enumerable (that is, it is the image of a Turing machine).

miraunpajaro
  • 1,560

1 Answers1

2

Using this definition of left-computability, our aim is to construct a computable increasing sequence of rationals that converges to a non-computable number.

Consider a sequence $q_{n}$ subunitary rational numbers.

Define the $k$'th digit after the decimal point of $q_{n}$ to be $1$ if $k \leq n$ and the program encoded by $k$ halts after $n$ steps or less, or $0$ otherwise.

The $q_{n}$ are increasing, as a digit that becomes $1$ stays $1$ for all $q_{p}$ with $p>n$. They are also rational, as each $q_{n}$ has at most $n$ non-zero decimal places. However, their limit will be a number $q$ who's $k$th digit is $1$ if the program encoded by $k$ halts, or $0$ otherwise. As it encodes the solution to the halting problem, it is not computable.

Thus $q$ is left-computable, but not computable.

user3257842
  • 3,617
  • Nice! Thanks. I do not understand why computable implies left computable. Computable means there is "fast" computable convergent sequence, while left computable requires any computable sequence as long as it is increasing. – miraunpajaro Nov 24 '21 at 19:31
  • 1
    You can take a computable number $q$ and easily compute for it an increasing sequence, ie $q_{n}$, made of the first $n$ digits of $q$ for example. – user3257842 Nov 24 '21 at 19:34