Hacker News new | past | comments | ask | show | jobs | submit login

I've recently learned about Gödel numbering and I have to admit; it's my favourite application of this theorem. Sorry RSA.

You don't actually need FTA to perform Gödel numbering. ASCII will do just as well.

You need it because you need a numer to give a unique sequence of symbols, otherwise it is not bidirectional, which is essential to G's code.

Yes. But Gödel originally used FTA, no?

He probably did. But for a programmer, ASCII is already something we're very familiar with, so why not use that?

Mathematicians have a general aversion to anything using the digits (or bits) of a number because it's generally too provincial. Numbers that are 'interesting' in one base tend to be boring in other bases but catch peoples eyes. It's like a self-defense mechanism to ward against quacks that sometimes catches legitimate uses as well.

Cantor's diagonalization argument for example, when used to show that R and Z have different cardinalities. It's a legitimate use, but huge numbers of incorrect counter-examples (that are really just examples) surface around it using the decimal expansion incorrectly. And the decimal expansion used in the actual diagonalization requires some careful consideration, since you have to be careful to remember that 0.10000... = 0.09999... so decimal expansions aren't unique.

Your use seems fine (and dealing only with integers the expansion is unique), but most of the time when a mathematician sees someone using digits they get a sense of unease and wonder if there were a better way to do things.

I didn't claim that FTA is the most practical way to perform Gödel numbering. I just said that it's my favorite application of it, in a general sense, not that I'd use it to do so. Preferences are subjective.

"Application" in mathematics usually means that something is used as a necessary component of a solution in another area. If Gödel numbering is an "application" of the FTA, that strongly suggests that you're saying that FTA somehow enables the possibility of Gödel numbering, or else that it is exploited somehow to endow that numbering with convenient properties (without loss of generality). Is that true?

> "Application" in mathematics usually means that something is used as a necessary component of a solution in another area.

I think that sentence is entirely true if you delete the word 'necessary', and otherwise entirely false. I think that almost everyone would agree that at the heart of modern cryptography is an application par excellence of modular arithmetic, but I think that no-one would claim that cryptography cannot be done without modular arithmetic.

Yes, exactly. The reason I said that is because Gödel himself used FTA to build his observation (Göodel numbering).

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact