  In the first of this pair of papers, it was proven that that no physical
computer can correctly carry out all computational tasks that can be posed to
it. The generality of this result follows from its use of a novel definition of
computation, ``physical computation''. This second paper of the pair elaborates
the mathematical structure and impossibility results associated with physical
computation. Analogues of Chomsky hierarcy results concerning universal Turing
Machines and the Halting theorem are derived, as are results concerning the
(im)possibility of certain kinds of error-correcting codes. In addition, an
analogue of algorithmic information complexity, ``prediction complexity'', is
elaborated. A task-independent bound is derived on how much the prediction
complexity of a computational task can differ for two different universal
physical computers used to solve that task, a bound similar to the ``encoding''
bound governing how much the algorithm information complexity of a Turing
machine calculation can differ for two universal Turing machines. Finally, it
is proven that either the Hamiltonian of our universe proscribes a certain type
of computation, or prediction complexity is unique (unlike algorithmic
information complexity).
