交替式图灵机（英語：Alternating Turing Machine, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和Stockmeyer（英语：Larry Stockmeyer）于1976年提出。...

左移动一次再向右移动一次来代替在原地不动。 其它的常见图灵机变种包括： 多带图灵机 非确定型图灵机 交替式图灵机 枚举器 图灵可识别语言 图灵可判定语言 递归可枚举语言 可计算函数 递归函数 停机问题 可判定性 不可判定性 不可解度 除了图灵机以外，人们还发明了很多其它的计算模型。包括： 寄存器机...

ATM可以指（按汉语拼音及英文字母顺序排序排序）： 標準大氣壓的單位符號 (英語：standard ATMosphere) 反戰車飛彈 （英語:Anti-Tank Missile） 交替式图灵机 （英語：Alternating Turing Machine） 米兰交通集团（意大利语：Azienda Trasporti Milanesi）...

了解在PSPACE中但可能不在NP中的问题。 利用交替式图灵机（ATM）的概念，PSPACE可被定义为一台ATM在多项式时间中解决的问题集合。这一复杂度类也被称为APTIME或者简称为AP。 复杂度理论中一个重要的结果为PSPACE与某个特定的交互式证明系统接受的所有语言等价，这个语言的集合也被定义...

\subseteq } ELEMENTARY. 2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用交替式圖靈機可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE ⊆ {\displaystyle \subseteq } 2-EXPTIME的方式。...

(计算机)（alphabet） 字母跨越搜索算法（Alpha Skip Search algorithm） 交替通路（alternating path） 交替式图灵机（alternating Turing machine） 交替 (计算机)（alternation） 美国国旗排序（American flag sort）...

圖靈機解決的問題。更精確的說，EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言，在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義，等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE...

PH最早是由Larry Stockmeyer定義，是一個受限交替式圖靈機(bounded alternating Turing machine)其譜系(hierarchy)的特例。這個複雜度包含於PPP(包含問題可以由多項式時間圖靈機，並且能取用PP 神諭的機器所解決的複雜度類。), P#P (根據Toda's...

{P}}} 。这个定义反映出多项式谱系和算数阶层之间的紧密关系。其中R和RE分别扮演了类似P和NP的角色。算数阶层同样是用一系列的实数子集来定义的。 用交替式图灵机的等价定义。定义 Σ k P {\displaystyle \Sigma _{k}^{\mathsf {P}}} （或 Π k P {\displaystyle...

n)=nO(1)的時間，因為這是所有可能組合方式的總數，因此L是P的子集合。另一個重要問題是：L是否相等於P？我們已知P=AL（問題可在對數記憶體上以交替式图灵机解決的問題之集合），而P也已知不大於PSPACE（可在多項式空間判定的問題）。再一次，我們面對P是否等於PSPACE的未知問題。整理一下上述問題：...

使用多少記憶體空間（參見計算資源），但是有可能會限制一些其他的計算資源（像是可否使用交替圖靈機）。 許多重要的複雜度類都使用DTIME來定義，這些類別包含需要花費特定時間才能解決的問題，來作為分類。任何適當複雜度函式（proper complexity function）都可以用來定義複雜度類，但是...

等。注意力机制的灵活性来自于它的“软权重”特性，即这种权重是可以在运行时改变的，而非像通常的权重一样必须在运行时保持固定。注意力机制的用途包括神经图灵机中的记忆功能、可微分神经计算机（英语：Differentiable neural computer）中的推理任务、Transformer模型中的语...

AC0 一個有限制深度的線路複雜度類。 AC 一種線路複雜度類 AH 算術階層（arithmetic hierarchy）的複雜度類 AP 使用交替式圖靈機在多項式時間之內可以解決的問題 AM 以亞瑟梅林協定在多項式時間內可以解決的問題 BPL 隨機演算法在多項式時間與對數空間內可以解答的問題集合（解答或許不正確）...

\Sigma ^{++}} 之上，这个性质不再成立，因为瓦片系统识别的语言不闭合于补集之下。因为全称量词等价于否定的存在量词，它不能被表达，全称和存在量词的交替生成了在 Σ + + {\displaystyle \Sigma ^{++}} 上的更大的一类语言。 二阶逻辑的各种形式的表达力密切的连系于计算复杂性理论。特别是：...

” 这个问题的最终回答由哥德尔不完备定理，图灵机和Alonzo Church的λ演算给出。他们的答案令人震惊：首先，他们证明了数理逻辑的局限性；其次（这一点对AI更重要），他们的工作隐含了任何形式的数学推理都能在这些限制之下机械化的可能性。 邱奇-图灵论题暗示，一台仅能处理0和1这样简单二元符号...