[Solved]: Why every finite set is computable?

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