Prime-exponent encoding of a finite list
ID: prime-exponent-encoding-of-a-finite-list
For a finite list of nonnegative integers, encode its length with the exponent of two and its entries with the following prime numbers: , where is the th prime number. Unique prime factorization recovers both the length and entries. Requiring positive exponents on exactly the prescribed consecutive primes also makes validity decidable. Nesting list descriptors therefore gives a Gödel encoding of deterministic finite automata and other finite syntactic objects.
New to topics? Read the docs here!