什么是图灵机？

Question

什么是图灵机,人们为什么一直提到它？我的IBM PC就是我完成计算所需要的!为什么有人关心这些机器？

Answer 1

图灵机是一个大问题的原因与经典计算科学或计算理论类型的研究有关.它基本上是关于分析计算机的一般属性,例如计算机具有的理论能力和限制,以及当我们谈论"计算"某些东西时我们的意思.

人们可能使用图灵机研究的一个例子是停机问题.虽然这个问题属于学术活动,但它具有明显的现实意义.为什么不编写一个调试器来简单地告诉你程序是否包含任何无限循环？停机问题确定了解决一般情况下的这个问题是不可能的.

图灵机的研究也有助于研究语言语法及其类,从而导致编程语言的发展.术语"正则表达式"的出现是因为它们是常规语法,对这些语法的研究(计算理论的一部分)将告诉您更多关于正则表达式可以解决的问题以及它们不能解决的问题.例如,传统的正则表达式语法将无法解决以下问题:在输入中解析一些N个'a'字符,然后解析相同数量N的char'b'.

如果您对关于此类事情的好文章感兴趣,请查看Michael Sipser 的计算理论简介.很好.

Answer 2

图灵机是由阿兰图灵发明的理论计算机,作为数学计算的理想模型,基本上是一种简单的计算机形式,它由一条带(纸带)组成,有一个头可以读取符号,写一个新符号到位,然后向左或向右移动.

据说图灵机处于某种状态,然后一个程序就是一个转换列表,头部下面有当前状态和符号,磁带上应该写什么,下一个状态是什么,以及头应该移动.

这是一个基本的图灵机,用JavaScript实现...

和草图:

Answer 3

我的IBM PC就是我完成计算所需要的!

别人没有指出的东西:你的IBM PC 是图灵机.更确切地说,它相当于它,从某种意义上说,你的PC可以做什么,图灵机可以做什么,以及图灵机可以做什么,你的电脑可以.

具体来说,图灵机是一种计算模型,可以完全捕捉可计算性的概念,同时保持简单的理由,而不需要PC架构的所有具体细节.

(普遍接受的)"Church-Turing论文"断言,每个设备或计算模型都不比图灵机更强大.因此,许多理论问题(例如P和NP等类,"多项式时间算法"等概念)都是用图灵机正式陈述的,当然,它们可以适应其他模型,如好.(例如,有时候根据lambda演算,组合逻辑或其他任何方式来考虑计算是很方便的......它们在功能上彼此相同,也与你的IBM PC相同.)

所以你去了:人们谈论图灵机,因为它是一种精确而完整的指定方式来说出"计算机"是什么,而不必描述CPU架构的每个细节,它的约束等等.

Answer 4

实际上有图灵机的例子.具体而言,将RNA翻译成蛋白质的核糖体实现了图灵机.

首先,一些背景:

1. RNA由一串核苷酸("碱基")组成,它们定义了遗传字母表的字母.
2. RNA字母表中有4个碱基--A,C,G,U.
3. 基础是方向性的:按照惯例,末端称为五元素和三元素(5',3')
4. RNA串中的碱基可以在"反平行互补对"中吸引另一个RNA串上的碱基,其中A粘附到U和C粘附到G.
5. 碱基以3个为一组组合形成"密码子"(单词).
6. 密码子有64种可能的组合(4 ^ 3).
7. 每个密码子都可以匹配"反密码子".例如AUG < - > UAC
8. 有特殊的载体分子("tRNA"),它们具有特定的反密码子并附着在特定的氨基酸(蛋白质)上.

核糖体的操作很简单:

1. 转录起始于"起始密码子",它定义了"阅读框架"
2. 转录总是以5' - > 3'方向进行
3. 阅读框下的密码子与含有特定氨基酸的特定tRNA相匹配
4. 起始密码子总是编码氨基酸甲硫氨酸.
5. 新的氨基酸与生长中的蛋白质相连
6. 然后框架将3个碱基前进至下一个密码子,并且蛋白质连续延伸
7. 在遇到"终止"密码子时,终止翻译,不附着氨基酸,核糖体与mRNA解离.

正如您所看到的,这是一台非常简单的图灵机,可以执行最复杂的操作 - 自然本身!

Answer 5

图灵机是一种理论机器,可用于推断计算机的极限.简而言之,它是一台具有无限记忆的虚构计算机.

我们关心图灵机,因为它们帮助我们发现真正的计算机(如IBM PC)无法实现的目标.如果图灵机不可能执行特定计算(如决定暂停问题),那么您的IBM PC无法执行相同的计算.