Problem Detail: According to wikipedia, every finite set is computable. Definition: set $S subset N$ is computable if there exists an algorithm which defines in finite time if a given number $n$ is in Set. Question: what is wrong with this counter-example:
- given some $TM$
- $S subset N$
- Lets assume $S$ could contain only $0$, i.e., either $S = {0}$ or $S = emptyset$
- if a given $TM$ halts then $S={0}$ otherwise $S=emptyset$
So set $S$ is finite, but not computable, since we cannot “compute” if a given $TM$ halts. What is wrong above?
Asked By : Ayrat
Answered By : svinja
A similar question was answered here: How can it be decidable whether $pi$ has some sequence of digits? We can ignore the question “if a given TM halts” as it is irrelevant what the question actually is, let’s just name the condition C. If C is true, then the correct algorithm is if n == 0 return true else return false. If C is false, the correct algorithm is return false. Whether C is true or false, one of these two algorithms is correct for every n, so such an algorithm exists. Additionally, “does a given TM halt” is computable for the same reason – the correct algorithm is either return true or return false. What is not computable is a function that answers “does this TM halt” for any TM.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13173
