Physically-Relativized Church-Turing Hypotheses

We turn the physical 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), it is suggested to study the CTH ‘sharpened’ relative to an arbitrary but specific physical theory—rather than vaguely referring to “nature” in general. For this purpose we combine physical structuralism with computational complexity theory. The benefits of this approach are illustrated by some exemplary results on computability and complexity in computational physics.