tag:blogger.com,1999:blog-5275657281509261156.post191772215810557342..comments2024-03-28T04:04:55.806-07:00Comments on Faculty of Language: More on recursionNorberthttp://www.blogger.com/profile/15701059232144474269noreply@blogger.comBlogger50125tag:blogger.com,1999:blog-5275657281509261156.post-2769578521780535252014-01-21T04:02:13.919-08:002014-01-21T04:02:13.919-08:00" Professor Goldsmith asks “What is an non-ar..." Professor Goldsmith asks “What is an non-arbitrary set?” Elementary: A set is non-arbitrary if conditions on set membership exist."<br /><br />I don't really understand this. Is this another vague way of saying a computable set?<br /><br />Suppose I take a random set of numbers less than 10^100. This is computable. It has a finite condition on set membership.But it is clearly arbitrary; they are not formed according to a rule.<br /><br />Consider the set of all indices of halting Turing machines. This has a finite condition -- it is well-defined, and not arbitrary. But it is not computable. <br /><br />The Chaitin/Kolmogorov/Solomonoff stuff -- which John Goldsmith is extremely familiar with -- is a completely different theory which you do not discuss or mention or cite (correct me if I am wrong) in the paper in question. I think the Kolmogorov/Chaitin notion of randomness is a good way of making the notion of arbitrariness contentful, and additionally of formalizing versions of learning. But I don't see that it has any relation to the content of your paper.Alex Clarkhttps://www.blogger.com/profile/04634767958690153584noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-18140710004613114432014-01-20T14:51:02.491-08:002014-01-20T14:51:02.491-08:00I have to say i find this recursion clarification ...I have to say i find this recursion clarification project utterly fascinating: we have now a 4 author paper [WHRH] claiming to clarify claims made in an earlier paper [HCF] about recursion. This was followed by two main posts by one of the 4 authors clarifying the clarification paper, and a 5 part post further clarifying the clarifications. In spite of this recursive clarification effort we also have dozens of comments claiming things remain unclear and now as latest treat a comment [by Greg] linking back to an earlier comment specifying what [still] remains unclear. So the only thing missing from this massively recursive project is clarity...Anonymoushttps://www.blogger.com/profile/03443435257902276459noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-38016101935979228452014-01-20T14:04:25.277-08:002014-01-20T14:04:25.277-08:00@Jeff: Please consider my comments here@Jeff: Please consider my comments <a href="http://facultyoflanguage.blogspot.com/2014/01/jeff-w-comments-on-comments-on-recursion.html" rel="nofollow">here</a>Greg Kobelehttps://www.blogger.com/profile/08006251459440314496noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-49956656007267923442014-01-20T11:20:14.017-08:002014-01-20T11:20:14.017-08:00Part 5
“if a set is non-arbitrary, then there mus...Part 5<br /><br />“if a set is non-arbitrary, then there must exist a reason why it subsumes all and only those things it does; and the rule is the reason” (Watumull, et al. 2014: 2). I and my coauthors stand by this statement. (For a discussion of “the rule is the reason,” see section 5, “Generation and Explanation,” in http://ling.auf.net/lingbuzz/001758.) In the reply to this post (http://facultyoflanguage.blogspot.com/2014/01/jeff-w-comments-on-comments-on-recursion.html), I quote Turing discussing rules and explanations. Here is a snippet:<br /><br />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.”<br /><br />Turing’s ideas are reflected in the sense of explanation Professor Goldsmith identifies with that of Kolmogorov complexity. Chaitin—projecting from Turing to Leibniz—is explicit on this notion of computation as explanation: “a scientific theory [can be seen as] a binary computer program for calculating the observations, which are also written in binary. And you have a law of nature if there is compression, if the experimental data is compressed into a computer program that has a smaller number of bits than are in the data that it explains. The greater the degree of compression, the better the law, the more you understand the data. But if the experimental data cannot be compressed, if the smallest program for calculating it is just as large as it is [...], then the data is lawless, unstructured, patternless, not amenable to scientific study, incomprehensible. In a word, random, irreducible[.] Understanding is compression[.] To comprehend is to compress” (Chaitin 2005: 64, 65). However we would maintain that compressions is necessary but not sufficient. We need to understand the program.Jeffrey Watumullhttps://www.blogger.com/profile/12132739985772197183noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-14660756091024548372014-01-20T11:19:44.925-08:002014-01-20T11:19:44.925-08:00Part 4
I and my coauthors stand by the statement ...Part 4<br /><br />I and my coauthors stand by the statement “computation can run to infinity, but its rules are finitely specified and at any step in the computation only a finite amount of tape has been processed” (Watumull, et al. 2014: 2). This is simply a paraphrase of Turing: “There is no theoretical difficulty in the idea of a computer with an unlimited store. Of course only a finite part can have been used at any one time. Likewise only a finite amount can have been constructed, but we can imagine more and more being added as required. Such computations have special theoretical interest and will be called infinite capacity computers” (Turing 1950: 438-439). (Gödel was more radical in going beyond “theoretical interest” to philosophize that “although at each stage the number and precision of the abstract terms at our disposal may be finite, both (and, therefore, also Turing’s number of distinguishable states of mind) may converge toward infinity in the course of the application of the procedure” (Gödel 1972: 306).)<br /><br />“if a set is non-arbitrary, then there must exist a reason why it subsumes all and only those things it does; and the rule is the reason” (Watumull, et al. 2014: 2). Professor Goldsmith asks “What is an non-arbitrary set?” Elementary: A set is non-arbitrary if conditions on set membership exist. As Carnap explained, “the intension of a predicate ‘Q’ [...] is the general condition which an object y must fulfill in order for [the ascription] ‘Q’ to y” (Carnap 1955: 42). I-language specifies conditions an object must satisfy to be an expression of the language. “For presumably, unless the grammar is the one-sentence grammar which says ‘Any finite sequence of English words is a sentence.’, then there must be some finite sequence of English words which, by implication at least, are ruled out as deviant and I will here and now guarantee to find situations under which informants would produce some of these sentences and hearers will understand some of them[...]. This act of classifying sentences as grammatical or ungrammatical seems to be [...] relying on something like an effective procedure. In this connection, I am of course relying on certain very general hypotheses as to the character of the human brain. To be specific, I would suggest that there are many considerations which point to the idea that a Turing machine [...] is a reasonable model of the human brain” (Putnam 1961: 27, 39). I-language qua Turing machine decides the set of possible expressions: the set is non-arbitrary in this sense. (NB: We do not assume the desideratum of linguistics be the classification of (un)grammatical sentences. Our project is a description of the mechanism generative of expressions, for only it can explain why the grammatical/ungrammatical distinction even obtains. And ultimately it is the mechanism independent of its inputs/outputs that is of interest.)Jeffrey Watumullhttps://www.blogger.com/profile/12132739985772197183noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-7146856020855889302014-01-20T11:18:01.153-08:002014-01-20T11:18:01.153-08:00Part 3
(If I may go off on a tangent, Turing was ...Part 3<br /><br />(If I may go off on a tangent, Turing was interested in computability not, as Professor Goldsmith implies, solely for its epistemological implications, but further—and fundamentally—for its implications for the ontology of mind. “To understand the Turing model of ‘the brain’, it was crucial to see that it regarded physics and chemistry, including all the arguments about quantum mechanics [...] as essentially irrelevant. In his view, the physics and chemistry were relevant only in as much as they sustained the medium for the embodiment of discrete ‘states’, ‘reading’ and ‘writing’. Only the logical pattern of these ‘states’ could really matter. The claim was that whatever the brain did, it did by virtue of its structure as a logical system, and not because it was inside a person’s head, or because it was [...] made up of a particular kind of biological cell formation. It was a materialist view of mind, but one that did not confuse logical patterns and relations with physical substances and things[...]. In particular it was a different claim from that of behaviourist psychology, which spoke of reducing psychology to physics. The Turing model did not seek to explain one kind of phenomenon, that of the mind, in terms of another. It did not expect to ‘reduce’ psychology to anything. The thesis was that ‘mind’ or psychology could properly be described in terms of Turing machines because they both lay on the same level of description of the world, that of discrete logical systems” (Hodges 1983: 291).)Jeffrey Watumullhttps://www.blogger.com/profile/12132739985772197183noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-45616560216453442342014-01-20T11:17:29.488-08:002014-01-20T11:17:29.488-08:00Part 2
In particular, I and my coauthors stand by...Part 2<br /><br />In particular, I and my coauthors stand by the notion that expressions are generated “in advance of” input just as the rule of summation generates (i.e., determines) a set of possible sums in advance of the input of any summands. That abstract space of possible sums would exist independent of any concrete adders. The scare quotes were intended not to connote any unseriousness, but rather to scare off any connotations of temporality. (It is not as if the expressions are produced in time and stored for later output. “[A] generative system involves no temporal dimension. In this respect, generation of expressions is similar to other recursive processes such as construction of formal proofs. Intuitively, the proof ‘begins’ with axioms and each line is added to earlier lines by rules of inference or additional axioms. But this implies no temporal ordering. It is simply a description of the structural properties of the geometrical object ‘proof.’” (Chomsky 2007: 6). Chomsky’s scare quotes on “begins” are not unserious: they scare away the specter of erroneous interpretations.)<br /><br />The locution “in advance of” simply restates a property criterial of an effective procedure: determinism. Gandy, Turing’s student, defined Church’s Thesis thus: “What is effectively calculable is computable[...]. The word ‘effective’ in the thesis serves to emphasize that the process of calculation is deterministic” (Gandy 1980: 123, 124). As Turing explained in the context of “construct[ing] an automatic machine [i.e., a Turing machine] which will find all the provable formulae of the calculus[...]. It is natural to construct first a choice machine[...] to do this. We can suppose that the choices are always choices between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices i1, i2, ..., in (i1 = 0 or 1, i2 = 0 or 1, ..., in = 0 or 1), and hence the number 2^n+i12^n-1+i22^n-2+...+in completely determines the proof. The [Turing] machine carries out successively proof 1, proof 2, proof 3, ....” (Turing 1936: 252). The Turing machine carries out proofs deterministically in the way a Merge-based system generates expressions deterministically. (As Turing’s biographer, Andrew Hodges, explained in the context of Turing’s theory of the brain qua Turing machine, at a “detailed level of description, [neural functioning] was all determined[...]. It was not the determinism of physics, or chemistry, or of biological cells[...]. It was something more abstract. It was the quality of being fixed in advance” (Hodges 1983: 96).) Jeffrey Watumullhttps://www.blogger.com/profile/12132739985772197183noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-64336535008935685542014-01-20T11:16:51.070-08:002014-01-20T11:16:51.070-08:00Part 1
“The machine produces a set of outputs if ...Part 1<br /><br />“The machine produces a set of outputs if and only if it enters the defined configurations, but that set—the set of possible outputs—is determined (generated) by the rules “in advance” of—indeed independent of—any input” (Watumull, et al. 2014: 2).<br /><br />I and my coauthors stand by the literal interpretation of this statement. I-language generates sets in the way axioms generate theorems. As I have discussed elsewhere (http://ling.auf.net/lingbuzz/001758), “Chaitin observes, ‘theorems are compressed into the axioms’ so that ‘I think of axioms as a computer program for generating all theorems’ (Chaitin 2005: 65). Consider how a computer program explicitly representing the Euclidean axioms encodes only a finite number of bits; it does not—indeed cannot—encode the infinite number of bits that could be derived from its postulates, but it would be obtuse to deny that such an infinity is implicit (compressed) in the explicit axioms” (Watumull 2013: 308). Similarly, independent of their use, a ruler and compass determine a space of possible shapes. And similarly, “general principles [...] are simply innate to the language faculty, as part of the schematism that determines admissible grammars and the ways in which their rules apply, thus determining the class of languages accessible to humans by application of the language faculty” (Chomsky 1975: 91): given the schematism of UG (as constrained by third factors), a set of possible I-languages and by extension a set of possible expressions are determined (i.e., generated).Jeffrey Watumullhttps://www.blogger.com/profile/12132739985772197183noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-34807831967490518662014-01-16T15:43:45.303-08:002014-01-16T15:43:45.303-08:00Part 2:
So it is wrong, it seems to me, to say th...Part 2:<br /><br />So it is wrong, it seems to me, to say that the outputs of a finite program are determined in advance and independent of any input in general (though that is true *in some cases*). The case of the non-halting Turing machine programs is precisely the case where this becomes very tricky. It has been argued that properly interpreted, a consequence of Godel's result is that no finite creature, no creature within the physical universe, can know the answer to some questions about halting, and that is a deep and perhaps disturbing discovery. It could be said, in a footnote and as a profession of religious faith, that one believes that there is an infinite God who actually does know, but that could never migrate up to the text (nor could it be published in a mathematics journal). <br /><br />In short: "in advance" cannot be interpreted literally, and I think that there is no non-literal interpretation that can replace it with that both makes sense and is true.<br /><br />2. "The range of a recursive function can be infinite, as with the arithmetical rule. The computation can run to infinity..." <br /><br />No, it can't. Its algorithm can be implemented in an unbounded fashion, but no Turing machine can run to infinity. <br /><br />"...but its rules are finitely specified and at any step in the computation only a finite amount of tape has been processed. The finiteness of the machine is fundamental: the set of theorems or data derivable or predictable in a consistent system or theory is non-arbitrary such that an extensional definition (a list of the theorems/data)<br />cannot suffice; a list does not derive and thereby delimit (and thereby explain) the set.<br /><br />This, too, seems confused to me. Data or theorems (as special cases of data, perhaps) can be defined by extension, or not. Sometimes that is possible, and sometimes it is not. If a list does not suffice, then a Turing machine could be programmed to generate them, but typically there are many ways to do that, and it is only in a loose and non-technical sense that that enterprise could be said to "explain" the set.<br /><br />"Therefore, it is necessary to define the set [presumably, the set of "theorems or data" referred to just above] intensionally by a finite procedure (a rule) to derive or predict what things satisfy the conditions to be subsumed in the set or equivalently to generate (describe) all and only those things the set subsumes. In other words, if a set is non-arbitrary,..." <br /><br />Wait: have we stopped talking about "the set" mentioned above, of theorems and data? I think we have. But I am not sure. <br /><br />What is an non-arbitrary set? This is not a well-defined notion. Someone familiar with Kolmogorov complexity might take this phrase to mean a set which can be defined with by an algorithm that is shorter than the list of all of the members. But this way of thinking (which is by now standard) would never let one say something like "the reason the set subsumes all and only those things it does" ...<br /><br />"...then there must exist a reason why it subsumes all and only those things it does; and the rule is the reason." <br /><br />No, the algorithm is not the reason. Or do we have in mind a new sense of reason? I'd be grateful if the authors could say whether I have misunderstood their position.<br /><br />JohnAGoldsmithhttps://www.blogger.com/profile/06850777314554054035noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-59752249402670825692014-01-16T15:39:12.006-08:002014-01-16T15:39:12.006-08:00A comment in two parts:
I have read some of the W... A comment in two parts:<br /><br />I have read some of the WHRH paper, and have puzzled over a number of points that are suggested. The trouble spots come early on in the paper, and it seems to me that there are some confusions here (though I know this paper is trying hard to overcome *other* confusions in the past). Perhaps my comments will be helpful to show how one reader interpreted what is there.<br /><br />Here are the two early quotations that I found difficult to get over:<br /><br />1. "The function is defined in intension: it specifies the conditions some object would need to satisfy to be subsumed in the set, and it is possible that no such objects are presented. This notion of intension is realized in a Turing machine as rules for conditional branching: e.g., “IF in state qi , reading symbol xi on the tape, THEN write yi , move one space, transition to state qj .” The machine produces a set of outputs if and only if it enters the defined configurations, but that set—the set of possible outputs—is determined (generated) by the rules<br />“in advance” of—indeed independent of—any input. For example, independent of its potential application to particular inputs, a rule of arithmetic determines (generates) a range of numbers (i.e., the non-arbitrary set of possible outputs) given a domain of inputs." <br /><br /><br />From this (and even more, from the next quotation, just below), my sense is that the writer has not understood what the question was that Turing and his contemporaries (and the previous generation) were trying to come to grips with, and that is how mathematicians can be sure about truths that cover an infinite range of cases when we are only finite creatures with finite time. (Perhaps that is too harsh, and I apologize in advance; but the paper does indeed set itself the goal of clarifying important points that have been misunderstood.) It is the age-old problem of infinity and in the present context, it could be paraphrased: Let us agree that we can define what we mean by an unbounded process: it is something can continue indefinitely, an indefinite number of times. At any particular moment in the process's unfolding, it has only applied some finite number of times; but there is no bound to it.<br /> <br />While there were divergent points of view about the foundations of mathematics in the first decades of the 20th century --- that is putting it mildly --- I don't think anyone has boldly asserted that the output of an imaginary machine, such as a Turing machine, had a set of outputs that were determined in advance of any input (which is what is suggested in the quote above). Now, WHRH put the phrase "in advance" in scare quotes, and that is a bad sign, because it shows that they know that they really should not be using that phrase; they sense that there is something off, something not technically correct, and then they goes ahead and use the phrase anyway, not having some other phrase that they are willing to defend. So we can object now that the determination is not *in advance*, and the authors might think they can come back and say that they didn't really mean "in advance"; and we'll have to have this conversation all over again.<br /><br />The point of the Turing machine model is to come to grips with the finiteness of our thinking ability. In some cases, we have succeeded in finding ways to make generalizations about what will or will not happen over unbounded periods of time. As far as I know, all of those cases involve some version of the principle of induction, which is why that is so important. (The axiom of choice is perhaps a second way, if we chose to accept it, to say something about infinities.)JohnAGoldsmithhttps://www.blogger.com/profile/06850777314554054035noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-59725409087505749762014-01-14T15:30:42.698-08:002014-01-14T15:30:42.698-08:00Link to an early source of Kleene star in PS rules...Link to an early source of Kleene star in PS rules: http://www.google.com.au/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQFjAA&url=http%3A%2F%2Fgeorgelakoff.files.wordpress.com%2F2011%2F01%2Fphrasal-conjunction-and-symmetric-predicates-lakoff-and-peters-1967.pdf&ei=dsbVUuG9DIeFiAfboYGIDw&usg=AFQjCNG4-N9ry5T3DoNyYRhGJv19LGeQFQ&sig2=f6NQjFiLOm0EuCx-KI2QoA&bvm=bv.59378465,d.aGc<br /><br />Got it by googling on "lakoff peters symmetric predicates"; it's in the Reibel and Schane reader, which some old folks might have lying around somewhere.<br /><br />This refers to Stan Peters' 1966 dissertation.AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-17752894091522885882014-01-14T15:28:34.489-08:002014-01-14T15:28:34.489-08:00Cool! A center-embedding processing Olympiad betw...Cool! A center-embedding processing Olympiad between Greeks and Germans would be interesting too, because Modern Greeks also use some fairly complex ones (or at least did so until fairly recently) in poetic style. Greek bureaucratese on the other hand seems fairly rigidly tail-recursive.AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-72872834348675934142014-01-14T15:09:50.399-08:002014-01-14T15:09:50.399-08:00Another distinction that seems to be ignored in th...Another distinction that seems to be ignored in the paper is between 'recursive PS rules' as understood in the classic generative textbooks, and what might be called a 'nonrecursive hierarchy' model of phrase structure, as sometimes expounded in other approaches. Such a hierarchy might for example have levels of sentence, phrase and word, with the idea that a unit of one type is made out of units of lower types, with no phrases inside of phrases, only words (and different types at some of the levels, such as especially 'phrase').<br /><br />This would fit the facts of Piraha as presented by Everett quite nicely, tho there might be motivation for an additional level of 'clause' in between sentence and phrase, if correlative structures exist, which doesn't seem impossible from what I recall.<br /><br />Such descriptions would not be workable for languages with center embedding, and provide only messy descriptions for those with lots of edge-embedding such as English. So messy, in fact, that I abandoned my attempt to produce one for English NPs. There is a Bayesian angle to this, in that without the possiblity for self-similar embedding in phrase structure, the extensionally adequate grammar has innumerable small variants that fails to happen in real life (due to the repetitions), whereas, with it, these typologically rare or nonocurring forms of grammar are longer than the actual ones, so will be disfavored by the prior aka evaluation metric.AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-4960499691117505552014-01-14T12:22:03.306-08:002014-01-14T12:22:03.306-08:00I had a look at the German examples after Benjamin...I had a look at the German examples after Benjamin provided the link to the paper [thanks for that!!] and I have to say they are not unintelligible at all to a native speaker. Not your everyday conversation kind of German that's true but for anyone who has encountered Amtsdeutsch these are "small fish". There is BTW interesting psycholinguistic work showing that Germans have an easier time with center embeddings than speakers of English - presumably because we actually use them [of course usage based accounts are not very popular here]. Anonymoushttps://www.blogger.com/profile/03443435257902276459noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-35195344967707393012014-01-14T06:01:53.879-08:002014-01-14T06:01:53.879-08:00Talking about the brain it bottoms out in some sor...Talking about the brain it bottoms out in some sort of highly parallel neural architecture that we understand poorly if at all. It seems that one can make a coherent and contentful (albeit wildly speculative) claim that, say, at a suitable level of description, human cognition consists of two systems, one which is iterative, ancient and homologous to systems in non human animals, and one which is evolutionarily more recent, species specific, and which is recursive (in the defined by induction sense). That might even be right. But this is the view, if I understand it correctly, that WHRH are arguing is a misinterpretation of HCF. This is the view that PJ argue against for example.Alex Clarkhttps://www.blogger.com/profile/04634767958690153584noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-27735958862296573662014-01-14T05:03:43.261-08:002014-01-14T05:03:43.261-08:00- as for tail/central, to be clear, it's not t...- as for tail/central, to be clear, it's not that there's no distinction to be made, it's that it doesn't distinguish at the level of "iteration and a stack", but at a finer level (something like with or without the stack) ...<br /><br />- ... however, I agree that there's no demonstrable point. for the first reason you're alluding to, which is that there is no obvious reason to think that there are distinct cognitive mechanisms that map to recursion and iteration in the narrow range of cases where you would wonder about converting between the two ...<br /><br />- ... and for the second, which is that neither the set of strings NOR the set of structures generated seems to bear on the intensional question at hand!<br /><br />- the fact that there is an implementation level at which the distinction is moot doesn't logically preclude there being evidence for differences in mechanism at some higher level of description of what's going on. thus, the fact that I bottom out to a von neumann machine doesn't change the fact that the code sitting on my hard disk is in lisp.<br /><br />- this, in turn, does not mean that I have any idea WHAT the intensional question at hand is in this case!ewanhttps://www.blogger.com/profile/00161859381870853353noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-75315551707700346422014-01-14T04:30:45.746-08:002014-01-14T04:30:45.746-08:00As for "if it turns out that the mechanism ha...As for "if it turns out that the mechanism has a stack or central recursion, then it does, regardless of whether phenomenon y in language x makes demonstrable use of it", I think I agree that that's sensible (minus the "central recursion" bit, what does that add? ultimately, everything bottoms out in "iteration and a stack", as Alex C put it very succinctly).<br />But now we really are left with a truism that doesn't even make use of "recursion" once its put in more precise terms (well, nothing wrong about stating truisms every once in a while)<br /><br />(Minor comment: If you kick out "arrays" for the loop, you also have to appropriately constrain tail-calls, otherwise the extensional equivalence does not hold (sorry, my computer-science lingo is very rusty, I'm sure one of the Alex's can elaborate this properly --- you need to ensure that you don't just push everything into the arguments of your tail call. But what exactly is the point of this, again?)<br /><br />I'm skeptical about "intensional facts of the matter" here, though, for to repeat:<br />"It's worth remembering that at the bottom, all real computers are, like Turing machines, iterative devices, and recursion is implemented using iteration and a stack." (Alex Clark)benjamin.boerschingerhttps://www.blogger.com/profile/00894608988488218285noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-2002776127747043062014-01-14T03:08:05.105-08:002014-01-14T03:08:05.105-08:00@Alex D: Right, all I was saying was a slightly tu...@Alex D: Right, all I was saying was a slightly turned around version of what you say, namely, that for cases which are extensionally indistinguishable with respect to tail recursion versus - well, I guess it would have to be a while loop, no arrays, yes? - in those cases there is still an intensional matter of fact. I think that's also what they're saying in the bottom of fn 2, i.e., if it turns out that the mechanism has a stack or central recursion, then it does, regardless of whether phenomenon y in language x makes demonstrable use of it.<br /><br />I am still quite baffled by the surrounding text, as it does not say anything so straightforward and sensible: "outputs are recursed (carried forward on tape) as inputs to strongly generate structured expressions; thus the process is not a form of iteration (equivalently tail recursion) as claimed". Is the logic "structured expressions => ! iteration"? And how on earth do they _equate_ iteration and tail recursion given that the whole point of the last sentence of footnote 2 is that they are intensionally NOT equivalent, even when they are extensionally indistinguishable?! Pardon my punctuation.ewanhttps://www.blogger.com/profile/00161859381870853353noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-68925649912543076502014-01-14T02:27:58.952-08:002014-01-14T02:27:58.952-08:00"The procedure concept in ALGOL 60 was also i..."The procedure concept in ALGOL 60 was also important because it made recursion possible. Although recursion was already known, ALGOL 60 popularised the concept.", from http://heerdebeer.org/ALGOL/conclusion.html.<br /><br />Of course loops existed in widely used programming languages well before ALGOL, so I think this might illustrate the origin of what I think is the commonest understanding of what recursion is amongst working linguists (also, more recently, Culicover's (2009) textbook, and Carnie's intro).<br />AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-89372384831973288392014-01-14T02:14:51.709-08:002014-01-14T02:14:51.709-08:00@Ben: I think Karlsson is implicitly assuming in e...@Ben: I think Karlsson is implicitly assuming in effect that the programming language doesn't have arrays, so that you can't build and manipulate a pushdown stack using an array and an ordinary variable as a stack pointer. So for example you couldn't program a parser for a centrally recursive language in Basic without the DIM statements. (since the subroutine equivalents in that language aren't recursive either).<br /><br />The distinction is linguistically murky in that notations such as the Kleene star have been floating around in PSR notation for a very long time (I think perhaps from the Peters and Lakoff paper about NP coordination in the late 60s, but I haven't yet found my copy of the anthology it's in), without any real, well worked out consensus on when it should be used as opposed to self-similar embedding. <br /><br />The non-distinguishing of iteration and recursion increases the bafflement expressed by Alex, in that dogs are perfectly capable of iterated behavior such as barking until they are let in, but it would presumably undermine a lot of recent claims about recursion if ordinary dogs were proposed to be doing it in their everyday lives.AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-7042677360789562212014-01-14T01:02:32.406-08:002014-01-14T01:02:32.406-08:00It's worth remembering that at the bottom, all...It's worth remembering that at the bottom, all real computers are, like Turing machines, iterative devices, and recursion is implemented using iteration and a stack.<br /><br />In practice, there are computations which are much easier to do recursively -- the example I used to use when I taught computer science was to print out all the n factorial permutations of a list. But I don't know of any attempts to characterise such computations.Alex Clarkhttps://www.blogger.com/profile/04634767958690153584noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-36472204785486734192014-01-14T00:33:56.606-08:002014-01-14T00:33:56.606-08:00Thanks for the pointer (the paper can be accessed ...Thanks for the pointer (the paper can be accessed here: http://www.ling.helsinki.fi/~fkarlsso/Syntactic_Recursion_and_Iteration.pdf )<br /><br />I'm still sceptical as to whether there really is a meaningful distinction between "mere" iteration and "full-blown" recursion. As Alex D pointed out in the previous comment, when it comes to programming languages there is no difference in expressiveness between WHILE-loops and recursive function calls (whether or not limited to tail-calls, no difference there either). So I'm somewhat puzzled when Karlsson's Table 1 on p. 6 which states that "full-blown recursion [is] not convertible to iteration".<br /><br />As for distinguishing co-ordination, apposition and the like, and bringing levels of embedding up, this seems to boil down to the question of what kind of machine is needed to account for syntax, whether (memory-less) finite state suffices or whether a push-down automaton or even something more powerful is needed. But "recursion" (or "iteration") don't seem like very helpful notions in which to couch this discussion.<br /><br />Then again, I might just not understand the relevant notions correctly, so clarification is highly appreciated.benjamin.boerschingerhttps://www.blogger.com/profile/00894608988488218285noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-65617120193151509762014-01-14T00:07:25.344-08:002014-01-14T00:07:25.344-08:00Leaving to one side the terminological confusions,...Leaving to one side the terminological confusions, the important claim in the paper is the claim that in HCF 2002, which WHRH endorses, recursion just means Turing computability.<br />This raises two interesting issues. First, it is really hard to make sense then of remarks in Fitch Hauser and Chomsky 2005 "The evolution of the language faculty".<br />(which is the rejoinder to the Pinker and Jackendoff (PJ)critique).<br /><br />E.g. "the necessity of recursion in syntax" .. p (189)<br />Clearly we don't need full Turing computability for syntax; but we do need perhaps some recursion in other senses. <br /><br />"We do not define FLN as recursion by theoretical fiat (note, we say “a key component”), which would contradict the aims of our paper, but offer this as a plausible, falsifiable hypothesis worthy of empirical exploration." <br /><br />How could one possibly falsify the claim that FLN is computable?<br /><br />Moreover, though PJ clearly and explicitly take recursion to mean "defined by induction" or "functions calling themselves", FHC do not anywhere point out that they are in error. Surely if PJ got it completely wrong then in their rejoinder this would be pointed out? <br /><br />Finally, I don't see what the content of this claim is. Essentially everyone in cognitive science from Turing (1950) onwards has assumed that the human mind/brain and indeed animal mind/brains are computable. This is an upper bound on the power of the brain. What would it even mean, empirically, to say that FLN, a component, is computable? Of course it is computable as all of the components of the human brain are computable.<br />How can you possible say that Turing computability is specific to language? (i.e. in FLN) It is the most domain general and universal concept imaginable. <br /><br />So I really doubt that HCF actually meant this notion of recursion. In this context it is very interesting indeed that Hauser is a co-author of this paper, but it would be nice to have some confirmation that this was actually the sense of recursion that they meant, since the paper is so confused. <br />Alex Clarkhttps://www.blogger.com/profile/04634767958690153584noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-89618424058903359222014-01-13T22:33:10.226-08:002014-01-13T22:33:10.226-08:00Thanks for the interesting history lesson, Avery. ...Thanks for the interesting history lesson, Avery. But keep in mind WHRH was written to provide clarification: "There are several confusions dissected and, hopefully (I know a vain hope), put to rest". Judging by the comments [most by generativists] it would seem the hope is in vain indeed - but not because the critics of minimalism are the kinds of morons Norbert wishes everyone to believe... Anonymoushttps://www.blogger.com/profile/03443435257902276459noreply@blogger.comtag:blogger.com,1999:blog-5275657281509261156.post-37284951802105321402014-01-13T19:14:11.908-08:002014-01-13T19:14:11.908-08:00The ambiguities pointed out by Tomalin seem to per...The ambiguities pointed out by Tomalin seem to persist into the TG textbook literature, so that Akmajian and Heny (1975) p 45 seem to characterize/define recursion as the capacity to produce an infinite number of outputs, implementing this in PSR's with the possibility of self-similar embedding, while Culicover (1976) p 27, 180 seems to define it as the possibility of self-similar embedding. I haven't yet found useful discussion in earlier sources that generative grammar students would have looked at, such as Aspects and Integrated Theory of Linguistic Descriptions. Emmon Bach's (1974) _Syntactic Theory_ has the best 'for ordinary working linguistics students' discussion that I've encountered so far from that era, not talking about 'recursion' as such, except in the context of recursive functions, but talking about 'recursive elements', symbols in PSG that participate in self-embedding, and distinguishing between languages that have essential (central) self-embedding, from those with initial and final self-embedding, which can be redescribed with fsms.AveryAndrewshttps://www.blogger.com/profile/17701162517596420514noreply@blogger.com