<blockquote>
  <p>If this is the case, then why bother turning any Turing machine deterministic?</p>
</blockquote>

<p>Informally speaking, it is expected that deterministic Turing machines correspond to classical computers, while nondeterministic Turing machines cannot be built.</p>

CC BY-SA 3.0
2017-09-19T07:32:56.483Z
I'd strike the last remark - machines tend to be nondeterministic in practice.
reinierpost
CC BY-SA 3.0
2017-09-18T16:56:41.520Z
2017-09-18T18:39:16.857Z
2017-09-18T18:39:16.857Z
Arnaud Casteigts
<p>I might have received an answer from a colleague, stating that nondeterministic machines are called nondeterministic because they don't always return the same output from a given input. So my question can be answered simply by saying : </p>

<p>deterministic automata are to make certain a same output is returned every time.</p>

CC BY-SA 3.0
2017-09-18T18:25:31.707Z
Please consult a standard complexity textbook like Sipser's or Papadimitriou's to clear up your confusion regarding (non) determinism and their relationships.
PsySp
CC BY-SA 3.0
2017-09-18T13:37:32.373Z
2017-09-18T13:37:32.373Z
J. Schmidt
<p>I have a question on a part from the wikipedia page on Savitch's theorem: <a href="https://en.wikipedia.org/wiki/Savitch%27s_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Savitch%27s_theorem</a></p>

<p>The part in question is the following:</p>

<blockquote>
  <p>[...], if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound. Although it seems that nondeterminism may produce exponential gains in time, [...] shows that it has a markedly more limited effect on space requirements.</p>
</blockquote>

<p>So, simply stated, it says deterministic Turing machines need more space AND more time to solve a problem (correct me if I'm wrong). If this is the case, then why bother turning any Turing machine deterministic? Thanks</p>

CC BY-SA 3.0
2017-09-18T13:41:08.387Z
This statement says that a non-deterministic Turing machine can do _no better than_ the square root of the space required for the deterministic machine. This does _not_ mean that the non-deterministic machine necessarily will do better.
user144527
CC BY-SA 3.0
2017-09-18T16:37:14.937Z
This is not a research level question, also, your answer is wrong.
rus9384
<turing-machines>
Why bother with deterministic Turing machines when nondeterministic Turing machines consume less space and time?
J. Schmidt
# Why bother with deterministic Turing machines when nondeterministic Turing machines consume less space and time?

(Asked by: username_0 on 2017-09-18)

I have a question on a part from the wikipedia page on Savitch's theorem: <https://en.wikipedia.org/wiki/Savitch%27s_theorem>

The part in question is the following:

> [...], if a nondeterministic Turing machine can solve a problem using f(n) space, an ordinary deterministic Turing machine can solve the same problem in the square of that space bound. Although it seems that nondeterminism may produce exponential gains in time, [...] shows that it has a markedly more limited effect on space requirements.

So, simply stated, it says deterministic Turing machines need more space AND more time to solve a problem (correct me if I'm wrong). If this is the case, then why bother turning any Turing machine deterministic? Thanks

**Tags:** turing-machines

> **Comments:**
> **username_1**: This statement says that a non-deterministic Turing machine can do _no better than_ the square root of the space required for the deterministic machine. This does _not_ mean that the non-deterministic machine necessarily will do better.  
> **username_2**: This is not a research level question, also, your answer is wrong.  

---

## 2 answers

### Answer by username_3 on 2017-09-18. Score: 2

> If this is the case, then why bother turning any Turing machine deterministic?

Informally speaking, it is expected that deterministic Turing machines correspond to classical computers, while nondeterministic Turing machines cannot be built.

> **Comments:**
> **username_4**: I'd strike the last remark - machines tend to be nondeterministic in practice.  

---

### Answer by username_0 on 2017-09-18. Score: -2

I might have received an answer from a colleague, stating that nondeterministic machines are called nondeterministic because they don't always return the same output from a given input. So my question can be answered simply by saying :

deterministic automata are to make certain a same output is returned every time.

> **Comments:**
> **username_5**: Please consult a standard complexity textbook like Sipser's or Papadimitriou's to clear up your confusion regarding (non) determinism and their relationships.  

---

