As far as I know, a Turing Machine is the widely used model in computational theory to know whether something could be computed and if computed can they can be computed in finite time (P, NP, NPSpace). But I have the following doubts:
- Is a Turing Machine essentially a black-box model where a set of inputs give a set of outputs such that there could be no interaction during computation? By no interaction, I mean that during computation the variables wouldn't be altered by an external factor.
- As an extension to the above question, are non-deterministic functions Turing complete?
- Is Turing Machine an efficient model for Quantum Computing?
Going by what I have learned so far, my answers are:
- Turing Machines cannot handle interaction and random behavior and it's not guaranteed even by Turing in his original paper.
- Non-deterministic functions may bring Turing machines to a halt.
- No since Turing machines cannot efficiently support the superposition of bits.
I am not well-versed in either Computational Theory or Quantum Computing. So a lot of links and some beginner's stuff would be a lot helpful and reading this article inspired this question.