file.pdf (641.5 kB)
K-graph machines : generalizing Turing's machines and arguments
journal contributionposted on 1996-01-01, 00:00 authored by Sieg, John Byrnes
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 informal concept with a mathematically precise one, has hardly progressed beyond the pioneering work of Church, Go╠ê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 involed, 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 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."