However, it feels like there is a fuzzy boundary somewhere nearby, similar to the fuzzy boundary of what constitutes life. Maybe there is a information theory explanation which relates the two.

You might find it useful thinking about computations in terms of turing machines and the tape they use: http://lesswrong.com/r/discussion/lw/5vx/torture_simulated_with_flipbooks/4b7p