[FOM] "algorithm" and the Church-Turing Thesis

[joeshipman at aol.com]

(previous version had a key statement reversed; moderator, please use this one instead.)


We seem to have made some progress. 


I like Chow's alternate history of how "compactness" could have been seen as an informal notion that was informally regarded as a consequence of a formal property (closed&bounded), and hypothesized to be equivalent to that property (this being a hypoTHESIS and not a "conjecture" because it wasn't a formal sentence of mathematics), until another formal property was proposed that it was informally seen to entail (finite open subcover property) and that was shown by an actual theorem to be equivalent to the first property, thereby making the informal notion precise via a squeezing argument.


(I put the concepts in this order because "compact implies closed and bounded" is the "easy direction" of the Heine-Borel theorem.)



The analogy with "algorithm" (as an informal concept, to be replaced by "effective procedure" if you insist that the word "algorithm" is mathematically unequivocal) and the Church-Turing Thesis (henceforth: CTT) is a good one, although the conceptual inclusion goes in the opposite direction, because the property that we currently hypothesize to be equivalent to our informal notion (Turing computability) is seen as a sufficient condition (Turing machine programs are algorithms, or, if your prefer, effective procedures) but only hypothetically a necessary one.


I now call attention to the generally accepted use of the term "quantum algorithm" to denote ways in which a theoretically possible physical device can be set up to do something which is most naturally interpreted as the calculation of a function (with a probability of error less than any prespecified value).


Although certain models of quantum computation have the property that any functions so computed are in fact Turing-computable functions, that is not known to be true for other models, and in any case the calculation is not known to be capable of being simulated by a human armed with the technology stack of "replenishable pencils and paper and a fair coin", where "simulated" means more than "arriving at the same result", it means "carrying out the same algorithm", or at least "carrying out a polynomial-time-transformation of the algorithm".  If it were capable of being so simulated, for the most common model of computation, then the mathematical result BPP=QP would true, instead of open and currently conjectured to be false by most computer scientists. (It is known that P is in BPP is in QP is in PSPACE, but as far as we know P could equal PSPACE.)


I also note the necessity of a "technology stack" even for the ordinary informal notion of "algorithm". The functions that humans can calculate without replenishable pencils and paper are more restricted (linear-bounded automata seems a better fit than finite-state machines, because one can imagine that a human unaided by technology can still manipulate the input information, for example if it is given by the positions of tokens on a finite grid and the tokens can be placed in a finite number of distinguishable ways but the grid cannot be expanded). Before writing was invented, no one might have had any notion of "procedure" powerful and general enough to do what we regard as computation, and they would have regarded the invention of writing as a technological advance which enabled humans to become more powerful calculators than they had previously been.

Therefore, I want to propose two inverses to Clarke's dictum "any sufficiently advanced technology is indistinguishable from magic". The first is "any sufficiently familiar technology is no longer regarded as a technology but rather as a natural human capability." The second is "any sufficiently reliable magic is indistinguishable from technology."


I hope you can see where this is going. First of all, if we had a technology that could calculate a function that is not Turing-computable, that would refute the "Physical Church-Turing Thesis" (PCTT), for example if some measurable dimensionless constant has a decimal expansion which a more comprehensive fundamental physical theory says is a definable real but not a computable real. But if that technology were in fact humanly accessible, and it became common for people to learn to use it and come to rely on it in the same way as they relied on pencil and paper in the past, then such people, or at least those of them familiar enough with the technology that they could build it themselves from raw materials, might come to see "algorithm" as including such use of technology (see my first dictum), and that would refute the ordinary CTT.





Furthermore, if one scraps the word "algorithm" and reverts to the term "effective procedure", which has the connotation of "something a human can perform" rather than "something a human can calculate", then a complete set of blueprints and instructions for building this hypothetical device, written in clear engineering language, along with a a program for running the device after it is constructed, might be regarded as refuting the ordinary CTT in its "effective procedure" version. Whether this "effective procedure" version is actually equivalent to the PCTT, I leave for discussion.


In the other direction, a sufficiently comprehensive physical theory might allow a proof of the PCTT assuming that the theory is correct, and that would, in conjunction with further assumptions such as materialism, entail the ordinary CTT.


Those further assumptions aren't eliminable. One may believe in the possibility of some form of spiritual inspiration, or else in some form of magic, which, if sufficiently reliable, would get around the PCCT (see my second dictum). Then an "algorithm", or "effective procedure", still ought to be expressible as an oracle program, where the relevant question or prayer or invocation may still be described in a formal language, even if the auxiliary function involved isn't Turing-computable or even ZFC-definable.


-- JS




-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160822/0dd057eb/attachment-0001.html>