Computational Processes and Incompleteness
Source: Carnegie Mellon University
The authors introduce a formal definition of Wolfram's notion of computational process based on cellular automata, a physics-like model of computation. There is a natural classification of these processes into decidable, intermediate and complete. It is shown that in the context of standard finite injury priority arguments one cannot establish the existence of an intermediate computational process. Degrees of unsolvability were introduced in two important papers by Post and Kleene and Post. The object of these papers was the study of the complexity of decision problems and in particular their relative complexity: How does a solution to one problem contribute to the solution of another, a notion that can be formalized in terms of Turing reducibility and Turing degrees.