http://wiki.foofun.cn//index.php?action=history&feed=atom&title=Register_Machine_Model_of_Computation 2026-04-05T12:05:30Z 本wiki上该页面的版本历史 MediaWiki 1.37.1 http://wiki.foofun.cn//index.php?title=Register_Machine_Model_of_Computation&diff=252&oldid=prev 2022-01-19T06:11:14Z

<p>创建页面，内容为“此页面旨在概述计算的理论寄存器机模型，这是大多数实际CPU设计的概念基础。 虽然假设任何来到这里的人都至少会对这些概念非常熟悉，但它的目的是对该主题进行回顾，以消除新来者可能有的任何误解。 “寄存器机模型” 是 “计算模型”，用于描述不同方程式的可计算性。 它是一类被称为「随机存取机器」 (RAMs) 的计算模型的子类型，其中也…”</p> <p><b>新页面</b></p><div>此页面旨在概述计算的理论寄存器机模型，这是大多数实际CPU设计的概念基础。 虽然假设任何来到这里的人都至少会对这些概念非常熟悉，但它的目的是对该主题进行回顾，以消除新来者可能有的任何误解。<br /> <br /> “寄存器机模型” 是 “计算模型”，用于描述不同方程式的可计算性。 它是一类被称为「随机存取机器」 (RAMs) 的计算模型的子类型，其中也包括相关的「堆栈机器」模型。 它是许多高度多样化的模型中的一种，其中一些 (包括许多寄存器机) 是 “图灵等效” 的，也就是说，它们可以计算与通用图灵机相同的命题集。 寄存器机模型的相关性在于，它是所有模型中最容易在电子硬件中近似的，实际上，该模型的开发是为了用数学术语描述第一个可编程计算机系统，以证明它们是图灵等效的。<br /> <br /> == 计算模型和计算历史 ==<br /> ''[https://en.wikipedia.org/wiki/Model_of_computation model of computation]'' 是一种数学形式，它描述了用于执行计算的机械过程 (确定性和基于规则的 “机械”，而不一定非要是机械化的或电子化的)。 这种形式主义的想法出现在20世纪初期，当时几位数学家-最著名的是阿尔弗雷德·怀特海 (Alfred Whitehead)，大卫·希尔伯特 (David Hilbert) 和贝特朗·罗素 (Bertrand Russell)-开始推测是否有可能开发一种用于推导数学证明的机械系统。<br /> <br /> === 早期模型: 递归函数、 λ-演算和通用图灵机 ===<br /> 最早的计算模型，都是在20世纪20年代初发展起来的 ''[https://en.wikipedia.org/wiki/%CE%9C-recursive_function 递归函数理论] ''和'' 递归集合论 ''，两者都用于开发一组用于执行计算和证明定理的规则。<br /> <br /> 当[https://en.wikipedia.org/wiki/Kurt_G%C3%B6del Kurt Gödel] 证明了任何数学逻辑形式主义都会有盲点-以 “无法确定的命题”，自动定理证明的最初目标1933年受到了沉重打击。无法证明的真实定理或 “无效命题” 的形式存在，定理可能在系统中是 “有效的”，但实际上不是正确的或与另一个定理相矛盾。 虽然这是一个重大挫折，但哥德尔使用的证明证明了递归函数是探索 “计算” 新领域的有用工具。<br /> <br /> 下一个重要的模型是由阿隆佐·丘奇·1935年创建的 ''[https://en.wikipedia.org/wiki/Lambda_calculus lambda calculus| λ演算]''。 这是一个比现有类型的递归函数理论更简单的函数模型，但被证明具有与RFT相同的计算能力。 丘奇假设这两个模型实际上是任何顺序模型都可以完成的。<br /> <br /> 同年，丘奇的研究生艾伦·图灵 (Alan Turing) 开发了另一种模型，“[https://en.wikipedia.org/wiki/ Universal_Turing_machine图灵机]”，他用来证明数学中一个众所周知的未解决的目标-找到 [https://en.wikipedia.org/wiki/ halting_problement证明任何任意计算过程都将完成的方法]-是不可能的，通过显示测试过程本身在一般情况下必然是 “[https://en.wikipedia.org/wiki/ 无法确定的问题]”。<br /> <br /> 图灵机，其基本形式如论文 “[https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf 关于可计算数字，并应用于“ entscheidungsproblem' ”] 中所述，被认为是由磁带读/写器和无限长的纸带组成的机器，该纸带被分成包含数据的单元格-人们可以将单元格视为在磁带上绘制的框，以标记特定数据的位置。对于每个操作，图灵机将自己定位在单元格上，读取单元格中的数据，并根据该数据，决定是否在单元格中写入数据 (是相同的还是不同的)，移动到另一个单元格，或停止运行并弹出当前状态的磁带作为其最终输出。 在他的论文中，他最初描述了每台机器对数据具有一组固定的响应，分别存储在 “操作表” 中，以及一组固定的状态，数据可以放入其中。然后他继续 <br /> <br /> 通过这样做，他表明有可能设计出一种可以模拟任何其他可能的图灵机的变体; 这种 “通用图灵机” (UTM) 展示了与RF和 λ-Calculius相同的通用性，他扩展了丘奇的前提，即这三个模型代表了顺序计算的绝对极限，这被称为 “[https://en.wikipedia.org/wiki/ Church-Turing_thesis丘奇-图灵论文]”。虽然没有得到证实，但人们普遍认为它可能是正确的，结果是 “[https://en.wikipedia.org/wiki/Turing_completenessTuring 完整性]” 成为任何机械模型计算能力的基准。<br /> <br /> 必须理解，这些模型仅在建立在一组规则的意义上是 “机械的”; 它们对于开发物理计算设备不是很有用。 在所有这些中，UTM是最接近的，因为它是根据由读写头和无限长的纸带组成的虚构机制来描述的。 虽然这不是一个实用的设计，但它证明了当时的机械计算器具有坚实的理论基础，更重要的是，重新引入了 “可编程” 计算设备的概念 (最初由查尔斯·巴贝奇提出)。<br /> <br /> === 早期的机电和电子计算机 ===<br /> 图灵将继续在第一批可编程电子计算机之一的开发中做重要的工作，这是ULTRA project的Colossus解密机，最初是由Tom Flowers在1943年构思的。 在此期间，从20世纪30年代末到20世纪50年代初，几组设计师似乎彼此独立地提出了类似的想法: 德国的Konrad Zuse，爱荷华州立大学的John Atanasoff和Clifford Berry，普林斯顿的Presper Eckert和John Mauchly，哈佛的Howard Aiken，所有人都重新发现了存储程序计算机1941年和1943的原理，这个概念后来由约翰·冯·诺伊曼 (John Von Neumann) 领导的团队在白皮书中编纂。 因此，将程序和数据存储在共享存储器中的设计被称为 “冯·诺依曼架构”，而那些具有独立的程序和数据存储器的设计，例如Zuse Z4和哈佛Mark 1，被称为 “哈佛架构”。<br /> <br /> === 线性有界自动机和物理计算的极限 ===<br /> 战后，电子计算如何与理论模型相关的问题变得很重要，因为尚不清楚它们是否等同于UTM，或者它们是否具有纯粹虚构的模型所没有的限制。 解决此问题的方法归结为图灵机和所有更抽象的等效物共享的重要属性: 至少一个无限资源的可用性，特别是通用图灵机的磁带存储器。<br /> <br /> 这导致创建了一个新模型，该模型可以描述这些限制并允许他们确定它们是什么。 这种新模型 “[https://en.wikipedia.org/wiki/Linear_bounded_automaton 线性有界自动机]”，是图灵机的一种变体，具有有限的可用内存 (通常根据读取器可以访问有限的连续部分来描述无限磁带，因此称为 “线性有界”)。 这样可以研究不同类别的计算的内存需求，并且开发了类似的模型来研究时间需求。<br /> <br /> === 有限自动机和乔姆斯基层次 ===<br /> 同时，继续进行更抽象形式的理解工作，并制定了各种各样的图灵完整计算模型，以及许多可证明功能较差的模型。 虽然Church-Turing论文是这些假设的极限，但它仍然是一个猜想，而且尚不完全清楚不同的模型如何相互关联，尤其是那些不是Turing的模型。<br /> <br /> 1955年，语言学家 [https://en.wikipedia.org/wiki/Noam_Chomsky 诺姆·乔姆斯基] 制定了一个层次结构，根据 [https://en.wikipedia.org/wiki/Formal_grammar 生成语法] 和 “识别” 语法正确句子的数学模型对 [https://en.wikipedia.org/wiki/Generative_gramma 语法正式语法] 进行分类。 他证明了相同的 [Chomsky层次结构] 不仅适用于如何机械地生成句子以及如何机械地识别句子，而且层次结构的级别与一定程度的可计算性相对应，他的 [https://en.wikipedia.org/wiki/Unrestricted_grammar Type-0语法] (也称为 “不受限制的语法”) 是 “递归可枚举的”，因此需要图灵完全机制来识别或生成。<br /> <br /> {{stub}}<br /> <br /> === 计数器、累加器、堆栈和寄存器 ===<br /> 但是，如果给定无限的资源 (主要是内存)，机器是否可以 “原则上” 是图灵完整的问题仍然存在。 这导致为机器创建了一组抽象模型，这些模型类似于实际使用中的机器，但没有LBA的内存限制。<br /> <br /> {{stub}}<br /> <br /> == 随机存取机模型 ==<br /> 随机存取机是一种抽象模型，与传统计算机的结构非常相似。 它由一个分为一组单元格的数据存储器组成，线性和单调排列 (也就是说，单元格以严格的数字顺序彼此跟随，并且每个单元格在地址空间中的 “大小” 相同-这并不 “必要” 反映其保存数据的能力)，其中单元格可以通过数字地址访问; 指令存储器，它可能与数据存储器相同，也可能不同，但结构相似; 它可以执行的一组操作; 一组指令，以一种形式编码，该形式可以保存在一组存储单元中，该存储单元用于指示要执行的操作; 以及程序计数器，该程序计数器保存指令存储器中的单元的地址，该单元对要执行的操作进行编码。<br /> <br /> <br /> {{stub}}</div>

Zhang3