The major results of Robertson and Seymour on graph well-quasi-ordering establish nonconstructively that many natural graph properties that constitute ideals in the minor or immersion orders are characterized by a finite set of forbidden sub- structures termed the obstructions for the property. This raises the question of what general kinds of information about an ideal are sufficient, or insufficient, to allow the obstruction set for the ideal to be effectively computed. It has been previously shown that it is not possible to compute the obstruction set for an ideal from a description of a Turing machine that recognizes the ideal. This result is significantly strengthened in the case of the minor ordering. It is shown that the obstruction set for an ideal in the minor order cannot be computed from a description of the ideal in monadic second-order logic. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.

well-quasi-ordering, monadic second order logic, decidability