Hacker News new | past | comments | ask | show | jobs | submit login
The Strangest Book on the Theory of Computation (2009) (recursed.blogspot.com)
138 points by Hooke 5 months ago | hide | past | web | favorite | 32 comments

What a coincidence.

Last week, I had a midterm that covered formal languages and automata theory. I went to the Davis Centre Library at the University of Waterloo looking for books on Automata Theory. I stumbled upon that very book. And though I dismissed it because the formatting was horrible, I did notice its odd epigraphs. I found the cover a bit mysterious and amusingly out of place, and went with something else.

Now, I read here on Hacker News, a high-profile website, about this most obscure review of this most obscure book written almost ten years ago - what's more? The person who wrote the review is also the one that requested that the library orders the book in the first place. He is one of my professors. Quite frankly the personification of what you would hope a scholar and teacher to be.

I know I have no reasons to feel agitated but why do I feel like this is the prologue of a thriller?

To make it more Borgesian for you, I have been baffled by the fact that the author of Automata Theory, Matthew Simon, has left almost no traces on Google besides this book and one other book called Emergent Computation, which is similarly eccentric. (Browsing it now, I came across a weird quote about Pope Clement and self-flagellation, then it's right back to automata theory again).

Could it be that he wrote under a pen name?

It's time travel and superposition of interfering multiverses all the way down :P

I feel like there's something I'm missing: it doesn't make any sense that this book would be published...

Reading some of the preview material at Amazon, the chapters often start with brutal depictions of violence against African American slaves. I get no sense of the purpose of these passages; they don't appear to be taking a stance in anyway, just quoting from old sources.

The only charitable interpretation I can think of is something along the lines I remember Asimov writing about: humankind always uses slaves; they stop when it's economically viable to use machines instead. And in a way automata theory is a very general theory of abstract machines which we use to substitute human labor in many ways... So maybe he's giving a visceral reminder of the importance of the subject matter at hand (automata theory)?

Additionally, the table of contents does look interesting. I've read Sipser, and I'd now be interested in this different angle on the subject (Sipser felt more isolated from other parts of mathematics; this starting out by connecting to semigroups for instance seems interesting)—but that said, it's just too bizarre:

Its 'Chapter 0,' titled "Mathematical Preliminaries," opens with a full-page passage of the sort I described above. To give the flavor, here are a few lines included in it:

"... Who are generally presented, being secur'd by Bastias or negro drivers, And instantly tied Up to the Beams of the Plaza, or a Tree, Without so much as being heard, When the flogging begins, men, women, or children, without exception, on theyr long naked bodies, by long hempin whips that cut round at every lash, and crack like a pistol, during which they alternately repeat Dankee Massera, /Thank You Master/, but while he stalks up and down with his overseer..."

—and on and on. wtf.

The next page is the standard sort of presentation of mathematical notation you'd expect.

Just a heads up, there are two types of semigroups out there, and I think that automata theory uses the weird (i.e., non-algebraic) kind, so don't be too disappointed if this doesn't hook in with other standard maths. I have only seen this second usage of semigroups in automata theory, and only heard it used by an automata theorist. A quick Google search didn't turn up this other usage, so it seems to be very domain-specific lingo.

On the other hand, you can look into algebraic automata theory (a subject I know nothing about) and play with monoids (the kleene closure of an alphabet with the concatenation operation is the free monoids over that alphabet).

Does it really bother you that much? Aren't you amused, even slightly?

I don't mean to give the wrong impression: I'm actually highly amused by it. But at the same time, as a heuristic for judging whether something I might read is worthwhile or not... well, the author gives me the impression of being slightly off his rocker, which makes me question whether I can trust the material.

> Aren't you amused, even slightly?

What about that do you find amusing?

Another fascinating and strange book on logic — The Laws of Form — is worth tracking down. Even more strange, the only other book published by the author, under a pseudonym.

Thanks for sharing, this is a fascinating topic I just started investigating. Check out "Calculating Space" by Konrad Zuse (the inventor of the first programmable computer). Coincidentally, he published in 1969 - "The Laws of Form" was published the same year.

Link: ftp://ftp.idsia.ch/pub/juergen/zuserechnenderraum.pdf

My knowledge of computation theory is not good enough to judge the book. Why he used the strange quotes. Who knows. But he wrote more books. Like this one:


You can browse a little bin on google books: https://books.google.com.sg/books?id=d2i8q2PayrQC&pg=PR7&lpg...

Must say, the content looks rather interesting to me. I am actually consider buying it.

You can browse a few pages of the Simon book at this link supplied in the OP's comments section[1]. It actually looks like a highly readable intro to automata theory, and much more enjoyable than Hopcroft and Ullman's book Introduction to Automata, Languages, and Computation that the OP himself recommends in his comments. I found Hopcroft and Ullman to be a dull, formal proof-based approach with few of the practical examples that one needs to get an intuitive feel for a subject. The Simon book might be a bit of the opposite--too many practical examples and not enough theory--but, hey, I would have preferred that over Hopcroft and Ullman (or in addition to it).

Many of OP's objections come off as petty, like "the author uses the capital letter "X" to represent ×, the cross product symbol." Come on, really? I think the OP's real reason for hating the book was the strange quotes Simon used; it was a bad decision for Simon to use those quotes even if he had absolutely no political agenda, because someone somewhere is going to take it the wrong way, and academia being the leading edge of the politically correct movement is especially dangerous.

[1] http://www.google.com/url?sa=t&source=web&ct=res&cd=1&url=ht...

That's a bit unfair, Hopcroft and Ullman is extensive and detailed by design. They invented the field AFAIK so this book ought to be deep as they use it to lay its foundations. If you - or lurkers - are looking for a solid, down-to-earth exploration of automata theory - but not so much proofs, then I would recommend these in no particular order:

- "Introduction to the Theory of Computation" [Part I] by M. Sipser

- "Introduction to Compiler Design" by Torben A. Mogensen

- "An introduction to Formal Languages and Automata" by P. Linz

- "Languages and Machines" by Thomas A. Sudkamp

>Many of OP's objections come off as petty

I have had the book in my hands, I have turned the pages and seen the typesetting myself. It's not an exaggeration. It looks like one of those books written by a typewriter with some of the lines are misaligned, except it wasn't and that is overall a pain to parse. Also the pages are small and margins wide.

Why inflict that upon yourself when there are plenty of other books that show a modicum of effort in editing.

> Come on, really?

Yes, really. It's exceedingly annoying to read a mathematics text that does not conform to the usual typographic conventions. These kinds of considerations are particularly important if one wants to teach out of a textbook, because it gets annoying and confusing for students to constantly have to transcribe notation into the modern convention.

Looks like it was typeset in MS Word. Seems this project is a good start but really could use some editing.

Given their assessment of the book, I don't see what the point was in even bringing it up in the first place.

The slavery quotes at the beginning of each chapter certainly make this strange enough that I’m glad to have heard of it

HN is, at least in name, about stuff that gratifies "intellectual curiosity", not pruient or morbid curiosity.

It's an oddity. How did it get published? How does the author manage to maintain a professional career?

NB the person writing the blog had bought a copy, so it's effectively a warning—and a negative review. Nothing inexplicable about that.

I tried googling around for Matthew Simon and couldn't find anything, even with San Jose State University added to the search terms (found from "Look Inside" on Amazon for the book--worth a look by itself). I'm a bit disappointed, was hoping for a zany blog or old school static site to enjoy.

If you’re in the mood for something zany and tech related there’s always Fabian Pascal:


FWIW, the reason it didn't seem to me worth mentioning is that it seems the kind of book that no-one would get unless they'd seen it recommended.

The author of the blog post bought it based on a description in a catalog, so evidently it seemed promising enough at least to them, and by the same token, worth reporting on. So there's no mystery about why the blog author felt it was worth making this post.

Curiosity value aside, buying an advanced textbook on spec based on the specific topics it promises to cover doesn't seem that uncommon, particularly if you are somehow isolated.

IMO hardly anyone is going to purchase or even pay attention to something unless they've seen some positive recommendations for it.

In a world of information-overload, I don't think it helps to call attention to things that aren't worth other people's time.

OK, I get that you object to the blogger "surfacing" this book at all.

More generally, though, a lot of people pay attention to value cues like the simple fact that something has been professionally published. With books, I'm sure you would agree that there are multiple filters that people apply. The general availability of a book attests to the fact that it passed some kind of quality control, however feeble.

The general condition when it comes to reviewing is that the products are out there anyway, so both positive and negative reviews are appropriate. The tradition of literary book reviews (e.g. the NYRB, LRB) is to turn the review into an timely essay, maybe cover a few recent releases, express an opinion, pass on the most interesting facts etc. The point is to make the review a self-contained literary work, capable of being read for its own sake, for information or for pleasure.

I think that's what this blog post does, it takes something curious and makes an entertaining story out of it. You might think that this isn't "worth other people's time", in the sense that it doesn't advance an alternative, more relevant approach to covering the book's subject matter. But the review is potentially worth their time if it sheds light on anything (academic eccentricity, the importance of typesetting in scholarly work, anxieties about systemic racism in 21st C academic writing, etc.)

There's another discussion to be had about fields where negative reviews are rare, like visual art. In that case, publishing any review at all does serve to draw attention to/advertise/"surface" the artwork in question. Critics aren't really able to distance themselves from the world of artists and curators, so they can't really say anything too negative.

But that's a bit of a digression.

The book might not be worth people's time as a CS text. That doesn't mean the blog post isn't worth their time as a reflection on other phenomena.

Underwood Dudley wrote multiple books about mathematical cranks. Cranks get a bad press for wasting mathematicians' time and being impossible to convince of the errors in their work. But isn't the phenomenon of crank culture interesting, and couldn't it potentially teach us something about human nature?

I saw things the same way as you. There are millions of books out there, most of them are pretty worthless. Not much point in drawing attention to one book not worth reading. I was hoping for something more along the lines of 'this book looks at things from a unique viewpoint but it actually makes sense'.

I think books on academic topics like this are typically not that numerous (eg about a dozen on this sort of introductory formal languages and automata), and as they don’t really make money for the author they are typically written by academics who either want there to be course material for some undergraduate course they are teaching or by academics who want to teach other academics/grad students about their field.

I would also argue with your point about most books being worthless. All books from an actual publisher will have been read by someone who has decided that the book will likely make money (and so should be printed), and that it will make money because it is worth money to the people who buy it. Eg I think the author of the article would probably consider any of the other books on the subject to not be worthless. All fiction books can basically be considered to have entertainment value, in the same way that a movie has value even if you won’t make money from seeing it.

There are books that many would consider worthless to themselves (eg books about advanced mathematics or some particular small region in history and space), and there are also books that many would consider worthless to any person (I suppose this is what you are referring to as worthless? Things that are more like terrible self-published fiction or conspiracy theory treatises).

I think this is interesting because it is unusual to see the second category disguised as the first for mathematics textbooks. I think it is also interesting to wonder why the author wrote such a book and why they made the strange choices in it. I would certainly guess that the author is some kind of not-very-formal linguist rather than a mathematician. I suppose it is more common to see the second class of “worthless book” trying to look like history books than mathematics books.

“Mirror Worlds” by David Gelernter if you want a weird CS book that contains genuine insight.

Seems to be overwhelmed by traffic.

Terrible textbooks are written all the time by cranks and eccentrics, and I did not see how this book stood out from the rest.

Title seems to imply there's only one theory of computation.

The Theory of Computation


The Theory of Computation

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact