pith. sign in

arxiv: 1102.1189 · v2 · pith:INLJ3C6Onew · submitted 2011-02-06 · 💻 cs.DM

Pi01 sets and tilings

classification 💻 cs.DM
keywords configurationstilesetcomputableconsequencecountabledegreesexactgiven
0
0 comments X
read the original abstract

In this paper, we prove that given any \Pi^0_1 subset $P$ of $\{0,1\}^\NN$ there is a tileset $\tau$ with a set of configurations $C$ such that $P\times\ZZ^2$ is recursively homeomorphic to $C\setminus 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.