What are the prerequisites for "Systems of Logic Based on Ordinals (1938)" by Turing?

275 Views Asked by At

I skimmed through the paper, but it seemed to become increasingly difficult. I'm a self learner and a math beginner.

Although I dabbled with linear algebra, calculus, and real analysis in university, I wasn't serious and didn't touch them for 6-7 years. So, I forgot almost everything. I recently finished “How to Prove It: A Structured Approach, 2nd Edition” by Daniel J. Velleman, and that's virtually all I know about math.

Can you compile an order of books and papers that I should read before I embark on reading "Systems of Logic Based on Ordinals (1938)" by Turing?

1

There are 1 best solutions below

7
On BEST ANSWER

As prerequisites, you'll need a good background in mathematical logic, up to and including Gödel's incompleteness theorem(s); familiarity with basic set theory (in particular, ordinals!); and somewhat more than the basics of computability theory, but circa 1938. Probably, and fortunately, you can get the basics in one place: Mendelson's Introduction to Mathematical Logic is a standard work that covers a lot of this material.

It will be helpful to have read about recursive ordinals and systems of ordinal notations as devised by Kleene. Hartley Roger's book Theory of Recursive Functions and Effective Computability is a masterful presentation of the subject circa 1967, and contains much more than was known in 1938. In particular Rogers discusses recursive ordinals and hierarchies built using them.

For context, Church and his 1930s PhD students Turing and Kleene were, it's fair to say, the founders of computability theory (aka recursion theory). Turing did his work on ordinal logic under Church at Princeton. The motivation of the study was to transcend the limitations of incompleteness, by using ordinals to ascend, in an "constructive" way, from a true but incomplete theory to larger, "less incomplete" theories.