About: Nondeterministic Turing machine     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)

In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine.

AttributesValues
rdfs:label
  • Màquina de Turing no determinista
  • Nichtdeterministische Turingmaschine
  • Nondeterministic Turing machine
  • Nedeterminisma maŝino de Turing
  • Machine de Turing non déterministe
  • 非決定性チューリングマシン
  • 비결정론적 튜링 기계
  • Niedeterministyczna maszyna Turinga
  • Máquina de Turing não determinística
  • Недетерминированная машина Тьюринга
  • Недетермінована машина Тюрінга
  • 非确定型图灵机
rdfs:comment
  • 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.
  • Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
  • Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
  • 非決定性チューリング機械(ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM)は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
  • 비결정론적 튜링 기계(nondeterministic 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.
  • Недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
  • В теоретичній інформатиці недетермінована машина Тюрінга — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат.
  • In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine.
  • Niedeterministyczna maszyna Turinga – teoretyczny model rozważany w teorii obliczeń w celu badania problemów decyzyjnych. Niedeterministyczna maszyna Turinga jest zdefiniowana tak samo jak deterministyczna maszyna Turinga z jedyną różnicą dotyczącą postaci funkcji przejścia, która w przypadku maszyn niedeterministycznych zwraca zbiór możliwych działań maszyny.
  • 如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。具体而言,其状态转移函数为 其中是状态集合,是带字母表,分别表示读写头向左和向右移动;符号 表示集合的幂集,即 例如,设非确定型图灵机的当前状态为,当前读写头所读的符号为,若 则将任意地选择一个,按其进行操作,然后进入下一步计算。 非确定型图灵机在输入串上的计算过程可以表示为一棵树,不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态,则称接受;只要有任意一个分支进入拒绝状态,则称拒绝;某些分支可能永远无法停机,但只要有一个分支可以进入接受或拒绝状态,我们就说在输入上可停机。注意,我们规定必须是无矛盾的,即它不能有某个分支接受而同时另一个分支拒绝,这样有矛盾的非确定型图灵机是不合法的。 定理:对于任意一个非确定型图灵机,存在一个确定型图灵机,使得它们的语言相等,即。 证明:因为非确定型图灵机的计算过程就是一棵树,因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历的计算树,但这样行不通,因为的某些计算分支可能永远不停机!所以我们可以采用一种在算法设计中称为的技巧来遍历的计算树。具体证明如下:
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • 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.
  • Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet.
  • Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
  • 非決定性チューリング機械(ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM)は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
  • In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine. NTMs are sometimes used in thought experiments to examine the abilities and limits of computers. One of the most important open problems in theoretical computer science is the P versus NP problem, which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer.
  • 비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 와 유사한 개념이다. 이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다.
  • Niedeterministyczna maszyna Turinga – teoretyczny model rozważany w teorii obliczeń w celu badania problemów decyzyjnych. Niedeterministyczna maszyna Turinga jest zdefiniowana tak samo jak deterministyczna maszyna Turinga z jedyną różnicą dotyczącą postaci funkcji przejścia, która w przypadku maszyn niedeterministycznych zwraca zbiór możliwych działań maszyny. Ewolucje niedeterministycznej maszyny Turinga można reprezentować w postaci drzewa w którym każdy poziom odpowiada jednemu krokowi maszyny, natomiast rozgałęzienia wynikają z niedeterminizmu funkcji przejścia. Taka maszyna kończy prace w momencie, gdy dochodzi do poziomu ze stanem końcowym w co najmniej jednym z węzłów. W tym modelu kolejny krok maszyny liczony jest jako przejście do następnego zbioru możliwych stanów (poziomu drzewa). Dany problem może zostać rozwiązany w czasie wielomianowym na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy poprawność rozwiązania tego problemu jest weryfikowalna w czasie wielomianowym na deterministycznej maszynie Turinga. Tego rodzaju problemy należą do klasy NP (nondeterministic polynomial time).
  • 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.
  • Недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
  • В теоретичній інформатиці недетермінована машина Тюрінга — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат.
  • 如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。具体而言,其状态转移函数为 其中是状态集合,是带字母表,分别表示读写头向左和向右移动;符号 表示集合的幂集,即 例如,设非确定型图灵机的当前状态为,当前读写头所读的符号为,若 则将任意地选择一个,按其进行操作,然后进入下一步计算。 非确定型图灵机在输入串上的计算过程可以表示为一棵树,不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态,则称接受;只要有任意一个分支进入拒绝状态,则称拒绝;某些分支可能永远无法停机,但只要有一个分支可以进入接受或拒绝状态,我们就说在输入上可停机。注意,我们规定必须是无矛盾的,即它不能有某个分支接受而同时另一个分支拒绝,这样有矛盾的非确定型图灵机是不合法的。 定理:对于任意一个非确定型图灵机,存在一个确定型图灵机,使得它们的语言相等,即。 证明:因为非确定型图灵机的计算过程就是一棵树,因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历的计算树,但这样行不通,因为的某些计算分支可能永远不停机!所以我们可以采用一种在算法设计中称为的技巧来遍历的计算树。具体证明如下: 对于非确定型图灵机,构造一个确定型图灵机如下: 1. * 令; 2. * 深度优先地模拟的每个分支的计算,但每个分支最多只计算步,如果某个计算分支在步内可以停机,则也停机,并将该计算分支的计算结果输出。 3. * 令增加 1,跳转到上一步继续执行。 显然,若有某个分支可以停机,则此也一定会找到该分支并停机。因此。 定理2:如果语言L被非确定型图灵机在多项式时间内接受,则一定存在多项式P使得语言L被时间复杂度为的确定型图灵机程序所接受。 定理2说明了为什么在证明P = NP之前,所有的NPC问题都只有指数时间复杂度算法。
prov:wasDerivedFrom
page length (characters) of wiki page
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git81 as of Jul 16 2021


Alternative Linked Data Documents: PivotViewer | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3322 as of Sep 15 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software