停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学…
标签：#計算理論
共 25 篇文章
邱奇-图灵论题
邱奇-图灵论题（，又称邱奇-图灵猜想，邱奇论题，邱奇猜想，图灵论题）是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说——在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。 20世纪上半叶，对可计算性进行公式化表示的尝试有： 美国数学家阿隆佐·邱奇创建了称为λ演算的方法来定义函数。 英国数学家阿兰·图灵创建了可对输入进行运算的理论机器模型，现在被…
递归
是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。]] 递归（），又译为-{zh-cn:递回; zh-tw:遞歸; zh-hk:遞迴;}-，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 …
计算理论
。圖靈機常用在計算的理論模型上]] 计算理论（）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题： 采用什么计算模型（即形式语言、自动机） 解决哪些是可计算的、哪些是不可计算的（即可计算性理论及演算法） 要用多少时间、要用多少存储（即計算複雜性理論） 這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」 計算理論的「計算」並非指純粹的算術運算…
超计算
超计算或超图灵计算可以输出非图灵可计算结果的计算模型。例如，一台可以解决停机问题的机器可算作一台超计算机；可以正确推演皮亚诺算术中每一个状态的机器亦然。 邱奇－图灵论题指出，任何可以用有限算法以纸笔计算的"可有效计算"函数都能被图灵机计算。超计算机能计算图灵机无法计算、即邱奇－图灵论题中不可计算的的函数。 严格说来概率图灵机的输出是不可计算的。然而，大多数超计算方向的文献更关注有用的计算而非随机、不可计算的函数。 参见 黑箱 图灵机 图…
柴廷常數
在计算机科学的算法信息论中，柴廷常数（也称柴廷欧米茄数）或任意随机图灵机停机的概率是一个实数。即，柴廷常数代表着随机生成的程序在通用图灵机上最终将会停机的概率。这一数字被格雷戈里·柴廷所构造。 即便有无穷多个最终停机的概率（存在无穷多个针对特定图灵机的停机概率常数），我们使用字母 \Omega 表示特定的前缀无符号通用图灵机最终停机的概率的统称。由于 \Omega 取决于图灵机具体编码的细节，因此在不指代任何特定图灵机的编码方式时，它常…
拜占庭将军问题
拜占庭将军问题（），是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错問題。 在分佈式計算中，不同的計算機通过通讯交换信息达成共识而按照同一套协作策略行动。但有時候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。 问题描述 莱斯利·兰波特在其论文 另一個解決方案需…
递归可枚举集合
递归可枚举集合（）是可计算性理论或更狭义的递归论中的一个概念。可数集合*'被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果 存在一个算法，只有当输入是*'中的元素时，算法才会中止。 或者等价的说， 存在一个算法，可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。 包含所有可递归枚举集合的复杂性类是 RE。 共同的编程意义会暗示出如何转换一种算法到…
计算符号学
计算符号学（）是一个跨学科领域，其研究、应用和借鉴领域涵盖了逻辑、数学、计算理论和实践、形式和自然语言研究、一般认知科学，以及符號學本身。该术语既涵盖了符号学在计算机硬件和软件设计中的应用，也包括使用计算来执行符号学分析。前者侧重于符号学可以为计算带来什么；后者与计算能给符号学带来什么有关。 计算符号学 该领域的一个共同主题是以符号理论视角看待人工智能和知识表示的问题。其许多应用场景是人机交互和基本识别装置。 代数符号学是该领域的一部分…
王氏砖
王氏砖（）也稱為王氏多米诺骨牌，最早由美籍華裔数学家、逻辑学家和哲学家王浩于1961年提出，屬於，也是形式系統。 王氏砖的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏砖拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。 关于特定一組王氏砖的基本问题是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式…
可計算數
可計算數（），是数学名詞，是指可用有限次、會結束的算法計算到任意精確度的实数。可計算數也被稱為遞迴數、遞迴實數或可計算實數。 等效的定義可以用递归函数、图灵机及λ演算等演算法的形式表示法而得。可計算數形成實閉域，可以在許多數學應用上取代实数。 定義 如果一個實數a能被某個可計算函數 f:\mathbb{N}\to\mathbb{Z} 以下述方式來近似，那麼 a 就是一個可計算數：給定任何正整數n，函數值f(n)都滿足： :{f(n) -…
计算模型 (数学)
在可计算性理论和计算复杂性理论中，计算模型（model of computation）描述了如何根据一组输入值计算函数的输出，包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法的计算复杂度，总结出算法的性能，而不受特定技术和实现方式的性能差异所误导。 模型 计算模型可分为三大类：顺序模型、函数式模型以及同步模型。 顺序模型 顺序模型包括 图灵机 有限状态机 下推自动机 函数式模型 函数式模型包括 递归函数 Λ演算 组合子…
決定性問題
在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一…
两军问题
两军问题（）是電腦领域的假想實驗，显示以不可靠的通訊渠道交换訊息并达成共识难以实现。问题中，两支军队的将军只能派信使穿越敌方领土互相通訊，以此约定进攻時間。该问题希望求解如何在两名将军派出的任何信使都可能被俘虏的情况下，就進攻时间达成共識。 两军问题是拜占庭将军问题的特例，常被编入与電腦网络相关的入门课程中。在传输控制协议（TCP）相关的课程中，问题可用作解释TCP协议无法保证通訊双方状态一致，也适用于其他有訊息丢失風險的通訊。作为认识…
阿克曼函數
阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。 歷史 1920年代後期，數學家大衛·希爾伯特的學生Gabriel Sudan和威廉·阿克曼，當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的苏丹函数。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。 他最初的念頭是一個三個變數的函數A(m,n,p)，使用康威鏈式箭號表示法是m→n→p。阿克曼證明了它是遞歸函數…
奇進偶捨
奇進偶捨，是一種計數保留法，是一種數值簡化規則。從統計學的角度，“奇進偶捨”比“四捨五入”更為精確：在大量運算時，因為捨入後的結果有的變大，有的變小，更使捨入後的結果誤差均值趨於零。而不是像四捨五入那樣逢五就進位，導致結果偏向大數，使得誤差產生積累進而產生系統誤差。“奇進偶捨”使測量結果受到捨入誤差的影響降到最低。 計算過程 其具體要求舉例如下（以保留兩位小數為例）： 保留位數的後一位如果小於5，則捨去。例如5.214保留兩位小數為5.…
忙碌的海狸
在计算机科学中，忙碌的海狸（）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1. 包含两个状态的忙碌的海狸游戏有下面两条规则： 该图灵机包括除终止态以外的两个状态 纸带初始值都是0 玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。 能赢得n个状态的忙碌的海狸游戏的图灵机，称为第n个忙碌的海狸，或者用BB-n表示(B…
圖靈完備性
在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它便符合图灵完备（Turing-complete或computationally universal）。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。 还有一个相关概念是图灵等价如果P可以模拟Q并且…
马尔可夫算法
马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的，这意味着它们适合作为一般的计算模型，并可以用它的简单概念表示任何数学表达式。 Refal是基于马尔可夫算法的编程语言。 算法 #自顶向下依次检查规则，看是否能在符号串中找到任何在箭头左边的字符串。 #如果没有找到，停止执行算法。 #如果找到一个或多个，把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。 #返回步骤1并继续…
苏丹函数
苏丹函数（），是递归函数，但如同阿克曼函数，不能通過μ算子定義更廣泛的偏遞歸函數類，因而不是原始递归函数。苏丹函数是第一个具有此属性的函数。 它于1927年由大卫·希尔伯特的学生羅馬尼亞数学家加布里埃尔苏丹发现并发表。 定义 : \begin{array}{lll} F_0 (x, y) & = x+y \\ F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\ F_{n+1} (x, y+1) & …