## 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

```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'
```