tag:blogger.com,1999:blog-11295132.post113337384683695052..comments2014-10-20T08:43:52.658-07:00Comments on A Neighborhood of Infinity: A Game of LogicDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-11295132.post-5580571971805993502014-09-05T09:54:04.231-07:002014-09-05T09:54:04.231-07:00See also http://cstheory.stackexchange.com/questio...See also http://cstheory.stackexchange.com/questions/25671/is-this-variation-of-tqbf-still-pspace-completeghttp://www.blogger.com/profile/04686862403622560424noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-89867131069646638302014-09-05T09:53:35.505-07:002014-09-05T09:53:35.505-07:00See also http://cstheory.stackexchange.com/questio...See also http://cstheory.stackexchange.com/questions/25671/is-this-variation-of-tqbf-still-pspace-completeghttp://www.blogger.com/profile/04686862403622560424noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-45169344873699695672007-10-04T13:24:00.000-07:002007-10-04T13:24:00.000-07:00This is basically a description of the standard ga...This is basically a description of the standard game-theoretic approach to semantics. Most students are only exposed to the truth-table method of proving validity, but in some logics (such as Quantum Logic) that option isn't available and so the semantics are given in terms of a game much like what you describe. If you look for some books on Quantum Logic, I'm sure you'll find more information.Bill Clarkhttp://www.blogger.com/profile/00965460944267232183noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133396926034753342005-11-30T16:28:00.000-08:002005-11-30T16:28:00.000-08:000xDE has some comments on the complexity of this g...<A HREF="http://www.livejournal.com/users/11011110/30066.html" REL="nofollow">0xDE</A> has some comments on the complexity of this game, FYIThanehttp://www.blogger.com/profile/00262698903359480609noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133396695643381402005-11-30T16:24:00.000-08:002005-11-30T16:24:00.000-08:00There are two "sum-like" things present here, if t...There are two "sum-like" things present here, if this game is to brought into the CGT theory (as I believe it can be, in a reasonable way). One is the logical ors that can be present inside the LogicGame positions. You've used the notation + for that. The other is the idea of a general combinatorial game sum (which is called 'disjunctive' but doesn't have to much to do with logical or). It also uses the + notation, usually.<BR/><BR/>If you take the +1 / -1 convention previously described, and know the CGT values for X and Y, I guess you're interested in whether that tells you anything about the LogicGame CGT value of X v Y (ie, "X or Y"). My guess is that there is no simple relationship, but it's worth thinking about what can be said...Thanehttp://www.blogger.com/profile/00262698903359480609noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133394271510897602005-11-30T15:44:00.000-08:002005-11-30T15:44:00.000-08:00Hi Thane,I was hoping that X or Y might be closely...Hi Thane,<BR/><BR/>I was hoping that X or Y might be closely related to the disjunctive sum of A and B (at least when there are no atoms in common between A and B) but it looks like not. Assigning +1 and -1 to 'true' and 'false' were the first thing I tried actually, but it doesn't seem to capture the notion that a position might always be a win for one particular player no matter how many moves they might waste in the other half of a disjunctive sum (if you see what I mean). Now I'm beginning to think the 'surreal number' approach is a red herring.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133392412296560632005-11-30T15:13:00.000-08:002005-11-30T15:13:00.000-08:00I'm assuming by "Conway's numbers" you mean the th...I'm assuming by "Conway's numbers" you mean the theory of disjunctive sums of combinatorial games as described in On Numbers and Games, or Winning Ways. One of the many things that makes this theory attractive is that it permits games with <B>different</B> rules to be analyzed together in a disjunctive sum. On a player's move in a disjunctive sum, he's required to select a single component and move in that component, only. Play ends when no move is available.<BR/><BR/>When you're asking for a "conway number" for this logic game, the natural interpretation (I think) is that you're looking for values that would permit them to be included in the general disjunctive CGT sum theory; ie you would be able to say "add" a logic game position to a Nim position, or a Chomp position, or apply thermography, or whatever; you could bring all the heavy machinery to bear on the problem.<BR/><BR/>One way to do it is to take the convention that a Logic Game ending in True is the number 1 by convention; and a Logic Game ending in False is by convention -1. Then all logical expressions will have a well defined game value, and can be included in the broader theory.<BR/><BR/>It's actually a nice game and there are interesting values; it doesn't boil down to the number of atoms. (I've worked out a few, but enough for one comment...)Thanehttp://www.blogger.com/profile/00262698903359480609noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133390443386020992005-11-30T14:40:00.000-08:002005-11-30T14:40:00.000-08:00In pure Conway-style counting, all that matters is...In pure Conway-style counting, all that matters is whether you can make a move. So the game as you described under Conway's idea of who wins and who loses depends only on the number of atoms.<BR/><BR/>So I propose a slight variant: True can place any atom with T (true), or any expression that evaluates to True with T. So, in particular, the game can end at the symbol T, where True can always replace T with T, and False has no moves.<BR/><BR/>Of course, such a replacement will never be an optimal strategy for True, unless that's all she can do; it's always better to replace some atom by T.<BR/><BR/><BR/>This isn't quite good enough, though... the game T is then larger than _every_ Conway Nimber, and F smaller, as Sigfpe said, and you can't add them Conway-style. In short, it's not immediately obvious to me how to dissect this game into a combinatorial game.Theohttp://www.blogger.com/profile/10449695704601441213noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133386434341634992005-11-30T13:33:00.000-08:002005-11-30T13:33:00.000-08:00'true' really wants to have the value +infinity be...'true' really wants to have the value +infinity because no matter how many turns goes you let False have True still wins.<BR/><BR/>I was hoping to be able to assign a value to positions in such a way that the values of XY and X+Y can be found from the values of X and Y (at least in the case where X and Y contain no common atom, the general case is more complex). But I don't think the assignment of -1 and +1 helps with that.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1133381925363637812005-11-30T12:18:00.000-08:002005-11-30T12:18:00.000-08:00Interesting.At first I thought the value of "true"...Interesting.<BR/><BR/>At first I thought the value of "true" would be zero, if I understand the question properly, since it is a terminal position (there are no available moves).<BR/><BR/>But that's not right, I'm sure you want "true" to be a win for True.<BR/><BR/>I guess the question is, how would you define an addition of your logical expressions in this game.<BR/>One way to make it well defined is to add separate components disjunctively, without any logical connectives between them, and say that a component ending in "true" is a +1 value, and one ending in "false" is a -1 value; play continues until all components have a value, and then the +1 and -1's are added up. If you like that, then "true" is +1, and "false" is -1 as logical expressions. This would allow a combinatorial game value for every logical expression, and a notion of a sum.Thanehttp://www.blogger.com/profile/00262698903359480609noreply@blogger.com