[plase use the BACK key to return to your previous page]
Goedel's Theorem
(iconosphere entry)

On this page:  {Intro}
               {Goedel Numbers}
               {Local Links}



Intro

   That is: Any sufficiently complex system will contain:

        Statements which are true (and can be shown to be such).

        Statements which are false (and can be shown to be such).

        Statements which either are true and false (and can be
                   shown to defintiely one or the other), but 
                   can not be proved which is the case.

        Statements which are meaningless.

        Statements which are neither true nor false, but "imaginary".            

        (This last bit by the work of G. Spenser Brown in his work
         -[The Laws of Form"]-).

Note that this begs the question of "meaningfull" and "meaningless"
statements.

We might see something that is self-contradictory such as:

    All red apples are green.

Now actually from a biolgical or arborist POV, this actually
does make sense, when TIME is brought into the equation, per:

    All red apples were once green.

But, setting that asside, we can see that the statement makes
no sense, since it in effect deines its own truth; taking as
read that red and green are mutually excludive.




Goedel Numbers
Note: This section of the Iconosphere owes much of its existence to
      "Best of" album by Charles Mingus. 

Goedel's invention of the idea of representing ANY message as the
product of powers of prime numbers goes like this:

  Let the POWER of a number (it's exponent) be placed
  in one-to-one correspondence as follows (i give the
  example for English, but this could be done via uni-code
  for all alphabets; it could be expanded to includ musical
  or danse notation using some ENCODING method).
   
    0 _ the blank space 
    1 A
    2 B
    3 C
   ....
   26 Z
   27 . etc

The position of a word is taken by successively increasing prime
numbers; eg, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Thus, the word "CAB" is expressed by:


     2^3  * 3^1 * 5^2   or 8 * 3 * 25  or  600
       C      A     B 

Goedel numbers get quite large, quite quickly. But in theory, any 
message can be encoded and then reduced using standard arithmetic
means; eg,

               600 =  6*10^2

Such compression becomes more readily apparent when the "Goedel product"
reaches very large values. A usefull function for such a reduction is
the facotrial function; given by the "!" symbol:

        1!                     = 1
        2! =             2 * 1 = 2
        3! =         3 * 2 * 1 = 6
        4! =     4 * 3 * 2 * 1 = 24
        5! = 5 * 4 * 3 * 2 * 1 = 120

Thus, 600 = 5*5!

In this case the reduction doesn't seem like much but as the numbers
in a Goedel product grown, there are vast economies of scale in using
expressions such as:

                            (2*5^10)^7 - 3

Part of the undecidability theorem rests on the fact that even THEOREMS
can be represented as Goedel numbers. And since he was ablt to show that
any system that is reducible to a system at least as complex as arithmetic
will have within it the "problemenatic" things discussed in the introduction,
above.... Thus, comes the problem.

Please use the BACK key on your 
browser to return to your previous page


Local Links

THe following are all articles (so far) by me that reference 
Goedel's theorem.

[pizoi: philo: computation]
[pizoi: philo: PSUEDO.htm]
[pizoi: philo: western] 
[pizoi: philo: borges] 
[mac-2001: philo: imortal.htm]