http://tracery.io/ is a tool to generate text. Its input is a mostly context-free grammar, and it outputs random instances of the language defined by that grammar ( Read more... )

I'm being driven kind of nuts by this book because it confuses perfect machine learning with near-perfect predictive ability. The examples given for the consequences for P=NP are simply outlandish. That's not so say they're all wrong--- machine-generated proofs really could demolish long-held problems if that were the situation. But in other ( Read more... )

My interest was sparked by this Quora question: How would you find all the Pythagorean triplets in an array of N numbers? The first answer was the straightforward O(N^2) examination of all pairs of numbers. It seemed like there might be a better way. One of the comments initially suggested O(N^2) was probably the best possible, because of its ( Read more... )

One branch of theoretical computer science looks at "circuit complexity", studying the size and depth of boolean logic circuits necessary to produce a particular function. A puzzle in this area is whether we can invert three binary digits using just two inverters (but as many AND and OR gates as we want ( Read more... )

From "Combinatorial Analysis and Computers", February 1965:

When the size of a combinatorial problem grows very rapidly, we can usually expect the computer to do only about one case larger than can be done by hand.

I am curious whether there are readily-available examples where this is still true.

How to implement a Turing Machine with M:tG cards. This is a pretty impressive reduction.

It's not an extremely surprising result. Once you have pattern-matching and some mechanism for unbounded state, you're pretty close to universal computation. In fact, one of the themes I picked up from reading "Games of No Chance" is how hard it is to ( Read more... )

Brian Hayes discusses whether binary operators and relations need be binary at all. In Scheme, the expression x + y is written (+ x y) and generalizes naturally to (+ x y z a b c). Well, what about (+ x)? That seems harmless enough. But consider (+)? Or (min)?

(= a b) can be extended to the "all equal" relation (= a b c) but what does (!= a b ( Read more... )

Suppose you're playing D&D and have a house-rule spell that does 100 attacks, each performing 1 point of damage to a random live enemy. (Suggested name: Schmendrick's Death From Papercuts.) So, if you are facing exactly one opponent it performs 100 hit points of damage to him; if you are facing 100 enemies each will get, on average, one point of ( Read more... )

Terra Nova has an interesting post today about poker and virtual worlds. Timothy Burke says that poker has two "deep games": a social one (how to read players) and a structural one (the power of position.) The claim is that most VWs also exhibit a social game and a structural game--- how to function within a society of players, and how to exploit ( Read more... )

In Hold'em any two-card hand can make the "nuts" (the best possible hand). Let's call games with this property "nutty"...