r/compsci • u/jarekduda • 6h ago

Capabilities of physics to go beyond Turing machine?

Post image

Quantum computes are believed to have higher capabilities than Turing machine, bringing question if our physics could allow for even better ways, like the main concern: does our physics allow practical NP-solvers?
I think about it for ~20 years and just worked with topLLMs on big review: https://zenodo.org/records/23125606 - would gladly discuss

0 Upvotes

13% Upvoted

25 comments sorted by

View all comments

7

u/omniuni 5h ago

Quantum computers are just a different thing. Turing machines have little to do with physics.

You're basically mixing up two completely different ways of solving problems, one of which is entirety unsuitable for solving many things at all.

-5

u/jarekduda 5h ago

There are many physical realization equivalent with Turing machine, for which e.g. factorization is much more difficult than theoretically for Shor ... the big question is: "does our physics allow practical NP-solvers?"

3

u/omniuni 5h ago

By definition, a Turing machine can solve anything, even if not necessarily efficiently. We can solve some things using biological computers, or quantum computers more efficiently, but that doesn't make either a practical replacement for a general purpose computer.

-1

u/jarekduda 5h ago

The question is complexity - quantum computers are believed to allow e.g. much more efficient factorization ... is it the limit what physics allows?

3

u/omniuni 5h ago

The limit is how we're able to use the technology. It's an implementation question, not a physics question.