Suppose we had an algorithm, which when applied to a complex system could give us a definite answer of `Emergent' or `Non-emergent'.
For the case of cellular automata, Wolfram[14] has suggested a classification into four classes of behaviour: homogeneous (Class I), periodic (Class II), chaotic (Class III) and complex (Class IV). Whether a cellular automaton is in class I, II or III has been shown[12][5] to be undecidable. It follows that the question of emergence in infinite systems is undecidable, with a possible reduction to NP-complete status for finite systems[8].
More heuristically, by considering the halting problem for any complex system which is capable of universal computation, we know that the best (only) means of prediction in such a situation is to `run the program' - i.e. perform the simulation. So all complex systems which fall prey to such isomorphisms would seem to be emergent, and the halting problem then analogises to tell us that, in the general case, the question of whether a system is emergent or not is an undecidable proposition.
The undecidability of emergence presents us with a particularly gnarly problem. For any such undecidable system, we can either:
(i) Assume it is emergent, and use large amounts of computational power for simulations. What do we do if Enrico Fermi suddenly arrives, with his deep understanding, and removes all mystery from the system. We have wasted a huge amount of effort.
(ii) Assume the system is non-emergent, and try to find its deep, hidden inner structure. All this effort could conceivably be in vain.
This devil's alternative becomes especially important when the system under consideration is one that has been designed by us as a cooperative attempt to solve a particular problem.