Freiburg 2008 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

AKPhil: Arbeitskreis Philosophie der Physik

AKPhil 7: Wissenschaftstheorie II

AKPhil 7.2: Talk

Tuesday, March 4, 2008, 18:30–19:00, KGI-HS 1015

A Meta-Theory of Physics and Computation — •Martin Ziegler — University of Paderborn

Mathematical proofs that several unrelated natural definitions of ‘computability’ (e.g. based on Turing machine TM, λ calculus, µ-recursion) are in fact equivalent, have led to what is known as the Church-Turing Hypothesis (CTH): every function that nature can be exploited to compute, can also be calculated on a TM. Since a TM provably cannot decide the Halting Problem H (basically the question of whether a given program satisfies the minimum requirement of correct software in that it terminates), this means that no physical (e.g. quantum) computer whatsoever can solve it either. However all attempts for formal arguments in favor of the CTH have failed so far; and in fact its validity is currently hotly disputed (buzzword: hypercomputation).

We notice that those disputes arise mostly from disagreeing conceptions of "nature": Already Classical Mechanics (CM) admits a bounded solid body B to have the entire H encoded as engraving and thus to ‘solve’ H by probing B. This is of course doubly impractical: 1) an ideal probe or body exists only in CM; and 2) even within CM one cannot construct (e.g. carve) B without solving H in the first place.

Credo 1: The CTH makes formal sense only relative to a specific physical theory (instead of vaguely referring to "nature")! Credo 2: Introduce constructionism to (Ludwig’s concept of) physical theories!

Since CTH is concerned equally with both physics and computer science, we propose their formal synthesis (based on 1 and 2) as a means for settling the above disputes and the state of the CTH itself.