通用图灵机:一个模型计算问题

爱德华·e·Ogheneovo
大学讲师,我部门的计算机科学,哈科特港,哈科特港尼日利亚。

文摘

图灵机是最强大的计算机器,是现代计算机的理论基础。通用图灵机适用于所有类别的语言包括正则语言(Res),上下文无关语言(节能灯),以及递归可枚举的语言(rel)。在本文中,我们讨论的概念通用图灵机计算设备,可用于解决任何电脑或一个人可以解决的问题。我们展示这台机器如何工作在解决计算问题和设计一些算法显示显示输入符号的操作程序,如左移动,或静止取决于输入符号。最后,我们认为,通用图灵机是一个通用的机器,可以用来计算任何可计算的问题。

关键字

图灵机、通用图灵机计算,计算模型

介绍

计算已经存在了很长时间。阿兰·图灵和其他(西德尼教堂,马尔可夫,埃米尔,斯蒂芬•克林等)独立考虑的问题可以定义指定的系统计算和研究。图灵关注人类的计算和思考人类手工计算的事情的方式。这次考试的人计算,他设计了一个系统的计算可以表达和执行。根据他的说法,任何琐碎的计算需要以下:

一个¯·一个简单的计算指令序列

一个¯·Scrath纸

一个¯·设备写入和擦除

一个¯·阅读设备

一个¯·的能力记住指令被执行

图灵那么发达的数学描述设备处理包括所有这些属性。这种装置称为图灵机,它是今天称为一个专用电脑。图灵机是简单抽象的计算设备旨在帮助调查的程度和所能计算的局限性。图灵机是最强大的计算机器和现代计算机的理论基础是[13],[15]。他们拥有无限记忆的形式磁带,和一头可以读取和改变磁带,和移动方向沿磁带或保持静止。通用图灵机(UTM)适用于所有类型的语言包括正则语言,上下文无关语言(节能灯)以及递归可枚举的语言(rel) [2], [7], [9]。也就是说,这些语言都是可以接受的图灵机。

图灵机的关键属性和所有其他等效模型计算的普遍性:存在一个图灵机,你,能够模拟其他图灵机。这台机器被称为通用图灵机你。因此一个通用图灵机,你可以被认为是一个图灵机翻译,写在图灵机的语言。此功能的自参照是图灵机的多功能性的来源和其他模型的计算。因此你可以模拟任意对任意输入图灵机。通用机达到这样的目标,阅读模拟机器的描述和输入从自己的磁带。图灵机的普遍性使它解决或计算任何问题,电脑还可以计算[18]。因此,通用图灵机的名称。阿兰·图灵在1937年推出的这台机器。

图灵机是等价的算法,是现代计算机的理论基础。但它往往是很难创建和维护图灵机的所有问题。这样做会消耗大量内存空间。,经颅磁刺激的创建多个任务非常复杂。这是一个通用图灵机的简单原因(UTM)设计。这个通用图灵机是一个机器,可以模拟其他图灵机,从而提供一个模型和解决方案[17]的计算问题。UTM是抽象模型计算模型。UTM (Tu)是一种自动化,根据输入的描述任何图灵机Tm,和一个字符串,一个¯害怕害怕一个½¯½,可以模拟计算Tm在¯害怕害怕一个½¯½。它减少了内存使用量相比,使用多个经颅磁刺激。

转换函数是一个通用图灵机的核心部分。UTM (Tu)作品的基础上定义的规则。转换函数的一个¯³你与一个磁带被定义为:

UTM可以解决任何的问题,可以解决使用FSA, PDA,甚至标准的图灵机()。

二世。相关工作

贾维斯和卢卡斯[10]实现的通用图灵机JFLAP平台。JFLAP是最成功的和广泛使用的工具等观察和模拟自动机有限状态机,下推自动机和图灵机。他们用JFLAP模拟通用图灵机。使用他们的系统,用户可以直接和互动体验的图灵机可以效仿其他图灵机。这个通用图灵机不改变其内存的一部分包含list-of-final Tm和list-of-transitions。Sumitha和Geddam[18]描述的实现递归可枚举的语言(rel)[8]使用的通用图灵机JFLAP平台。JFLAP是最成功的和广泛使用的可视化的工具,模拟各种类型的自动机。他们用JFLAP模拟许多图灵机和提供单一模型和解决所有的计算问题。

Maheshwari和Dorairangaswamy[14]实现上下文无关语言通用图灵机(utm)使用JFLAP工具。他们使用JFLAP模拟图灵机作为UTM,充当一个模型和解决所有的计算问题。埃伯[6]提出了一种进化进化计算的计算机器使用一个正式的模型。它调查了收敛性和收敛速度和提供所需的完整性和最优性充分条件的进化搜索与特定参考总体最优的多目标优化的实例普遍进化图灵机。该模型能够解决non-algorithmically停止的问题。

三世。计算问题

正式使用定义的计算通常是图灵机的数学概念,一种计算的操作是很简单很精确的描述。这样的机器需要强大到足以执行任何计算,一台计算机可以和图灵机能够执行任何计算,目前的计算机的能力。计算任何过程都可以由计算机[4]。必须指出计算等用在这里并不意味着数学计算的计算两个数的乘积或数量的对数。计算用在这里仅仅意味着包括各种计算机操作,包括数据处理、信息存储和检索等[1]。它包括机器的可读性。也就是说,语言是机器可读的,它必须有一个简单的结构,以便有效的翻译。首先,必须有一个算法来翻译语言,也就是说,一个循序渐进的过程,是明确的和有限的。其次,算法不能太复杂[12]。

可计算函数的函数可以计算使用力学计算设备给予无限的时间和存储空间[3]。如前所述,图灵机是非常强大的。它们可以用于计算任何问题都是可计算的。也就是说,他们可以计算任何问题有效的程序或算法,计算机可以计算等物理机器。因此,对于大量的计算问题,可以建立一个图灵机可以执行计算。图灵的原始论文是可计算的数字。根据他的说法,是图灵机可计算如果存在

图灵机的从一个空白磁带计算任意精确逼近这个数字[17]。因此图灵机可以做的不仅仅是写下数字。它们也可以被用于计算数值函数和其他任何可计算函数。

根据Church-Turing论文,任何函数的算法可以计算[19]。算法的概念,这里使用说明一步一步解决的问题如一个函数证明了算法1和2。有许多模型的计算,提出了求解函数是可计算的。然而,这些计算模型是等价的功率来计算功能。这些计算模型:

一个¯·阿兰·图灵在1936年提出的图灵机。

一个¯·λ(¯¬)微积分·教会在1936年提出的

一个¯·埃米尔邮报在1952年提出的机器

一个¯·斯蒂芬·克林在1952年提出的递归函数

一个¯·A·马尔可夫在1943年提出的马尔可夫模型

一个¯·寄存器机器

尽管这些模型使用不同的函数,表示他们的输入,输出,和翻译之间存在任何两个模型。每个可计算函数需要一个固定数量的自然数作为参数。一个函数可以部分或全部。部分函数是一个函数没有定义为每一个可能的选择输入[[16]。因此部分函数是一个函数定义了一个特定的输入和结果输出是一个自然数。然而,输出可以解释为数字使用成对的函数的列表。

可以将部分功能与每一个图灵机。在这种情况下,输入图灵机作为n-triple表示(例如X1,…, Xn)。最大的整数代表二进制由空格分隔。这种方式,图灵机一些迹象或0如果一个空白时扫描机器停止。这是被称为计算的输出。这样,每个图灵机定义一个局部函数从整数到整数n元数组,n > 1。这种类型的函数被认为是部分可计算的。然而,对于总可计算函数,这些函数被定义为所有可能的参数。因此,如果所有输入的图灵机暂停,然后定义的函数计算所有参数。

一个函数的范围(0,1)被称为一个谓词函数。一个谓词函数的一个主要特性是谓词函数值TRUE或FALSE。值为TRUE,如果相应的函数值1 n元组的值的参数是错误的或未定义的。例如,可以设计一个图灵机,当开始一个胶带与真正代表一个数字终止胶带当且仅当参数是一个1。因此一个图灵机可计算函数递归函数。

认为X是一个二进制字符串。因此对于函数X | |,可以看到的。

第四,可以计算函数

在前面的小节中,我们表明,一些函数是可计算的。除了功能之外,还有其他的问题,可以通过图灵机计算。在本节中,我们进一步讨论这些问题,图灵机可以用来计算算术自然数,编码图灵机。根据阿兰·图灵,号码是图灵机可计算如果存在一个图灵机从一个空白磁带计算任意精确的近似。可计算的数字是真实的数字可以计算任意精度有限,终止算法。图灵可计算的数字定义为序列的数字解释为十进制分数在0和1之间。以类似的方式,明斯基[15]定义了一个可计算的数字作为一个数字的图灵机,给定一个初始磁带,终止与第n个数字的号码。

仔细看看明斯基的定义表明,三个重要的观点是值得注意的:(1),n是指定的计算,对任意n(2)计算只需要有限数量的步骤,之后机器产生期望的结果,然后终于停止,和(3)利用图灵机,有限的形式定义机表——被用来定义,什么是潜在的无限小数位数。

正式,我们定义了一个可计算的数量等一个实数,如果它可以用一些近似函数给出任何整数n,等函数产生一个整数:

因此,一个实数是可计算当且仅当存在一个可计算的有理数分割D收敛。每个非理性的函数D是独一无二的可计算的数字。最后,一个复数是可计算的,如果它的实部和虚部都是可计算的。

诉的特征可计算的功能

如前所述,每个可计算函数必须有一个算法显示了如何计算一个函数的循序渐进的过程。然而,正如前面看到的,许多的模型计算了从图灵机¯害怕一个½¯害怕一个½递归函数、微积分和一系列其他的问题。然而,这些模型一个有趣之处在于,即使他们有不同的属性,他们都给可计算函数的等价类,他们都是有能力解决同样的问题。因此每个程序或算法计算一个可计算的功能有以下特点根据[5],[20]。

我。一定有指令(即程序)长度有限,算法。这意味着每个可计算函数必须有一个算法,完全描述了功能是如何被计算。

二世。如果算法k-tuple x域(即所有输入的函数定义)的f,之后一个有限数目的离散步骤过程必须终止和生产f (x)。

三世。如果过程是给定一个k-tuple x域f的,那么这个过程可能永远持续下去,永不停止;也可能被困在某种程度上,但它不能假装产生一个值在x。因此,如果一个值f (x)是迄今为止所发现,它必须是正确的值。

VI。通用图灵机

UTM在两端带无限输入并执行计算。它也有一个读/写头位置输入符号无限记忆[9],[11]。还有两个磁带还用于处理。第一个磁带保存原始图灵机Tm的描述,和其他磁带保存Tm的内部状态。

UTM的输入,你,在表单< Tm,ω> Tm的图灵机是操纵和¯害怕害怕一个½¯½是Tm的输入字符串。图灵机的执行指定的转换规则或δ规则。每个转换的形式:

一个¯¤(气)= (qj、b R)

气=初始状态在哪里

=当前阅读的象征

qj =下一个状态最终状态

b =写的象征

R =磁带头的方向移动(即。(左或右)

图灵机的带头和UTM可以直接进入移动左右由L或移动指定由r指定磁带头也可以决定留在目前的位置,这是由美国指定编码输入UTM。磁带头扫描磁带的内容和读取当前输入符号和当前的内部状态。它检查转换规则描述存储在磁带中指定的操作,并执行规则的原始Tm的过渡。当所有输入符号已经扫描,你进入最终状态,检查部分和执行一样的Tm。通用图灵机的内部结构是图1所示。

七世。通用图灵机的算法

算法1显示通用图灵机的初始化。算法设计使用结构化编程方法例如Pascal编程语言使用,并重复直到循环控制结构。

下一个算法,算法2是用于通用图灵机的主循环1中定义的初始化算法。图灵机的算法显示了操作的输入符号左移动,右,或保持位置到最后输入符号。

Algorithm2:通用图灵机,主循环。

算法2是用于通用图灵机的主循环1中定义的初始化算法。图灵机的算法显示了操作的输入符号左移动,右,或保持位置到最后输入符号。算法描述的迭代模拟通用图灵机,你。你开始读的输入符号从最左边的位置的磁带内容从一个非空的位置。磁带头检查如果有任何输入符号。如果没有,机器停止。然而,如果输入符号匹配,重复迭代过程和机器录音头向右移动到文件的末尾,最后停止。这个过程重复两次,但这一次使用“是”或“否”的选择“暂停”。磁带头的移动到左边缘描述磁带和磁带。重复这个过程,直到没有更多的输入符号离开,直到达成¢描述磁带。

八世。结论

在这篇文章中,我们已经讨论了通用图灵机的概念和如何使用它来解决任何问题,电脑可以解决或任何问题,都是可计算的。可计算函数的函数可以计算使用力学计算设备给予无限的时间和存储空间。如前所述,图灵机是非常强大的。它们可以用于计算任何问题都是可计算的。也就是说,他们可以计算任何问题有效的程序或算法,计算机可以计算等物理机器。因此,对于大量的计算问题,可以建立一个图灵机可以执行计算。图灵的原始论文是可计算的数字。因此图灵机可以做的不仅仅是写下数字。它们也可以被用于计算数值函数和其他可计算函数。图灵机的关键属性和所有其他等效模型计算的普遍性:存在一个图灵机,你,能够模拟其他图灵机。 This machine is referred to as Universal Turing machines Tu. Thus a Universal Turing Machine, Tu can be thought of as a Turing machine interpreter, written in the language of Turing machines. This capability of self-referencing is the source of the versatility of Turing machines and other models of computation. Thus Tu can simulate an arbitrary Turing machine on arbitrary input. The universal machine achieves this by reading both the description of the machine to be simulated and the input from its own tape. This universality of Turing machine makes it possible for it to solve or compute any problem that a computer can also compute.

引用

巴拉克Arora, s和b (2009)。计算复杂度:一种现代方法,剑桥大学出版社。
C·p。,Asoquo, D. E., and Akpan, I. O. (2010). Undecidability of the Halting Problem for Recursively Enumerable Sets, World Journal of Applied Science and Technology, Vol. 2, No. 1, ISSN: 2141 – 3290, pp. 41-48.
Boolos, g . s和Jeffrey r . c (1974)。可计算性和逻辑,剑桥:剑桥大学出版社。
戴维斯m (1982)。可计算性和不可解性,纽约:麦格劳-希尔。
Enderton, h (1977)。递归理论的元素。数理逻辑的手册,由巴韦斯编辑北荷兰(1977),页527 - 566。
埃,大肠(2005)。对进化的理论计算,生物系统,卷》82。-页。
Gramond,大肠和罗杰,s . h (1999)。在自动机理论使用JFLAP与定理。在ACM SIGCSE学报,236 - 340页。
Herken, R。,(ed.) (1988). The Universal Turing Machine: A Half-Century Survey, New York, Oxford University Press.
Hopcroft, J。,Motwani, R. and Ullman, J. (2006). Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison- Wesley.
贾维斯,j .和卢卡斯,j . m . (2008)。理解通用图灵机:一个实现JFLAp, ACM学报,23卷,问题5,页180 - 188。
克林,s . c (1936)。自然数的一般递归函数,数学年鉴,112卷,第727 - 742页。
刘易斯·h·r·Papadimitrinu, c . h (1981)。元素的理论计算,英格伍德克里夫报道:美国新世纪。
林,s和雷达手表,t (1965)。图灵机的计算机研究问题,ACM学报,12卷,第196 - 212页。
Maheshwari和Dorairangaswamy (2011)。上下文无关语言通用图灵机的实现。国际会议上电子计算机技术,5卷,332 - 335页,2011年4月8 - 10日。
明斯基,m (1967)。计算:有限与无限的机器,新世纪,Inc .)。,1967年。
Petrzold, g (2008)。带注释的图灵:导游通过阿兰·图灵的历史性的纸可计算性和图灵机,印第安纳波利斯,印第安纳州,威利的出版商
雷达手表,t (1962)。非计算性的数字,Etscheidungsproblem应用程序。在伦敦数学学会学报》,爵士。2,42卷,第230 - 265页。
c . h和Geddam Sumitha, k . o . (2011)。实现通用图灵机的递归可枚举的语言。如计算机理论与工程学报,3卷,1号,1793 - 8201,153 - 157页。
图灵,a . m . (1936)。Etscheidungsproblem可计算的数据与应用程序。在伦敦数学学会学报上,42岁,页230 - 265;修正在43(1937),页544 - 546;转载(戴维斯,1965年,页。115 - 154年)
图灵,a . m . (1937)。可计算性和λ-Definability。《符号逻辑,卷2,页153 - 163。