We provide upper bounds for the Vapnik-Chervonenkis dimension (VCD) of classes of subsets of Rⁿ that can be recognized by computer programs represented by expression trees built from arithmetic operations ({+,−,*,/,}), infinitely differentiable algebraic operations (like l-root extraction), conditional instructions and sign tests. Our VCD bounds for this genotype are expressed as a polynomial function in the height of the expression trees used to represent the programs. This implies, in particular, that a GP learning machine dealing with a search space containing sequential exponential time computer programs of polynomial parallel complexity needs only a polynomial amount of training examples.