Ⅱ_1~0 Sets and Tilings

摘要

In this paper, we prove that given any Ⅱ_1~0 subset P of {0,1}~N there is a tileset r with a countable set of configurations C such that P is recursively homeomorphic to C U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.