Question

Describe a non-deterministic Turing machine algorithm that takes one integer and checks for primality. What is the complexity of the algorithm?

Answer 1

Answer:-

in theoretical computer science, a non-deterministic Turing machine is a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. One of the most important open problems in theoretical computer science is the P vs. NP problem, which concerns the question of how difficult it is to simulate non-deterministic computation with a deterministic computer.

By contrast, in a non-deterministic Turing machine (NTM), the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to:

• Write a Y, move right, and switch to state 5

or

• Write an X, move left, and stay in state 3.

Resolution of multiple rules

How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If at least one branch of the tree halts with an "accept" condition, we say that the NTM accepts the input.

Definition

A non-deterministic Turing machine can be formally defined as a 6-tuple {\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}, where

• {\displaystyle Q} is a finite set of states
• {\displaystyle \Sigma } is a finite set of symbols (the tape alphabet)
• {\displaystyle \iota \in Q} is the initial state
• {\displaystyle \sqcup \in \Sigma } is the blank symbol
• {\displaystyle A\subseteq Q} is the set of accepting (final) states
• {\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)} is a relation on states and symbols called the transition relation. {\displaystyle L} is the movement to the left, {\displaystyle S} is no movement, and {\displaystyle R} is the movement to the right.

The difference with a standard (deterministic) Turing machine is that for those, the transition relation is a function (the transition function).

Configurations and the yields relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the yields relation is no longer single-valued. The notion of string acceptance is unchanged: a non-deterministic Turing machine accepts a string if, when the machine is started on the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise, at least one of the machine's possible computations from that configuration puts the machine into a state in {\displaystyle A}. (If the machine is deterministic, the possible computations are the prefixes of a single, possibly infinite, path.)

Computational equivalence with DTMs

Any computational problem that can be solved by a DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the time complexity may not be the same.

DTM as a special case of NTM

NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM.

DTM simulation of NTM

It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting a string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way.

Multiplicity of configuration states

One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever the transition relation defines multiple continuations.

Multiplicity of tapes

Another construction simulates NTMs with 3-tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree.^[1] The 3-tape DTMs are easily simulated with a normal single-tape DTM.

complexity of the algorithm:-

Algorithm complexity is a measure which evaluates the order of the count of operations, performed by a given or algorithm as a function of the size of the input data. To put this simpler, complexity is a rough approximation of the number of steps necessary to execute an algorithm.