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.NoteI 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.
Quantum computers and Turing Machine
computer science;turing completeness
1) As you pointed out a lot of the theory about what can be computed is based on it. For that to work out it is essential to know how it operates internally. A Turing machine is not a black box. A favorable property of Turing machines is their locality of change. Every step changes just very little, that is, the internal state (think of it as number), the letter on the tape and the position on the tape. The latter can only be changed by 1 step to the left or to the right. In this model all input is in form of what is written on the tape. The tape content is only changed by the machine. So - no interaction.2) A machine or programming language is called Turing complete, if it can simulate all Turing machines. Thus, non-deterministic Turing machines are Turing complete, because they can simulate a Turing machine by simply not using non-determinism. Interestingly enough, a deterministic Turing can simulate a non-deterministic one, simply by trying all possible outcomes of non-deterministic results sequentially. This is a brute force approach and not very efficient. It is unclear if there is an efficient way to do it. BTW, most computer scientist do not think that it can be done.As for your own answer to this - Turing machines are supposed to halt. In this context it means that the computation is finished and has a result. You might think it means that the machine gets frozen. But it is the other way round. A frozen machine (e.g. your desktop computer) did not halt, when it was supposed to and know you are waiting forever and cannot do anything (but reboot). Non-determinism has no effect on a machine halting or not.3) The only known way to simulate a quantum computing device uses non-determinism. As said under 2), we can simulate non-determinism, but not efficiently. And we probably never will.