-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$
  • 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.