Domino Systems

Definition 3.1   For $n \in \mathbb{N}$, let $\mathbb{Z} _n$ denote the set $\{0,\dots,n-1\}$ and $\oplus_n$ denote the addition modulo n. A domino system is a triple $\mathcal{D} = (D,H,V)$, where D is a finite set (of tiles) and $H,V \subseteq D \times D$ are relations expressing horizontal and vertical compatibility constraints between the tiles. For $s,t \in \mathbb{N}$, let U(s,t) be the torus $\mathbb{Z} _s \times \mathbb{Z} _t$, and let $w = w_0 \dots w_{n-1}$ be a word over D of length n (with $n \leq s$). We say that $\mathcal{D}$ tiles U(s,t) with initial condition w iff there exists a mapping $\tau: U(s,t) \rightarrow D$ such that, for all $(x,y) \in U(s,t)$,

• if $\tau(x,y) = d$ and $\tau(x \oplus_s 1,y) = d'$, then $(d,d') \in H$ (horizontal constraint);
• if $\tau(x,y) = d$ and $\tau(x, y \oplus_t 1) = d'$, then $(d,d') \in V$ (vertical constraint);
• $\tau(i,0) = w_i$ for $0\leq i < n$ (initial condition).

Bounded domino systems are capable of expressing the computational behaviour of restricted, so-called simple, Turing Machines (TM). This restriction is non-essential in the following sense: Every language accepted in time T(n) and space S(n) by some one-tape TM is accepted within the same time and space bounds by a simple TM, as long as $S(n),T(n) \geq 2n$ [BGG97].

Theorem 3.2 ([BGG97], Theorem 6.1.2)
Let M be a simple TM with input alphabet $\Sigma$. Then there exists a domino system $\mathcal{D} = (D,H,V)$ and a linear time reduction which takes any input $x \in \Sigma^*$ to a word $w \in D^*$ with |x| = |w| such that

• If M accepts x in time t₀ with space s₀, then $\mathcal{D}$ tiles U(s,t) with initial condition w for all $s\geq s_0+2, t\geq t_0 +2$;
• if M does not accept x, then $\mathcal{D}$ does not tile U(s,t) with initial condition w for any $s,t \geq 2$.

Corollary 3.3
There is a domino system $\mathcal{D}$ such that the following is a -hard problem:

Given an initial condition $w = w_0 \dots w_{n-1}$ of length n. Does $\mathcal{D}$ tile the torus U(2ⁿ⁺¹,2ⁿ⁺¹) with initial condition w?

Proof. Let M be a (w.l.o.g. simple) non-deterministic TM with time- (and hence space-) bound 2ⁿ deciding an arbitrary -complete language $\mathcal{L}(M)$ over the alphabet $\Sigma$. Let $\mathcal{D}$ be the according domino system and $\textit{trans}$ the reduction from Theorem 3.2. The function $\textit{trans}$ is a linear reduction from $\mathcal{L}(M)$ to the problem above: For $v \in \Sigma^*$ with |v| = n, it holds that $v \in \mathcal{L}(M)$ iff M accepts v in time and space 2^|v| iff $\mathcal{D}$ tiles U(2ⁿ⁺¹,2ⁿ⁺¹) with initial condition $\textit{trans}(v)$.