I don't see how that matters: if there exist any states for which it is impossible to infer the previous state, that is a loss of information and therefore an increase in entropy.
I agree it's hard to know "the" way to map the 2nd law onto an arbitrary universe and see how it applies, but based on some heuristics (checking for irreversibility, agent-perceived flow of time) it seems like Life doesn't violate it.
I never said you were wrong, I agree with your main point. I was just pointing out that you were reasoning in a very strange way, deriving a simple fact using a very difficult to establish one. People knew that life wasn't backwards deterministic long before they knew about Garden of Eden patterns.
Sort of like arguing that 8+8 != 27 by appealing to Fermat's Last Theorem instead of just pointing out that 8+8 = 16 which is a different number to 27.
Many experts suspect that there is no polynomial-time solution to the so-called NP-complete problems, though no-one has yet been able to rigorously prove this and there remains the possibility that a polynomial-time algorithm will one day emerge. However unlikely this is, today I would like to invite LW to play a game I played with with some colleagues called what-would-you-do-with-a-polynomial-time-solution-to-3SAT? 3SAT is, of course, one of the most famous of the NP-complete problems and a solution to 3SAT would also constitute a solution to *all* the problems in NP. This includes lots of fun planning problems (e.g. travelling salesman) as well as the problem of performing exact inference in (general) Bayesian networks. What's the most fun you could have?