Gödel Numbering
January 16, 2015
We begin by hard-coding a list of prime numbers:
(define primes (list 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71 73 79 83 89 97))
Then the function that converts a string to a Gödel number iterates over the characters of the string, accumulating the product as it goes:
(define (godel str)
(let loop ((cs (string->list str)) (ps primes) (g 1))
(if (null? cs) g
(loop (cdr cs) (cdr ps)
(* g (expt (car ps) (- (char->integer
(char-upcase (car cs))) 64)))))))
> (godel "praxis")
83838469305478699942290773046821079668485703984645720358854000640
Reversing the process is only a little bit more complicated; there are three legs to the conditional, instead of two, and a new variable to count the number of factors in the exponent:
(define (ungodel num)
(let loop ((cs (list)) (ps primes) (g num) (cnt 64))
(cond ((= g 1)
(list->string (reverse (cons (integer->char cnt) cs))))
((zero? (modulo g (car ps)))
(loop cs ps (/ g (car ps)) (+ cnt 1)))
(else (loop (cons (integer->char cnt) cs) (cdr ps) g 64)))))
> (ungodel (godel "praxis"))
"PRAXIS"
You can run the program at http://programmingpraxis.codepad.org/jakEOZPF. There’s more to Gödel numbering that we have shown here; Wikipedia is a good place to start further study.
Programming Praxis 
Haskell:
Python:
def factorize(number): factors = [] while not (number % 2): number = number / 2 factors.append(2) i = 3 while i <= number**0.5 and number-1: if not (number % i): factors.append(i) number = number / i else: i += 2 if number != 1 and i >= number**0.5: factors.append(number) return factors def first_n_primes(n): result = [] i = 2 while len(result) < n: if len(factorize(i)) == 1: result.append(i) i += 1 return result def encode(s): result = 1 if len(s): fnp = first_n_primes(len(s)) for i,c in enumerate(s): result *= fnp[i]**ord(c) return result def decode(n): factors = factorize(n) return "".join(map(chr, [factors.count(f) for f in set(factors)])) s = 'Hey!' assert (decode(encode(s)) == s)Factor:
: >gödel ( str — n )
[ length nprimes ] keep [ 64 – ^ ] 2map product ;
: gödel> ( n — str )
group-factors values [ 64 + ] "" map-as ;
Implemented as a Python class that takes a sequence of symbols as a configuration parameter.
import itertools as it import string from math_utils import factor, primes class Godel: def __init__(self, symbols=string.ascii_lowercase): self.toint = dict(zip(symbols, it.count(1))) self.tosym = dict(zip(it.count(1), symbols)) def encode(self, s): n = 1 for p,c in zip(primes(), s): n *= p**self.toint[c] return n def decode(self, n): return ''.join(self.tosym[k] for _,k in factor(n))Example:
>>> g = godel.Godel() >>> g.encode('praxis') 83838469305478699942290773046821079668485703984645720358854000640 >>> g.decode(_) 'praxis' >>> a = 'πραχις' >>> symbols = [chr(n) for n in range(ord('\u03B1'), ord('\u03C9') + 1)] >>> g = godel.Godel(symbols) >>> g.encode(a) 307100620166588644477255578926084540910204043899801173475655680 >>> g.decode(_) 'πραχις'Also in Haskell, and similar to Francesco’s solution. This one uses the arithmoi package for the list of primes and the factorization function. I don’t shift the powers, so the resulting numbers are even larger.
import Data.List (foldl') import Math.NumberTheory.Primes (factorise, primes) toGodel :: String -> Integer toGodel = foldl' (\n (p, c) -> n * p^fromEnum c) 1 . zip primes fromGodel :: Integer -> String fromGodel = map (toEnum . snd) . factorise main :: IO () main = do let msg = "Hello, Kurt Gödel!" msg' = fromGodel $ toGodel msg putStrLn msg putStrLn msg'