Gödel Numbering

January 16, 2015

Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =

83838469305478699942290773046821079668485703984645720358854000640

The process is reversible; factor the Gödel number and decode the exponents.

Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: