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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Màquina de Turing no determinista (ca)
- Nichtdeterministische Turingmaschine (de)
- Nedeterminisma maŝino de Turing (eo)
- Machine de Turing non déterministe (fr)
- 비결정론적 튜링 기계 (ko)
- 非決定性チューリングマシン (ja)
- Nondeterministic Turing machine (en)
- Niedeterministyczna maszyna Turinga (pl)
- Máquina de Turing não determinística (pt)
- Недетерминированная машина Тьюринга (ru)
- Недетермінована машина Тюрінга (uk)
- 非确定型图灵机 (zh)
|
| 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. (ca)
- Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet. (de)
- 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é. (fr)
- 非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。 (ja)
- 비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 와 유사한 개념이다. 이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다. (ko)
- 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. (pt)
- Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА). (ru)
- В теоретичній інформатиці недетермінована машина Тюрінга — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат. (uk)
- En teorio de komputado, nedeterminisma maŝino de Turing estas maŝino simila al maŝino de Turing, sed por kiu, en iuj okazoj, povas esti difinita pli ol unu varianto de la konduto. La elekto de konduto en ĉi tia nedeterminisma okazo estas nomata kiel preno de konsilo de orakolo. Kiel nedeterminisma maŝino de Turing elektas kiu el la eblaj variantoj donas akcepton de la enigo: Nedeterminisma maŝino de Turing povas esti modelata per determinisma maŝino de Turing per kreo kaj laŭvica prilaboro de kopioj de la modelata maŝino. Ĉi tiu modelado povas bezoni eksponente pli grandan rultempon. (eo)
- 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. (en)
- 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. (pl)
- 如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 其中是状态集合，是带字母表，分别表示读写头向左和向右移动；符号 表示集合的幂集，即 例如，设非确定型图灵机的当前状态为，当前读写头所读的符号为，若 则将任意地选择一个，按其进行操作，然后进入下一步计算。 非确定型图灵机在输入串上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称接受；只要有任意一个分支进入拒绝状态，则称拒绝；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说在输入上可停机。注意，我们规定必须是无矛盾的，即它不能有某个分支接受而同时另一个分支拒绝，这样有矛盾的非确定型图灵机是不合法的。 定理：对于任意一个非确定型图灵机，存在一个确定型图灵机，使得它们的语言相等，即。 证明：因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历的计算树，但这样行不通，因为的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为的技巧来遍历的计算树。具体证明如下： (zh)
|
| foaf:depiction
| |
| dcterms: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
| |
| thumbnail
| |
| 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. (ca)
- En teorio de komputado, nedeterminisma maŝino de Turing estas maŝino simila al maŝino de Turing, sed por kiu, en iuj okazoj, povas esti difinita pli ol unu varianto de la konduto. La elekto de konduto en ĉi tia nedeterminisma okazo estas nomata kiel preno de konsilo de orakolo. Malsimile al determinisma maŝino de Turing kiu havas nur unu vojon de kalkulado, nedeterminisma maŝino de Turing havas arbon de la vojoj. Nedeterminisma maŝino de Turing akceptas la enigon se iu el branĉoj de la arbo haltiĝas je la akcepta stato aŭ alivorte redonas jesan respondon. Tiel, la nea kaj jesa respondo ne estas simetriaj por ĉi tia maŝino. Eblas diri, ke ĝia respondo estas logika aŭo de respondoj de ĉiuj branĉoj, kaj eĉ unu "jes" sufiĉas por ke estu entuta "jes". Kiel nedeterminisma maŝino de Turing elektas kiu el la eblaj variantoj donas akcepton de la enigo:
* Eblas konsideri, ke ĝi estas ĉiam bonŝanca, do ĝi ĉiam elektas tiun varianton kiu rezultiĝas je akcepto de la enigo, se ĉi tia varianto ekzistas (konsilas kun bona orakolo).
* Eblas konsideri, ke en ĉiu okazo kiam estas pli ol unu varianto ĝi faras kopiojn de si, kaj la malsamaj kopioj laboras plu laŭ ĉiu el la eblaj variantoj. Poste ĉiu el la kopioj denove povas disdividiĝi, kaj la kvanto de funkciantaj kopioj povas kreski eksponente kun tempo. Nedeterminisma maŝino de Turing povas esti modelata per determinisma maŝino de Turing per kreo kaj laŭvica prilaboro de kopioj de la modelata maŝino. Ĉi tiu modelado povas bezoni eksponente pli grandan rultempon. (eo)
- Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet. (de)
- 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é. (fr)
- 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. (en)
- 非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。 (ja)
- 비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 와 유사한 개념이다. 이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다. (ko)
- 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. (pt)
- 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). (pl)
- Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат (НКА). (ru)
- В теоретичній інформатиці недетермінована машина Тюрінга — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат. (uk)
- 如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 其中是状态集合，是带字母表，分别表示读写头向左和向右移动；符号 表示集合的幂集，即 例如，设非确定型图灵机的当前状态为，当前读写头所读的符号为，若 则将任意地选择一个，按其进行操作，然后进入下一步计算。 非确定型图灵机在输入串上的计算过程可以表示为一棵树，不同的分支对应着每一步计算的不同的可能性。只要有任意一个分支进入接受状态，则称接受；只要有任意一个分支进入拒绝状态，则称拒绝；某些分支可能永远无法停机，但只要有一个分支可以进入接受或拒绝状态，我们就说在输入上可停机。注意，我们规定必须是无矛盾的，即它不能有某个分支接受而同时另一个分支拒绝，这样有矛盾的非确定型图灵机是不合法的。 定理：对于任意一个非确定型图灵机，存在一个确定型图灵机，使得它们的语言相等，即。 证明：因为非确定型图灵机的计算过程就是一棵树，因此我们只需遍历该树就可以模拟其计算过程。一个简单的想法是利用深度优先搜索来遍历的计算树，但这样行不通，因为的某些计算分支可能永远不停机！所以我们可以采用一种在算法设计中称为的技巧来遍历的计算树。具体证明如下： 对于非确定型图灵机，构造一个确定型图灵机如下： 1.
* 令； 2.
* 深度优先地模拟的每个分支的计算，但每个分支最多只计算步，如果某个计算分支在步内可以停机，则也停机，并将该计算分支的计算结果输出。 3.
* 令增加 1，跳转到上一步继续执行。 显然，若有某个分支可以停机，则此也一定会找到该分支并停机。因此。 定理2：如果语言L被非确定型图灵机在多项式时间内接受，则一定存在多项式P使得语言L被时间复杂度为的确定型图灵机程序所接受。 定理2说明了为什么在证明P = NP之前，所有的NPC问题都只有指数时间复杂度算法。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
