games and multiple quantifiers

From: David Bernier (david250_at_videotron.ca)
Date: 01/14/05 

Date: Fri, 14 Jan 2005 11:13:15 -0500

To express that White has a winning strategy in <= 60 moves in chess,
(White: 60 moves, Black: 60 moves), one could write:

(E w1) (A b1) (E w2) (A b2) .... (E w60) (A b60)
     [ WhiteWins(w1, b1, w2, b2, ... w60, b60 ] .

Here, WhiteWins(.) can be taken to be a recursive function
on 120 integers restricted to a domain D^120 where
D = {1, 2, ... NMAX}, and NMAX is not too large,
certainly NMAX < 10000.

If f is a recursive function on N^120,
is it the case that even having an
oracle for the halting problem,

it need not be the case that:
(E w1) (A b1) (E w2) (A b2) .... (E w60) (A b60)
     [ f(w1, b1, w2, b2, ... w60, b60 ]
      is decidable?

David Bernier

Relevant Pages

  • games and multiple quantifiers
    ... To express that White has a winning strategy in <= 60 moves in chess, ... WhiteWins(.) can be taken to be a recursive function ...
    (sci.logic)
  • Re: games and multiple quantifiers
    ... WhiteWins(.) can be taken to be a recursive function ... is decidable in the abstract computational sense (even if not in any ... because the 120-deep game tree is *finite*. ...
    (sci.logic)
  • Re: games and multiple quantifiers
    ... WhiteWins(.) can be taken to be a recursive function ... is decidable in the abstract computational sense (even if not in any ... because the 120-deep game tree is *finite*. ...
    (sci.math)
Quantcast