Gödel Numbers and Lojban

<- Lojbanic Qabbalah

Now we can construct Gödel numbers for any Lojban language text.
Therefore, if we can prove that the lojban grammar & morphology is
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, 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 & 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 & morphology is *not* fully parsable 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.''

'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 Richard Curnow has mentioned before that the DFA
(Deterministic Finite Automaton) 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 (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) --((Jay

''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 language 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 Lojban language to be
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. --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 --

Yes, but this is rather tough. A useful analogy can be found at
Goedel's Record Player.

More information and clear explanation about this stuff can be found in
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...

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

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 language 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

...And is it possible to change the title of this discussion? Done


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 language 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

Lojban language, 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 language, 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

Additionally, the link Image
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


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 language 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 language (and maybe even just MEX), a Turing machine which recognized
Lojban. Maybe, though, I'm misinterpreting what the conundrum is.

Yes, and that is why neither C nor Lojban language 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 language 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 language 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 language (and assume that semantics includes the meaning of statements
made with mekso), you cannot express anything. So, in order for Lojban language
to make statements about itself, it has to do so at the semantic level.
If you create a mathematical system which can process Lojban language 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


Well, I've acquired GEB, will read that, and from there investigate the
original papers as needed to grok this topic, and then return. :-)

Created by admin. Last Modification: Saturday 20 of September, 2003 00:59:01 GMT by admin.