Talk:Nondeterministic Turing machine

Transition function is partial!?

The article says that the transition function $\delta$ is a partial function. The only reason I can see why that would be the case is because it's undefined over states $a\in A$, in which case that should be specified.

Also, it seems at first that $\delta$ should be a total relation, not a function, as Planetmath define it. I guess the defintion here must be handling the multiple possible actions by using ${\mathcal {P}}$ to denote a set of one or more elements.... but how is the reader supposed to know that? -- pde 02:45, 24 March 2006 (UTC)

Bounded nondeterminism

The article makes the following claim

A NTM has the property of bounded nondeterminism, i.e., if a NTM always halts on an empty tape then it halts in a bounded number of states.

Shouldn't this say:

Let T be a (fixed) input tape. If a NTM always halts when given that input T, then it halts in bounded number of steps when given that input T.

I believe this follows immediately from Konig's lemma.

I think there are two things wrong with the statement. (1) The input is irrelevant. (2) It should say steps not states. --CSTAR 05:58, 26 November 2005 (UTC)

Thanks for your help. I have corrected the article to incorporate your comments. See the discussion in Unbounded nondeterminism.--Carl Hewitt 06:05, 26 November 2005 (UTC)

It still says states. This is trivial, since Q (the set of states of the control device) is assumed to be finite (what other states could you be referring to?)--CSTAR 06:11, 26 November 2005 (UTC)

It is referring to the total state of the machine including the tape.--Carl Hewitt 06:30, 26 November 2005 (UTC)

The total state is usually called the configuration and is not, strictly speaking, a state of the machine. Rp (talk) 16:36, 5 July 2008 (UTC)

I have two issues with this paragraph:

A NTM has the property of bounded nondeterminism, i.e., if a NTM always halts on a given input tape T then it halts in a bounded number of states (where a state is the total state of the machine including its tapes). This is in contrast to some models of concurrent computation such as the Actor model that have the property of unbounded nondeterminism. (See Unbounded nondeterminism.)

One is, I'm not sure it's relevant - it's not at all necessary to look at a NTM as a model of concurrent computation, you can just think of it as a "maximally lucky guesser" that accepts if there is any path to an accepting state.

The other is that I don't think it's correct, assuming I've understood the claim. If "halts in a bounded number of states" means "accepts in a finite number of configurations", I can provide a counter-example of an NTM which has an infinite number of accepting configurations (basically, have the start state accept on a blank symbol as well as have a self-transition that writes X and moves right - then there are an infinite number of accepting configurations, one for each string in X*.) --Chris Pressey 04:42, 18 April 2006 (UTC)

I think you are right. See discussion immediately above for the source of the formulation in terms of "states".--CSTAR 04:49, 18 April 2006 (UTC)

I've changed the paragraph to use "configuration" for this meaning of "total state", which appears to match common terminology (and the rest of the page.) I still disagree with the correctness and relevancy of the statement, though. --Chris Pressey 18:02, 25 April 2006 (UTC)

Hello Chris, I think there is a problem with your counterexample. There is a path which never stops (write X, move right, write X, move right, etc.), so it violates the hypothesis of "if a NTM always halts". 141.227.1.1 16:12, 18 May 2006 (UTC)

It's easily seen that finite number of steps implies finite number of states because there is a finite number of configurations that can be gotten to in any finite number of steps. (For example, if there are n steps made, than at most n places on the tape are different from the input, and there is a finite library of symbols.) It's also easily seen that the theorem is true: regarding the possible computations of the machine as a tree (with the n-step computations on level n), then if the tree is infinitely deep, there must be an infinite path through the tree, since there are finitely many allowable moves from any configuration. (As mentioned above, this is a direct application of Konig's Lemma.) But in infinite path through the tree is precisely a non-terminating computation. Hence a NTM which halts with any possible computation halts in a bounded number of steps and in a bounded number of states. I don't have a reference for this, but it should at least quash the discussion over whether the statement is true. --Althai 01:10, 31 July 2006 (UTC)

Introduction

I'm deleting the sentence "More concisely, an NTM is to an ordinary (deterministic) TM as a non-deterministic finite automaton is to a deterministic finite automaton." from the introduction. As a reader with a limited understanding of the material, I don't find anything more concise about this analogy, and it sounds very intimidating. If it's truly an important point to make, then perhaps it should be reserved for a later section where the reader can be expected to have a better chance of understanding it. mcs (talk) 17:25, 27 July 2008 (UTC)

You have a point. Rp (talk) 21:45, 20 October 2008 (UTC)

Computational equivalence with DTMs

I have an issue with the following text in section DTM as a special case 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.

It seems from Theorem 2.3. in Computability and Complexity Theory (2nd Edition), from Steven Homer and Alan L. Selman that NTM and DTM are equally powerful. Could someone clarify? Thanks! --Mcasariego (talk) 17:42, 23 October 2017 (UTC)

Requested move 22 October 2019

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: moved (non-admin closure) Danski454 (talk) 19:21, 29 October 2019 (UTC)

---

Non-deterministic Turing machine → Nondeterministic Turing machine – Harmonizing with all other article titles that begin with the same first word. D.Lazard (talk) 17:40, 22 October 2019 (UTC)

• Support per WP:CONSISTENT._{ZXCVBNM (TALK)} 22:46, 22 October 2019 (UTC)

---

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.