Karl Jones: /* External links */

2016-04-26T02:14:59Z

‎External links

Karl Jones: Created page with "A '''non-deterministic Turing machine''' ('''NTM''') is a Turing machine in which different actions may apply for the same combination of state and symbol. Th..."

2016-03-02T19:13:04Z

Created page with "A '''non-deterministic Turing machine''' ('''NTM''') is a Turing machine in which different actions may apply for the same combination of state and symbol. Th..."

New page

A '''non-deterministic Turing machine''' ('''NTM''') is a [[Turing machine]] in which different [[actions]] may apply for the same combination of [[state]] and [[symbol]].

The original [[Turing machine]] is deterministic: it requires a single specific action for a given combination of state and symbol.

== Deterministic Turing machines ==

In [[theoretical computer science]], a [[Turing machine]] is a theoretical machine that is used in thought experiments to examine the abilities and limitations of [[computers]].

In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation.

In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees.

An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', change it to 'B' and move left."

A deterministic Turing machine (DTM) has a [[transition function]] that, for a given [[state]] and [[symbol]] under the [[tape]] head, specifies three things:

* The [[symbol]] to be written to the tape,
* The direction (left, right or neither) in which the head should move
* The subsequent [[state]] of the [[finite control]]

For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5.

== Non-deterministic Turing machines ==

A non-deterministic Turing machine (NTM) may have a set of rules that prescribes more than one action for a given situation.

The state and tape symbol no longer uniquely specify these things. Rather, many different actions may apply for the same combination of state and symbol.

Example 1:

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"
* "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set.

Example 2:

An X on the tape in state 3 might now allow the NTM to either:

* Write a Y, move right, and switch to state 5
* Write an X, move left, and stay in state 3

== See also ==

* [[Theoretical computer science]]
* [[Turing machine]]

== External links ==

* [https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Non-deterministic Turing machine] @ Wikipedia

← Older revision		Revision as of 02:14, 26 April 2016
Line 49:		Line 49:

	* [https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Non-deterministic Turing machine] @ Wikipedia		* [https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Non-deterministic Turing machine] @ Wikipedia
		+
		+
		+	[[Category:Computing]]
		+	[[Category:Turing machines]]

Non-deterministic Turing machine - Revision history

Karl Jones: /* External links */

Karl Jones: Created page with "A '''non-deterministic Turing machine''' ('''NTM''') is a Turing machine in which different actions may apply for the same combination of state and symbol. Th..."