题

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

有帮助吗？

解决方案

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

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

图灵机的研究也有助于研究语言语法及其类，从而导致编程语言的发展。术语<！>“正则表达式<！>”;是因为它们是常规语法，以及这些语法的研究（计算理论的一部分） ）会告诉你更多关于正则表达式可以解决什么类型的问题以及它们不能解决的问题。例如，传统的正则表达式语法将无法解决以下问题：在输入中解析一些N个'a'字符，然后解析相同数量N的char'b'。

如果您对这类事情的好文章感兴趣，请查看简介Michael Sipser的“计算理论”。这很好。

其他提示

  

我的IBM PC就是我计算所需的全部内容！

其他人没有指出的东西：您的IBM PC 是图灵机。更确切地说，它相当于它，从某种意义上说，你的PC可以做什么，图灵机可以做什么，以及图灵机可以做什么，你的电脑可以。

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

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

所以你去了：人们谈论图灵机，因为它是一个精确而完整的指定方式来说出什么<！>“计算机<！>”;是，无需描述CPU架构的每个细节，其约束等等。

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

首先，一些背景知识：

  1. RNA由一串串组成 核苷酸（<！>“base <！>”;）定义 遗传字母表中的字母。
  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 <！> lt; - <！> gt; UAC
  8. 有特殊的载体分子 （<！>“tRNA <！>”）具有特殊性 反密码子和附着 特定氨基酸（蛋白质）。

    9. 核糖体的操作很简单：

    1. 转录在<！>“开始时开始 密码子<！>“;”，它定义了<！>“读数 帧QUOT <！>;
    2. 转录始终以5' - <！> gt; 3'方向进行
    3. 阅读框下的密码子是 与特定的tRNA匹配 含有特定氨基酸
    4. 起始密码子总是编码 氨基酸蛋氨酸。
    5. 新的氨基酸与生长的蛋白质相连
      6. 然后，框架将3个碱基前进至下一个密码子，并且蛋白质连续延伸
    6. 遇到<！>“;停止<！>”;密码子，翻译终止，没有氨基酸附着，核糖体与mRNA解离。

      7. 正如您所看到的，这是一个非常简单的图灵机，它执行最复杂的操作 - 自然本身！

图灵机是一种理论机器，可用于推断计算机的限制。简单地说，它是一台具有无限记忆的虚构计算机。

我们关心图灵机，因为它们帮助我们发现真实计算机（如IBM PC）无法实现的目标。如果图灵机无法执行特定计算（例如决定暂停问题），那么你的IBM PC不可能执行相同的计算。

为什么设计飞机的人会关心莱特兄弟，或者<！>“背后的科学”升力<！>那让固定翼飞机飞起来了？

Alan Turing被誉为现代计算之父。图灵机是所有现代计算机的先驱。

可计算性理论是我在大学里最难上课的，但我很高兴我接受了它。这让我想到了我从来没有过的事情，或者以我从未想过的方式思考事物，这些都是好事。

图灵机是一种能够计算的抽象机器。

来自维基百科：

  图灵机是基本的抽象符号操作设备，尽管它们简单，但可以适用于模拟任何计算机算法的逻辑。它们于1936年由Alan Turing描述。图灵机不是一种实用的计算技术，而是一种关于机械计算极限的思想实验。因此它们实际上并没有构建。研究它们的抽象属性可以产生对计算机科学和复杂性理论的许多见解。

     

能够模拟任何其他图灵机的图灵机称为通用图灵机（UTM，或简称为通用机器）。更具数学定义的定义，具有类似的<！> quot; universal <！> quot;大自然是由Alonzo教堂引入的，他对lambda微积分的研究与图灵的形式交织在一起，被称为Church-Turing论文。论文指出，图灵机确实捕捉到逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。

根据一些逻辑，图灵机是一个抽象的机器，它可以对一系列数据进行操作，并且可以在操作时改变它自己的状态和数据。

这是一个概念，通常构成算法，存储程序和计算的基础。如果您处理算法，状态，数据等，它提供了很好的见解和抽象。

为大多数人提供思考的食物。

除了维基百科条目，你可能还想拿起这本书 The Annotated查尔斯·佩佐尔德的图灵。字幕<！>“通过艾伦图灵关于可计算性和图灵机的历史性论文的引导之旅<！>”，它包括完整的论文，分解成有关该主题的大量讨论，包括历史观点。

图灵机相当于一种算法。当它接受字符串时停止，当它不接受字符串时拒绝或进入无限循环。

磁带充当内存，转换规则充当“if then else”条件

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top