Natural language - no infinity and probably no recursion

Natural language – no infinity and probably no recursion Erkki Luuk (erkkil@gmail.com) Institute of Computer Science, University of Tartu, Liivi 2 50409 Tartu, Estonia Hendrik Luuk (hendrik.luuk@gmail.com) Department of Physiology, University of Tartu,  Abstract 1 Recursion We question the need for recursion in human cognitive processing by arguing that a generally simpler and less resource demanding process – iteration – is sufficient to account for human natural language and arithmetic performance. We claim that the only motivation for recursion, the infinity in natural language and arithmetic competence, is equally approachable by iteration and recursion. Second, we submit that the infinity in natural language and arithmetic competence reduces to imagining infinite embedding or concatenation, which is completely independent from the ability to implement infinite computation, and thus, independent from both recursion and iteration. Furthermore, we show that natural language is a finite rather than infinite set.  recursion; iteration; language; brain; infinity; embedding; arithmetic. Recursion and embedding An influential line of thought claims that a hallmark of human cognitive processing is recursion (e.g. Fitch, Hauser, & Chomsky, 2005; Hauser, Chomsky, & Fitch, 2002; Premack, 2007). Hauser et al. (2002) drew a distinction between the whole language faculty, including the aspects shared with other species or faculties (the faculty of language in the broad sense) and the unique aspects of the language faculty (the faculty of language in the narrow sense). They hypothesized that the unique aspects of the language faculty comprise only the core computational mechanisms of recursion as they appear in narrow syntax and the mappings to the Sensory-Motor and Conceptual- Intentional interfaces (Hauser et al., 2002, p. 1573). Lately, this hypothesis has been vigorously challenged (e.g. (Jackendoff & Pinker, 2005; Pinker & Jackendoff, 2005). Interestingly, none of the challenges question the infinity in natural language, and recursion is contested only in Lieberman (2008) and Bickerton (2009) from a neuroscientific and linguistic perspective, respectively. An earlier version of this paper The redundancy of recursion and infinity for natural language appeared in Cognitive Processing (2011, 12 (1)). As compared to the earlier version, some inaccuracies have been corrected, loosely relevant parts omitted and new arguments added to the present paper. Defining recursion Rogers Jr. (1987, pp. 5-6) gives the following description of a Godelian recursive definition: A recursive definition for a function is, roughly speaking, a definition wherein values of the function for given arguments are directly related to values of the same function for simpler arguments or to values of simpler functions. For example, in the recursive function for defining Fibonacci numbers (for integers n>1), Fib(n) is directly related to Fib(n-1) and Fib(n-2): Fib(n) = Fib(n-1) + Fib(n-2). For the present discussion, the most imporant aspect of recursion lies in its ability to describe an infinity of (input,output) pairs by a finitely definable set of operations in an effectively computable manner (see Odifreddi, 1992, pp. 34-36, for details). Recursion differs from iteration (another form of repetition) in two essential respects. First, definitions employing iteration do not involve self-reference. Second, without self-reference, every (input,output) pair needs to be defined explicitly, rendering it impossible to define infinite sets by finite means other than by a control flow loop. Computationally, there is a clear difference between a procedure that invokes another instance of itself (recursion) and a procedure that repeats itself either mechanically or with a control flow loop (iteration). Recursion and iteration are the only computational solutions for handling repetition. As a rule, implementations of recursive functions are slower than those of iterative because recursive functions must allocate memory for their multiple instances. In Abelson et al. (1996), the difference between recursive and iterative processes is captured as follows. Recursive processes are characterized by a chain of deferred operations and require that the interpreter keep track of the operations to be performed later on. An iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state. All this being said, recursive procedures (or definitions) tend to be formally and notationally more elegant than iterative ones. The difference between process and procedure is explained below. The influential paper by Hauser et al. (2002) was the first to explicitly formulate the view that recursion is a component of the language faculty (regrettably, no definition of recursion was given in the article).