  We turn `the' Church-Turing Hypothesis from an ambiguous source of
sensational speculations into a (collection of) sound and well-defined
scientific problem(s):
  Examining recent controversies, and causes for misunderstanding, concerning
the state of the Church-Turing Hypothesis (CTH), suggests to study the CTH
relative to an arbitrary but specific physical theory--rather than vaguely
referring to ``nature'' in general. To this end we combine (and compare)
physical structuralism with (models of computation in) complexity theory. The
benefit of this formal framework is illustrated by reporting on some previous,
and giving one new, example result(s) of computability and complexity in
computational physics.

Computational Physics;Computational Complexity