Hacker News Reader

Comment by kqr | Hacker News Reader

> making Jot a natural Gödel numbering of all algorithms.

This sounds very cool. I wish I understood both Jot and that sentence.

A Gödel numbering is simply a mapping to integers (that is easily decoded). If your programs are arbitrary binary strings, then you're basically already done, since bitstrings are in 1-1 correspondence with integers:

    empty  0  1  00  01  10  11  000  001  ...
        0  1  2   3   4   5   6    7    8  ...

> A Gödel numbering is simply a mapping to integers (that is easily decoded).

"easily" is arguable. Sure, I could multiply/factor an enormous number and count how many copies of each prime it has, but I'd much rather concatenate/split some digits.

Factoring numbers is difficult. Manipulating digits is easy, or it looks that way, but this is partially an illusion resulting from the number being given to you with the digits already known.

If you have a quantity in mind but you're not sure what its digits are, it can be a lot of work to learn.

I don't know what you mean by "not sure what its digits are".

If you mean what base to represent the number in, that's no more arbitrary than knowing the exact way Gödel numbers use primes.

Maybe it's an unfair example but: the number of people on Earth. We know the quantity more or less, the leftmost digit in base ten, then it's a lot of work to figure out the other digits.

Definitely unfair, because we're discussing this as a way to encode and decode a string of numbers into a single number, no measurements involved.

And factoring the number of people on earth would be just as hard.

You don't need to factor, if you know the nth prime you can easily find what value is at the nth position.

If you're clever about the way you write your syntax tree you can limit the primes to below 13 or so. Don't think there are many useful language constructs that consist of more than 5 or so terms (I think you can limit it to 3 if you encode lists as (list a (list b (list c nil))).

But doesn't Gödel numbering imply some sort of uniqueness, i.e. that each algorithm is only present once?

Otherwise, wouldn't any language assigning a valid meaning to any sequence of 0 and 1 be a Gödel numbering, even if only by saying that "an unrecognised sequence is a noop"?

Yes, in order to be decodable it must be an injective mapping.

No, an algorithm may be written in many ways, each of which would encode to a different Gödel number.

> To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence (x_1, x_2, x_3, ..., x_n) of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence

https://en.wikipedia.org/wiki/Gödel_numbering

Reply on news.ycombinator.com