...the paper by Madani et al: www.labri.fr/perso/gimbert/stageM2/*madani*.pdf
> > 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) > > > -- ========================================================= 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
