There were several mistakes in PS5, Problem 1, which are now corrected (updated ps5.pdf, ps5.zip).
Problem 1a should be:
Prove that when $f^*(i) = 0$, $f_{i+1} = f_i$. That is, the two functions denoted by $f_{i + 1}$ and $f_i$ are actually the same function.Thanks to Joey Rudek for noticing the problem!
Problems 6 and 7 mixed up NAND-CIRC and NAND-TM. Problem 6 should be asking if NAND-LOOP is more powerful than NAND-CIRC (it would be silly to ask if it is more powerful than NAND-TM, since NAND-TM has everything in NAND-LOOP plus arrays, so there’s no way NAND-LOOP could be more powerful than NAND-TM). Similarly, Problem 7 should be asking if NAND-ARRAY is more powerful than NAND-CIRC.
Thanks to Jiahe for pointing out the problems!
Sorry for all the confusing mistakes on this problem set.