Show HN: A reference implementation of Turing's paper “On Computable Numbers”

63 points

3 years ago

Hey HN!

I've been curious about the history of computer science and decided to try to read Turing's 1936 paper where he conceptualizes the Turing Machine, etc.

I had trouble understanding the paper, read The Annotated Turing by Charles Petzold (which is wonderful), but felt that reading a reference implementation would help formalize my understanding. When I couldn't find an open source implementation, I decided to write my own.

The implementation includes:

  - Abbreviated tables (m-functions)
  - Conversions to Standard Descriptions and Description Numbers
  - A working universal machine
  - A walkthrough of the paper section-by-section in the context of the codebase

I'm still working on sections 8-11 (the math/logic is a bit difficult for me) - if you understand these sections well enough to explain, I'd love to talk to you!

In general I am interested in new mediums for learning source material (web annotations, walkthroughs, reference implementations, etc.), and was inspired by Karpathy's Zero to Hero course in particular for this project.

14 comments