莱斯定理
莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 定理 P是所有图灵可计算函数构成的集合，S是P的一个非空真子集，即：\emptyset\neq S \subsetneq P。将图灵机以某种方式编码，使得每一个n\in \mathbb{N}都唯一对应一个…
标签：#计算模型
共 38 篇文章
SECD机
SECD机（SECD machine），是较有影响力的一种抽象机和虚拟机，它意图用作函数式编程语言编译器的编译目标。SECD这四个字母分别表示这个机器的内部寄存器：stack、environment、control和dump。 SECD机是第一个专门设计用来求值叫做应用表达式的扩展λ演算的机器。它最初描述于Peter J. Landin的1964年论文《表达式的机器求值》中。Landin发表的SECD抽象机，处理的是抽象语法树，故而可视…
隨機存取機
在理論計算機科學中，隨機存取機（，縮寫為RAM）是一種抽象機器，屬於寄存器機的一種。近似於計數器機，但是它擁有能對暫存器間接定址的能力。隨機存取機是圖靈機的一種，等價於通用圖靈機。隨機存取機屬於哈佛架構，與電子計算機的特徵近似；如果修改為馮紐曼架構，則成為隨機存取儲存程式機（RASP）。 與圖靈機、計數器機模型相同，隨機存取機器與隨機存取儲存程式機，都常被用於計算複雜性理論之中。 相關條目 * 隨機存取儲存程式機
量子線路
傳傳輸的線路。 該線路由量子閘和測量組成。測量是一種量子現象，在經典電路中不會發生。]] 量子線路或沿用古典稱呼而稱作量子電路，是在抽象概念下，對於量子資訊儲存單元（例如量子位元）進行操作的線路。組成包括了於量子資訊儲存單元、線路（時間線），以及各種邏輯閘；最後常需要量子測量將結果讀取出來。電路需要能夠對量子位元執行以實現量子計算的最小操作集被稱為迪文森佐準則（DiVincenzo's criteria）。 編寫電路時，水平軸是時間，從…
D-Wave 系统公司
D-Wave 系统公司（D-Wave Systems, Inc）是一家量子计算机公司，佐迪·羅斯創立，座落于加拿大英属哥伦比亚省的本那比市。 歷史 佐迪·羅斯認為傳統的量子電腦構思方法是一種很差的設計，導致長期以來突破有限，2003年他認為找到另一種達成量子運算的蹊徑旁路方法，此方法至今仍有部分保密，於當年成立D-Wave 系统公司。 量子電腦最大困難在於操作量子位元必須使用量子纏結，而這過程外部任何因素都會干擾所以必須搭配龐大複雜的機…
量子体积
量子体积（）是一项综合性指标，旨在衡量并比较不同量子计算机的整体性能和保真度。 它通过一个单一数值来概括量子计算机所能成功运行的最大“方形”量子线路的尺寸，这个尺寸同时取决于系统的量子比特（）数量和它们的质量。 提出量子体积这一概念，是为了解决仅用量子比特数量来评判性能的局限性。与经典计算机的晶体管数量不同，量子比特的数量并不能完全代表计算能力，因为量子比特会因退相干及各种噪声（如门操作错误、测量错误和串扰）而出错，导致性能下降。 因此…
量子计算机
乃一種對於二階量子系統之純態空間的幾何表示法，是建立量子電腦的基礎。]] 量子计算机（）是以量子力学为基础搭建、用于進行通用計算的設備。量子计算机使用量子比特来儲存數據，使用量子演算法操作數據。不同于电子计算机的比特只能处于0或1两种状态之一，量子比特可以处于这两个基态之间的叠加态，也就是说，它可以以一种抽象意义上的“中间状态”同时表现出两种基态的特性（即同时为0和1）。当对量子比特进行测量时，结果是一个经典比特的概率性输出。如果量子计…
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。 图灵的基本思想 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一处移动到另一处； 而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某…
个体为本模型
基于主体的模型（agent-based model，ABM） , 又称多行为体系統（multi-agent system, MAS），若行为体具有異質性，则称为异质行为体模型（heterogeneous agent model, HAM） ，是一种用来模拟具有自主意识的行为体（独立个体或共同群体，例如组织、团队）的行动和相互作用的计算模型，通过图像展示评估行为体在系统整体中的作用。它综合了一些其他思想，比如博弈论、复杂系统、涌现、计算社…
預言機
在计算复杂度理论与可计算性理论中，预言机（），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具備在一次运算之內解答特定问题的黑盒子（又稱為预言者）的图灵机；該问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。 定義 一部預言機可以視為是與一個預言者（）相連接的圖靈機。所謂預言者的概念，是一個可以回答特定問題集合的一個實體，而且常常使用特定的自然數子集A來表示這個問題。我們可以很自然的發現，一部預言機可以執行很多對…
Λ演算
λ演算（英語：lambda calculus，λ-calculus）是一套從數學邏輯中發展出的形式系統，以變數綁定和替換的規則，來研究函式如何抽象化定義、函式如何被應用以及遞迴。它由數學家阿隆佐·邱奇在20世紀30年代首次發表。lambda演算作為一種廣泛用途的計算模型，可以清晰地定義什麼是一個可計算函式，而任何可計算函式都能以這種形式表達和求值，它能模擬單一磁帶图灵机的計算過程；儘管如此，lambda演算強調的是變換規則的運用，而非實…
芝诺机
在数学和计算机科学中，芝诺机（缩写为ZM ，也称为加速图灵机、 ATM ）是一种与图灵机相关的假设计算模型，它能够执行涉及可数无限个算法步骤的计算。 大多数计算模型都不考虑这些机器。 芝诺机的想法最早由赫尔曼·外尔于 1927 年提出；该名称指的是芝诺悖论，源于古希腊哲学家埃利亚的芝诺。芝诺机在某些理论中发挥着至关重要的作用。例如，物理学家弗兰克·J·蒂普勒(Frank J. Tipler) 提出的欧米茄点理论只有在芝诺机可行的情况下才…
抽象機器
抽象機器（），又稱抽象電腦（），利用自動機理論，建立出電腦硬體或軟體的理論模型。把運算過程抽象化，一般來說是採用離散時間模型，可應用於電腦科學或電腦工程。在計算理論中，抽象機器經常被當成是一種思想實驗，用來推論可計算性（），或是分析演算法的時間複雜度及空间复杂度。 参见 抽象機器 垃圾进，垃圾出 算法导论 计算理论 可计算性理论 計算複雜性理論 * 高级综合
指称语义
在计算机科学中，指称语义（）是通过构造表达其语义的（叫做指称(denotation)或意义的）数学对象来形式化计算机系统的语义的一种方法。编程语言的形式语义的其他方法包括公理语义和操作语义。指称语义方式最初开发来处理一个单一计算机程序定义的系统。后来领域扩展到了由多于一个程序构成的系统，比如网络和并发系统。 指称语义起源于 克里斯托弗·斯特雷奇 和 Dana Scott 在1960年代的工作。在 Strachey 和 Scott 最初开…
狀態空間 (計算機科學)
]] 计算机科学裡的狀態空間是對應一系統中所有可能組態的离散空间 }} 外部連結 [http://www.mathematik.uni-muenchen.de/~pareigis/Papers/Fds.pdf Equivalence Relations on Finite Dynamical Systems] , Laubenbacher, R. Pareigis, B., ADVANCES IN APPLIED MATHEMATICS…
串流處理
串流處理（）是一種計算機編程範式，相當於數據流程編程，，和反應式編程 ，其允許一些應用更容易地利用了有限形式的並行處理。這些應用程序可以使用多個計算單元，例如圖形處理上的浮點運算器或現場可編程門陣列（FPGAs），而無需明確管理這些單元之間的分配，同步或通信。 串流處理範例通過限制可執行的並行計算來簡化並行軟件和硬件。給定一個數據序列（串流處理），一系列操作（內核函數）被應用到串流中的每個元素。例如：直播軟件。內核函數通常使用流水線(計…
演员模型
在電腦科學中，演員模型（）是一種並行運算上的模型。「演員」是一種程式上的抽象概念，被視為並行運算的基本單元：當一個演員接收到一則訊息，它可以做出一些決策、建立更多的演員、傳送更多的訊息、決定要如何回答接下來的訊息。演员可以修改它们自己的私有状态，但是只能通过消息间接的相互影响（避免了基于锁的同步）。 演員模型在1973年於、Peter Bishop及Richard Steiger的論文中提出。它已经被用作并发计算的框架和并发系统的基础。…
整体同步并行
整体同步并行（Bulk Synchronous Parallel）抽象机器，是用来设计并行算法的计算模型，由哈佛大学莱斯利·瓦利安特提出，他希望像冯·诺伊曼体系结构那样，架起计算机程序语言和体系结构间的桥梁，故又称其为桥接模型（Bridging Model）。 历史 BSP是哈佛大学计算机科学家Leslie Valiant在1980年代开发的，决定性文章发表于1990年。 在1990年至1992年间，Leslie Valiant在普林斯…
隨機存取儲存程式機
在理論計算機科學中，隨機存取儲存程式機（，縮寫為RASP）是一種抽象機器，屬於寄存器機，可使用於演算法開發與計算複雜性理論中。隨機存取儲存程式機類似於隨機存取機，這兩者都是一種圖靈機，等價於通用圖靈機。這兩者主要的區別是，隨機存取機是哈佛架構下的一個實例，而隨機存取儲存程式機則屬於冯·诺伊曼结构。
資料串流
資料串流（），是一个用在電腦计算的術語，有多方面的含義，取决于具體的应用程序及使用情境。在软件架构領域，資料流指的通常是串流處理或响应式编程。 軟件架構 資料流是一種軟件範例，它基於將計算參與者與可以同時執行的階段（管道）斷開連接的想法。數據流也可以稱為串流處理或响应式编程。 硬件架構 並發性 另見 参考文献 外部链接