Формула игры - Formula game

А формула игры искусственная игра, представленная полностью количественная логическая формула. Ходы игроков чередуются, а пространство возможных ходов обозначено связанные переменные. Если переменная универсально определяемый, следующая за ней формула имеет то же значение истины как формула, начинающаяся с универсального квантора, независимо от сделанного хода. Если переменная экзистенциально количественно, формула, следующая за ней, имеет то же значение истинности, что и формула, начинающаяся с экзистенциального квантора как минимум для одного хода, доступного на ходу. Ходы чередуются, и игрок проигрывает, если он не может двигаться в свой ход. В теория сложности вычислений, язык FORMULA-GAME определяется как все формулы таким образом, что Игрок 1 имеет выигрышную стратегию в игре, представленной . FORMULA-GAME - это PSPACE-полный.

Рекомендации

  • Сипсер, Майкл. (2006). Введение в теорию вычислений. Бостон: Технологии курса Томсона.