[Solved]: What’s an intuitive distinction between semi-computable problems and noncomputable problems/functions?

Intuitively, a set of numbers is computable or decidable or recursive if there is an algorithm deciding membership for the set. A set of numbers is semidecidable or recursively enumerable (r.e.) if it has verifiable “proofs” of membership. For example, the set of programs which halt is semidecidable, since given a program $A$ and a time bound $t$, one can check that $A$ halts after at most $t$ steps. But this set is not computable, since without the time bound, we don’t know how long to wait for. (That’s an intuitive explanation; you can google for a proof that the halting problem is not decidable.) There are several equivalent definitions of semidecidable sets:

• A set $S$ is semidecidable if there exists an algorithm $A$ which always terminates with either YES or NO as an answer, such that $x in S$ iff there is a witness $w$ for which $A(x,w)$ answers YES.
• A set $S$ is semidecidable if there exists an algorithm $A$ such that $x in S$ iff $A(x)$ halts.
• A set $S$ is semidecidable if there is an algorithm that enumerates all members of $S$.

See if you can show that all these definitions are equivalent. You might want to look up the technique of “dovetailing”. What about the digits of $e$? We need to phrase the problem of computing the digits of $e$ in our framework. The set of digits of $e$ is the set of pairs $(k,d)$, where $d$ is the $k$th decimal digit of $e=2.71828ldots$, i.e. ${(0,2),(1,7),(2,1),(3,8),(4,2),(5,8),ldots}$. Since there is an algorithm computing the $k$th digit of $e$ (e.g. using the Taylor series $e = sum_{k=0}^infty 1/k!$), the set of digits of $e$ (under this encoding) is computable. Edit: Following the OP’s comment, suppose we’re interested in the set of positions $n$ such that the decimal expansion of $e$ contains the digit $2$ somewhere past the $n$th digit. This set is decidable, for the following reason: either the digit $2$ appears infinitely often, or its last appearance is at digit $N$. In the first case, the set in question contains all natural numbers, in the second case it is ${0,ldots,N-1}$. The same trick works for any fixed real number. Consider, however, the set consisting of pairs $(A,n)$ such that $A$ is an algorithm that enumerates the decimal expansion of some real number, which contains the digit $2$ somewhere past the $n$th digit. This set is not computable, only semidecidable, since one can reduce the halting problem to it and vice versa (how?).