Puzzle 3

A weak tiling system is a quadruple ${\mathcal D} = (D,D_0,H,V)$ where $D$ is a finite set, $D_0 \subseteq D$ and $H,V \subseteq D \times D$. A tiling by ${\mathcal D}$ is a function $f : \Nat \times \Nat \to D$ such that the following hold:

$f(m,0) \in D_0$ for all $m \in \Nat$.
$(f(n,m),f(n{+1},m)) \in H$ for all $m,n \in \Nat$.
$(f(n,m),f(n,m{+1})) \in V$ for all $m,n \in \Nat$.

Show that it is undecidable whether there exists a tiling by a weak tiling system.

(Normally, a tiling system is specified as a quadruple ${\mathcal D} = (D,d_0,H,V)$, where $D$, $H$ and $V$ are as above and $d_0 \in D$. A tiling $f$ by such a system ${\mathcal D}$ must satisfy $f(0,0) = d_0$. In the puzzle, the constraint at the origin is replaced by a weak constraint for the bottom row of the tiling. Notice that the weak constraint does not insist that all tiles from $D_0$ be used on the bottom row.)