-3
$\begingroup$

I am working on a cryptography project and I have come up with this problem.

Let's say I have a boolean expression L with $k$ variables $A_{1},..., A_{k}$. Let's assume this boolean expression is satisfiable, and the binary set (where 1 is true and 0 is false, for every variable) of lenght k that satisfies it is unique. Let's call this set S. It is clear that there is a relation between S and L, but computing S from L is the SAT problem.

Now, if I encode the boolean expression with Gödel numbering, I get an integer, which we will call E. The question is.

Is there a relation between the enconded integer E and S? If so, what kind of relation?

Also, is there an equivalent of S in terms of arithmetic/Gödel numbering? I just don't know what happens when I use Gödel numbering on L.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First of all, there is not just one Gödel encoding: it depends very much on which conventions you use. But essentially, this is just a (very clumsy) way to represent statements in some formal system as numbers. In principle it is possible to unpack the statement from the number, in such a way that manipulations of these statements correspond to arithmetic operations on the numbers. In particular, the validity of a proof written in the formal system can be checked by an algorithm using the Gödel numbers. But nobody ever actually does it this way.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Actually, all proof assistants do this all the time, and even youtube videos are just numbers, and so is music, and what you're reading on the the screen at the moment. It's just that the basic operations aren't $+$ and $\times$ but $NAND$. $\endgroup$
    – Andrej Bauer
    Commented May 30, 2017 at 6:00
  • $\begingroup$ By "this way" I meant "using Gödel numbers". Proof assistants use much more efficient representations of mathematical structures. $\endgroup$
    – Robert Israel
    Commented May 30, 2017 at 16:27
  • $\begingroup$ My remark is much more trivial than than that. All computers use all Gödel numberings for the simple reason that they use sequences of bits, which are just numbers in binary. $\endgroup$
    – Andrej Bauer
    Commented May 30, 2017 at 18:19
  • $\begingroup$ OK, so the question is whether an encoding qualifies as "Gödel" if it uses bit sequences. I personally wouldn't use that adjective, but I won't argue the point. $\endgroup$
    – Robert Israel
    Commented May 31, 2017 at 1:01
  • $\begingroup$ I think it's about propaganda, namely that mathematicians (and more specifically logicians) laid the ground for the digital era. Gödel had the idea that data which has nothing to do with arithmetic can be represented with numbers. Then Turing took one step closer by thinking of more concrete representations of such "numbers". And of course they also asked the question "what is computable?" $\endgroup$
    – Andrej Bauer
    Commented May 31, 2017 at 8:52

Not the answer you're looking for? Browse other questions tagged .