SICP 1.2

This week: Procedures and the Processes Who Love Them!

40: "we must learn to visualize the processes generated by various types of procedures" -- contrast bret victor, jedwards, et al
45: process vs procedure re linearly recursive vs recursive
55: why theta instead of oh?
Entscheidungsproblem, etc non-computable (but maybe RE?)
fib tree hausdorff dimension: probably just one (like a binary tree) -- 3-branch tree is log(3)/log(2) ~1.58

LIGHTNING TOPIC: ACKERMANN

• simple proof that countable computable, uncountable funs
• primitive recursive: zero, succ, proj -- closed under composition and primitive recursion
• intuitively, PR has no unbounded loops (e.g. a language using only folds or catamorphisms)
• PR equal to computable?
• PR allows tetration and higher exponentiation...
• but A introduces a "new level" for each m, and is provably not in PR
• so R == (total) computable, bigger than PR (... RE also includes partial computable, bigger than R)
• A is in R: the set of all recursive decision problems, i.e. Turing solvable, i.e. computable
• (curiously, despite A always terminating, it can't be computed by always terminating systems (LOOP))
• R is way harder than NP, but not as hard as RE
• what do we mean by "new level"?
• Knuth up-arrows, Conway's chained arrows, Graham's number, Moser's number
• fast-growing --> slow-growing...
• inverse of A -- algorithm for union-find with path compression

weekly recap message

Hi folks!

We had another great meeting on Friday covering chapter 1.2 of SICP. We decided that for the next meeting we would cover 1.3.1 - 1.3.3, but save 1.3.4 to pair with the beginning of section 2, in order to balance the exercise to reading ratio.

I've added a 1.3 directory to the repo -- please check in your solutions when you get a chance. We also have a number of topic talks scheduled for this coming Friday, so this would be a great time to prepare a short talk on an interesting topic so you'll fit in with the crowd. Peer pressure is a wonderful motivational tool, innit?

Have a great week!

Oct 20