莱斯定理
莱斯定理（Rice's theorem）是可计算性理论中的一条定理，由亨利·戈登·莱斯于1953年提出。定理指出，递归可枚举语言的所有非平凡（nontrival）性质都是不可判定的。 “非平凡”是指，仅被部分递归可枚举语言具有的特性。 定理 P是所有图灵可计算函数构成的集合，S是P的一个非空真子集，即：\emptyset\neq S \subsetneq P。将图灵机以某种方式编码，使得每一个n\in \mathbb{N}都唯一对应一个…
标签：#图灵机
共 13 篇文章
交替式图灵机
交替式图灵机（, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。 定义 直观描述 NP的定义中使用了语言的存在形式，亦即如果存在一个选择都能够使得图灵机达到接受状态，那么整个语言就能够被接受。与此对应，反NP的定义中使用了语言的全称形式，亦即整个语言被接受，当且仅当每一个选择都达到一个接受状态…
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。 图灵的基本思想 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一处移动到另一处； 而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某…
量子圖靈機
量子图灵机( QTM ) 或通用量子计算机是一种用于模拟量子计算机效应的抽象机器。它提供了一个简单的模型，可以捕捉量子计算的所有能力——也就是说，任何量子算法都可以正式表示为特定的量子图灵机。然而，计算等效量子电路是更常见的模型。 量子图灵机可以在基于转换矩阵的框架中与经典和概率图灵机相关联。也就是说，可以指定一个矩阵，其与表示经典或概率机器的矩阵的乘积提供了表示量子机器的量子概率矩阵。兰斯·福特诺（Lance Fortnow）展示过这…
芝诺机
在数学和计算机科学中，芝诺机（缩写为ZM ，也称为加速图灵机、 ATM ）是一种与图灵机相关的假设计算模型，它能够执行涉及可数无限个算法步骤的计算。 大多数计算模型都不考虑这些机器。 芝诺机的想法最早由赫尔曼·外尔于 1927 年提出；该名称指的是芝诺悖论，源于古希腊哲学家埃利亚的芝诺。芝诺机在某些理论中发挥着至关重要的作用。例如，物理学家弗兰克·J·蒂普勒(Frank J. Tipler) 提出的欧米茄点理论只有在芝诺机可行的情况下才…
非确定型图灵机
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 : \delta: Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}} 其中Q是状态集合，\Gamma是带字母表，L, R分…
機率圖靈機
在計算複雜性理論內，機率圖靈機（probabilistic Turing machine）是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變（transition）。 在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號（概括地說，這個寫入指令以相同的機率在紙帶上面寫入「1」或者「0」。）另一個常用的定義是多了一條隨機…
圖靈完備性
在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它便符合图灵完备（Turing-complete或computationally universal）。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。 还有一个相关概念是图灵等价如果P可以模拟Q并且…
枚举器
枚举器是图灵机的一种变种。它和图灵机的工作原理类似，但它不需要接受输入，一旦开始运行后就不停地在纸带上打印出一个一个的字符串。可以把它看作是一种带打印机的图灵机。枚举器E所打印出的字符串的集合称为该枚举器的语言，记作L(E)。 注意： L(E)可能是无限集合，这种情况下E将永不停机。 枚举器E可以以任意的顺序枚举语言L(E)，而且可能多次重复地打印出L(E)中的同一个串。 参见 图灵机 递归可枚举语言 图灵可判定语言 图灵可识别语言
递归语言
在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。 定义 递归语言有两种等价的主要定义: 递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。 设 S ⊆ Σ 是一个语言，M 是一台图灵机， 若对于任何字符串 ω ∈ Σ，有 ω ∈ S 当且仅当 M 接受 ω ω ∉ S 当且仅当 M 拒绝 ω 则称 M 判定语…
递归可枚举语言
在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。 形式定义 递归可枚举语言定义：设S ⊆ Σ为一个语言，E是一个枚举器，若L（E） = S，则称E 枚举了语言S。若存在这样 的E，S就称为递归可枚举语言。 注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E） 中的某个串可能会被E多次重复地打印。 图灵可识…
判定器
在可计算性理论中，总是停机的机器也叫做判定器（，1996年）或全图灵机（，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。 全图灵机可计算的函数 在实践中，很多有价值的函数都是用总是停机的机器可计算的。通过限制它的流控…
多带图灵机
多带图灵机和图灵机类似，唯一的不同在于它可以有 k > 1 条纸带，每条纸带上 都有一个读写头。其状态转移函数 \delta 修改为： \delta : Q\times\Gamma^k \to Q \times \Gamma^k \times \{L, R\}^k 此处 k 是带子的数目。表达式 \delta(q, x_1, x_2, \ldots, x_k) = (q', x'_1, x'_2, \ldots, x'_k, m_1, …