I have no idea what's going on in the lambda calculus excerpt further down the page, in particular substituting (λx.x x) with (x x)? There seems to be a fairly big misunderstanding here. And lambda calculus isn't reduced in any particular order -- there are many ways to reduce the same term.
I think books like this are a good idea, and having self-taught people write them is also a good idea. BUT it looks like this particular book is in serious need of quality control.
(Also it should be split up into several parts. Any book that teaches both the Y combinator and how to configure zsh is... weird.)
> Lambda Calculus is reduced from left to right, which is very important
No, you can do feasible reductions in any order. The problem is that you need to define β-conversion and normal forms (β normal from is obtained by repeatedly applying β-conversion to the leftmost redex).
Also, the example reduction is just wrong. You cannot transform (λx. x x) (λx. x x) into x x (λx. x x) - that's just not how β-reduction works. Applying a β-reduction to that term yields the same term, because you substitute the second expression for x in the first, thus obtaining the input all over.
> That "undecidable" part is what makes this problem [the Halting Problem] NP-hard.
I mean, that's true - but it's very misleading. The most common context in which NP-hardness is discussed is when talking about NP-complete problems - those that are NP-hard and in NP. The way you go about showing that a problem X is NP-complete is showing that it's in NP (most of the time, this is the easy bit) and then showing that it's at least as hard as some NP-complete problem Y. This is usually done by transforming an arbitrary instance of Y into an instance of X in (deterministic) polynomial time, and showing that the X-instance is satisfiable iff (<=>) the Y-instance is.
Then there are problems for which NP-hardness has been shown but it's unclear whether they're in NP. Those are often of a continuous nature. I think deciding whether a level of Super Mario World is doable falls into this category.
> The basic concept that people have figured out, so far, is that a number of NP-complete problems can likely be solved if we crack the Boolean Satisfiability problem.
And
> If NP-Complete problems get resolved, it is likely (though nobody knows for sure) that we'll crack every NP-Problem
Isn't the definition of a NP-Complete problem exactly that it is in NP _and_ every other problem in NP can be reduced to it in polynomial time. So we know _for sure_ ([Cook71]), that as soon we have a polynomial algorithm for SAT _every_ problem in NP can be solved in polynomial time, and not just some of them as the excerpt claims.
Am I missing something? Because this seems like a very confusing, if not downright wrong, way to explain NP-completeness and its link to SAT.
[Cook71] Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158.