1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You know that - according to your definition - $S = \{0\}$ OR $S = \emptyset$ (exclusive or); you don't know which of the two sets you are referring, but you know that both $\{0\}$ and $\emptyset$ are computable. $\endgroup$ – Vor Jul 9 '13 at 14:29
  • $\begingroup$ so you are saying that my definition of the set is invalid? That is, i defined a function that maps TM to a set, but not the set itself? Hm, this raises the question what is a valid definition of the set... $\endgroup$ – Ayrat Jul 9 '13 at 14:49
  • 1
    $\begingroup$ ... in other words you are able to (formally) prove that for the set $S$ there exists an algorithm which defines in finite time if a given number n is in the set; it is one of the two algorithms: 1) given n, return n==0 2) given n, return false $\endgroup$ – Vor Jul 9 '13 at 15:26
  • $\begingroup$ thanks, @Vor, but why cannot i extend it to halting problem: there is infinite # of TM, there is inf # of possible answers for all these TM, but there is an algorithm which answers correctly, because we "can" just enumerate all such algorithms, and our algorithm is one of them. I think this proof fails because we cannot enumerate all of them, right? (due to "diagonalization" argument) $\endgroup$ – Ayrat Jul 9 '13 at 19:01
  • $\begingroup$ No, for the halting problem there is no algorithm which answers correctly, it can be proven that such an algorithm cannot exist. $\endgroup$ – svinja Jul 10 '13 at 6:33
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

The problem is, you haven't defined a language. You have defined a function that returns a language.

What you call $S$ is really $S(M)$, for some Turing Machine $M$. What is undecidable is the function problem: given a Turing Machine $M$, determine $S(M)$.

Once you have a fixed $S$, deciding which numbers are in this $S$ is always decidable if $S$ is finite. This is because all finite languages are regular. If $L = \{w_1, w_2, \cdots, w_n\}$, then the regular expression $R = w_1 + w_2 + \cdots + w_n$ accurately describes $L$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

The simplest answer I can think of: because we can make a finite look-up table for answers. In other words, if you have a finite language $L = \{w_0, \ldots, w_{k-1}\}$, consider the following algorithm:

Input: $x$
$L \leftarrow [w_0, \ldots, w_{k_1}]$
for $i$ from 0 to k-1 do
$~~$ if $x = L[i]$
$~~$$~~$ accept
reject

Now, the problem with your argument is that you are thinking of $M$ as input in one place and not thinking of it as input in another place. If $M$ is not part of the input then the machine does not decide the halting problem but only a fixed instance of it, so the algorithm for deciding it doesn't imply that the halting problem is decidable.

Note that we don't need to construct (uniformly in $M$) the algorithm deciding the halting of a given machine $M$, we only need to show that it exists, i.e. the process of finding the machine that decide if $M$ halts or not does not need to be a computable process (and it can't, if it could then your argument would go through).

On the other hand, if we assume that $M$ is a part of the input, then the set is not finite anymore. It is essentially $A = \{\langle M,b\rangle \mid \text{$b=0$ and $M$ halts}\}$. What you are doing is taking a slice of this set $B_M = \{ w \in A \mid \mathsf{fst}(w)=M \}$ which is finite and therefore decidable. But the decidability of all slices of a set does not imply the set itself is decidable. We need to be able to decide membership in $A$ uniformly in $M$, i.e. we need a single algorithm that works for all $M$, not a different algorithms for each $M$.

|cite|improve this answer
$\endgroup$

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.