Decidability of periodic tilings of the plane I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (2) there are finite sets of tiles that tile the plane, but only aperiodically. Also, (1) implies (2).
Is the question "can one tile the plane periodically with the following finite set of tiles?" decidable? 
 A: Deciding whether a set of tiles admits a periodic tiling or no tiling at all is undecidable as well.
This has been shown in Y.S. Gurevich, I.I. Koryakov, Remarks on Berger's paper on the domino problem, J Sib Math J 13, 319–321 (1972).  The results can also be found in the book The Classical Decision Problem by Egon Börger, Erich Grädel, Yuri Gurevich, where Theorem 3.1.7 states

The set of domino systems that admit, respectively, no tiling and a periodic tiling of $\mathbb Z\times \mathbb Z$ or $\mathbb N\times \mathbb N$ are recursively inseparable.

A: The answer appears to be no. 
Consider first the case of the anchor-tile
periodic tiling problem, where we insist that a particular anchor
tile is used. Let's modify the usual Wang tile argument, due to Berger,  for the oringal tiling problem. That argument shows that for any Turing machine
program $p$, we can create a set of Wang tile types (square tiles
with labels on the edges, to be matched up in a tiling) such that
the operation of program $p$ corresponds directly to the pattern of tiles
appearing in any tiling. Basically, the anchor row displays a complete picture of the Turing machine in the start configuration, and each subsequent row shows the configuraton after one additional step of computation using program $p$. The main idea of the scheme is that the tiling can
continue as long as the program keeps running, and so there is a
tiling if and only if the program does not halt. This is why the original anchor tiling problem is undecidable.  (And the anchor feature was removed by a separate argument.)
But essentially the same idea can be used to solve your problem.
We can modify the tiles involving the halt state so that a halting
computation will support a periodic tiling. Basically, what is
needed are tiles that will lead from a tile on which the program
has halted to transform the next row to the initial configuration
again. It would be a detailed thing to check, but after one has
spent time using these Wang tiles to simulate Turing machine
computations, this seems to be easily handled in the same way.
The end situation will be that if $p$ halts, then there will be a
periodic tiling using the desired anchor tile, and if $p$ does not
halt, then there will be no periodic tiling using that anchor
tile. So the question will be undecidable.
Finally, it seems to me that one can remove the anchor tile requirement in the same way that is done 
with the original Wang tile argument (but this is a complication).
