Difference between revisions of "Gödel Numbers and Lojban"

From Lojban
Jump to navigation Jump to search
m (Gleki moved page jbocre: Gödel Numbers and Lojban to jbocre: Gödel Numbers and Lojban without leaving a redirect)
 
(12 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{See also|Lojbanic Qabbalah}}
 +
We can construct Gödel numbers for any Lojban text. Therefore, if we can prove that the lojban grammar & morphology is expressible using lojban [[mekso|MEX]] pertaining to the Gödel numbers, then, according to Gödel's proof (1931), it would be proven that there exist lojban sentences that cannot be proven grammatically/morphologically correct using a proof expressed in lojban. (not like '''[[na nei|na nei]]''', mind you, correctness on the syntactical view is meant).
 +
* OK, but '''na nei''' was the kind of sentence whose equivalent Gödel use to blow up sign systems <u>semantically</u>... And given that Lojban's grammar & morphology seems to be parsable using DFAs (Deterministic Finite Automaton), I am pretty sure that it is expressible with arithmetical statements and therefore MEX. Of course, this is an annoying conclusion, because we feel that Lojban is very able to fully express its own syntax. But on the other hand, if this conclusion proves to be false, then it would mean that Lojban's grammar & morphology is <u>not</u> fully parseable using DFAs. And because we already know that the grammar is (it is [[YACC|YACC]]-defined), it would mean that the morphology is problematic. ''(which I was already pretty sure of, dunno why ;-).''
 +
**Although I may have not been precise enough for a mathematical proof, I am sure that lojban's claim about being a "logical language" should entail discussions involving Gödel's statements about logic.
 +
**[[xod]]:
 +
**:Very interesting; the limits of Lojban! I lack the mathematical power to join the discussion, but I am extremely interested in the conclusions!
 +
**[[User:Jay Kominek|Jay Kominek]]:
 +
**:I believe [[Richard Curnow|Richard Curnow]] has mentioned before that the DFA for handling [[Lojban morphology|Lojban morphology]] has somewhere between 900 and 1000 different states, and can't reliably be human-generated. Instead, he describes it with a NFA (Non-Deterministic Finite Automaton) and then converts the NFA to a DFA. Lemme tell 'ya, the NFA is hideous, too. The whole point of this is to point out that while the grammar can be proven, nobody is seems sure about the morphology yet).
 +
**Correct me if I misunderstand, but the conclusion would be that Lojban's grammar and morphology cannot be expressed by [[mekso|mekso]] or any other formal system, though the grammar and morphology could still be fully expressed using informal statements in Lojban.
 +
***Of course, as well as with informal statements in any other language.
 +
****But the point is, Lojban is supposed to be parseable using computers, which means that its syntax ought to be fully expressible in computer terms, and thus mekso. It would be a major lose (correct me if I'm wrong) in regards to Lojban's goals...
 +
*[[rab.spir|rab.spir]]:
  
'''<- [[jbocre: Lojbanic Qabbalah|Lojbanic Qabbalah]]'''
+
*So this seems to be saying that either Lojban's morphology is vague in some area, or there are grammatically correct sentences which cannot be proven to be grammatically correct. Why do you assume it is the first? Number theory, a very powerful language indeed, contains true statements which cannot be proven. Why should we expect Lojban to be different? Consider that these sentences which cannot be proven to be grammatically correct are going to be huge, monstruously long sentences. I don't think this defeats any of Lojban's goals.
 +
* [[xod]]:
 +
*:An aside into provability: how can you say "true statements which cannot be proven"! That's completely meaningless.
 +
**[[nitcion]]:
 +
**:Gödel settled this in 1931. See http://kilby.stanford.edu/~rvg/154/handouts/incompleteness.html
 +
***Yes, but this is rather tough.  A useful analogy can be found at [[Goedel's Record Player|Goedel's Record Player]].
  
Now we can construct Gödel numbers for any [[jbocre: Lojban Description|Lojban Description]] text.
+
More information and clear explanation about this stuff can be found in ''[[Gödel, Escher, Bach]]'' by Hofstadter.
 +
* [[Jay Kominek|Jay]]:
 +
** The class of languages to which Lojban's grammar belongs is well understood. Assuming you can properly decompose a string of sounds or symbols into their separate words, there is no string of words for which membership in the language is undecidable. Whether or not that holds for the morphology seems to be unproven at this point. Maybe the LLG should investigate this and maybe stick their seal of approval on something as the official machine description of the morphology? Maybe I should snarf the lexer out of the official parser and see what it looks like...
 +
** [[rab.spir|rab.spir:]]
 +
*** The lexer in the official parser is weak: about all it can do is divide compound cmavo.  It is ''not'' a full implementation of the morphology algorithm. We can decide whether the string is grammatically correct using [[YACC|YACC]]. However, in the situation which started this discussion, we don't have the option of using [[YACC|YACC]]. You have to use the numerical rules, expressed in [[mekso|mekso]], which determine whether a sentence is grammatically correct. The implication of this is that there exist monstrous sentences, probably involving [[mekso|mekso]] which include the Godel numbers of other [[Lojban]] sentences, which cannot be proven to be grammatically correct using those mekso rules. If you don't believe me, read [[Gödel, Escher, Bach]] and all will become clear.
  
Therefore, if we can prove that the lojban grammar &amp; morphology is
+
* [[rab.spir|rab.spir:]]
 
+
** Now that I finally have my own copy of [[Gödel, Escher, Bach]], I've looked into how Gödel-incompleteness works - and I don't believe [[Lojban]] is affected by it. Mathematics (and particularly systems such as Typographical Number Theory) attempt to determine which statements are true and which are not in a formal way; these systems are incomplete because it is possible to create statements which imply their own falsehood. [[Lojban]], on the other hand, does not attempt to distinguish the true from the false mathematically. It only distinguishes the grammatically correct from the grammatically incorrect. For Gödel-incompleteness to apply to [[Lojban]], there would need to be a sentence for which demonstrating it to be grammatically correct somehow required that it is grammatically incorrect - ''without any regard to the meaning of the ''sentence.'' I don't think that grammar alone can imply anything of the ''sort. Additionally, an [http://kilby.stanford.edu/~rvg/154/handouts/incompleteness.html article] points to a theorem saying that the correctness of a theorem in a sufficiently powerful system cannot be recognized by a Turing Machine. We know that a [[YACC|YACC]] grammar ''can'' be recognized by a Turing machine. I believe this proves that Lojban's grammar alone is not "sufficiently powerful" to make statements about itself - which is a good thing, because that is the job of semantics - and so is not Gödel-incomplete.
expressible
+
** [[Jay Kominek|Jay:]]
 
+
*** Erm. Ok. Again, forget YACC, think LALR(1). Turing machines can determine if any sentence does or does not belong to a LALR(1) language, in polynomial time, given memory proportional to sentence length. The question, then, is whether or not [[Lojban]] can express a Turing machine for recognizing itself. C is capable of constructing a Turing machine for recognizing itself, and thousands of other languages, and it has significantly fewer primitives than Lojban. (Further, C can express Turing machine rules for manipulating the semantics of itself) I'm confident that if you were bored enough, you could describe, using [[Lojban]] (and maybe even just MEX), a Turing machine which recognized Lojban. Maybe, though, I'm misinterpreting what the conundrum is.
using lojban [[jbocre: mekso EX|mekso EX]] pertaining to the Gödel numbers, then,
+
*** [[rab.spir|rab.spir]]:
 
+
**** Yes, and that is why neither C nor [[Lojban]] is Gödel-incomplete at this level. Number theory is incomplete because it can mathematically determine whether statements are true or false, which necessitates that there are statements whose truth cannot be determined by number theory. [[Lojban]] cannot mathematically determine whether statements are true or false. Its mathematics only go as far as recognizing whether a statement is grammatically correct or not. Hence, the mathematical structure of a statement cannot make a statement about itself, and so no Gödel sentence exists in Lojban. Similarly, it can be determined in C whether a given C program (as long as it doesn't do weird stuff with the preprocessor) will compile, because the act of being compiled does not allow the program to make statements about itself. You could go to a higher level and find incompleteness. For example, you could set up a sub-grammar in MEX - not just the [[number subgrammar|number subgrammar]] we already have, but one which would sort out true mathematical statements from false ones. This grammar would ''not'' be LALR(1). Then if you tried to describe this system using itself, you would have a Gödel-incomplete system. The system would '''be''' number theory, except with [[Lojban]] cmavo instead of mathematical symbols. On the same level, C (or any computer language) ''is ''Gödel-incomplete when it comes to determining whether a program will halt, because there the mechanism used to determine whether the program halts is the same mechanism that the program uses. It comes down to the grammatical/semantic distinction which is mentioned at the very top of this discussion. If you take the semantics out of [[Lojban]] (and assume that semantics includes the meaning of statements made with mekso), you cannot express anything. So, in order for [[Lojban]] to make statements about itself, it has to do so at the semantic level. If you create a mathematical system which can process [[Lojban]] at the semantic level, you have an AI, and no longer something which is defined by the language itself; and to confuse this AI you might only need to say ''na nei''. (If I were Hofstadter, I would be able to phrase this much more clearly.)
according to Gödel's
 
 
 
proof (1931), it would be proven that there exist lojban sentences that
 
 
 
cannot be proven grammatically/morphologically correct using a proof
 
 
 
expressed in lojban.
 
 
 
(not like ''[[jbocre: na nei|na nei]]'', mind you, I really mean correctness on the
 
 
 
syntactical view.) ''OK, but ''na nei'' was the kind of sentence whose
 
 
 
equivalent Gödel use to blow up sign systems '''semantically'''...''
 
 
 
And given that Lojban's grammar &amp; morphology seems to be parsable using
 
 
 
DFAs, I am pretty sure that it is expressible with arithmetical
 
 
 
statements and therefore MEX.
 
 
 
Of course, this is an annoying conclusion, because we feel that lojban
 
 
 
is very able to fully express its own syntax. But on the other hand, if
 
 
 
this conclusion proves to be false, then it would mean that Lojban's
 
 
 
grammar &amp; morphology is *not* fully parsable using DFAs. And because we
 
 
 
already know that the grammar is (it is [[jbocre: YACC|YACC]]-defined), it would mean
 
 
 
that the morphology is problematic. ''(which I was already pretty sure
 
 
 
of, dunno why ;-)''
 
 
 
''Although I may have not been precise enough for a mathematical proof,
 
 
 
I am sure that lojban's claim about being a "logical language" should
 
 
 
entail discussions involving Gödel's statements about logic.''
 
 
 
'''Very''' interesting; the limits of Lojban! I lack the mathematical
 
 
 
power to join the discussion, but I am extremely interested in the
 
 
 
conclusions! --xod
 
 
 
I believe [[jbocre: Richard Curnow|Richard Curnow]] has mentioned before that the DFA
 
 
 
(Deterministic Finite Automaton) for handling [[jbocre: Lojban morphology|Lojban morphology]] has
 
 
 
somewhere between 900 and 1000 different states, and can't reliably be
 
 
 
human-generated. Instead, he describes it with a NFA (did I just forget
 
 
 
the acronym? argh) (Non-Deterministic Finite Automaton) and then
 
 
 
converts the NFA to a DFA. Lemme tell 'ya, the NFA is hideous, too. (the
 
 
 
whole point of this is to point out that while the grammar can be
 
 
 
proven, nobody is seems sure about the morphology yet) --[jbocre: Jay
 
 
 
Kominek|jay]
 
 
 
''Correct me if I misunderstand, but the conclusion would be that
 
 
 
Lojban's grammar and morphology cannot be expressed by [[jbocre: mekso|mekso]] or any
 
 
 
other formal system, though the grammar and morphology could still be
 
 
 
fully expressed using informal statements in Lojban.''
 
 
 
Of course, as well as with informal statements in any other language.
 
 
 
But the point is, [[jbocre: Lojban Description|Lojban Description]] is supposed to be parseable using computers,
 
 
 
which means that its syntax ought to be fully expressible in computer
 
 
 
terms, and thus mekso.
 
 
 
It would be a major lose (correct me if I'm wrong) in regards to
 
 
 
lojban's goals...
 
 
 
''So this seems to be saying that either Lojban's morphology is vague in
 
 
 
some area, or there are grammatically correct sentences which cannot be
 
 
 
proven to be grammatically correct. Why do you assume it is the first?
 
 
 
Number theory, a very powerful language indeed, contains true statements
 
 
 
which cannot be proven. Why should we expect [[jbocre: Lojban Description|Lojban Description]] to be
 
 
 
different?<br />Consider that these sentences which cannot be proven to be
 
 
 
grammatically correct are going to be huge, monstruously long sentences.
 
 
 
I don't think this defeats any of Lojban's goals. --[[jbocre: rab.spir|rab.spir]]''
 
 
 
----
 
 
 
''An aside into provability:''
 
 
 
Hey, how can you say "true statements which cannot be proven"! That's
 
 
 
completely meaningless. --xod
 
 
 
Gödel settled this in 1931.
 
 
 
[http://kilby.stanford.edu/~rvg/154/handouts/incompleteness.html] --
 
 
 
nitcion.
 
 
 
Yes, but this is rather tough.  A useful analogy can be found at
 
 
 
[[jbocre: Goedel's Record Player|Goedel's Record Player]].
 
 
 
More information and clear explanation about this stuff can be found in
 
 
 
''[[jbocre: Gödel, Escher, Bach]]'' by Hofstadter (see previous paragraph)
 
 
 
----
 
 
 
The class of languages to which Lojban's grammar belongs is well
 
 
 
understood. Assuming you can properly decompose a string of sounds or
 
 
 
symbols into their separate words, there is no string of words for which
 
 
 
membership in the language is undecidable. Whether or not that holds for
 
 
 
the morphology seems to be unproven at this point. Maybe the LLG should
 
 
 
investigate this and maybe stick their seal of approval on something as
 
 
 
the official machine description of the morphology? Maybe I should snarf
 
 
 
the lexer out of the official parser and see what it looks like...
 
 
 
--[[jbocre: Jay Kominek|Jay]]
 
 
 
The lexer in the official parser is weak: about all it can do is divide
 
 
 
compound cmavo.  It is ''not'' a full implementation of the morphology
 
 
 
algorithm.
 
 
 
We can decide whether the string is grammatically correct using
 
 
 
[[jbocre: YACC|YACC]]. However, in the situation which started this discussion, we
 
 
 
don't have the option of using [[jbocre: YACC|YACC]]. You have to use the numerical
 
 
 
rules, expressed in [[jbocre: mekso|mekso]], which determine whether a sentence is
 
 
 
grammatically correct. The implication of this is that there exist
 
 
 
monstrous sentences, probably involving [[jbocre: mekso|mekso]] which include the
 
 
 
Godel numbers of other [[jbocre: Lojban Description|Lojban Description]] sentences, which cannot be proven to be
 
 
 
grammatically correct using those mekso rules. If you don't believe me,
 
 
 
read [[jbocre: Gödel, Escher, Bach]] and all will become clear. --[[jbocre: rab.spir|rab.spir]]
 
 
 
...And is it possible to change the title of this discussion? '''Done'''
 
 
 
---------
 
 
 
Now that I finally have my own copy of [[jbocre: Gödel, Escher, Bach]], I've
 
 
 
looked into how Gödel-incompleteness works - and I don't believe
 
 
 
[[jbocre: Lojban Description|Lojban Description]] is affected by it. Mathematics (and particularly systems such
 
 
 
as Typographical Number Theory) attempt to determine which statements
 
 
 
are true and which are not in a formal way; these systems are incomplete
 
 
 
because it is possible to create statements which imply their own
 
 
 
falsehood.
 
 
 
[[jbocre: Lojban Description|Lojban Description]], on the other hand, does not attempt to distinguish the true from
 
 
 
the false mathematically. It only distinguishes the grammatically
 
 
 
correct from the grammatically incorrect. For Gödel-incompleteness to
 
 
 
apply to [[jbocre: Lojban Description|Lojban Description]], there would need to be a sentence for which
 
 
 
demonstrating it to be grammatically correct somehow required that it is
 
 
 
grammatically incorrect - ''without any regard to the meaning of the
 
 
 
sentence.'' I don't think that grammar alone can imply anything of the
 
 
 
sort.
 
 
 
Additionally, the link {img
 
 
 
src=http://kilby.stanford.edu/~rvg/154/handouts/incompleteness.html}
 
 
 
points to a theorem saying that the correctness of a theorem in a
 
 
 
sufficiently powerful system cannot be recognized by a Turing Machine.
 
 
 
We know that a [[jbocre: YACC|YACC]] grammar ''can'' be recognized by a Turing
 
 
 
machine. I believe this proves that Lojban's grammar alone is not
 
 
 
"sufficiently powerful" to make statements about itself - which is a
 
 
 
good thing, because that is the job of semantics - and so is not
 
 
 
Gödel-incomplete.
 
 
 
[[jbocre: rab.spir|rab.spir]]
 
 
 
Erm. Ok. Again, forget YACC, think LALR(1). Turing machines can
 
 
 
determine if any sentence does or does not belong to a LALR(1) language,
 
 
 
in polynomial time, given memory proportional to sentence length. The
 
 
 
question, then, is whether or not [[jbocre: Lojban Description|Lojban Description]] can express a Turing machine
 
 
 
for recognizing itself. C is capable of constructing a Turing machine
 
 
 
for recognizing itself, and thousands of other languages, and it has
 
 
 
significantly fewer primitives than Lojban. (Further, C can express
 
 
 
Turing machine rules for manipulating the semantics of itself) I'm
 
 
 
confident that if you were bored enough, you could describe, using
 
 
 
[[jbocre: Lojban Description|Lojban Description]] (and maybe even just MEX), a Turing machine which recognized
 
 
 
Lojban. Maybe, though, I'm misinterpreting what the conundrum is.
 
 
 
--[[jbocre: Jay Kominek|Jay]]
 
 
 
Yes, and that is why neither C nor [[jbocre: Lojban Description|Lojban Description]] is Gödel-incomplete at this
 
 
 
level. Number theory is incomplete because it can mathematically
 
 
 
determine whether statements are true or false, which necessitates that
 
 
 
there are statements whose truth cannot be determined by number theory.
 
 
 
[[jbocre: Lojban Description|Lojban Description]] cannot mathematically determine whether statements are true or
 
 
 
false. Its mathematics only go as far as recognizing whether a statement
 
 
 
is grammatically correct or not. Hence, the mathematical structure of a
 
 
 
statement cannot make a statement about itself, and so no Gödel
 
 
 
sentence exists in Lojban. Similarly, it can be determined in C whether
 
 
 
a given C program (as long as it doesn't do weird stuff with the
 
 
 
preprocessor) will compile, because the act of being compiled does not
 
 
 
allow the program to make statements about itself.
 
 
 
You could go to a higher level and find incompleteness. For example, you
 
 
 
could set up a sub-grammar in MEX - not just the [[jbocre: number subgrammar|number subgrammar]]
 
 
 
we already have, but one which would sort out true mathematical
 
 
 
statements from false ones. This grammar would ''not'' be LALR(1). Then
 
 
 
if you tried to describe this system using itself, you would have a
 
 
 
Gödel-incomplete system. The system would '''be''' number theory, except
 
 
 
with [[jbocre: Lojban Description|Lojban Description]] cmavo instead of mathematical symbols.
 
 
 
On the same level, C (or any computer language) ''is''
 
 
 
Gödel-incomplete when it comes to determining whether a program will
 
 
 
halt, because there the mechanism used to determine whether the program
 
 
 
halts is the same mechanism that the program uses.
 
 
 
It comes down to the grammatical/semantic distinction which is mentioned
 
 
 
at the very top of this discussion. If you take the semantics out of
 
 
 
[[jbocre: Lojban Description|Lojban Description]] (and assume that semantics includes the meaning of statements
 
 
 
made with mekso), you cannot express anything. So, in order for [[jbocre: Lojban Description|Lojban Description]]
 
 
 
to make statements about itself, it has to do so at the semantic level.
 
 
 
If you create a mathematical system which can process [[jbocre: Lojban Description|Lojban Description]] at the
 
 
 
semantic level, you have an AI, and no longer something which is defined
 
 
 
by the language itself; and to confuse this AI you might only need to
 
 
 
say ''na nei''.
 
 
 
(If I were Hofstadter, I would be able to phrase this much more
 
 
 
clearly.)
 
 
 
[[jbocre: rab.spir|rab.spir]]
 
 
 
Well, I've acquired GEB, will read that, and from there investigate the
 
 
 
original papers as needed to grok this topic, and then return. :)
 
 
 
--[[jbocre: Jay Kominek|Jay]]
 

Latest revision as of 18:35, 4 August 2014

We can construct Gödel numbers for any Lojban text. Therefore, if we can prove that the lojban grammar & morphology is expressible using lojban MEX pertaining to the Gödel numbers, then, according to Gödel's proof (1931), it would be proven that there exist lojban sentences that cannot be proven grammatically/morphologically correct using a proof expressed in lojban. (not like na nei, mind you, correctness on the syntactical view is meant).

  • OK, but na nei was the kind of sentence whose equivalent Gödel use to blow up sign systems semantically... And given that Lojban's grammar & morphology seems to be parsable using DFAs (Deterministic Finite Automaton), I am pretty sure that it is expressible with arithmetical statements and therefore MEX. Of course, this is an annoying conclusion, because we feel that Lojban is very able to fully express its own syntax. But on the other hand, if this conclusion proves to be false, then it would mean that Lojban's grammar & morphology is not fully parseable using DFAs. And because we already know that the grammar is (it is YACC-defined), it would mean that the morphology is problematic. (which I was already pretty sure of, dunno why ;-).
    • Although I may have not been precise enough for a mathematical proof, I am sure that lojban's claim about being a "logical language" should entail discussions involving Gödel's statements about logic.
    • xod:
      Very interesting; the limits of Lojban! I lack the mathematical power to join the discussion, but I am extremely interested in the conclusions!
    • Jay Kominek:
      I believe Richard Curnow has mentioned before that the DFA for handling Lojban morphology has somewhere between 900 and 1000 different states, and can't reliably be human-generated. Instead, he describes it with a NFA (Non-Deterministic Finite Automaton) and then converts the NFA to a DFA. Lemme tell 'ya, the NFA is hideous, too. The whole point of this is to point out that while the grammar can be proven, nobody is seems sure about the morphology yet).
    • Correct me if I misunderstand, but the conclusion would be that Lojban's grammar and morphology cannot be expressed by mekso or any other formal system, though the grammar and morphology could still be fully expressed using informal statements in Lojban.
      • Of course, as well as with informal statements in any other language.
        • But the point is, Lojban is supposed to be parseable using computers, which means that its syntax ought to be fully expressible in computer terms, and thus mekso. It would be a major lose (correct me if I'm wrong) in regards to Lojban's goals...
  • rab.spir:
  • So this seems to be saying that either Lojban's morphology is vague in some area, or there are grammatically correct sentences which cannot be proven to be grammatically correct. Why do you assume it is the first? Number theory, a very powerful language indeed, contains true statements which cannot be proven. Why should we expect Lojban to be different? Consider that these sentences which cannot be proven to be grammatically correct are going to be huge, monstruously long sentences. I don't think this defeats any of Lojban's goals.
  • xod:
    An aside into provability: how can you say "true statements which cannot be proven"! That's completely meaningless.

More information and clear explanation about this stuff can be found in Gödel, Escher, Bach by Hofstadter.

  • Jay:
    • The class of languages to which Lojban's grammar belongs is well understood. Assuming you can properly decompose a string of sounds or symbols into their separate words, there is no string of words for which membership in the language is undecidable. Whether or not that holds for the morphology seems to be unproven at this point. Maybe the LLG should investigate this and maybe stick their seal of approval on something as the official machine description of the morphology? Maybe I should snarf the lexer out of the official parser and see what it looks like...
    • rab.spir:
      • The lexer in the official parser is weak: about all it can do is divide compound cmavo. It is not a full implementation of the morphology algorithm. We can decide whether the string is grammatically correct using YACC. However, in the situation which started this discussion, we don't have the option of using YACC. You have to use the numerical rules, expressed in mekso, which determine whether a sentence is grammatically correct. The implication of this is that there exist monstrous sentences, probably involving mekso which include the Godel numbers of other Lojban sentences, which cannot be proven to be grammatically correct using those mekso rules. If you don't believe me, read Gödel, Escher, Bach and all will become clear.
  • rab.spir:
    • Now that I finally have my own copy of Gödel, Escher, Bach, I've looked into how Gödel-incompleteness works - and I don't believe Lojban is affected by it. Mathematics (and particularly systems such as Typographical Number Theory) attempt to determine which statements are true and which are not in a formal way; these systems are incomplete because it is possible to create statements which imply their own falsehood. Lojban, on the other hand, does not attempt to distinguish the true from the false mathematically. It only distinguishes the grammatically correct from the grammatically incorrect. For Gödel-incompleteness to apply to Lojban, there would need to be a sentence for which demonstrating it to be grammatically correct somehow required that it is grammatically incorrect - without any regard to the meaning of the sentence. I don't think that grammar alone can imply anything of the sort. Additionally, an article points to a theorem saying that the correctness of a theorem in a sufficiently powerful system cannot be recognized by a Turing Machine. We know that a YACC grammar can be recognized by a Turing machine. I believe this proves that Lojban's grammar alone is not "sufficiently powerful" to make statements about itself - which is a good thing, because that is the job of semantics - and so is not Gödel-incomplete.
    • Jay:
      • Erm. Ok. Again, forget YACC, think LALR(1). Turing machines can determine if any sentence does or does not belong to a LALR(1) language, in polynomial time, given memory proportional to sentence length. The question, then, is whether or not Lojban can express a Turing machine for recognizing itself. C is capable of constructing a Turing machine for recognizing itself, and thousands of other languages, and it has significantly fewer primitives than Lojban. (Further, C can express Turing machine rules for manipulating the semantics of itself) I'm confident that if you were bored enough, you could describe, using Lojban (and maybe even just MEX), a Turing machine which recognized Lojban. Maybe, though, I'm misinterpreting what the conundrum is.
      • rab.spir:
        • Yes, and that is why neither C nor Lojban is Gödel-incomplete at this level. Number theory is incomplete because it can mathematically determine whether statements are true or false, which necessitates that there are statements whose truth cannot be determined by number theory. Lojban cannot mathematically determine whether statements are true or false. Its mathematics only go as far as recognizing whether a statement is grammatically correct or not. Hence, the mathematical structure of a statement cannot make a statement about itself, and so no Gödel sentence exists in Lojban. Similarly, it can be determined in C whether a given C program (as long as it doesn't do weird stuff with the preprocessor) will compile, because the act of being compiled does not allow the program to make statements about itself. You could go to a higher level and find incompleteness. For example, you could set up a sub-grammar in MEX - not just the number subgrammar we already have, but one which would sort out true mathematical statements from false ones. This grammar would not be LALR(1). Then if you tried to describe this system using itself, you would have a Gödel-incomplete system. The system would be number theory, except with Lojban cmavo instead of mathematical symbols. On the same level, C (or any computer language) is Gödel-incomplete when it comes to determining whether a program will halt, because there the mechanism used to determine whether the program halts is the same mechanism that the program uses. It comes down to the grammatical/semantic distinction which is mentioned at the very top of this discussion. If you take the semantics out of Lojban (and assume that semantics includes the meaning of statements made with mekso), you cannot express anything. So, in order for Lojban to make statements about itself, it has to do so at the semantic level. If you create a mathematical system which can process Lojban at the semantic level, you have an AI, and no longer something which is defined by the language itself; and to confuse this AI you might only need to say na nei. (If I were Hofstadter, I would be able to phrase this much more clearly.)