Addition. Let me try to address Thierry Zell's concern about thethird question. To my way of thinking, the phenomenon ofthe question is an instance of the problem of uniformityof algorithms, a pervasively considered issue incomputability theory.

To illustrate, consider the question of whether a givenprogram $p$ halts on input $0$ before another program $q$.Let $f_p(q)=1$ if it does and otherwise $f_p(q)=0$. Everysuch function $f_p$ is computable, for similar reasons tomy $\pi$ function $f$ above, since either $p$ doesn't haltat all on input $0$, in which case $f_p$ is identically$0$, or $p$ does halt in $N$ steps, in which case we needonly run $q$ for $N$ steps to see if it halts, and give ouroutput for $f_p(q)$ by that time. So each $f_p$ is acomputable function. But the joint function$f(p,q)=f_p(q)$, a binary function, is not computable (ifit were, then we could solve the halting problem: to decideif $p$ halts on input $0$, design a program $q$ that wouldtake one step extra after a halt, and ask if $p$ haltsbefore $q$).

In other words, the function $f(p,q)$ is computable for anyfixed $p$, but not uniformly in $p$. And such uniformityissues are ubiquitous in computability theory.

In the example of the question, each class of graphs isdecidable, but not uniformly so, since by Tony's answerthere is no uniform algorithm, given a description of theclass, to find the collection of excluded minors. But forany such fixed class, the membership question is decidable.

The issue of whether a given algorithm is uniform in agiven parameter is a very common concern in computabilitytheory, and occurs throughout the subject.

1

Consider the following simplified example of the same phenomenon, which many students find clarifying.

Let $f(n)=1$, if there are $n$ consecutive $7$s in the decimal expansion of $\pi$, and otherwise $f(n)=0$. Is this function computable?

A naive attempt to compute $f(n)$ would simply proceed to search $\pi$ for $n$ consecutive $7$s. If found, the algorithm outputs $1$, but otherwise....and then the naive algorithm doesn't seem to know when to output $0$, and so students sometimes expect that $f$ is not computable.

But actually, $f$ is a computable function. If it happens that there are arbitrarily long sequences of $7$s in the decimal expansion of $\pi$, an open question, then $f$ is the constant $1$ function, which is certainly computable. Otherwise, there is some longest sequence of $7$s in $\pi$, having length $N$, and so $f$ is the function that is $1$ up to $N$ and then $0$ above $N$. And this function also is computable, for any particular $N$.

So the situation is that we have proved that $f$ is computable by exhibiting several algorithms, and proving that $f$ is definitely computed by one of them, but we don't know which one. (In fact, $f$ is linear time computable.) So we have proved that $f$ is a computable function, but by a pure existence proof that merely shows there is an algorithm computing $f$, without explicitly exhibiting it.

It seems to be the same phenomenon in your case, where you have a computable function, but you don't know which algorithm computes it.