Need some clarification on what "decidability" means.

Question

[I am relatively new to computability theory, so please try to avoid complicated jargon except as absolutely necessary. Thank you for your time!]

So I get that a decision problem is decidable iff one can write a program (equiv., construct a Turing machine) that always halts with the correct answer. My question is: how much information does the algorithm author/constructor of the Turing machine have, a priori, about the set of inputs for which the answer is "yes"?

It doesn't matter for a lot of problems (e.g., primality testing), but the validity of the (apparently correct) statement that "membership in finite and cofinite sets is decidable" seems to depend on what information the author is given:

• Suppose that the question is: Does n belong to the set $\{1, 2, 3\}$? Given the members of the set we make at most three comparisons; the question is thus decidable.
• But what if the question is: Does there exist a prime number of the form $2^{2^k} + 1$ (i.e., a Fermat prime) for some k > n? The answer to that question is currently unknown for $n > 4$, so the set may well turn out to be finite. Now suppose we knew that only it were finite but had neither information about the cardinality of the set nor a list of members: would the finiteness alone imply that there must exist some means of testing the truth of the statement for a given n without checking all $k > n$ world without end? The difference in this case would be that, unlike in the first case, the author of the algorithm would be unable to trivially compare the input to a pre-formed list.

My guess is that we assume that a pre-formed list of members can exist (esp. since this condition is equivalent to the (weaker) concept of semi-decidability unless I'm mistaken) and can be coded into the alphabet we use for our Turing machine; i.e., if the set has $n$ members then we can construct an alphabet with at least $n$ symbols. I don't see how the computability of finite sets is necessarily true otherwise.

But it seems, on the other hand, like such a list would defeat the purpose of creating an algorithm in the first place; it would reduce every question about the natural numbers to a possibly infinite Ctrl-F. Can you help? I'd really appreciate it!

Answer 1

Basically, you are allowed an arbitrary finite amount of information.

Do you need the first thirty billion digits of $\pi$ for your algorithm? Great! Do you need to know if the Riemann hypothesis is true? That's just one bit of information!

However, let's say you want to know about the generalized twin prime conjecture: that is, you want to know for which $n$ are there infinitely many pairs of primes of the form $p, p+n$?

Well, this is infinitely many facts - I can't (on the face of it) write down a finite amount of information that will tell you everything you want to know.

The reason the amount of "built-in" information has to be finite is: a Turing machine only has finitely many states! Or, to put it another way, the code for a computer program can only be finitely long. So, for example, I can have a separate line of code to handle each of a trillion special inputs - but at some point, I need to write something that's going to work "in general."

Answer 2

Now suppose we knew that only it were finite but had neither information about the cardinality of the set nor a list of members: would the finiteness alone imply that there must exist some means of testing the truth of the statement for a given $n$ without checking all $k>n$ world without end?

Of course, if we know that the set is finite, it must be equal to $\{k_1, k_2, \ldots, k_m\}$ for some $k_i$. Then the algorithm is just "check if $n$ is larger than any $k_i$ on the hardcoded list". Of course, if you only know that the set is finite, but you don't know what exactly $k_i$ are, that doesn't allow you to write down the algorithm explicitly and run it, but it's enough for you to conclude that algorithm exists.