图灵机简介和原理分析

摘要

：

1936

年，

阿兰·图灵提出了一种抽象的计算模型

——

图

灵机

(Turing Machine)

。图灵机是指一个抽象的机器，可被视作任

意解决有限数学逻辑过程的机器，

它提供了一种简单有效的解决逻辑

过程的方法，

加快了后来诺依曼设计的计算机的出现。

本文将对图灵

机的原理和历史等进行简介和分析。

关键字：图灵机，计算模型。

一．

图灵机的历史发展

图灵机被公认为现代计算机的原型，

这台机器可以读入一系

列的零和一，

这些数字代表了解决某一问题所需要的步骤，

按这

个步骤走下去，

就可以解决某一特定的问题。

这种观念在当时是

具有革命性意义的，因为即使在

50

年代的时候，大部分的计算

机还只能解决某一特定问题，

不是通用的，

而图灵机从理论上却

是通用机。

1936

年

,

图灵向伦敦权威的数学杂志投了一篇论文

,

题为

"

论

数字计算在决断难题中的应用

"

。

在这篇开创性的论文中

,

图灵给

"

可计算性

"

下了一个严格的数学定义

,

并提出著名的图灵机

"(Turing

Machine)

的设想。

"

图灵机

"

不是一种具体的机器

,

而是

一种思想模型

,

可制造一种十分简单但运算能力极强的计算装置

,

用来计算所有能想像得到的可计算函数。

"

图灵机

"

与

"

冯•诺伊曼

机

"

齐名

,

被永远载入计算机的发展史中。

1950

年

10

月

,

图灵又