关于艾伦·图灵《论可计算数》中若干要点的技术问询
关于艾伦·图灵《论可计算数》中若干要点的技术问询
最近我在读艾伦·图灵的《论可计算数及其在判定性问题上的应用》,一开始觉得内容还算易懂,但在§5和§8部分遇到了几个困惑点,想请教一下:
第一个问题(§5,第240页):图灵在这里引入了一种新的符号表示法,其中每行操作都会包含打印动作,他提到既不打印也不擦除的行可以写成
q1 Sj PSj q2的形式。但在该页下方的段落中,当他解释如何将m-配置转换为字母串时,只给出了擦除(D)、打印0(DA)、打印1(DAA)的对应形式,却没有说明“不打印”该用什么字母串表示?第二个问题(§8,第247页):我对图灵关于机器H的描述感到困惑。他说“机器H的动作被划分为若干段”,这里的“段”指的是每个方格就是一段吗?还是说段的长度可以超过一个方格?
第三个问题(同§8,第247页):图灵在这里用到了一个常量或函数R,还出现了
R(N-1)这样的表达式。这里是R乘以(N-1)吗?但如果总共有N段的话,除非R小于1,否则R(N-1)怎么能指代这些段中的一部分呢?如果R确实小于1,为什么不写成(N-1)/R?这个R到底起到什么作用?
备注:内容来源于stack exchange,提问作者Caleb Thoburn
相关产品推荐
相关产品推荐

