Comments about "Non-deterministic Turing machine" in Wikipedia
This document contains comments about the document Non-deterministic Turing machine in Wikipedia
- The text in italics is copied from that url
- Immediate followed by some comments
In the last paragraph I explain my own opinion.
Contents
Reflection
Introduction
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:
- When you execute the program again the answer can be different.
- This type of rules only makes sense when chance is involved. For a DTM this means when a random number generator is involved.
-
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
Feedback
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