John, You'll confuse the issue with so many words. For "completeness" I am happy to agree with Yorick Wilks and equate it with "decidability". I'm indebted to Yorick for pointing out this was how the problem was seen by generativists.

What it means to be "computable" was first defined by Alan Turing (and Alonzo Church?) I do not intend my sense to differ in any way. The question of decidability is a technical one within this framework. According to Turing's theory there are computable problems which are not decidable. It is not a question of adding more information, "semantic" or otherwise, to make them decidable. They are not decidable because they have too much power, not too little.

I am suggesting natural language might be such a system. That would not be a bad thing by the way. Decidability acts as a kind of straitjacket on computability. It is a limitation on its power. A generally computable model of natural language would be more powerful than a decidable model. It could be powerful enough to account for the detail of collocation and phraseology, for instance.

To get that power we would only need to lose the ability to _label_ language definitively. That is the content of decidability: the ability to fit language to a grammar, nothing more. I personally would not be bothered it if turned out that tags and tree-banks were officially meaningless, and corpora the most complete description of a language possible, especially if that meant we could recognize speech accurately, and index information effectively.

<br><br>Anyway, I think the possibility is worth considering.<br><br>-Rob<br><br> On 9/9/07, <b class="gmail_sendername">John F. Sowa</b> <<a href="mailto:sowa@bestweb.net">sowa@bestweb.net</a>> wrote:<div><span class="gmail_quote">

</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Rob,<br><br>The original definition of "generative grammar", which is used<br>

for formal languages, very explicit defines "completeness":<br><br>    A language L is defined as the set of all and only those<br>    sentences that can be generated (or parsed) by a grammar G.<br><br>This definition has proved to be very useful for artificial

<br>languages, such as programming languages and formal logics.<br><br>But it quickly became obvious that no grammar and parser could<br>come anywhere close to generating or parsing all and only the<br>sentences commonly used in any NL.  Therefore, Chomsky qualified

<br>it by saying that G would only describe the "competence" of an<br>"ideal" speaker, not the performance of any actual speaker.<br><br>But even that definition is woefully inadequate, because there<br>

is no grammar/parser combination in existence today that can<br>correctly parse more than about 50% of the sentences published<br>in well-edited texts.  (Many parsers can produce parses for more<br>than 50% of the sentences, but if you eliminate any parse that

has one or more errors, as judged by a competent linguist, even the best have difficulty in reaching 50% completely correct.)  > Take the opposite point of view. Assume only that language is  > generally computable. Then it may be undecidable.

<br><br>I don't know what you mean by "computable".  But the question<br>of undecidability is trivial to show for any NL grammar in<br>existence today.  Just pick up any any well-edited book, magazine,<br>or newspaper you can find around the house.  Then run the sentences

<br>from the first page through the parser.  That will demonstrate<br>that at least 99% of the grammars fail on a small finite set.<br>In the unlikely event that one of the parsers actually produces<br>correct parses for all the sentences, just try it on the next

<br>book, magazine, or newspaper.<br><br>By the way, you can get higher percentages of correct parses *if*<br>you supplement the grammar with semantic and pragmatic tests.<br>But that is harder to implement, and it violates Chomsky's

<br>assumption of the autonomy of syntax.<br><br>John<br><br></blockquote></div><br>