Jogo de fórmula
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
Um Jogo de fórmula é um jogo artificial representado por uma fórmula booliana completamente quantificada. Jogadores alternam seus turnos e o escopo de movimentos possíveis é definido pelas variáveis ligadas. Se uma variável é universalmente quantificada, a fórmula seguinte a ela deve possuir o mesmo valor verdade que a fórmula, iniciando com o quantificador universal independentemente do movimento jogado. Se uma variável é existencialmente quantificada, a fórmula seguinte a ela deve possuir o mesmo valor verdade que a fórmula, iniciando com o quantificador existencial por ao menos um movimento disponível durante o turno. Os turnos alternam, e um jogador perde se ele não pode mover durante o seu turno. Na teoria da complexidade computacional, a linguagem JOGO-DE-FORMULA é definida como todas as formulas que causam o primeiro jogador ter uma estratégia vencedora no jogo representado por . JOGO-DE-FORMULA é PSPACE-completa.
Referências
editar- Sipser, Michael. (2006). Introduction to the Theory of Computation. Boston: Thomson Course Technology.