刚刚拜读了一本书, 《图灵的秘密》. 该书介绍了图灵的论文《论可计算数及其在判定上的应用》, 其指出: 一个拥有铅笔, 纸和一串明确指令的人类计算者, 可以被看做是一种图灵机. 那么图灵机是什么呢?...一起跟着图灵来看看, 他在这台机器上都能够做些什么操作吧.
打印序列010101...
先给出一格简单的例子, 来看看这台机器是如何运行的....完美, 此时其实已经发现了, 图灵的方法是在连续1的后面添加x标记, 每个x标记都对应一格末尾的1. 以此来获得上一次打印1的数量.
至此, 这台简单的机器已经能够记忆一些内容了....方法听上去很简单, 先假设下一位是1, 然后让这个 n 位数与自身相乘, 若结果是2n-1位, 则说明结果小于2, 下一位是1. 若结果是2n位, 则大于2, 下一位是0....当然, 每一个位与位的乘积, 并不是加到过程和的最低位, 而是加到中间的某个位置上.
二进制的乘法很简单, 1*1=1, 其他情况都是0.