"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


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

| cite | improve this answer | |
  • $\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.