[stungeye]

I'm not sure that "the universe as Turing machine" is anything more than a theory. The universe can contain Turing machines -- we're both using one right now -- but I don't think we can say for certain that the universe is one.

Also, not everything is computable. Alan Turing proved this in his paper "On Computable Numbers, with an Application to the Entscheidungsproblem." The Halting Problem is a related example of the limits of computation.

http://en.wikipedia.org/wiki/Halting_problem

[confluence]

Computers are an existence proof - the universe is indeed at least a Turing machine.

The halting problem can be effectively solved for deterministic finite machines - it would just take a long time time.