The Game Description Language Is Turing Complete

摘要

In this short paper, we show that the game description language (GDL) is Turing complete. In particular, we show how to simulate a Turing machine (TM) as a single-player game described in GDL. Positions in the game correspond to configurations of the machine, and the TM accepts its input exactly when the agent has a winning strategy from the initial position. As direct consequences of the Turing completeness of GDL, we show that well formedness as well as some other properties of a GDL description are undecidable. We propose to strengthen the recursion restriction of the original GDL specification into a general recursion restriction. The restricted language is not Turing complete, and the aforementioned properties become decidable. Checking whether a game description satisfies the suggested restriction is as easy as checking that the game is syntactically correct. Finally, we argue that practical expressivity is not affected as all syntactically correct games in a collection of more than 500 games having appeared in previous general game playing (GGP) competitions belong to the proposed GDL fragment.