Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?

  • 2
    $\begingroup$ What does "make a non-determinstic computer" mean? There are several equivalent formulations of non-deterministic machines. Also note that non-deterministic machines can be simulated easily, and that there are programming languages that allow you to write programs in non-deterministic style. $\endgroup$ – Andrej Bauer Jan 31 '20 at 8:15
  • 1
    $\begingroup$ A computer which can choose the next step arbitrarily. If such computers exist, then it would be a counterexample to strong Churh-Turing thesis. $\endgroup$ – TCS Guy Jan 31 '20 at 8:19
  • $\begingroup$ So you are not talking about non-determinstic Turing machines. Those choose between two options in such a way that in the future they will succeed, if possible. What is strong Church-Turing thesis? $\endgroup$ – Andrej Bauer Jan 31 '20 at 8:28
  • $\begingroup$ There is a typo $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Jan 31 '20 at 19:22
  • 2
    $\begingroup$ John, my guess is that you got a downvote from someone because "nondeterministic" is ambiguous, "arbitrarily" in your comment is even more ambiguous, and the question doesn't spell out the sense in which you intend "hard to make". It would be good to specify your reasoning about why the result would be a counterexample to Church-Turing, and since there are slightly different formulations of the Church-Turing thesis, and certainly different extended Church-Turing theses, it will be important to state exactly what thesis the counterexample is a counterexample to. $\endgroup$ – Mars Feb 1 '20 at 18:59

Is it possible to make a machine that when it encounters a non-deterministic step it takes an arbitrary one? Yes easily.

Will this machine be able to solve NP problems in P? No because it will most likely pick the wrong path through the execution.

Similarly for outputting a number there is no way to force the machine to match the required path needed to output said number.


Do you mean "indeterministic" in the sense of quantum mechanics? It's easy to build that kind of indeterminism into a computer, by incorporating a routine that goes and checks the state of a quantum mechanical physical source. That doesn't necessarily violate the Church-Turing thesis, since the source of quantum mechanical randomness might not be the result of an algorithmically realizable process. In that case, if it turned out that what the quantum mechanical source produced was uncomputable, this wouldn't violate a Church-Turing thesis that says that any algorithmic process can be computed by a Turing machine.

There are discussions of a variety of versions of and extensions of the original Church-Turing thesis, and discussions about whether natural processes or specially constructed experiments are ever counterexamples to these versions. Jack Copeland has useful papers on this. Not everyone agrees with him about everything--I don't think I do--but I think that papers such as his "The Church-Turing Thesis: Logical Limit or Breachable Barrier" provide good entry-points into this literature.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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