@VilleSalo That is indeed the obvious proof strategy, but nobody yet has found a "playing around" scheme that always works. I'm afraid there's no reference.

@TimothyChow As Ville Salo said, by compactness a Garden of Eden must contain an "orphan", a finite set of cells whose states cannot be achieved no matter how the other cells are filled in. Orphans are decidable because one can check all possible assignments to the cells in the neighbourhoods of the orphan's cells. So one would decide a Garden of Eden by alternatingly trying to find a predecessor and trying to prove that an $n\times n$ box around the pattern gave an orphan.

@MikeShulman I think that's the answer! How embarrassing.

This also shows that we can have inequivalent categories with full-and-faithful functors both ways.