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.

Pages: 1 2

5 Responses to “Gödel Numbering”

  1. Francesco said

    Haskell:

    import Data.Numbers.Primes (primes, primeFactors)
    import Data.List (group)
    
    enc s = product $ zipWith (^) primes (map (\c -> fromEnum c - 96) s)
    dec n = map ((toEnum . (+96)) . length) . group . primeFactors $ n :: [Char]
    
  2. Rutger said

    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)
    
  3. John said

    Factor:

    : >gödel ( str — n )
    [ length nprimes ] keep [ 64 – ^ ] 2map product ;

    : gödel> ( n — str )
    group-factors values [ 64 + ] "" map-as ;

  4. Mike said

    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(_)
    'πραχις'
    
  5. Globules said

    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'
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: