Decidability of tiling of $\mathbb{R}^n$

The non-existence of an algorithm (for the plane) can be found in a paper by Adler and Holroyd, Geometriae Dedicata, 1981. The proof uses a straightforward simulation of Wang tiles.

The book Tilings and Patterns by Branko Grünbaum and Geoffrey Shephard (W.H. Freeman) is still, despite its 1987 publication date, an excellent source of information about tiling questions. Wang tiles and decidability problems are treated in Chapter 11.

Edit 9/30/2015 My revised understanding is still not correct! The undecidability of the tiling problem is not equivalent to the existence of an aperiodic tiling. See Edmund Harris's answer at this related MO post.

Edit 3/14/2013: My original answer below was confusing "undecidability" with "independence from the axioms of set theory," and I want to preface it with my revised, hopefully more accurate understanding.

At one point in time, it was open whether or not there exists a Turing machine which could decide if a given set of tiles would tile the plane. Then Hao Wang showed that this problem was indeed decidable if and only if every set of tiles that could tile the plane could do so periodically. Wang's student Berger, and later others like Penrose demonstrated the existence of aperiodic sets of tiles, thus proving via Wang's result that the tiling problem is undecidable. (No Turing machine could reliably spit out a yes-no answer, given a set of tiles.) For a long time it remained open whether there was a single tile that could only tile aperiodically. (Penrose had gotten it down to 2. Berger had started with about 20,000 I think.) But then in 2010 the Taylor-Socolar tile was discovered. It is a single disconnected tile which tiles the plane but only aperiodically. I've included a picture.

This does not directly address the OP, but is suggestive that it could be an undecidable problem.

Original post: Probably there is not! Indeed I believe there is a single (very complicated) 2D tile for which the problem of whether it tiles the plane is logically undecidable [Edit: meaning independent of the axioms of ZFC set theory]! I don't have the reference handy. Perhaps somebody else can supply it. With a quick Google search, the Wikipedia article on Wang tiles is the closest I could come. Wang tiles are presented as colored tiles where the colors have to match on shared edges, but these can be converted to regular tiles by modifying the boundary so that only like colors can join. According to Wikipedia, there is a set of 13 tiles for which the tiling problem is logically undecidable [Edit: meaning independent of the axioms of ZFC set theory], but I seem to recall hearing that this number has been reduced to 1, but possibly no longer in the Wang tile category.

Edit: As was pointed out to me in the comments, this seems different than asking whether the tiling problem is decidable in the decision problem sense, for which the truth of any finite proposition is assumed to be known, and the question is whether an algorithm exists that successfully runs on the set of all tiles.