A. , N. Aubrun, and M. Sablik, An order on sets of tilings corresponding to an order on languages Simulation of effective subshifts by two-dimensional subshifts of finite type, 26th International Symposium on Theoretical Aspects of Computer Science AS13. Nathalie Aubrun and Mathieu Sablik, pp.99-110, 2009.

R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, vol.0, issue.66, 1964.
DOI : 10.1090/memo/0066

C. , D. Cenzer, A. Dashti, and J. L. King, Computable symbolic dynamics, Mathematical Logic Quarterly, vol.54, issue.5, pp.460-469, 2008.

C. , D. Cenzer, and J. B. , ? 0 1 classes in mathematics, Handbook of Recursive Mathematics - of Studies in Logic and the Foundations of Mathematics, chapter 13, pp.623-821, 1998.

A. Dashti, Effective Symbolic Dynamics, 2008.

B. Durand, A. Romashchenko, and A. Shen, Effective Closed Subshifts in 1D Can Be Implemented in 2D, Fields of Logic and Computation , number 6300 in Lecture Notes in Computer Science, pp.208-226, 2010.
DOI : 10.1002/j.1538-7305.1961.tb03975.x

URL : http://arxiv.org/abs/1003.3103

M. Richard, H. Friedberg, and . Rogers, Reducibility and Completeness for Sets of Integers, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, pp.117-125, 1959.

G. Higman, Subgroups of Finitely Presented Groups, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol.262, issue.1311, pp.455-475, 1961.
DOI : 10.1098/rspa.1961.0132

H. and M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Inventiones mathematicae, vol.47, issue.1, 2009.
DOI : 10.1007/s00222-008-0161-7

G. Higman and E. Scott, Existentially Closed Groups, 1988.

M. Hochman and P. Vanier, On the turing degrees of minimal subshifts

J. Carl, G. Jockusch, and R. I. Soare, Degrees of members of ? 0 1 classes

K. and P. Kurka, On topological dynamics of Turing machines, Theoretical Computer Science, vol.174, issue.1-2, pp.203-216, 1997.
DOI : 10.1016/S0304-3975(96)00025-4

L. A. Douglas and . Lind, Multi-Dimensional Symbolic Dynamics, Symbolic Dynamics and its Applications, number 60 in Proceedings of Symposia in Applied Mathematics, pp.61-79, 2004.

L. Douglas, A. Lind, and B. Marcus, An Introduction to Symbolic Dynamics and Coding, 1995.

M. and J. S. Miller, Two notes on subshifts, Proceedings of the American Mathematical Society, pp.1617-1622, 2012.
DOI : 10.1090/S0002-9939-2011-11000-1

M. and C. Moore, Generalized one-sided shifts and maps of the interval, Nonlinearity, vol.4, issue.3, pp.727-745, 1991.
DOI : 10.1088/0951-7715/4/3/006

D. Mye74 and . Myers, Non Recursive Tilings of the Plane II, Journal of Symbolic Logic, vol.39, issue.2, pp.286-294, 1974.

R. Raphael and M. Robinson, Undecidability and Nonperiodicity for Tilings of the Plane, Inventiones Mathematicae, vol.12, issue.3, pp.177-209, 1971.

R. A. Yu, M. A. Rumyantsev, and . Ushakov, Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences, 23rd International Symposium on Theoretical Aspects of Computer Science, STACS 2006, number 3884 in LNCS, pp.396-407, 2006.

. J. Sho60 and . Shoenfield, Degrees of Models, Journal of Symbolic Logic, vol.25, issue.3, pp.233-237, 1960.

. Sim11, G. Stephen, and . Simpson, Mass problems associated with effectively closed sets, Tohoku Mathematical Journal, vol.63, issue.4, pp.489-517, 2011.

G. Stephen and . Simpson, Medvedev degrees of two-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems, pp.679-688, 2014.