关于哥德尔编码的疑问

我们使用的课本是 a friendly introduction to mathematical logic,里面对哥德尔编码的示例是:

我们讨论的问题是指数为什么是k+1而不是k。同学给的解释,如果指数是k,那么如果序列以0结尾,在还原编码的过程中就无法确定序列最后一位。
以(0,1,0)和(0,1)为例,如果指数为k,二者计算出的编码数字都是3。但是如果规定序列中没有0就可以避免这个问题。

我们在疑问中下课了…

我提供一个思路:在01图灵机里面表达函数的变元需要用一个1来占位。

是的,我也觉得x=0的话是无法确定序列长度,谢谢解答!

嗯嗯,大概只是为了确定“这里有一个变元。”

是和你主楼里说的理由一样,但不是为了确认最后一位。而是因为,用你的例子,3可以是(0,1,0)也可以是(0,1)这就不是unique coding了

好的!谢谢!