3
1
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?
sdfasdgasg
Posted 2012-10-11T02:57:07.000
Reputation: 423
3
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:
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?).
Yuval Filmus
Posted 2012-10-11T02:57:07.000
Reputation: 245 786
1thanks 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) – sdfasdgasg – 2012-10-11T03:49:36.877
Thanks for the addition. I was not familiar with the property that after the nth decimal digit, a particular digit cannot appear only once. – sdfasdgasg – 2012-10-11T07:04:16.280
@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. – Raphael – 2012-10-11T07:30:22.103
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.) – Raphael – 2012-10-11T07:31:33.193
@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.. – sdfasdgasg – 2012-10-11T08:38:35.790
@sdfasdgasg The Halting program is NP-hard because there are no time constraints on the programs involved. For that matter, it is also PSPACE-hard. But you're right that the comparison doesn't make much sense. – Yuval Filmus – 2012-10-11T12:52:05.690
@Raphael I was trying to give intuition. The concept of semidecidability suddenly appears quite arbitrary... Perhaps its recursively enumerable nature is more natural. – Yuval Filmus – 2012-10-11T12:53:25.407
@YuvalFilmus I understand; I felt that if I, having understoof the underlying concept somehwat, was confused while reading the paragraph, it might not help a novice. Imho, decidability is something not really suited to be done without formal definitions. – Raphael – 2012-10-11T15:21:29.170
2"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. – Raphael – 2012-10-11T07:26:50.563
For the problem with $e$, see also this related question.
– Raphael – 2012-10-11T07:32:42.660