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.  


HIDE A BAD FACE


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
5
1
3
5
FACTOR
19^5
23^1
29^3
31^5
INTEGER
2476099
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).” Wikipedia here



No comments:

Post a Comment