Thanks Steve for your answer. 1) One-player randomized games (paper by Madani et al) For the paper by Madani et al, they work on unobservable problems; there is a graph, some transitions are labelled with actions (e.g. just binary actions), and some others are labelled with probabilities (rational probabilities are ok, so there's no problem for encoding this). The instance also contains a rational number c, and the question is "is there a sequence of actions leading to acceptance with probability at least c". The undecidability result is then a classical undecidability result, by reduction to the halting problem for Turing machines.
2) Two-player games For the extension to two players non-stochastic games, there's no more randomness. Unobservability is still ok. The point is that in non-fully observable games, even when they are deterministic, there is a probability c of winning for an optimal stochastic strategy S at the worst case on the opponent's stochastic strategies S'. This is well defined, and so the question "given graph G (equipped with decision nodes for player 1 and decision nodes for player 2), is c bigger than d ?" makes sense, and is undecidable. Importantly, approximate answers are also undecidable. (nb: my email address is [email protected], [email protected], [email protected], all of them leading to the same email account) could you be a bit more precise with your definition of the language you'd > like to show is undecidable? try to phrase it as a decision question that > results in a language of strings over some finite alphabet, and then maybe > you can get somewhere, with a reduction, for instance. > > i'm not sure how you intend to define undecidability in the face of > randomness, or even what your question is really asking. > > a natural way to use computability to include the flavor of randomness is > to bound the number of bad cases. i.e., to imagine that something is > happening either uniformly at random or with a particular distribution, and > to bound the probability in the uniform case is just to bound the number of > bad cases in the deterministic case. but you have to be careful about how > you state this. > > it could be a fairly straightforward undecidability result, but it depends > upon the question that you're asking. > > PS i tried to email you directly instead, but apparently your return email > address is invalid... > > s. > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > -- ========================================================= Olivier Teytaud -- [email protected] TAO, LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud F-91405 Orsay Cedex France http://0z.fr/EJm0g (one of the 56.5 % of french who did not vote for Sarkozy in 2007) -- ========================================================= Olivier Teytaud -- [email protected] TAO, LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud F-91405 Orsay Cedex France http://0z.fr/EJm0g (one of the 56.5 % of french who did not vote for Sarkozy in 2007)
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
