如何对位串进行 goedel 编号？

Question

我正在寻找一个为位串（即任意二进制数据）进行哥德尔编号的概念。

方法 1（失败）：简单地将二进制数据解释为无符号整数数据。
这失败了，因为例如两个不同的字符串 "01" 和 "001" 都表示相同的整数 1.

有标准的方法吗？ 0通常包含在哥德尔编号中还是排除在外？

Answer 1

原始的哥德尔编号使用质数和符号的唯一编码。如果要对由“0”和“1”组成的字符串执行此操作，则需要“0”（比如 1）和“1”（比如 2）的正码。那么“01”的编号是

    2¹ * 3²

而“001”的编号是

    2¹ * 3¹ * 5²

对于更长的字符串，使用下一个质数。然而，请注意，哥德尔的编号目标不包括任何实际考虑，他只是需要将编号作为证明其定理的工具。在实践中，对于相当短的字符串，您将超出您的语言的整数范围，因此您需要使用内置任意大整数的语言（如 Scheme）或支持语言中没有内置大数的库。

Answer 2

一个超级简单的解决方案是在二进制数据前添加一个1，然后将结果解释为无符号整数值。这样，位串左侧不会丢失 0 位数字。

效果图：

对位串进行排序的一个明显方法是先按长度排序，然后再按字典顺序排序：

+------------+
| bit string |
+------------+
|          ε |
|          0 |
|          1 |
|         00 |
|         01 |
|         10 |
|         11 |
|        000 |
|        001 |
|        010 |
|        011 |
|        100 |
|        101 |
|        110 |
|        ... |
+------------+

（ε表示没有数字的空字符串。）

现在我们给这个table加上一个索引号n，从1开始，然后看索引号n的二进制表示。我们会在那里有一个不错的发现：

+------------+--------------+-------------+
| bit string | n in decimal | n in binary |
+------------+--------------+-------------+
|          ε |            1 |           1 |
|          0 |            2 |          10 |
|          1 |            3 |          11 |
|         00 |            4 |         100 |
|         01 |            5 |         101 |
|         10 |            6 |         110 |
|         11 |            7 |         111 |
|        000 |            8 |        1000 |
|        001 |            9 |        1001 |
|        010 |           10 |        1010 |
|        011 |           11 |        1011 |
|        100 |           12 |        1100 |
|        101 |           13 |        1101 |
|        110 |           14 |        1110 |
|        ... |          ... |         ... |
+------------+--------------+-------------+

结果出奇地好，因为 n 的二进制表示（以非常明显的方式排序时每个位串的索引）只不过是 1 加在原先的前面位字符串，然后将整个内容解释为无符号整数值。

如果您更喜欢从 0 开始的 Goedel 编号，则从生成的整数值中减去 1。

伪代码中的换算公式：

// for starting with 1
n_base1 = integer(prepend1(s))
s = removeFirstDigit(bitString(n_base1))

// for starting with 0
n_base0 = integer(prepend1(s)) - 1
s = removeFirstDigit(bitString(n_base0 + 1))

如何对位串进行 goedel 编号？

How to do a goedel numbering for bit strings?

binary-data