502 – More on tilings

October 16, 2009

In class I mentioned without proof that there is a finite set of squares with which we can tile the plane, but not periodically. Hao Wang was the first to study the question of whether there are such tilings. He conjectured that the answer was not. In 1966, his student Robert Berger disproved the conjecture. He explained how tiles could be used to code the workings of a formalized computer (a Turing machine), in a way that one could solve recursively the Halting Problem if it were the case that any set that tiles can do so periodically. Since it is a well-known result from computability theory that the halting problem cannot be solved recursively, it follows that Wang’s conjecture is false.

Examining the tiling given by Berger, one finds that he requires 20426 tiles to do his coding. The number has been substantially reduced since. I believe the currently known smallest set of tiles that can only cover the plane aperiodically has size 13. It was exhibited by Karel Culik II in his paper An aperiodic set of 13 Wang tiles, Discrete Mathematics 160 (1996), 245-251. The Wikipedia entry on Wang tiles displays his example. Once again, the proof of aperiodicity uses the halting problem.

(I would be curious to know of improved bounds.)

502 – Ordinal exponentiation

October 16, 2009

The exercise I mentioned in class is the following: Let \alpha^{\cdot\beta} denote ordinal exponentiation. For ordinals \alpha,\beta, define F(\alpha,\beta) as the set consisting of those functions f:\beta\to\alpha such that there are only finitely many \xi such that f(\xi)\ne0. 

(We haven’t formally defined “finite” yet, but we can take this to mean that the order type of the set \{\xi\in\beta\mid f(\xi)\ne0\} is a natural number, using our formalized notion of natural number.)

For functions f,g in F(\alpha,\beta) set f\triangleleft g iff f(\xi)<g(\xi) for \xi largest such that f(\xi)\ne g(\xi).

Then (F(\alpha,\beta),\triangleleft) is a well-ordered set, and its order type is precisely \alpha^{\cdot\beta}.