## Friday, August 8, 2014

### Gödelized Codes

This was described in "The Gold at Starbow's End" by Frederick Pohl in Analog Science Fiction / Science Fact, April 1972. The example here is mine.

Write out the plain text message.  Encipher each letter with a prime number in sequence: 1, 2, 3, 5, 7, 11, 13, 17, 19, ... Then, use the alphabet position of the letter as an exponent.  A=1, B=2, C=3, D=4, and so on.  Raise the prime number to the exponent and you have an integer.  Multiply all the integers of the text into one large number.

 TEXT H I D E A B A D PRIME 1 2 3 5 7 11 13 17 POSITION 8 9 4 5 1 2 1 4 FACTOR 1^8 2^9 3^4 5^5 7^1 11^2 13^1 17^4 INTEGER 1 512 81 3125 7 121 13 83521 TEXT F A C E PRIME 19 23 29 31 POSITION 6 1 3 5 FACTOR 19^6 23^1 29^3 31^5 INTEGER 47045881 23 24389 28629151

The product of all the integer factors for this one artificially easy example is over

4,739,426,072,295,360+ sextillion.

Using the Preamble to the Constitution - "We the people of the United States..." - the H enciphers to 3^20 or 3486784401 and the first P is more than 45949729863572200.

The message conveys meaning only when it is deciphered.  It is easy to see that the longer the message, the harder that will be.  It quickly surpasses any theoretical computing ability and soon requires more time than is in the universe.

That being true, it remains that the single large integer does uniquely contain that information and no other.

The method was name for Kurt Gödel. “In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was used by Kurt Gödel for the proof of his incompleteness theorems. (Gödel 1931).”