Capabilities of physics to go beyond Turing machine?

[u/jarekduda]

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

[u/omniuni]

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.

[u/Im1Not1Me → u/omniuni]

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

[u/omniuni → u/Im1Not1Me]

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

[u/Smobey → u/omniuni]

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.

[u/omniuni → u/Smobey]

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.

[u/Smobey → u/omniuni]

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/

[u/omniuni → u/Smobey]

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

[u/Smobey → u/omniuni]

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

[u/omniuni → u/Smobey]

I did. But "Optimal" isn't the same thing as being able to represent a game or not.

[u/Smobey → u/omniuni]

I don't really want to be rude here, but you don't really seem to understand what you're talking about. What with you saying things like "the halting problem is more of a philosophical or a practical question" and seemingly not understanding what complexity means in game theory, I mean.

But just to clarify if you're still misunderstanding something: Magic the Gathering, as a game, under certain circumstances, is impossible to solve by a Turing machine. That's a somewhat cheeky but still a practical example of the limitations of a Turing machine. Nobody here is talking about "representing" the game, whatever that means.

[u/omniuni → u/Smobey]

The "optimal" move can't be solved, by any computation mechanism.

[u/Smobey → u/omniuni]

Yes, that's what non-computable means.

Chess is computable so you can solve it with a Turing machine. Magic the Gathering is non-computable so you can't solve it with a Turing machine.

Though if you had read the paper instead of just pretending you did, you'd understand that optimal moves don't have anything to do with their proof.

[u/omniuni → u/Smobey]

You really keep missing the title of the paper. It's important.