Comments about "Non-deterministic Turing machine" in Wikipedia

This document contains comments about the document Non-deterministic Turing machine in Wikipedia
In the last paragraph I explain my own opinion.




The article starts with the following sentence.
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.
IMO a Turing is: a detailed description of a theoretical machine to discuss and to examine the abilities and limitations of computers.

1. Background

1.3 Resolution of multiple rules

How does the NTM "know" which of these actions it should take?
The term "know" is wrong.
May be: How does the NTM decides which action to perform.
Ofcourse this raises two problems:
There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks the transition that eventually leads to an accepting state, if there is such a transition.
Both transitions should lead to an accepting state.
The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions
The concept of copies is not very scientific.

3. Computational equivalence with DTMs

In particular, nondeterministic Turing machines are equivalent with deterministic Turing machines. This equivalency refers to what can be computed, as opposed to how quickly.
Does this equivalence mean that you can use both to solve the same problem and that the answer is the same ?
If that is true than the difference is in speed ?
Why not use simpler language ?

3.1 DTM as a special case of NTM

3.2 DTM simulation of NTM

3.2.1 Multiplicity of configuration states

3.2.2 Multiplicity of tapes

4 Computational inequivalent efficiency

5 Bounded non-determinism

Comparison with quantum computers

7. See also

Following is a list with "Comments in Wikipedia" about related subjects

Reflection 1

Reflection 2

Reflection 3


Read: Nature News: Million-dollar problem cracked? At the end there is a comment by the author.

If you want to give a comment you can use the following form Comment form
Created: 10 December 2014
Modified: 25 September 2018

Back to my home page Index