Gödel Numbering

The Programming Praxis blog has a post about Gödel Numbering which I thought would be fun to implement in Factor, showing off our support for working with prime numbers.

Spoiler alert: my solution is below.

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 2¹⁶ × 3¹⁸ × 5¹ × 7²⁴ × 11⁹ × 13¹⁹ =

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.

The math.primes vocabulary provides words for checking if numbers are prime or not and working with various sequences of prime numbers. The math.primes.factors vocabulary provides ways to find the prime factors for a number. Using these, we can simply implement our conversion words:

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

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