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

### 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.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 ?

### 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