文档介绍：图灵机是什么_图灵机有什么用
图灵机简介
图灵机,又称图灵计算、图灵计算机,是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。
所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。
图灵机的主要作用及功能:
作为研究计算的一般性质的抽象工具,替代人们进行数学运算,并有以下作用:
1、作为语言接受器:被M接受的语育记作L(M),它是Σ中的这样一些字符串的集合,当把这些字符串放在M的带子上,。给定一个识别语言L的图灵机M,一般假定,当输入被接受时,M为停机,即没有下一动作。然而对于不被接受的字符串,。递归集合是递归可枚举集合的子类,递归集合总能被对所有输入都能停机的图灵机所接受。
2、作为整数函数计算机:被图灵机计算的函数称为部分递归函数。在某种意义上,。。
3、作为语言产生器:设M是一个多带图灵机,它用一条带作为输出带,在这条带上,。假定在输出带上,M写出某个字毋表Σ的一些字符串,并用分隔符分开,则最终打印在输出带上的字符串的集合就称为由M生成的语言,记为G(M),G(M)Σ。如果L是某个图灵机生成的语言,则L是递归可枚举集合,反之亦然。图灵机产生背景
任何科学思想、科学概念的诞生都有它的背景,在背景中往往有很多迷人的故事。关于计算理论可以追溯到1900年,当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。其中第十问题是这样的:存在不存在一种有限的、机械的步骤能够判断“丢番图方程”是否存在解?这里就提出来了有限的、机械的证明步骤的问题,用今天的话说就是算法。但在当时,人们还不知道“算法”是什么。实际上,当时数学领域中已经有很多问题都是跟“算法”密切相关的,因而,科学的“算法”定义呼之欲出。之后到了30年代的时候,终于有两个人分别提出了精确定义算法的方法,一个人是图灵,一个人是丘奇。而其中图灵提出来的图灵机模型直观形象,于是很快得到了大家的普遍接受。
不知道你是否听说过图灵这个名字。可能有些人知道牛顿,知道爱因斯坦,甚至知道冯诺依曼,但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基础,人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明:计算机。因此人们称图灵为:计算机理论之父。
图灵生活的年代经历了第二次世界大战。在二战期间他曾经为英国政府效力成功破译了德国的密码,因而为