> If we find a completely different way of computing it that doesn't map to a CA, we'll know it's false.

This is wrong. You would have to additionally prove that the other thing is the only alternative.

Also, CA is not testable in the sense that the theory of relativity is testable. The latter makes measurable predictions that can be satisfied, the former does not. I can imagine any model - unicorns and fairies included - and say that is behaves like the universe. The only way to falsify my claim is to empirically contradict one of my claims. NKS does not put forth such claims. Not the kind you would build a new CERN for.