0
$\begingroup$

After reading Church's thesis, and godelization theory, it seems everything is futile, is this really true, all the machines we are making machine which is same as before, bounded to not solve halting problems, in more simple terms can quantum computer do anything that a Turing machine can't?

PS: In book named Elements of theory of computation first edition, you will find Godelization otherwise it is redacted since second edition reason unknown but chapter 5 named Church Thesis is highly altered since second edition.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

No. A classical computer can compute anything a quantum computer can do, given long enough. There are simple methods of simulation that cause an exponential slowdown, which suffices to show that if it is decidable on a quantum computer, it is decidable on a classical computer. (We don't know whether the there might be other faster ways of simulating a quantum computer on a classical computer, but that doesn't affect decidability.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ So all the hope for GOD machine is futile, if quantum is same as classical, what is the benefit in living a false hope for technology innovation? $\endgroup$
    – TheExorcist
    Commented Nov 30, 2020 at 2:55
  • 1
    $\begingroup$ @TheExorcist, You asked a technical question. I gave an answer. The question and answer are probably primarily of theoretical interest. They have very little implications about hope for technology innovation. Quantum computers are not a god machine; they never were. $\endgroup$
    – D.W. ♦
    Commented Nov 30, 2020 at 5:33
1
$\begingroup$

As far as we know right now, no. Quantum computation makes some problems tractable that are currently intractable for classical computers, but problems that are theoretically impossible for classical Turing machines remain impossible for quantum computers as we understand them. Intractable, meaning the computation would take too long for the result to be useful. Impossible meaning literally not possible.

Computing something outside what's possible for a Turing machine enters the realm of hypercomputation, but that's not quite what quantum computers do.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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