From: Ian Wright (iwright@GMAIL.COM)
Date: Mon Sep 19 2005 - 12:46:02 EDT
Paul, Great paper! Very nice examples. I learnt things. The practical realisability of an effective computation is a really important point to stress. The onus is on those who claim that the mathematical objects labelled "super-Turing" are *real*. That demonstration requires that they *build* such machines. In other words, it requires experimentation. Otherwise, it is so many angels dancing on the heads of pins. I agree that Aristotle's notion of the difference between potential and actual infinite is crucial, but perhaps this points to more fundamental philosophical issues and questions. For example, an area you don't go into, but is relevant, is the role of diagonal proofs, which I believe assume the existence of (actual) infinite sets. Cantor used a diagonal proof to argue there is a hierarchy of infinities, Godel used a diagonal proof to derive his incompleteness theorems, and Turing used it in the halting problem. Without getting into details, the diagonal proof method is a proof by contradiction. It is philosophically controversial that a proof by contradiction can demonstrate the existence of a mathematical object. Showing that *if* a statement "S " is true a contradiction ensues, does not imply that "not S" is true. This is the debate over the validity of the law of excluded middle, which assumes that either "S" or "not S" is true, and in a way denies the possibility of dynamic contradiction (your oscillator). Intuitionistic logic and variants deny its validity, and it is no accident that these philosophy of math approaches are close to computational approaches. I think it would be interesting to peer a little deeper into the respective uses of the diagonal proof by Cantor, Godel and Turing. To what extent are the conclusions regarding the existence of: (i) the existence of a hierarchy of inifinites; (ii) the non-existence of a complete axiomatization of the natural numbers; and (iii) the non-existence of super-Turing machines that can solve the halting problem, reliant on the law of excluded middle applied to actual infinite sets? My question is whether some of these conclusions are in a sense "undecidable" in theory, as the proofs of existence and non-existence are subject to the critique of the law of excluded middle. -Ian. P.S. Typo of "inherentaly" on P4.
This archive was generated by hypermail 2.1.5 : Fri Sep 30 2005 - 00:00:02 EDT