What sort of theoretical machine would be needed to solve the tiling problem?
According to Wikipedia, the halting problem reduces to the tiling problem. This means that one thing that prevents Turing machines from solving the tiling problem is their inability of deciding whether a given procedure ever halts. The tiling problem might be even more difficult that the halting problem, but unfortunately I wasn't able to confirm or disprove this.