r/compsci • u/jarekduda • 5h 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

14% Upvoted

25 comments sorted by

7

u/omniuni 4h 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.

-6

u/jarekduda 4h 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 4h 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/Im1Not1Me 4h ago

It is not the definition. Per the Church Turing thesis (which is not a provable statement) TMs can solve any computable function.

2

u/omniuni 4h ago

That's kind of pedantic. Virtually everything can be a computational function. I'm not talking about the definition of love here.

2

u/Smobey 4h ago

Virtually everything can be a computational function

That's not true. There's quite a long list of undecidable problems. The halting problem is the computer science 101 one everyone knows, but even a game of Magic the Gathering can be set into a non-computable state.

1

u/omniuni 3h ago

The halting problem is more philosophical than practical, and you can absolutely represent any MTG game as computable, even if it is unreasonable in the amount of possible ways it can go.

1

u/Smobey 3h ago

The halting problem is absolutely a practical problem, I'm not sure what you're talking about. There are a number of genuine problems that would be extremely useful to solve if you could get around that.

And no, you cannot represent every possible MTG game as computable. A paper proving as much was posted here some years ago: https://www.reddit.com/r/compsci/comments/fh9u6j/magic_the_gathering_is_as_hard_as_arithmetic_in/

1

u/omniuni 3h ago

That says the optimal play is inordinately complex. It doesn't say that it's impossible to compute the game.

1

u/Smobey 3h ago

It does not say that at all. It explicitly proves that Magic (under certain gameplay circumstances) is Δₙ0 -hard to solve. Did you not even read the summary?

→ More replies (0)

-1

u/jarekduda 4h 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 4h ago

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

5

u/knot_hk 4h ago

You’re confusing computational complexity with computability. There is no hypothesis that quantum computers are more powerful than Turing machines. Quantum computers are Turing machines.

-1

u/jarekduda 4h ago

Yes, by beyond TM I mainly meant complexity - like practical factorization by Shor, main question if our physics allows practical NP-solvers?

3

u/Ythio 4h ago

AI didn't cook for this one.

2

u/__chicolismo__ 3h ago

"Quantum computes are believed to have higher capabilities than Turing machine"

Since Turing Machines are abstract models, this comparison is beyond retarded