[FOM] the axiom of determinancy

Alexander, Samuel alexander at math.ohio-state.edu
Sat Jun 11 01:09:26 EDT 2011

Dear Adam,

I assume you mean the Gale-Stewart game for the set X of computable sequences.  If so, a winning strategy for player 2 for this game is as follows:  on the nth move (assuming it is player 2's turn), ignore everything player 1 did, and play the nth busy beaver number.  Accordingly, player 1 has no winning strategy.

One might also ask about the case when strategies are required to be computable (though this is a departure from the Axiom of Determinacy).  It is not difficult to see that neither player has a computable strategy.  For example, player 2 does not have a computable strategy, because as long as player 1 uses any computable strategy and player 2 does likewise, then the resulting sequence will be computable.

You might be interested in a short note of mine, "A paradox related to the Turing Test", which you can read here (page 90):  http://www.kent.ac.uk/secl/philosophy/jw/TheReasoner/vol5/TheReasoner-5(6).pdf

-Sam Alexander
From: fom-bounces at cs.nyu.edu [fom-bounces at cs.nyu.edu] on behalf of addamo at wp.pl [addamo at wp.pl]
Sent: Friday, June 10, 2011 11:48 AM
Subject: [FOM] the axiom of determinancy

I have the following question:

Let us take the axiom of determinancy (AD). And let X be the set of
sequences of the values
of the one variable recursive functions. Let us play about this set. This
play is
deteremined as the AD says. Is it true that there is a winning strategy for
a player II?
Is it true that it doesn't exist a winning strategy for the player I? And
what is the connection between
AD and CT (Church's Thesis)?


FOM mailing list
FOM at cs.nyu.edu

More information about the FOM mailing list