A summary of a devastating review of the "Shadows" book: Frank Wilczek, writing in Science (266 9 December pp1737-1738) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The writer notes the stylistic excellence of the author and notes the elements of "occasional brilliance" which are to be found in the book. The development of discussion in the book is then described: 1.1: The author argues that humans can perform feats which machines that follow finite algorithms cannot. 1.2: He notes that the conventional laws of physics can be simulated by a finite algorithm (or TM). 1.3: He concludes that there are, therefore, mental feats which cannot be explained by (simulated in accordance with) the conventional laws of physics. 2.1: The author argues that the laws of physics are flawed in that the rules of quantum mechanics are logically incoherent, breaking down when applied to "semi-macroscopic" bodies. 3.1: He concludes that a set of better laws of physics carry within them better ways of thinking about cognition. The reviewer examines each of these ideas in turn. He notes the centrality of the idea that humans can do things which Turing machines cannot, a view which is based upon the "obvious" ability of humans to transcend the limitations of Godel's theorum. The reviewer points out that this theorum states that any closed, powerful and self-consistent system will allow statements which are true but not provable. Penrose asserts that human mathematicians can grasp the truth of - for example - Godel's theorum even when it is applied to itself. Humans can, allegedly, grasp a truth in circumstances when that proof cannot be arrived at by formal means: there must be, therefore, a proof process which transcends formal processes. (The writer note the descent of this idea for John Lucas's 1961 article and points to the common objection that the Godel proof follows from the assumption of completeness, closure and consistency, attributes which are questionable for a powerful system). Opinion is, therefore, divided on this issue as to whether human intuition transcends formal processes of exploration. It is, however, equally far from obvious that all physical phenomena can be simulated on TMs. Humans are, however, a part of physical reality. The reviewer asks for a demonstration of any circumstance in which a human can be shown to perform a task which is even difficult for TMs, let alone impossible. He asks: are there, for example, "holistic" perceptual tasks at the NP level which humans do in polynomial time? (See note below if NP passes you by). He suggests that a confirmation of an example would have revolutionary implications, although the finding would be less "hard" than the view taken by Penrose as the basis of his arguement. In respect of the second tranche of issues - those of physics - Penrose is unhappy with current quantum theory. Two views are advanced: what he calls the "R process" and the conventional and deterministic dynamics described by the Schrodinger equation, which he calls the "U process". The R process is deemed necessary in order to make a bridge between the quantum rules for adding amplitudes and the classical rules for building probabilities. The reviewer points to the current trend to see whether we cannot get by with just the U process; and he notes the tentative and vague proposals which Penrose brings forward to indicate why the other route is appropriate. The suggestion that quantum gravity will bring together the macroscopic and microscopic is, the reviewer indicates, little more that a suggestion; and that current ideas work very well on the mesoscopic coherence of neutrons, k mesons, photons; on more than mesoscopic behavious of superconductors, superfluid helium and, indeed, on those aggregations of a few hundred or thousand atoms in which behaviour predicted by quantum theory is being born out by observation. Quantum gravity, the reviewer notes, is highly problematic at high energies and short distances; but relatively accessible at the longer and broader scales at which Penrose wishes to work. The review suggest that tentative estimates of the effects of quantum gravity at this scale will be swapmed by other sources of noise. The results will, however, be "eminently computable", whereas Penrose is looking for a *non-computable* R process. The third step in the arguement is to evoke a hypothetical non-computable R process to explain the supposed noncomputable activity of the human brain. Microtubules are further evoked as the hosts of this ineffable interaction of the ill-defined. Microtubules are, it is noted, a common component of cells of many kinds in most nucleated cells and they are nor primarily a characteristic of the human nerve cell. In addition, the temperature and circumstances of the cell "hardly seem conducive to quantum coherence on a macroscopic scale"; but if the effet was tere, one should be able to measure it. "It seems to me, in summary, that Penrose's argument, from formal logic and philosophy, that human beings perform non-omputable operations is simply mistaken; that his argument that quantum theory is incomplete is unconvincing and hs proposed remedy implausible; that his conclusion that an essentially classical description of microtubule fuction must ail is premature, to say the least; and that his discussion of this topic, of neurobiology in general, does not do justice to a large important body of relevant empirical knowledge. Moreover, the whole grand structure of his arguments is exceedingly frail, being at no point butressed by specific reference to non-trivial experimental fact." _________________________________________________ Note: NP The following is stolen from David Gifford's article, as he has said it far better that I could (Science 266 11 November pp 993-994). Square brackets [] show interpolations needed to make sense of his text when wrenched from the issue which he was discussing, the use of DNA synsthesis technology to solvethe directed Hamiltonian path problem. __________________________________ | | | Universal | | ___________________________ | | | Exponential | | | | _______________________ | | | | | ________________ | | | | | | | NP complete | | | | | | | ---------------- | | | | | | NP | | | | | | ________________ | | | | | | | Polynomial | | | | | | | ---------------- | | | | | ----------------------- | | | --------------------------- | ---------------------------------- The figure shows how computer science problems are ranked in difficulty, starting with easy polynomila time problems on the inside, ranging up to difficult universal machines at the outside. This ranking is based on how long the best algorithm to solve a problem will take to execute on a single processor bounded by a constant factor times the size of the probelm. Algorithms whose running time is bounded by a polynomial function are in the complexity class "polynomial time" (P for short) and algorithms whose running time is bounded by an exponential function are in the complexity class "exponential time". A problem is referred to as intractble if there is no polynomial time algorithm that can solve it. For example, if an O(n^2) algorithm takes 1 microsecond to solve a poblem size 10, then it will take 100 mmS to solve a problem size 100. If an O(2^n) algorithm takes 1mmS to solve a problem size 0, then it will take 3.9 times 10 to the power 11 *centuries* to solve a problem size 100. [There is an additional class of polynomial time algorithms] called "non- deterministic polynomial time", or NP for short. An NP problem is one which can have its answer checked in polynomial time. The "checked" part is the important clause. If an oracle can tell you the answer to your problem, [then an NP algorithm will be able to check the correctness of this answer in polynomial time.] {omit a discussion on Hamiltonians} [There is a special kind of problem in NP] known as "NP complete". Any problem in NP can be translated into an NP complete problem in polynomial time. Thus, NP complete problems are the granddaddies of the NP family and can be used to solve any problem in the class. One of the largest open questions in computing science is the question of whether NP hard problems can be solved in polynomial time. At present, no polynomial-time solution is known of NP-complete problems, and thus they are considered intractable. _________________________________________________ Oliver Sparrow ohgs@chatham.demon.co.uk $ gorithm$ quantum$ consciousness$ Penrose$ In respect of the second tranche of issues - those of physics - Penrose is unhappy with current quantum theory. Two views are advanced: what he calls the "R process" and the conventional and deterministic dynamics described by the Schrodinger equation, which he calls the "U process". The R process is deemed necessary in order to make a bridge between the quantum rules for adding amplitudes and the classical rules for building probabilities. The reviewer points to the current trend to see whether we cannot get by with just the U process; and he notes the tentative and vague proposals which Penrose brings forward to indicate why the other route is appropriate. The suggestion that quantum gravity will bring together the macroscopic and microscopic is, the reviewer indicates, little more that a suggestion; and that current ideas work very well on the mesoscopic coherence of neutrons, k mesons, photons; on more than mesoscopic behavious of superconductors, superfluid helium and, indeed, on those aggregations of a few hundred or thousand atoms in which behaviour predicted by quantum theory is being born out by observation. $