ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A strongly terminating game is a game G\mathcal{G} in which every play terminates. The winning positions of G\mathcal{G} are the positions from which the winning player can force a win; these positions form a language over the game's position alphabet.

The conjecture. Given a strongly terminating game G\mathcal{G}, it is undecidable whether the winning positions of G\mathcal{G} form a regular language.

The paper presents this as an open problem in the context of taking-and-merging games. The preceding results establish undecidability for related restricted questions, but the supplied text does not give a proof of this stronger regularity problem.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.