K-graph machines : generalizing Turing's machines and arguments

Abstract: "The notion of mechanical process has played a crucial role in mathematical logic since the early thirties; it has become central in computer science, artificial intelligence, and cognitive psychology. But the discussion of Church's Thesis, which identifies the informalconcept with a mathematically precise one, has hardly progressed beyond the pioneering work of Church, Gödel, Post, and Turing. Turing addressed directly the question: What are the possible mechanical processes a human computor [sic] can carry out in calculating values of a number-theoretic function? He claimed that all such processes can be simulated by machines, in modern terms, by deterministic Turing machines.Turing's considerations for this claim involved, first, a formulation of boundedness and locality conditions (for linear symbolic configurations and mechanical operations); second, a proof that computational processes (satisfying these conditions) can be carried out by Turing machines; third, the central thesis that all mechanical processes carried out by human computors [sic] must satisfy the conditions. In Turing's presentation these three aspects are intertwined and important steps in the proof are only hinted at. We introduce K-graph machines and use them to give a detailed mathematical explication of the first two aspects of Turing's considerations for more general configurations, i.e. K- graphs.This generalization of machines and theorems provides, in our view, a significant strengthening of Turing's argument for his central thesis."