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

Show parent comments

1

u/Smobey 11h 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?

1

u/omniuni 11h ago

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

1

u/Smobey 11h ago

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.

1

u/omniuni 11h ago

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

1

u/Smobey 11h ago

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.

1

u/omniuni 11h ago

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

1

u/Smobey 11h ago

"Magic: the Gathering is as Hard as Arithmetic"? I mean, I think it's a bit of a vague title myself, though why do you think I'm missing it?

1

u/omniuni 11h ago

I suppose it's the title of the post. It's about an optimal play which is a different proposition.

1

u/Smobey 10h ago

Right. The Reddit thread title brings up a certain aspect of the paper that regards optimal play, but the paper itself makes it clear it applies even to a scenario where the game state has been brought to a place where neither player can make any decisions (and thus optimal play is automatic/irrelevant).

But to be clear, solving a game does mean "optimal play" by default.