什么是图灵机

万物皆数学。

图灵(Turing)在他的论文《论数字计算在决断难题中的应用》中提出了图灵机的概念。当然后人们称之为图灵机。

图灵机不是真正的机器,简单说是一种模型,一种思维方式。

图灵机由4个部分组成:输入集合、输出集合、内部状态、固定的程序指令。

在现实中总有很多场景惊人的相似,如打酱油、吃瓜,当我们用图灵机来描述这些行为时,会将生动的事物变得轻描淡写,把感官逻辑变得生涩。以打酱油作为个例子:

  1. 打酱油的地方在出门:左转,右转,右转,左转,左转,左转,右转,左转的地方。
  2. 当我们遇到指示牌就会沿着指示牌改变方向。
  3. 如果手里的没封口的酱油瓶撒出了一些,最好还是原路返回再打满。

上面这些仿佛机器一般的逻辑,已经不能再直白,但是用图灵机来描述,将会是另一番样子:

  • 输入集合:{向左转指示牌,向右转指示牌}
  • 输出集合:{向左转,向右转}
  • 内部状态:{酱油瓶满,酱油瓶不满}
  • 固定程序指令:
    • 如果酱油瓶满,向前走,看见向左转的指示牌,就向左转。
    • 如果酱油瓶满,向前走,看见向右转的指示牌,就向右转。
    • 如果酱油瓶不满,向后退,看见向左转的指示牌,就向右转。
    • 如果酱油瓶不满,向后退,看见向右转的指示牌,就向左转。

打酱油的例子换成图灵机描述后,最难理解的是固定程序指令。它是一种脚本,而当我们按照脚本来行动的时候,要考虑酱油瓶自身的状态。我们拿着酱油瓶,看着指示牌,再看看酱油瓶的状态,从而决定到底是前进还是后退,是向左还是向右。

图灵机的组成

如果把上面4个组成部分放在这张图上,可以看到,Tape的每一格就是向左或向右的指示牌,Program就是固定的程序,CurrentState就是内部状态,整个“方盒子”的移动,就是根据上面这些条件和专题进行运算后的结果。

对图灵机来说,Tape可以是无限长的,上面存满了信息。无论这些信息是0或1,还是A或B,都是抽象的存在。理解到这里,可以说现实的各类行为和决策都可以通过图灵机来描述。

除了图灵机,还有个概念叫“图灵完备”。

可图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。

《维基百科》

粗犷地说一个系统具备图灵机那四点抽象概念,基本上就算是图灵完备了。

留下评论

电子邮件地址不会被公开。 必填项已用*标注