- if and , then (horizontal constraint);
- if and , then (vertical constraint);
- for (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
[BGG97].

- If
*M*accepts*x*in time*t*_{0}with space*s*_{0}, then tiles*U*(*s*,*t*) with initial condition*w*for all ; - if
*M*does not accept*x*, then does not tile*U*(*s*,*t*) with initial condition*w*for any .

Given an initial conditionof lengthn. Doestile the torusU(2^{n+1},2^{n+1})with initial conditionw?

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

May 02 2000