Hi,

The idea of undecidability in computability theory seems to be along the lines of:
There can't be an effective procedure, that decides *all instances* of input, but a *single instance* can still be decided. I view this as requiring a lot of "ad hoc" techniques specific to the class of inputs: Like "If input is of this form(one computable function)->Do this procedure(another computable function)".
No matter how hard you try to generalize your techniques, you won't be able to reduce it to finite number of such statements that covers all class of inputs. This is the reason why a single instance can still be solved with some ad hoc technique. (Feel free to correct this view, if you think it isn't a right view)

Along these lines, can there be "problems" in which even *all specific instance* is also not decidable? (Something like nowhere differentiable function. Let us call it "nowhere decidable function/set/problem)
My attempt to create such a problem doesn't seem to get me anywhere. I thought of starting with {set of all undecidable first-order theories} and asking for membership in that set, given a theory T as an input. But, once we can prove that the theory can have Natural Numbers as Model, we know that there are statements that are independent of the system by Godel's incompleteness theorem and therefore undecidable, so we have an instance of the input on which we can decide membership. Is this sufficient condition, which means it's all-input-decidable? But i am not sure how easy it is to do Model-check on a given Theory for Natural Numbers.

Or is there a way to see that such a problem can never exist? Like some ill-definedness comes in: What des it even mean to pose a problem, when all its input are undecidable? We can say a problem is defined, if only we can give at least one example to it, in which case we have already one instance i.e.the example itself, for which we know the answer, so no problem can be *all instance undecidable*?
More generally, is it even possible to define a set S without being able to list even a single member in it? Does that even make sense?

general mechanismfor: given any set of natural numbers, you can "decide" whether it has a single-program that can test membership, without being able to construct that program? Note the meta-level here. In some sense, we are saying provability is decidable? Is there any pointer on it? – rajeshsr Oct 21 '12 at 18:04