  Recent work has examined how undecidable problems can arise in quantum
information science. We augment this by introducing three new undecidable
problems stated in terms of tensor networks. These relate to ideas of Penrose
about the physicality of a spin-network representing a physical process, closed
timelike curves, and Boolean relation theory. Seemingly slight modifications of
the constraints on the topology or the tensor families generating the networks
leads to problems that transition from decidable, to undecidable to even always
satisfiable.
