图灵计算机器简介-软件工程专业导论

图灵计算机器是阿兰·图灵(Alan Turing)于1936年提出的,被称为自动机(automata)。该机器有一个无限长的存储纸带,被分为若干个离散单元(cell)。机器有一个读写头,指向单元,“读”取单元上的符号,每个符号和其所代表的含义存在一个有限的字母表中。图2-2是用机械电气装置实现自动计算的设计图。

图灵奖

① https://en.wikipedia.org/wiki/Turing_machine_gallery.

采用图2-2的设计,机器可以:

(1)在单元上写符号(例如,写有限字母表中的数字、字符),也可擦除或不写;

(2)左右移动纸带(或移动读写头);(www.xing528.com)

(3)(依据观察到的符号和机器在表中的位置)决定继续处理后续指令,还是停机。

用这个模型,图灵提出两个问题:

(1)机器能否判断纸带是否会有“循环圈(circular)”——永远循环,不能再继续做计算,即求解的问题无解;

(2)机器是否可以确定在纸带上打印了给定符号,即得到了确定的结果。

这两个问题实际上是计算机器的“停机”问题。程序自动计算且能够自动停下,说明被求解的问题是有解的,否则,陷入循环圈(第一个问题),或不能给出所期望的结果(第二个问题),说明该问题是无解的。

这个问题称为“图灵停机问题”,即可计算问题。判断一个问题是否可计算是理论计算机科学领域的重要方向。