This is kind of a fun question because it places the notion of “computational” computability (classical CS) alongside that of classical computability (finding a

This is kind of a fun question because it places the notion of “computational” computability (classical CS) alongside that of classical computability (finding a model by, say, minimizing an error which in turn boils down to calculus or linear system solution). Long story short, because of the power of real numbers — with each one encoding an infinite sequence of bits — it’s not clear that even “simple” computations important to elementary statistical models, like exponentiating, have low computational complexity. Computing, say, “e” can be done by a Turing machine, but it’s nontrivial. Another observation along the same lines is that some simple statistical models turn out to really complex — like “find a such that the model y = sin (a x) fits sample data (x1, y1),..., where abs(y) < 1”. This simple model class is well known to have infinite VC dimension, because a can be arbitrarily large. Another way to say it may be that Turing completeness is not a very sharp tool to separate model classes. I found this helpful: http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf