众所周知的图灵机基于坚实且独立的数学结构,具有通过算法使用来解决数学运算的品质。尽管这个定义非常复杂,但事实并非如此。
简单来说,这台机器是1936年制造的一台可以无限计算计算机数据的设备。毫无疑问,它的发展标志着计算史上的一个关键事件。事实上,我们可以认为,多亏了这台机器,我们今天所知道的计算机才得以存在。
简单来说,图灵机并不复杂。相反,它最重要的属性之一恰恰是其简单的性能。它只是在磁带上使用遵循不同过程的符号表示。然而,仅仅因为它简单并不意味着它没有用。事实恰恰相反。
图灵机接受来自各种计算机的各种算法代码。从这个意义上说,它无缝地模拟了计算机行为的逻辑。
这台机器的名字来源于其发明者、英国裔艾伦·图灵。这个角色在他一生的不同领域都表现突出。他的出色表现主要是逻辑天才。事实上,从上面来看,该机器最初被称为“逻辑计算机器”。
图灵机代表了计算史上最相关的贡献之一。
图灵机的创建历史
到了 19 世纪,数学已经在许多领域发挥了重要作用。然而,这还没有正式宣布。大多数学科专家为建立这一研究领域付出了努力。
这是一个对一组符号和方法实施假设的问题,这些符号和方法的实现将由一台机器负责。
艾伦·图灵于1936 年提出了他的图灵机倡议。这正是在他的研究“论可计算数,及其在Entscheidungsproblem 中的应用”的演示中发生的。同年的出版物分析了大卫·希尔伯特研究数学可判定性的方法。
换句话说,该方法是为了确认适用于任何数学答案的固定程序的存在,而这反过来又确认了所述结果是否正确。基于上述,阿兰·图灵设计了图灵机,确认某些机器可以解决各种算法。
迄今为止,图灵留下了重要的遗产。尽管他的工作并不专注于物理表示,但它与现代计算机设计的相关性是不可否认的。对于所有这些,当我们观察计算机的行为时,我们面对的是图灵机。
图灵机是如何制造的?
图灵机有无限数量的磁带,这些磁带被分成管理部分,充当存储设备。此外,它还有一个磁头,可以在磁带上读取和写入代码。另一方面,这个部分负责将磁带从一个空间移动到另一个空间。
它还包括健康检查记录和简化的进程表。后者也称为操作表。正如我们之前提到的,图灵机是自动工作的。因此,要破译不同类型的算法,就受乔姆斯基层次结构的约束。
- 功能区:此功能区分为多个部分,每个部分都根据另一个部分进行定位。所有单元格都有有限引物的符号。底漆又具有一个称为“B”的特殊符号。此外,它还包括其他附加符号。胶带可根据工作需要向任一方向(左或右)延伸。
- 磁头——图灵机的这一部分读取并生成磁带上的代码。此外,它还负责将磁带向相应的方向移动。根据头部型号,它可能会移动。如果是这样,则频带是固定的。
- 保存状态– 顾名思义,您需要保存设备的状态。这是指有限的状态。此外,登记册开始工作时还有一个特定的初始状态。阿兰·图灵指出,当个体执行某种数学运算时,每种状态都会取代“精神状态”。
- 指令表——基本上它负责所有图灵机提示。也就是说,它指示设备在给定时间应该运行什么。例如,移动头部、写入符号或删除符号等。
图灵机是如何工作的?
一旦磁头被放置在磁带上,图灵机就会执行三项基本任务。该设备读取位于给定单元中的符号,更改位于单元中的符号的值,或者向右或向左移动条带以解密并替换相邻单元。
此外,每个值都可以有一个相关的任务。也就是说,例如,如果读取的符号对应于数字 1,则图灵机写入 0 并将条带向右移动。但是,如果读取的符号为 0,则机器写入数字 1。
图灵机执行的这项任务称为反转。那么,二进制值就有了利害关系。因此,图灵机被编程来执行特定的任务,从而破译非常复杂的算法。该设备的中心对象是通过数学运算计算出的数字。
图灵机是用来做什么的?
事实上,图灵机在其历史上有着无数的用途。而且,尤其重要的是,这是一项革命性的发明,改变了我们看待和解释数学的方式。例如,以前它被用作语言生成器。
然而,此时有许多应用可以讨论。其中一些最重要的是:
- 计算理论——该理论是计算机科学和数学研究的一部分。其主要目标是分析计算机的基本品质和局限性。特别是,该理论试图找到能够根据操作的复杂程度进行计算和分类的数学程序。
- 神谕机:这是一种图灵机,具有神谕,可以回答与特定数字符号系统相关的问题。
存在哪些类型的图灵机?
图灵机有多种类型。它们每一个的诞生都是为了简化算法问题的实现。这五种类型的描述如下:
- 具有停留指令的图灵机– 该机器具有沿一个方向移动的无限带。通常乐队会向右移动。向左移动被禁用。
- 双向图灵机——如果图灵机有无限数量的磁带,它可以像双向机一样运行,但有两个轨道。在这种情况下,信息将根据频段的布局进行定位(如果适用)。
- 多磁带图灵机——顾名思义,它有多个磁带。它的奇特之处在于它们每个人都有自己的头。因此,每个部分都是独立工作的。另一方面,它们不必沿相同方向或同时移动。
- 多维图灵机:在这种情况下,机器条具有多个维度。即,一条左右、上下移动的二维带。根据机器的状态和要解密的算法,状态会被修改。
- 非确定性图灵机:可以用非确定性机器来模拟确定性机器,反之亦然。在确定性的情况下,它是基于对于带状符号和当前状态而言,由有限数量的数字组成以供选择。
图灵机有什么优点?
与其他机器相比,这种类型的机器最重要的优点之一是它的语言相当广泛。另一方面,算法可以被授权或拒绝,而不必完全重新读取它。无论如何,在处理图灵机时都会计算运算。而且,它的编码是可判定的。
这些机器列出或枚举语言。另一方面,他们拥有的自主权是其他人无法比拟的。后者允许它在不同状态之间跳转。不需要总结逻辑方程,因为内存足够大。