-2
$\begingroup$

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

$\endgroup$

closed as off-topic by Marzio De Biasi, Aryeh, Emil Jeřábek supports Monica, Kaveh, András Salamon Sep 18 '17 at 20:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Marzio De Biasi, Aryeh, Emil Jeřábek supports Monica, Kaveh, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ 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. $\endgroup$ – user144527 Sep 18 '17 at 13:41
  • $\begingroup$ This is not a research level question, also, your answer is wrong. $\endgroup$ – rus9384 Sep 18 '17 at 16:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd strike the last remark - machines tend to be nondeterministic in practice. $\endgroup$ – reinierpost Sep 19 '17 at 7:32
-2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please consult a standard complexity textbook like Sipser's or Papadimitriou's to clear up your confusion regarding (non) determinism and their relationships. $\endgroup$ – PsySp Sep 18 '17 at 18:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.