Frontier between decidability and undecidability: a survey

AbstractAfter recalling the definition of decidability and universality, we first give a survey of results on the as exact as possible border betweeen a decidable problem and the corresponding undecidablity 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. We then go on with results more specific to classical Turing machines, with a survey of results and a sketchy account on technics. We conclude by an illustration on simulating the 3x+1 problem