HDTenEightyP/NetNews huggingface dataset:
From: pugh@cs.umd.edu (Bill Pugh)
Newsgroups: sci.logic,comp.theory
Subject: Difficulty of Presburger over the reals
Date: 6 Oct 92 22:26:31 GMT
Followup-To: sci.logic
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742

I'm looking at some problems that involve producing constructive
proofs for Presburger-like formulas, except over the reals, not
over integers. 

Questions:

  * Is there a better name for this class of formulas other than 
	"Presburger over the reals"

  * Any pointers to algorithms or upper bounds for either verifying
	such formulas or producing constructive proofs?

We actually don't need full Presburger over the reals, but we do need
to deal with formulas that have an arbitrary number of alternating 
quantifiers. If there are any methods that work for subsets of Presburger 
that allow an arbitrary number of alternating quantifiers, that would be 
of interest as well.

  Thanks,
    Bill Pugh
Newsgroups: sci.logic,sci.math,rec.games.chess
From: hau4@ellis.uchicago.edu (sven  hauptfeld)
Subject: Re: "Solvability" in Chess
Reply-To: hau4@midway.uchicago.edu
Organization: University of Chicago Computing Organizations
Date: Mon, 28 Sep 1992 04:30:01 GMT

I want to point out that the 'optimal play' as understood in the solvability
problem and 'optimal play' in actual game may be *very* different.

When we try to solve a game, we ask if it is possible for either side to 
force a win against perfect play (i.e. against any reply). The optimal strategy
in this case is minimax strategy: if we can force a draw, but not a win, we 
must not play a move which wins against all but one reply, against which it
loses.

The optimal strategy for *playing* the game is the same *only* if one side
can force a win and we are playing that side. Then we simply play the moves 
which win against all replies.

But what if neither side can force a win from the initial position? (This may
well be true for chess, at least I'd bet on this outcome if the solution were
practically achievable.) Suppose the supercomputer that has solved the game
challenges the World Champion? If it consistently applies minimax strategy,
and the Champion never plays a losing move, all games end in a draw and the
Champion retains the title!

Therefore, the optimal algorithm for winning games is considerably different!

Incidentally, this means that the discovery that the initial position is a 
forced draw would be good news for all the people who fear the loss of
'uncertainty' in chess: it would mean that one must take risks to win!

	Sven

P.S. The last statement is oversimplified. It is true only under some
additional assumptions. Namely, it is possible that the initial position is
a draw with best play, but that (say) white has winning paths in which best
play by black still leads only to a draw, i.e. that white doesn't have to
risk. 

Xref: sparky sci.logic:1627 sci.math:12469 rec.games.chess:8330
From: ed@cbnewsl.cb.att.com (edward.m.hummel)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 30 Sep 92 00:40:24 GMT
Organization: AT&T

In article <xeno.717738632@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>  The very term "solvable" assumes
>against a player does not make mistakes.

Ah!  I think I see your point.

I had been assuming the players will play consistent with their optimal
strategies in my definition of the solution of the game.  I.e., "best
play" does not go against optimal strategy.  The view I was taking was
that we were "solving the game", rather than actually playing the
game.  Sort of like, working out the best sequence prior to making
the move.

It is very interesting to look at the system that includes that
game plus the two players.  Then lots of questions can come up --
and usually do.  If both players have complete knowledge and can
adjust their strategy based upon their knowledge, then the best
they can do is for each to follow their "optimal strategy" -- a
Nash equilibrium.  (Because if they don't, their opponent will.)

If the players don't have complete knowledge, but can still
calculate the solution to the game (i.e., assuming perfect play by
the opponent), then they also should go for the Nash equilibrium.

If the opponents, don't have perfect knowledge and either can't
calculate the solution to the game (i.e., they will play "inferior"
moves) then there are lots of possibilities depending upon how much
we know about the imperfections in the opponent.  This models the
behaviour of actual chess players who alter their openings to suit
their needs against particular opponents.  There are also some
interesting non-symmetric possibilities, where one player has
complete knowledge, including complete knowledge of the others
imperfections.  As long as the moves played by the "imperfect"
player are deterministic in a known way, an optimal strategy can be
calculated.
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: sci.logic
Subject: Church's Heresy and the Unsolveability of chess
Date: 6 Oct 1992 03:29:31 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

   Call this Church's Heresy:  the set of all computable functions is a finite
set, and a proper subset of the recursive functions.

Application:
   The game solving algorithm is not (yet) computable with the input being
the game of chess.  Thus, by Church's Heresy, chess is not (yet) computable.

   The strong version of Church's Heresy: the set of all functions that have
been, are being, ever will be, or ever could be computed is a finite subset
of the recursive functions bounded above in size by 2-to-the-256.

Corollary:  Every computable function can be represented uniquely by 32 bytes.
Theorem:    This 32-byte coding is not computable, but is finite and recursive.
Newsgroups: sci.logic,sci.math,rec.games.chess
From: xeno@iastate.edu (Gary L Snethen)
Subject: Re: "Solvability" in Chess
Organization: Iowa State University, Ames IA
Date: Sun, 27 Sep 1992 06:32:03 GMT

In <1992Sep26.132508.24956@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:

>In article <xeno.717471510@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>>It is not possible for both players to have better than a draw and
>>less than a win....  What one player has, the other does not.  One's
>>loss is the other's win... zero sum game.
>>
>>How do I prove this?  The rules of chess state it quite plainly...
>>If white wins, black loses.  If black loses, white wins.  A draw is
>>considered a perfect 50%/50% game for each (a half-loss, half-win situation).

>There is a loop hole:  the rules do not give a value to games that do
>not end.

I beg to differ, but they most certainly do!  This is called a 'draw'.  If
it were NOT considered a 'draw' then a king vs. king position would very
plainly fall under the category of such a loop hole.  If you then say
'well, there is not enough of a material advantage for either side to win
so therefore it is obviously a draw since all paths lead to draws, but in
another example, this might not be the case' then my response is:

You've added a synthetic rule to the game which states that lack of material
advantage is a draw. (Note that this is *not* really synthetic as the rules
of chess plainly state that such positions are draws, JUST as they state
that indefinite loops are draws...  if you take one, you MUST take the other).

If you are interested in 'rigor' then all you need do is add these two rules:

(1) ANYTIME a position has been repeated three times, the game is a draw.

and/OR (yes, OR...  either rule suffices)

(2) If 50 moves pass with no capture, the game is a draw.


You are accusing the rules of chess of having 'loop holes' whereby players
can claim a condition other than win/lose/draw...  If you wish to contort
the rules of chess to create such synthetic loop holes to support your
argument, then at least explain it as such.  If there ARE loopholes and I
am still confused on the issue, PLEASE try to create an example situation
where this question would arise.

Even if so, I think I can easily gain a consensus amoung the players here
on the net that if a game lasts forever (ie., has infinite moves whether in a
loop or not), then that game is a draw since neither side has a hope to
win unless the other side makes a mistake.  But luckily, the accepted rules
of play prohibit such situations from arising.

Now, if you are interested in a variant of chess where these rules do not
apply, then your argument is completely founded.  But then we are no longer
talking about a finite game, so the previous discussions do not apply.


---Xeno












Xref: sparky sci.logic:1591 sci.math:12333 rec.games.chess:8205
From: ark@alice.att.com (Andrew Koenig)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 28 Sep 92 13:05:46 GMT
Article-I.D.: alice.23738
Reply-To: ark@alice.UUCP ()
Organization: AT&T Bell Laboratories, Murray Hill NJ

In article <1992Sep27.161451.20136@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:

> Consider the game 1. Nf3 Nf6 2. Ng1 Ng8 3.Nf3 Nf6 4.Ng1 Ng8 5.Nf3 Nf6
> and so on, forever; with neither player choosing to claim a draw.  I 
> am asking for a proof that when collapsing the game tree to determine the
> value of the initial position, this sequence must have the value of a draw.

We can solve the problem in at least two ways.

1. Define it away by saying that any position from which neither player can
   force a win is a draw.

2. Ask why, in the situation you mention, neither player claims the draw after
   the third repetition.  Evidently the answer must be that they both think
   that playing indefinitely is preferable to ending the game with a draw.
   But in that case, the game is not zero-sum, which contradicts one of the
   conditions necessary for the theorem to apply in the first place.
-- 
				--Andrew Koenig
				  ark@europa.att.com
Newsgroups: sci.logic,sci.math,rec.games.chess
From: xeno@iastate.edu (Gary L Snethen)
Subject: Re: "Solvability" in Chess
Organization: Iowa State University, Ames IA
Date: Tue, 29 Sep 1992 03:50:32 GMT

In <1992Sep28.114530.7475@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:

>In article <xeno.717656375@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>>>Well, of course!  Once you ASSUME this, the rest is trivial.  The point
>>>was that an additional assumption is NEEDED.
>>
>>No, an additional assumption is not needed.
>>
>>Let me rephrase:  If you wish to apply the theorems we have used
>>so far from game theory, this assumption has ALREADY been made...  

>Speak for yourself.  I had not made this assumption, AND the game
>can be proven "solvable" even without making the assumption.  In
>the "real" game of chess, the rules do not make the assumption.

Please prove the game is solvable without the assumption.
I would VERY much like to see it.  The very term "solvable" assumes
against a player does not make mistakes.

Here's why:
  Let's say you cannot force a win with ANY move, but you can force a draw
  with e4, and I will make no mistakes in that variation, so the game will
  always draw.
  Let's say that I can force a win if you move d4...  but that I will
  always make a mistake in response to d4 that allows you to force a win.
  Against a perfect player you would NEVER move d4, because you know that
  you would lose.  Against me, however, you should ALWAYS move d4, because
  the outcome of your game will be maximal (ie., you will always win instead
  of draw).

  You MUST make an assumption about your opponent before you can analyze your
  'best move'.

>>In other words, the assumption is:  We don't take chances and assume our
>>opponent will be blind to our weaknesses.  We assume that if he CAN force
>>a win, he WILL, and that if he CAN force a draw, he WILL do that
>>in preference 
>>to allowing you to force a win against him.  This is an assumption we (who
>>support 'solvability') have been making all along.

>I also "support solvability", and I managed to do it without making
>the assumption.

Do it.


>>Summary of my position:
>>  Making the assumption that our opponent will not make mistakes, chess is
>>  solvable and the 'loops' presented do not interfere with the analysis.
>>
>>  Without this assumption, the version of game theory we are trying to
>>  apply does not hold, anyway...  And indeed, I feel it's very
>>  provable that optimal play cannot be obtained without insight
>>  into your opponent's 'algorithm' or 'psychology'.

>I would be interested in such a proof.  I think there is a solution
>to the "chess problem" that does not involve psychology or "insight
>into your opponents algorithm".

Take my example above as a demonstration.  You can not predict your optimal
play at d4, although that IS your optimal move.


---Xeno

Newsgroups: sci.logic,comp.theory,ieee.general
From: rz@mips.complang.tuwien.ac.at (Richard Zach)
Subject: Multiple Valued Logic Conference
Followup-To: poster
Reply-To: zach@csdec1.tuwien.ac.at
Organization: Technische Universit"at Wien
Date: Mon, 28 Sep 1992 17:19:51 GMT

Can anyone please tell me when and where the next
IEEE Confernece on Multiple-Valued Logic
takes pleace and where I can get a Call for Papers?

-- 
Richard Zach                      [zach@csdec1.tuwien.ac.at]
Technische Universitaet Wien, Institut fuer Computersprachen
Resselgasse 3/185.2,     A-1040 Vienna,       Austria/Europe
Xref: sparky sci.logic:1609 sci.math:12389 rec.games.chess:8273
From: hpm@frc.ri.cmu.edu (Hans Moravec)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" (long & pedantic)
Date: 29 Sep 92 09:29:59 GMT
Article-I.D.: sheep.HPM.92Sep29042959
Reply-To: moravec@cs.cmu.edu
Followup-To: sci.math
Organization: Field Robotics Center, CMU



Alpha-beta pruning with a good branch ordering function can evaluate
a min-max tree of N nodes, while visiting only Sqrt[N] of them.

My reference is a pamphlet written by Donald Knuth in the 1970s
titled "Alpha Beta Prunes", but this is a widely known result.

			-- Hans Moravec
Date: Friday, 25 Sep 1992 11:51:41 EST
From: <RVESTERM@vma.cc.nd.edu>
Newsgroups: sci.logic
Subject: Re: "Solvability" in Chess
 <1992Sep24.122426.28445@access.digex.com> <Bv34IL.E5w.2@cs.cmu.edu>
 <12609@sail.LABS.TEK.COM>

somebody said, "ok, is chess solvable? i hope we never find out."

well, too bad.

chess is solvable, by very elementary arguments that people have been
posting here for quite some time.

there is a difference between "solvable" and "solved".
Newsgroups: sci.logic
From: wft@math.canterbury.ac.nz (Bill Taylor)
Subject: Reply for Peter Vafeades.(chess solvability)
Organization: Department of Mathematics, University of Canterbury
Date: Fri, 2 Oct 1992 00:56:00 GMT

Peter Vafeades; couldn't email you, it bounced.

If anyone else can help, please do !

==========================
>At an international tournament some Greek players showed this game of anti-chess
>to some Russians.  We found out months later that "anti-chess" had been solved:
>white moves first, black always wins!

I am very interested in this game. Can you supply me with an outline of the
"black-wins" procedure, or a reference as to where I might find it?

I would be very grateful.

Hoping you can help me,  regards,  Bill Taylor.     wft@math.canterbury.ac.nz

==========================
Newsgroups: sci.philosophy.tech
From: chalmers@bronze.ucs.indiana.edu (David Chalmers)
Subject: Re: Dualism
Organization: Indiana University
Date: Wed, 30 Sep 1992 02:20:25 GMT

In article <1992Sep28.151204.4333@guinness.idbsu.edu> holmes@opal.idbsu.edu (Randall Holmes) writes:

>By asking for an "entailment", you _assume_ a difference between the
>two sets of phenomena.  I claim that there is no reason to assume such
>a difference.

This is just silly.  The fact that John is a bachelor entails the
fact that John is male, without this implying any kind of dualism
about John.  Similarly, I've outlined at length how the physical
facts about a dog, say, can entail the fact that it is alive.  This
doesn't assume or imply any kind of dualism about life -- it just
implies an intensional difference -- that the dog's being alive, as
a fact to be explained (or as a *phenomenon*) is a different fact
to be explained than the dog's microphysical constitution (as evidenced
by the fact that it's possible to explain one without explaining
the other, although in this case an explanation of one can easily
yield an explanation of the other).

All I've been asking for is the same kind of entailment for qualia
as it's straightforward to give for life, or for tables, or for
learning, or for just about any other property around.  And that's
what nobody, manifestly, has been able to give.  I suggest that
this is prima facie evidence that with qualia, something very
different is going on.

-- 
Dave Chalmers                            (dave@cogsci.indiana.edu)      
Center for Research on Concepts and Cognition, Indiana University.
"It is not the least charm of a theory that it is refutable."
Newsgroups: sci.philosophy.tech
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: Dualism
Organization: Smith College, Northampton, MA, US
Date: Tue, 29 Sep 1992 13:04:41 GMT

In article <Bv9vGp.Ax3@usenet.ucs.indiana.edu> chalmers@bronze.ucs.indiana.edu (David Chalmers) writes:

>Precisely what needs to be explained is why that [blue] radiation "feels"
>like anything at all -- i.e. why that all physical processing is
>accompanied by an experiential feel [...] 
>There is also the secondary question
>of why it feels like *that* rather than like *this* -- it seems
>perfectly coherent that our blue experiences and red experiences
>could be systematically inverted, for instance. [...]
>Evolution is irrelevant to the question of why *this* physical
>s[t]ructure gives rise to *this* experiential feel.

We seem to be getting to the crux of the dispute here, not only
between you and other netters, but between e.g. Dennett & Block (say).
So let's pursue this further.

You want an explanation of two facts:

	1. Why we feel at all.
	2. Why it feels like this rather than like that.

Despite your rejection of evolution, I believe it can give a type
of answer to both.  We feel because it is evolutionarily advantageous
to experience pain, to have our pulse quicken at sharp sounds, etc.
And perhaps it is neurologically most efficient for these survival
advantages to be implemented via experiential feel, rather than
zombie reactions.
	Why this rather than that may again answer to what is
most advantageous and most efficient:  there is some sense to
experiencing blue as darker than red, since it *is* darker;
so inverting blue and red might weaken other cues of the experiential
feel, other uses.  So perhaps inverted spectra are perfectly possible,
but just not a wise use of neurological resources.
	If explanations along these lines do not satisfy you, then
it seems you seek a finer neurochemical understanding of why
opiates make us feel good, why epinephrine heightens awareness, and
so on.  Surely this type of micro-understanding of our brain processes
is on the way.
	If even these explanations would not satisfy you, then
perhaps you could make clear what type of explanation *would* satisfy you.
Newsgroups: sci.philosophy.tech
From: rickert@mp.cs.niu.edu (Neil Rickert)
Newsgroups: sci.philosophy.tech
Subject: Re: Dualism
Date: 2 Oct 92 18:05:42 GMT
Article-I.D.: mp.1992Oct2.180542.22527
Organization: Northern Illinois University

In article <BvH2w8.EtA@usenet.ucs.indiana.edu> chalmers@bronze.ucs.indiana.edu (David Chalmers) writes:

>Incidentally, I certainly think that most of our mental states have
>evolved to enhance our fitness -- e.g. belief, learning, emotion,
>language capacity, and the like -- as all those mental notions can
>be analyzed functionally.  It's only the raw experiential feel that
>this doesn't seem to work for.

This doesn't compute.  Belief, learning, emotion, etc, require qualia
as a point of reference to the phenomena about which the learning, belief
are involved.  Thus evolution does account for qualia.  I agree that it
doesn't account for the actual form of the qualia (whatever that may
be), but it surely accounts for the existence of qualia.
Newsgroups: sci.philosophy.tech
From: chalmers@bronze.ucs.indiana.edu (David Chalmers)
Subject: Re: Dualism
Organization: Indiana University
Date: Wed, 30 Sep 1992 01:15:53 GMT

In article <n=_ps8=.kmc@netcom.com> kmc@netcom.com (Kevin McCarty) writes:

>DC:
>>Not so.  Nothing in my position implies that our reports of
>>consciousness don't accurately reflect the contents of our consciousness.
>
>Then I'm still misunderstanding your position.  If the functional
>organization of our brains gives rise to an "explanation" of why we
>report having qualia, but whether we actually do or not is a
>contingent further fact which might not be the case in some alternate
>universe, then the fact that we actually do have qualia is logically
>independent of what we are bound to say.  In other words, our reports
>of consciousness might not accurately reflect the contents of our
>consciousness (even though I think in this case they do).  Perhaps I
>have a faulty notion of what "logical independence" means.
>Or perhaps logical independence is irrelevant to principle (2), and
>you're simply stating what you believe to be an empirical fact.

The latter is closest to the mark.  Principle (2) says that, in fact,
our reports of conscious states do accurately reflect those mental
states.  That's compatible with logical independence.  It asserts
simply that there's an empirical connection there.

-- 
Dave Chalmers                            (dave@cogsci.indiana.edu)      
Center for Research on Concepts and Cognition, Indiana University.
"It is not the least charm of a theory that it is refutable."
Newsgroups: sci.philosophy.tech
From: oz@ursa.sis.yorku.ca (Ozan Yigit)
Subject: Re: "Consciousness Explained"
Organization: York U. Student Information Systems Project
Date: Tue, 6 Oct 1992 14:30:54 GMT

Fyi, There is also a review of CE in the May/June issue of "The Sciences",
by Adina L. Roskies and Charles C. Wood, titled "A Parliament of the Mind",
pp. 44-50. They conclude

	Regardles of its flaws, Consciousness Explained is a significant
	step toward narrowing the gulf between scientific, philosophical
	and literary approaches to the mind and the brain.

... oz
---
It is harder to get lost in an imagined forest than in a real one,
for the former assists the thinker furtively. -GOLEM [lect. XLIII]
Newsgroups: sci.philosophy.tech
From: jfh@reef.cis.ufl.edu (James F. Hranicky)
Newsgroups: sci.philosophy.tech,sci.math,sci.physics,sci.astro
Subject: Re: STRUCTURE OF TIME (at numerous requests)
Date: 4 Oct 92 22:23:26 GMT
Followup-To: sci.philosophy.tech
Organization: Univ. of Florida CIS Dept.

In article <1992Sep30.092352.1@tnclus.tele.nokia.fi> hporopudas@tnclus.tele.nokia.fi writes:

>    Unfortunately scientists teach to ordinary peoples presisely what they
>  talk in private or in public situations all around the world. Ordinary
>  peoples respect all their words (mostly without any criticism).
>    This is why these 'wise teachers' are fully responsible for all their
>  words they have 'teached' to ordinary peoples.
>

Obviously, these "ordinary people" are fully not responsible for their
acceptance or non-acceptance of any "scientific" doctrine, eh? There
are plenty of scientist who can find the middle ground between science
and religion, and for those who don't: If you don't like what they say,
don't pay attention to it. The advances in science and technology prove 
that gee, something must be right about these doctrines, right?

Science merely attempts to find the truth through verifyable means, and
of those things which cannot be proved or disproved, science is silent.
The scientists themselves are free to believe what they want to after this
point, but laying the responsibility for anyone elses acceptance of 
scientists' beliefs on the scientists themsevles is unwarranted. Do you 
categorically reject the scientific method?

Do you commit blasphemy by using this network created by science?

Jim Hranicky (jfh@reef.cis.ufl.edu)