A non-deterministic hypersubstitution maps any operation symbol of a tree language of type ? to a set of trees of the same type, i.e. to a tree language. Non-deterministic hypersubstitutions can be extended to mappings which map tree languages to tree languages preserving the arities. We deflne the application of a non-deterministic hypersubstitution to an algebra of type ? and obtain a class of derived algebras. Non-deterministic hypersubstitutions can also be applied to equations of type ?. Formally, we obtain two closure operators which turn out to form a conjugate pair of completely additive closure operators. This allows us to use the theory of conjugate pairs of additive closure operators for a characterization of M-solid non-deterministic varieties of algebras. As an application we consider M-solid non-deterministic varieties of semigroups.