3
$\begingroup$

The definitions I've found were highly technical and using terms I've never seen before.

Say, I have a certain irrational number e that I get get closer and closer to with a computer and I want to determine if there is a particular digit d appearing after a certain position. Or what about the halting problem (give a program and ask 'will the computer ever halt?')? Are these problems semi-computable problems or noncomputable?

$\endgroup$
  • 2
    $\begingroup$ "The definitions I've found were highly technical and using terms I've never seen before" -- In my experience, it is worthwhile to sit down and learn the basics first. Otherwise, you are likely to have trouble understanding the concepts as many of them are inherently formal-theoretic resp. abstract. $\endgroup$ – Raphael Oct 11 '12 at 7:26
  • $\begingroup$ For the problem with $e$, see also this related question. $\endgroup$ – Raphael Oct 11 '12 at 7:32
3
$\begingroup$

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.71828\ldots$, 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?).

$\endgroup$
  • 1
    $\begingroup$ thanks for your Interesting answer. I didnt know that a program can be semidecidable and noncomputable at the same time (the Halting problem). regarding e, i was referring to an arbitrary irrational number e not the particular Euler number, and the program should return true if after a certain decimal digit there is an occurence of the digit '2' say. and it might never stop...so, this would be not decideable, since algortihm A might never terminate (irrational number that has .11 repeating to infinity and we're looking for a 2) $\endgroup$ – sdfasdgasg Oct 11 '12 at 3:49
  • $\begingroup$ Thanks for the addition. I was not familiar with the property that after the nth decimal digit, a particular digit cannot appear only once. $\endgroup$ – sdfasdgasg Oct 11 '12 at 7:04
  • $\begingroup$ @sdfasdgasg "I didnt know that a program can be semidecidable and noncomputable at the same time (the Halting problem)" -- that is wrong on so many levels! Computability is a property of problems, not programs. If the problem is undecidable, there is no program that solves it. Some undecidable problems can be semi-decided, so that's when you can't have a decider but you have a semi-decider. $\endgroup$ – Raphael Oct 11 '12 at 7:30
  • $\begingroup$ The first paragraph is misleading. The first two sentences give, in some sense, circular intuition. The second part mixes in a time bound, which imho muddies the distinction between deciding and semi-deciding. (The rest of the answer is fine.) $\endgroup$ – Raphael Oct 11 '12 at 7:31
  • $\begingroup$ @Raphael: I appreciate your sharp insights. Random note just opped into my mind: Why is it that Halting is not decidable AND in NP hard? I thought you can only place computable problems into any complexity class.. $\endgroup$ – sdfasdgasg Oct 11 '12 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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