How can you not also mention “The Armchair Universe”? 
(Same Author, earlier book.) I remember writing a QBasic program to draw the mandlebrot set based on the descriptions of the mathematics in that book!) It is a collection of his “Mathematical Recreations” columns that were published in Scientific American. While I’ve not read “The New Turing Omnibus,” I do recommend the Armchair Universe. (What geek can’t find the description of “corewar” interesting?
List of books by this Author:
http://www.csd.uwo.ca/faculty/akd/PERSONAL/books_and_articles.html