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.

Posted by programmingpraxis

Filed in Exercises

5 Comments »

5 Responses to “Gödel Numbering”

Francesco said

January 16, 2015 at 10:14 AM

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]

Rutger said

January 16, 2015 at 11:50 AM

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)

John said
January 17, 2015 at 1:38 AM
Factor:

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

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

Mike said

January 20, 2015 at 6:52 PM

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

Globules said

February 2, 2015 at 2:26 AM

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'

Programming Praxis