Frontier between decidability and undecidability: A survey (Q1575913)

The author gives first a survey of results on the border between a decidable problem and the corresponding undecidability question in various models of discrete computation: diophantine equations, word problem, Post systems, molecular computations, register machines, neural networks, cellular automata, tiling the plane and Turing machines with planar tape. After that the author studies the deterministic Turing machines with a single bi-infinite tape and a single head and introduces notions of decidability criteria and strong decidability criteria. At the end the \(3x + 1\) problem is considered.