Excellent discussion! This meditation should be required reading straight after you have read Why Functional Programming Matters :)

I also liked mstone's clarification of Church's paper and the relationship to Gödel, Turing and the Entscheidungsproblem. Anyone who likes that kind of thing should be sure to read Engines of Logic by Martin Davis.