Computability and the algebra of fields: Some affine constructions
John Vivian Tucker · Journal of Symbolic Logic · 1980
A natural way of studying the computability of an algebraic structure or process is to apply some of the theory of the recursive functions to the algebra under consideration through the manufacture of appropriate coordinate systems from the natural numbers. An algebraic structureA= (A;σ1,…,σk) iscomputableif it possesses a recursive coordinate system in the following precise sense: associated toAthere is a pair (α, Ω) consisting of a recursive set of natural numbersΩand a surjectionα:Ω→Aso that (i) the relation defined onΩbyn≡αmiffα(n) =α(m) inAis recursive, and (ii) each of the operations ofAmay be effectively followed inΩ, that is, for each (say)r-ary operationσonAthere is anrargument recursive function onΩwhich commutes the diagram whereinαrisr-foldα× … ×α. This concept of a computable algebraic system is the independent technical idea of M.O.Rabin [18] and A.I.Mal'cev [14]. From these first papers one may learn of the strength and elegance of the general method of coordinatising; note-worthy for us is the fact that computability is a finiteness condition of algebra—an isomorphism invariant possessed of all finite algebraic systems—and that it serves to set upon an algebraic foundation the combinatorial idea that a system can be combinatorially presented and have effectively decidable term or word problem.