A decision procedure using discrete geometry

AbstractA decision procedure is given which makes essential use of concepts in discrete geometry. The procedure decides for any one-state Turing machine with three-dimensional tape, whether or not it has an immortal configuration, i.e., it solves the uniform halting problem for such devices. The history and significance of the problem is examined. The solution is given with the main motivation of showing how traditional mathematical concepts can be used in decision procedures. The paper is introductory in the sense that all notions are carefully defined