事件驅動有限狀態機
在計算機科學中，有限状态机（FSM）是事件驅動的，若從一個狀態到另一個狀態的轉換是由事件或是訊息所驅發的，這和有限状态机一詞出自的語法分析理論相反，其中將状态机描述為消費字元或是記號（tokens）的機器。 多半有限状态机是一個线程或行程，是較大應用程式的一部分，需要和其他程式通訊。例如，電信通訊協定大部份都會用事件驅動有限狀態機來表示。 C語言的例子 以下程式描述一個簡單汽車收音機系統的狀態機，基本上是一個讀取事件的無窮迴圈，狀態機有…
标签：#计算模型
共 38 篇文章
组合子逻辑
组合子逻辑是Moses Schönfinkel和哈斯凱爾·加里介入的一种符号系统，用来消除数理逻辑中对变量的需要。它最近在计算机科学中被用做计算的理论模型和设计函数式编程语言的基础。它所基于的组合子是只使用函数应用或早先定义的组合子来定义从它们的参数得出的结果的高阶函数。 数学中的组合子逻辑 组合子逻辑意图作为简单的元逻辑，它能澄清在逻辑符号中的量化变量的意义，并真正的消除对它们的需要。消除量化变量的另一种方式是蒯因的谓词函子。尽管多数…
计算模型 (数学)
在可计算性理论和计算复杂性理论中，计算模型（model of computation）描述了如何根据一组输入值计算函数的输出，包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法的计算复杂度，总结出算法的性能，而不受特定技术和实现方式的性能差异所误导。 模型 计算模型可分为三大类：顺序模型、函数式模型以及同步模型。 顺序模型 顺序模型包括 图灵机 有限状态机 下推自动机 函数式模型 函数式模型包括 递归函数 Λ演算 组合子…
计数器机
計數器機（）是一種抽象機器，作为用于形式逻辑和理论计算机科学中的计算模型，计数器机是寄存器机模型的最原始的子类。 它只由如下组成：(i)一序列的一个或多个(唯一性)命名的“无界”寄存器(只包含一个单一无界正整数的寄存器)，(ii)假如到或减去自寄存器的叫做“计数器”的物件，(iii)让计算机(人或机器)服从的(通常顺序的)算术和控制指令的列表。 对于给定的计数器机模型，指令集是非常微小的，只有从 1 到 6 或 7 指令。所有模型都包含…
可逆計算
可逆計算（），是一種計算模型，它的計算過程是可逆的。在這種計算模型中，使用的能量很低，熵的增加會最小化，換句話說，它幾乎不會產生額外的熱。 在可逆計算模型中，轉換函數的前一個狀態，與下一個狀態之間的關係，是一對一的反函數。因此，它的邏輯閘，除了產生出我們想要的答案之外，還需要包含許多額外的位元，用以記憶運算的歷史。最早提出可逆計算的先驅，是IBM的工程師羅夫·蘭道爾（Rolf Landauer）。 可逆电路 对于可逆电路的实现，人们一般…
堆疊結構機器
堆疊結構機器（），又稱堆疊機器，是電腦科學中一種計算模型。這種類型的電腦，記憶體以堆疊（Stack）儲存。 這種機器，它的指令集中包含了零位址指令（"0-operand" instruction set）。硬體在執行運算時，到堆疊的頂端去取出運算元，至運算結束時，再儲存到堆疊的頂端。 相較於累加器（採用 "1-operand instruction set"） 和寄存器機（"2-operand instruction set" 或 "3…
单一指令计算机
单一指令计算机（，OISC）也称最简指令集计算机（ultimate reduced instruction set computer，URISC），它是一种抽象计算机，该计算机只有一条指令 }}
寄存器机
在数理逻辑和理论计算机科学中，寄存器机（），又譯為暫存器機，是以类似于使用图灵机的方式使用的一类抽象機器。所有模型都是图灵等价的。 寄存器机得名于它有一个或多个“寄存器”——替代了图灵机的磁带和磁头，这个模型使用了多个唯一寻址的寄存器，每个都持有一个单一正整数。 在文献中至少可找到4个子类，下面按最原始到最类似计算机的次序列出： 计数器机——最原始和精简的模型。缺乏间接寻址。指令在按照哈佛结构的有限状态机内。 指针机——计数器机和RAM…
佩特里網
佩特里網（），又譯為裴氏網、派翠網路，是对离散并行系统的数学表示。佩特里網屬於離散事件動態系統，是1960年代由卡尔·亚当·佩特里发明的，适合于描述异步的、并发的计算机系统模型。佩特里網既有严格的数学表述方式，也有直观的图形表达方式。 由于佩特里網能表达并发的事件，被认为是自动化理论的一种。研究领域趋向认为佩特里網是所有流程定义语言之母。 背景 卡尔·亚当·佩特里是一名物理学家，他发明佩特里網主要是从物理的角度去描述并发现象的。据佩特里…
LogP模型
LogP是由大衛·卡勒等人提出的，它使用了L,O,G,P四个参数来描述这个模型。 ; L (Latency) :表示信息从源到目的地所需的时间； ; O (Overhead) :表示处理器接受或发送一条消息所需额外开销，并且在此期间处理器不能做作任何操作； ; G (Gap):表示处理器连续进行两次发送或接收消息之间必须有的时间间隔； ; P (Processor) :表示处理器的数目。 由上可以看出，LogP模型一方面充分讨论了网络的…
實現 (控制系統)
系统科学中，針對状态空间模型的實現是指針對給定輸入-輸出關係的系統表示法。給定一個輸入-輸出關係，其實現是時變矩阵的四元組 A(t),B(t),C(t),D(t), 使得 : \dot{\mathbf{x}}(t) = A(t) \mathbf{x}(t) + B(t) \mathbf{u}(t) : \mathbf{y}(t) = C(t) \mathbf{x}(t) + D(t) \mathbf{u}(t) 其中(u(t),y(t)…
马尔可夫算法
马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的，这意味着它们适合作为一般的计算模型，并可以用它的简单概念表示任何数学表达式。 Refal是基于马尔可夫算法的编程语言。 算法 #自顶向下依次检查规则，看是否能在符号串中找到任何在箭头左边的字符串。 #如果没有找到，停止执行算法。 #如果找到一个或多个，把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。 #返回步骤1并继续…
肽運算
肽运算是一种与传统的硅基计算机技术不同的，运用了多肽-分子生物学的运算形式。 简介 这种计算模型是基于抗体在肽序列（氨基酸序列）的链接。与DNA运算相仿，肽序列与抗体之间的平行相互作用已被利用于这个模型来解决一些“NP完备”问题。具体来说，现在已经运用这种计算模型解决了汉米尔顿路径问题（HPP）和一些版本的集合覆盖问题。这种计算模型也显示出自身的具有等用于通用图灵机的计算能力(或者说是“图灵完全”的)。 这种计算模型比起DNA运算有些关…
标记系统
标记系统是 Emil Leon Post 在1943年创立的确定性计算模型，作为一种简单形式的字符串重写系统。标记系统也可以看作抽象机，叫做 Post 标记机（不要混淆于Post-图灵机）——简单的说，其唯一的磁带是无限长度的FIFO队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。 定义 标记系统是三元组 (m, A, P)，这里的 m 是正数，叫做删除数。 A 是有限的符号…
持久化
在计算机科学中，持久性是的一個特征。一般計算機是将某個状态作为数据存储在電腦數據存貯器以实现持久化。程式必須将数据存儲在儲存設備以及从存储设备中讀取数据，并且必须提供本地编程语言数据结构和存储设备数据结构之間的映射。 参考文献
波斯特-图灵机
波斯特-图灵机（-图灵机）是一种特别简单类型的图灵机的“程序公式化”由下面描述的的图灵等价的计算模型构成。波斯特的模型和图灵的模型，尽管相互之间非常类似，但却是独立开发的。图灵的论文在1936年五月出版，波斯特的论文在十月出版。波斯特-图灵机使用二元字母表，无限序列的二元存储位置，和带有在存储位置上双向移动和一次一个更改其内容的指令的原始编程语言。 “波斯特-图灵程序”和“波斯特-图灵机”的名字由馬丁·戴維斯在1973年-1974年使用…
斯科特信息系统
信息系统和 Scott 领域 给定一个信息系统 A = (T, Con, \vdash) ，我们可以建造斯科特域如下。 定义: x \subseteq T 是一个点当且仅当 如果 X \subseteq_f x 则 X \in Con 如果 X \vdash a 并且 X \subseteq_f x 则 a \in x 设 \mathcal{D}(A) 指示 A 的点的集合并按子集排序。在 T 是可数的时候，\mathcal{D}(A)…
变迁系统
在计算机科学和控制理论中，“变迁系统”用数学的方法描述离散系统的行为。变迁系统主要由“状态”和状态之间的“状态迁移”组成。 有标号的变迁系统可以从已定义的标签集合中选择相应标签来标记状态迁移，而且相同的标签可能被应用在多个状态迁移上。 变迁系统也可以是无标记的，此时也可以认为标签集合中只有单一标签元素，从而省略了状态迁移上的标签记号。 变迁系统在数学定义上和有向图一致，但与有限状态自动机有一定不同。 变迁系统的特点有： 系统状态的集合不…