A few twists on Turing’s proof of undecidability of predicate calculus By permission of Rich Longmore, artist, blog source Alan Turing presaged Stephen Cook’s proof of -completeness of Turing reduced the halting problem for his machines to the decision problem of the first-order predicate calculus, thus showing (alongside Alonzo Church) that the latter is undecidable. […]