We recommend downloading and viewing or printing the Postscript files, due
to their much better presentation. Postscript files follow the style of
the text (fonts, sizes, notation, etc.), whereas HTML files use whatever tools
are at hand to render the mathematical formulae.
Exercise 4.6 (page 117): prove that a Turing machine that can leave its
head stationary is no more powerful than our standard TM.
Retrieve the Postscript file or the
HTML file.
Exercise 4.13 (page 118): prove that 3-register RAM can simulate a
k-register RAM, for any k > 3.
Retrieve the Postscript file or the
HTML file.
Exercise 4.20, part 4 (page 120): devise a Post system that, on inputs
m and n, will produce 2mn.
Retrieve the Postscript file or the
HTML file.
