An Interesting Puzzle in Propositional Logic

Suppose that you’re translating an ancient text, and in this text you come across three words whose meaning you are unsure of: , , and .  So, you head down to the ancient language department of your local university. The first professor you come across, , knows what means, the second professor you come across, […]

What Happens When You Iterate Gödel’s Theorem?

Let be Peano Arithmetic.  Gödel’s Second Incompleteness Theorem says that no consistent theory extending can prove its own consistency. (I’ll write for the statement asserting ‘s consistency; more on this later.) In particular, is stronger than .  But certainly, given that we believe that everything proves is true, we believe that does not prove a […]

A Simple Introduction to Quantum Groups

In the course of reading some background material for an article by James Worthington on using bialgebraic structures in automata theory, I was led to finally reading up on what a Hopf algebra (sometimes called a “quantum group“) is. Although it is not strictly related to logic, I’ll write up what I learned here.

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” to actually be a sequence of games for . For example, would be checkers played on an board. The problem was then to analyze the computational complexity of the function which takes and tells you which […]

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 […]