Effective computability
Peter James Smith · Cambridge University Press eBooks · 2013
The previous chapter talked about functions rather generally. We now narrow the focus and concentrate more specifically on effectively computable functions. Later in the book, we will want to return to some of the ideas we introduce here and give sharper, technical, treatments of them. But for present purposes, informal intuitive presentations are enough. We also introduce the crucial related notion of an effectively enumerable set, i.e. a set that can be enumerated by an effectively computable function. Effectively computable functions (a) Familiar school-room arithmetic routines – e.g. for squaring a number or finding the highest common factor of two numbers – give us ways of effectively computing the value of some function for a given input: the routines are, we might say, entirely mechanical. Later, in the logic classroom, we learn new computational routines. For example, there's a quite trivial syntactic computation which takes two well-formed formulae (wffs) and forms their conjunction, and there's an only slightly less trivial procedure for effectively computing the truth value of a propositional calculus wff as a function of the values of its atoms. What is meant by talking of an effective computational procedure? The core idea is that an effective computation involves (1) executing an algorithm which (2) successfully terminates . 1. An algorithm is a set of step-by-step instructions (instructions which are pinned down in advance of their execution), with each small step clearly specified in every detail (leaving no room for doubt as to what does and what doesn't count as executing the step, and leaving no room for chance). …