-1
$\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

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

2 Answers 2

Reset to default
2
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'd strike the last remark - machines tend to be nondeterministic in practice. $\endgroup$
    – reinierpost
    Sep 19, 2017 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.

Improve this answer
$\endgroup$
1
  • $\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, 2017 at 18:25

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