This question already has an answer here:

"Can QTM (Quantum Turing machine) solve halting problem" Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the same proof which turing use it" Let H be a program in a quantum turing machine that will solve the issue of halting , why not say that a contradiction will occur Thanks


marked as duplicate by David Richerby, Evil, Yuval Filmus turing-machines Aug 23 '18 at 14:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Because we can simulate QTM with DTM and it is an easier proof method than proving directly for QTM (which we can do). Also, this method of simulating a model with DTM to prove they are equivalent in power is somewhat a standard tool, not just for various TMs, but also for other computaitonal models ($\lambda$-calculus, RAM-machines,$\ldots$)

I think this question and answers address everything else you may be wondering

  • $\begingroup$ I understand from your answer, it can not and DTM equivalent QTM, Right?? Thanks sir @sandro $\endgroup$ – small Aug 25 '18 at 0:45
  • 1
    $\begingroup$ Yes, QTM cannot solve Halting problem and QTM is computationaly equivalent to DTM, i.e. both can compute the same class of functions - partial recursive functions. $\endgroup$ – Sandro Lovnički Aug 25 '18 at 0:49

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