Turing projectability.
Tim McCarthy, Stewart Shapiro · Notre Dame Journal of Formal Logic · 1987
IntroductionLet N be the set of natural numbers.A function g: Λf-> N is effectively (or mechanically) computable if there is an algorithm or effective procedure which, given (a representation of) an integer n as input, terminates after finitely many steps, and yields (a representation of) g(n) as output.The Church-Turing thesis (CT) states that the effectively computable number-theoretic functions are precisely the Turing computable number-theoretic functions, or, equivalently, the recursive functions.In this paper, we develop a generalization of the notion of mechanical computability and use CT to argue for an analogous thesis concerning that generalization. 1 It is an important aspect of the classical notion of effective or mechanical procedure that an effective procedure terminate for each natural number given as input. 2 We consider here a generalization of effective computability according to which a nonterminating effective process may be said to determine the values of a number-theoretic function.Our idea is to describe such a process in the following terms.There is, first, an effective procedure (in the ordinary sense) which, applied to any input m, generates a computation that proceeds in stages σ lw , σ 2m , Secondly, there is an effective function / which, applied to any stage σ nm of the computation, yields & projection, or tentative value, for the computation at the stage n.The projection is subject to revision, in the sense that at a further stage σ km (k > n), it may happen thatf(σ km ) Φf(σ nm ).But we allow the projected value to change only finitely often, so that for each m there is a value p such that ln\fk> nf(σ km ) = p.We say that the given pair of effective procedures is a projective strategy.The function g is said to be projected by that strategy if and only if for each m an n can be found such that Vk>nf(σ km )=g(m).In this case, we say that the strategy is stable for m at stage n?