Keith Douglas' Web Page

About me Find out who I am and what I do.
My resumé A copy of my resumé and other documentation about my education and work experience for employers and the curious.
Reviews, theses, articles, presentations A collection of papers from my work, categorized and annotated.
Current research projects What I am currently working on, including some non-research material.
Interesting people People professionally "connected" to me in some way.
Interesting organizations Organizations I am "connected" to. (Some rather loosely.)
Intellectual/professional influences Influences on my work, including an organization chart. Here you can also buy many good books on philosophy and other subjects via I have included brief reviews of hundreds of books.
Professional resources Research sources, associates programs, etc.
What is the philosophy of computing? A brief introduction to my primary professional interest.
My intellectual heroes A partial list of important people. Limited to the dead.
My educational philosophy As a sometime teacher I've developed one. Includes book resources.

Book Influences - Logic: Recursion Theory

Purchase / Enjoy Cover
An Introduction to Kolmogorov Complexity and Its Applications (3e) Li and Vitányi This is a giant hardcover textbook of a field which studies what might be called the "computational theory of descriptions". It has applications in data compression, learning theory, epistemology (precise notions of Occam's Razor), metaphysics (randomness), language parsing/recognition, foundations of mathematics (proof theory) etc. Quite complex - this book is not easy going and actual implementations are not much in evidence. However, exercises are reasonably plentiful and come from (what are labeled to be) easy applications of definitions to open research problems.
Automata and Computability Kozen Nicholas Pippenger assigned this in his introductory theory of computation class at UBC. I like its presentation of automata - very "visualizable." It also got me thinking more about metaphysics of computation.
Church's Thesis after 70 Years Olszewksi, Wolenski, Janusz (eds) Two dozen or so papers (some previously published) on the status of "Church's" thesis (arguably the thesis is due to Post and Kleene). Some are historical, trying to figure out what was claimed and when; some attempt to evaluate the nature of the thesis; and some even argue for its falsity. Bringsjord's odd contribution, where he argues (!) with his co-author, is along the latter lines. Most of the contributions are clear, but some of the positions are a bit strange. Cleland's paper, claiming we should discard CT because it is part of the failed legacy of Hilbert's program (debatable in itself) is just bizarre: was Gödel, who praised Turing's work, a partisan of the (caricature?) Hilbert program discussed? Surely not! My only large complaint about the work as a whole, however, is the incredibly high price for what is a useful volume, especially moving into the Turing year ...
Classical Recursion Theory Odifreddi An absolutely stunning book on recursion theory, including much material that is substantially too advanced for me to comment usefully on. It does include a philosophically very interesting discussion of the Church-Turing thesis, too.
Computability and Incompleteness Avigad   A course pack: Jeremy Avigad's notes for his course at CMU by this title.
Computability and Unsolvability Davis One of the first textbooks on computability/recursion theory since reprinted in a Dover edition. The typography is a bit strange and takes a bit of getting used to. Also includes (in this Dover edition) a reprint of the paper containing the proof of the MRDP theorem.
Computability: Computable Functions, Logic, and the Foundations of Mathematics Epstein and Carnielli An otherwise relatively ordinary book on recursion theory and incompleteness, it also includes interesting exerpts from the historical figures involved in the development, philosophical discussion, and a timeline. These features alone make it much more "humanistic" than similar texts.
Feynman Lectures on Computation Feymann A little gem of a book on many topics on computing from a unique point of view. Even includes some discussions of the thermodynamics of computation. (This book appears in the logic section because of the discussion of automata theory, etc.)
Neural Networks and Analog Computation Byeond the Turing Limit Siegelmann Hypercomputing/super-Turing computation is likely ridiculous, but only in a subtle way. As argued in my MS thesis (CMU, 2003, under the direction of Wilfried Sieg) this book describes the most (meta)physically plausible of all such proposals. See the aforementioned thesis for details. Not addressed in the thesis in sufficient detail is the question of idealizations the book raises: everyone concerned recognizes that both the Turing machine model and the analogue network models of this volume involve idealizations; so why adopt the former rather than the latter? The answer, which I have yet to develop, seems to center around the notion of programmability.
The Universal Turing Machine: A Half Century Survey (2e) Herken (ed.)

In a way this work is misnamed: one can better regard it as a celebration of topics which arose out of Turing's work as a whole, not just about the UTM. A wide variety of considerations are discussed by many different authors; as usual with edited volumes it is difficult to evaluate generally. One thing I relearned when rereading the copy I just (2011) purchased (I had read this twice as a student, once as an undergraduate and once while an MS at CMU) is that Penrose regards algorithms as strictly mathematical objects: this clinches the usual misunderstanding on his part which computing professionals have been pointing out for a while now. I wonder if any of them read the first edition of this book: if they did it had alas no impact on Penrose's subsequent volumes.

One topic which a lot of papers address are actual machines and computable physics. This seems to be still a topic of consideration, with Wilfried Sieg continuing work in the Gandy line in recent years and the (pseudo?)debate over hypercomputing.

All in all not a superb volume, but a reasonable collection and an important contribution to the secondary literature on Turing, amongst other things. I might note finally that Kleene and Gandy were both alive when the book was first published and contributed to this volume, as well as other well known logicians like Feferman and Davis (twice). This makes for something of an "all star" cast!


Finished with this section? Go back to the list of book subjects here.