In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left. " and "If you are in state 2 and you see an 'A', change it to a 'C' and move right.

PropertyValue
dbpprop:abstract
  • In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left. " and "If you are in state 2 and you see an 'A', change it to a 'C' and move right. " in its rule set.
  • Eine nichtdeterministische Turingmaschine (NTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
  • En teoria de la computació, una Màquina de Turing no determinista (MTN) és una Màquina de Turing on el seu mecanisme de control treballa com un autòmat finit no determinista.
  • 非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
  • Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.
  • В теоретической информатике недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
  • Belirlenimsiz Turing makinesi, bulunduğu durumdan sonraki durum için birden fazla seçenek Turing makinasıdır. Makina aşağıdaki bileşenlerden oluşur: Bir veya birkaç şerit Şerit(ler)i okumak için kafa(lar) Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık Belirlenimli Turing makinasından farklı olarak, belirlenimsiz Turing makinesi aynı durum için birkaç adım arasından seçim yapabilir. Başka bir deyişle, geçiş tablosunda aşağıdaki gibi girdiler olabilir: Güncel Okunan İşlem Yeni Durum Sembol Durum d0 1 Sağa git d2 d0 1 Sola git d1 Bu durumda, ilgili Turing makinesi d0 durumundayken ve 1 sembolünü görürken ister sağa ister sola gidebilir. İki çeşit belirlenimsizlik vardır: Melek-vari belirlenimsizlik: bu tip bir belirlenimsizlikte, makine birkaç seçim arasından her zaman "doğru" olanı seçer. Şeytani belirlenimsizlik: bu tip belirlenimsizlikte ise makine birkaç seçim arasından her zaman "yanlış" olanı seçer. Belirlenimsiz Turing makinesi, melek-vari bir belirlenimsizlik kullanır ve dolayısıyla her zaman kendini sonuca yaklaştıran seçimi yapacaktır. Melek-vari belirlenimsiz bir Turing makinasıyla polinomsal zamanda çözülebilen problemler NP kümesini oluşturur. Belirlenimsiz makina, belirlenimli bir Turing makinası ile simüle edilebileceği için belirlenimsiz makinanın çözebildiği problemler kümesi, belirlenimli makinanın çözebildiği problemler kümesine eşittir.
  • 如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机 的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为 止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^{Q \times \Gamma \times \{L, R\}} 其中<math>Q是状态集合，<math>\Gamma是带字母表，<math>L, R分别表示读写头向左和向右移动；符号<math>2^{A} 表示集合<math>A的幂集，即 2^A = \{ S~|~S \subseteq A \} 例如，设非确定型图灵机<math>M的当前状态为<math>q，当前读写头所读的符号为<math>x，若 \delta(q,x) = \{ (q_1, x_1, d_1), (q_2, x_2, d_2), \ldots, (q_k, x_k, d_k)\} 则<math>M将任意地选择一个<math>(q_i, x_i, d_i)，按其进行操作，然后进入下一步计算。 非确定型图灵机<math>M在输入串<math>\omega上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称<math>M接受<math>\omega；只要有任意一个分支进入拒绝状态，则称<math>M拒绝<math>\omega；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说<math>M在输入<math>\omega上可停机。注意，我们规定<math>M必须是无矛盾的，即它不能有某个分支接受<math>\omega而同时另一个分支拒绝<math>\omega，这样有矛盾的非确定型图灵机是不合法的。 定理：对于任意一个非确定型图灵机<math>M，存在一个确定型图灵机<math>M'，使得它们的语言相等，即<math>L(M) = L(M')。 证明：因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历<math>M的计算树，但这样行不通，因为<math>M的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为迭代加深搜索的技巧来遍历<math>M的计算树。具体证明如下： 对于非确定型图灵机<math>M，构造一个确定型图灵机<math>M'如下： 令<math>k= 1； 深度优先地模拟<math>M的每个分支的计算，但每个分支最多只计算<math>k步，如果某个计算分支在<math>k步内可以停机，则<math>M'也停机，并将该计算分支的计算结果输出。 令<math>k增加 1，跳转到上一步继续执行。 显然，若<math>M有某个分支可以停机，则此<math>M'也一定会找到该分支并停机。因此<math>L(M) = L(M')。 定理2：如果语言L被非确定型图灵机<math>M在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为<math>O(2^{P})的确定型图灵机程序所接受。 定理2说明了为什么在证明P = NP之前，所有的NP问题都只有指数时间复杂度算法。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left. " and "If you are in state 2 and you see an 'A', change it to a 'C' and move right.
  • Eine nichtdeterministische Turingmaschine (NTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
  • En teoria de la computació, una Màquina de Turing no determinista (MTN) és una Màquina de Turing on el seu mecanisme de control treballa com un autòmat finit no determinista.
  • 非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
  • Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.
  • В теоретической информатике недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
  • Belirlenimsiz Turing makinesi, bulunduğu durumdan sonraki durum için birden fazla seçenek Turing makinasıdır. Makina aşağıdaki bileşenlerden oluşur: Bir veya birkaç şerit Şerit(ler)i okumak için kafa(lar) Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık Belirlenimli Turing makinasından farklı olarak, belirlenimsiz Turing makinesi aynı durum için birkaç adım arasından seçim yapabilir.
rdfs:label
  • Non-deterministic Turing machine
  • Nichtdeterministische Turingmaschine
  • Màquina de Turing no determinista
  • Machine de Turing non déterministe
  • 非決定性チューリングマシン
  • Máquina de Turing não-determinística
  • Недетерминированная машина Тьюринга
  • Belirlenimsiz Turing makinesi
  • 非确定型图灵机
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of