Monthly Archives: November 2008

November 14, 2008 · 10:32 pm

Doing Calculus on the Rationals (with the help of Nonstandard Analysis)

Nonstandard Analysis is usually used to introduce infinitesimals into the real numbers in an attempt to make arguments in analysis more intuitive.

The idea is that you construct a superset \mathbb{R}^* which contains the reals and also some infinitesimals, prove that some statement holds of \mathbb{R}^*, and then use a general “transfer principle” to conclude that the same statement holds of \mathbb{R}.

Implicit in this procedure is the idea that \mathbb{R} is the real world, and therefore the goal is to prove things about it. We construct a field \mathbb{R}^* with infinitesimals, but only as a method for eventually proving something about \mathbb{R}.

We can do precisely the same thing with \mathbb{Q} instead of with \mathbb{R}. But, in Weak Theories of Nonstandard Arithmetic and Analysis, Jeremy Avigad observed that if we don’t care about transferring the results back down to \mathbb{Q}, then we can get all the basic results of calculus and elementary real analysis just by working with \mathbb{Q}^*, and without ever having to construct the reals.

Continue reading →

5 Comments

Filed under Uncategorized

November 9, 2008 · 10:38 am

Games Which are Impossible to Analyze

In the last post, I mentioned the computational complexity of various games. To be explicit, we consider each “game” G to actually be a sequence of games \{G_n\} for n\in \mathbb{N}. For example, \text{checkers}_n would be checkers played on an n\times n board. The problem was then to analyze the computational complexity of the function which takes n and tells you which player has a winning strategy and what the winning strategy is. I’ll call that function the analysis function of G.

Are there any games which can actually be played in the real world with an undecidable analysis function? Robern Hearn, in the same thesis that I linked to last time, showed that the answer is yes.

Continue reading →

Leave a Comment

Filed under Uncategorized

November 3, 2008 · 10:35 pm

How to Show that Games are Hard

Peg Solitaire is a pretty popular game, often found in restaurants (including Cracker Barrel, if I remember correctly). It’s also NP-complete (by which I mean determining a winning strategy given the initial set-up is an NP-complete problem). You may have also heard of computational complexity results for Minesweeper (see here, for example). There are a number of other results showing that various popular games are complete for some complexity class.

But what if you come across a new game, which no computer scientist has heard of yet? Well, you’re in luck, as Robert Hearn, in his thesis, formulated a framework called Constraint Logic intended to make it easy to prove complexity results for games.

Continue reading →

2 Comments

Filed under Uncategorized