图灵机②的名词解释

【图灵机②名词解释如下】

图灵机名词解释：
一种定义算法的理想机器。由英国数学家图灵在1936年定义的。1939年他又将图灵机的概念进行了推广。图灵机是图灵提出的一种自动机的抽象路线,是描述现代数字计算机的基本行为的模型。这种自动机在原则上适于实现任何算法。由三个基本部分组成名词解释：
一是控制部件,二是读写头,三是一条无限长的存贮带。因该存贮带有开端而无结尾,所以图灵机是一种无限记忆的自动机。控制部件是一台时序机,它有一个驱动系统,这个驱动系统能在两个方向上移动存贮带。存贮带可以设想为是任何一种能够存贮,阅读和修改信息的外部介质。存贮带被划分成一个个的方格,每个方格或者包含一个不记录数据的空白,或者包含属于有限符号集A的一个符号。读写头一次只能扫描一个方格。图灵机的运行是这样的名词解释：
准备一条存贮带,将数据符号设置在带上的相应方格中,时序机进入起始状态,再把所准备的存贮带装在机器上,并使相应方块位于读写头下,然后开机。在这里需要指出的是,图灵机只是现代数学计算机的基本行为的描述性模型,在实际上使用按图灵原理作出的自动机是不现实的,因为解决非常复杂的问题所需要进行的步数太多,这就意味着解决一个问题需要很长的解题时间。尽管如此,图灵机理论对于某一类问题的解的算法存在性问题是很重要的,因为它可以指明什么功能是能自动完成的,什么功能是不能自动完成的,特别是用象数字计算机这样的通用自动机。
图灵机分为特定图灵机和通用图灵机。特定图灵机是通过机器的控制部件所安排的步骤来计算给定函数的。通用图灵机则用来解释存贮带表达式,然后执行适当的计算过程。这种通用图灵机是一种能模拟任何特定图灵机的图灵机。任何特定图灵机所能完成的任何计算,通过适当的编码方法,通用图灵机都能完成。通用图灵机的使用过程与常规存贮程序数字计算机并无差别,主要不同点在于通用图灵机具有一条潜力无限的存贮带。

相关阅读：