On “On Recursion”
Our paper (http://www.frontiersin.org/Journal/10.3389/fpsyg.2013.01017/abstract) has generated interesting discussion in a previous post (http://facultyoflanguage.blogspot.com/2014/01/more-on-recursion.html). Here I comment on those comments.
Turing and Gödel:
It is no error to equate Turing computability with Gödel recursiveness. Gödel was explicit on this point (I am quoting from numerous Gödel papers in his Collective Works; I can furnish references if requested): “A formal system can simply be defined to be any mechanical procedure for producing formulas, called provable formulas[...]. Turing’s work gives an analysis of the concept of ‘mechanical procedure’ (alias ‘algorithm’ or ‘computation procedure’ or ‘finite combinatorial procedure’). This concept is shown to be equivalent with that of a ‘Turing machine.’” It was important to Gödel that the notion of formal system be defined so that his incompleteness results could be generalized: “That my [incompleteness] results were valid for all possible formal systems began to be plausible for me[.] But I was completely convinced only by Turing’s paper.” This clearly holds for the primitive recursive functions: “[primitive] recursive functions have the important property that, for each given set of values of the arguments, the value of the function can be computed by a finite procedure.” And even prior to Turing, Gödel saw that “the converse seems to be true if, besides [primitive] recursions [...] recursions of other forms (e.g., with respect to two variables simultaneously) are admitted [i.e., general recursions].” However, pre-Turing, Gödel thought that “[t]his cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle.” But Turing proved the true generality of Gödel recursiveness. As Gödel observed: “The greatest improvement was made possible through the precise definition of the concept of finite procedure, which plays a decisive role in these results [on the nature of formal systems]. There are several different ways of arriving at such a definition, which, however, all lead to exactly the same concept. The most satisfactory way, in my opinion, is that of reducing the concept of finite procedure to that of a machine with a finite number of parts, as has been done by the British mathematician Turing.” Elsewhere Gödel wrote: “In consequence of [...] the fact that due to A.M. Turing’s work a precise and unquestionably adequate definition of the general notion of formal system can now be given, a completely general version of Theorems VI and XI [of the incompleteness proofs] is now possible.”
Intension and Extension:
Properly formulated formal systems can be understood as intensionally and extensionally equivalent to Turing machines. In such systems the axiomatic derivations correspond to the elementary computation steps (e.g., reading/writing); this is as constructive as a Turing machine. (There exists a machine that directly performs derivations in the formal system rather than encoding the information in binary strings to be manipulated by the machine.) Accordingly, Gödel did not see formal systems and Turing machines as simply extensionally equivalent: a formal system is as constructive as a proof: “We require that the rules of inference, and the definitions of meaningful formulas and axioms, be constructive; that is, for each rule of inference there shall be a finite procedure for determining whether a given formula B is an immediate consequence (by that rule) of given formulas A1, ..., An[.] This requirement for the rules and axioms is equivalent to the requirement that it should be possible to build a finite machine, in the precise sense of a ‘Turing machine,’ which will write down all the consequences of the axioms one after the other.” This equivalence of formal systems with Turing machines established an absoluteness: “It may be shown that a function which is computable in one of the systems Si or even in a system of transfinite type, is already computable in S1. Thus, the concept ‘computable’ is in a certain definite sense ‘absolute,’ while practically all other familiar metamathematical concepts depend quite essentially on the system with respect to which they are defined.” Gödel saw it as “a kind of miracle that”, in this equivalence of computability and recursiveness, “one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen.” Emil Post went further into ontology: The success of proving these equivalences raises Turing-computability/Gödel-recursiveness “not so much to a definition or to an axiom but to a natural law” (Post 1936: 105). As a natural law, computability/recursiveness applies to any computational system, including a generative grammar.
Rules and Lists:
The important aspect of the recursive-function/lookup-table distinction is not computability per se (table look-up is trivially computable) but explanation. A recursive function derives--and thus explains--a value. A look-up table stipulates--and thus does not explain--a value. (The recursive function establishes epistemological and ontological foundations.) Turing emphasized this distinction, with characteristic wit, in discussing “Solvable and Unsolvable Problems” (1954). Imagine a puzzle-game with a finite number of movable squares. “Is there a systematic way of [solving the puzzle?] It would be quite enough to say: ‘Certainly [b]y making a list of all the positions and working through all the moves, one can divide the positions into classes, such that sliding the squares allows one to get to any position which is in the same class as the one started from. By looking up which classes the two positions belong to one can tell whether one can get from one to the other or not.’ This is all, of course, perfectly true, but one would hardly find such remarks helpful if they were made in reply to a request for an explanation of how the puzzle should be done. In fact they are so obvious that under the circumstances one might find them somehow rather insulting.” Indeed. A look-up table is arbitrary; it is equivalent to a memorized or genetically preprogrammed list. This may suffice for, say, nonhuman animal communication, but not natural language. This is particularly important for an infinite system (such as language), for as Turing explains: “A finite number of answers will deal with a question about a finite number of objects,” such as a finite repertoire of memorized/preprogrammed calls. But “[w]hen the number is infinite, or in some way not yet completed[...], a list of answers will not suffice. Some kind of rule or systematic procedure must be given.” Gallistel and King (2009: xi) follow Turing’s logic: “a compact procedure is a composition of functions that is guaranteed to generate (rather than retrieve, as in table look-up) the symbol for the value of an n-argument function, for any arguments in the domain of the function. The distinction between a look-up table and a compact generative procedure is critical for students of the functional architecture of the brain. One widely entertained functional architecture, the neural network architecture, implements arithmetic and other basic functions by table look-up of nominal symbols rather than by mechanisms that implement compact procedures on compactly encoded symbols.”
Iteration and Tail Recursion:
This is mathematics, not computer science. (Or, rather, I am a mathematician, now interloping in linguistics. In mathematics, iteration--a general notion applicable to a pattern of succession--is seen as a form of recursion: the function f is defined for an argument x by a previously defined value (e.g., f(y), y < x); but iteration is “tail” recursion given that the previously defined value y is the immediately previously define value.) We are on the computational level, not the level of mechanisms. It is important to recall that Marr and Nishihara (1978) distinguished four--not three--levels: “At the lowest, there is the basic component and circuit analysis--how do transistors (or neurons), diodes (or synapses) work? The second level is the study of particular mechanisms: adders, multipliers, and memories, these being assemblies made from basic components. The third level is that of the algorithm, the scheme for a computation; and the top level contains the theory of computation.” (The theory of computation is mathematical.) Much of the muddling of iteration and tail recursion in the comments on the previous post is the result of misclassifying the level of analysis. “[W]e may consider the study of grammar and UG to be at the level of the theory of computation” (Chomsky 1980: 48). Thus discussion of loops, arrays, etc. is irrelevant. In fact, algorithms and mechanisms are arguable irrelevant in principle. We concur with Chomsky that, for the computational system of language “there’s no algorithm for the system itself; it’s kind of a category mistake. [T]here’s no calculation of knowledge; it’s just a system of knowledge[...]. You don’t ask the question what’s the process defined by Peano’s axioms and the rules of inference, there’s no process” (Chomsky 2013a). Analogously, a Turing machine is not a description of a process or algorithm or mechanism but “a mathematical characterization of a class of numerical functions” (in the words of Martin David (1958: 3), one of the founders of computability theory). Thus to define the faculty of language as a type of Turing machine as we did in our paper, “On Recursion,” is to give a function: “a finite characterization of an infinite set” (Chomsky 2013b). A Turing machine--and thus the language faculty--is defined by a tuple containing a finite set of symbols (axioms), a set of states (with “states” defined as “structures” in the sense of mathematical logic), and a transition function (rule of inference) mapping from state/symbol to state/symbol. “A derivation is thus roughly analogous to a proof with Σ,” a finite set of initial symbols, “taken as the axiom system and F,” the finite set of rewrite rules (or Merge), “[taken] as the rules of inference” (Chomsky 1956: 117), consistent with Gödel’s characterization: “We require that the rules of inference, and the definitions of meaningful formulas and axioms, be constructive; that is, for each rule of inference there shall be a finite procedure for determining whether a given formula B is an immediate consequence (by that rule) of given formulas A1, ..., An[.] This requirement for the rules and axioms is equivalent to the requirement that it should be possible to build a finite machine, in the precise sense of a ‘Turing machine,’ which will write down all the consequences of the axioms one after the other.