图灵机-一流百科

递归可枚举语言

递归可枚举语言在数学、逻辑和计算机科学中，一种形式语言被称为递归可枚举的（也可识别的、部分可判定的、半可判定的、图灵可接受的或图灵可识别的）如果它...

词条百科

波斯特对应问题

波斯特应对问题波斯特对应问题是 Emil Post 于 1946 年提出的不可判定问题。因为它比停机问题和 Entscheidungs 问题更简单，所以经常用于不可判定性的证明。...

词条百科

超计算

超计算超计算或超图灵计算是指可以提供图灵不可计算的输出的计算模型。 Hava Siegelmann 在 1990 年代早期提出的超级图灵计算指的是这种神经学启发的、生物和...

词条百科

枚举器

枚举器枚举器是带有打印机的图灵机。图灵机可以使用该打印机作为输出设备来打印字符串。每次图灵机要向列表中添加一个字符串时，它都会将该字符串发送到打...

词条百科

可判定性

可判定性在数学和计算机科学中，可判定性（发音为 [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]，德语为“决策问题”）是 David Hilbert 和 Wilhelm Ackermann 在 1928 年提出的一...

词条百科

可计算数

可计算数在数学中，可计算的数字是可以通过有限的终止算法计算到任何所需精度的实数。它们也被称为递归数、有效数或可计算实数或递归实数。可以使用 μ 递归...

词条百科

可计算性

可计算性可计算性是有效解决问题的能力。它是数理逻辑中可计算性理论领域和计算机科学中计算理论领域的一个关键课题。问题的可计算性与解决问题的算法的存...

词条百科

忙碌的海狸

忙碌的海狸在理论计算机科学中，忙碌的海狸游戏旨在找到一个给定大小的终止程序，以产生尽可能多的输出。由于无限循环产生无限输出的程序很容易想到，因此此...

词条百科

计算理论

计算理论在理论计算机科学和数学中，计算理论是处理在计算模型上可以解决哪些问题、使用算法、解决这些问题的效率或程度（例如，近似解决方案与精确解决方案...

词条百科

图灵完备性

图灵完备性在可计算性理论中，如果一个数据操作规则系统（例如计算机的指令集、编程语言或元胞自动机）可以用来模拟任何图灵，则它被认为是图灵完备的或计算...

词条百科

量子计算和通信的时间线

简介这是一个量子计算的时间线。1968年StephenWiesner发明了共轭编码。1970年JamesPark阐述了无克隆定理。1973年AlexanderHolevo发表论文，表明n个量子比特可...

词条百科

非限制性语法

非限制性语法在自动机理论中，非限制性语法类（也称为半休、0型或短语结构语法）是乔姆斯基层次中最一般的语法类。对非限制性语法的生成没有任何限制，只是它...

词条百科

递归可列举语言

递归可列举语言在数学、逻辑学和计算机科学中，如果一种形式语言是该语言字母表上所有可能的词语集合中的一个可递归可列举的子集，也就是说，如果存在一台图...

词条百科

递归语言

什么是递归语言在数学、逻辑学和计算机科学中，如果一种形式语言（取自固定字母表的符号有限序列的集合）是该语言字母表上所有可能的有限序列集合的递归子集...

词条百科

图灵机

什么是图灵机图灵机是一个计算的数学模型，描述了一个抽象的机器，它根据一个规则表来操作磁带上的符号。尽管这个模型很简单，但它能够实现任何计算机算法。...

词条百科

量子复杂性理论

量子复杂性理论量子复杂性理论是计算复杂性理论的一个子领域，涉及使用量子计算机定义的复杂性类别，这是一种基于量子力学的计算模型。它研究计算问题的硬度...

词条百科

描述数

什么是描述数描述数是图灵机理论中出现的数字。它们与哥德尔数非常相似，在文献中也偶尔被称为哥德尔数。给定一些通用的图灵机，每台图灵机都可以在该机器上...

词条百科

复杂性类

复杂性类在计算复杂性理论中，复杂性类是一组基于资源的相关复杂性的计算问题。两种最常分析的资源是时间和内存。一般来说，一个复杂度类是以一种计算问题的...

词条百科

量子计算机

量子计算机量子计算机是量子具体叠加使用并行正在实现性能的计算机。关于使用“量子门”代替计算机的常规逻辑门来执行量子计算的原理的研究正在进行中，但是也...

词条百科