Physically-relativized Church-Turing Hypotheses: Physical foundations of computing and complexity theory of computational physics

摘要

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 apply, and emphasize the utility of, concepts from philosophy: physical structuralism, ontological commitment, and constructivism. This general approach is then illustrated with some exemplary results on computability and complexity theory in computational physics.