Subtle Logic, Winning Game | Science News

Real Science. Real News.

Science News is a nonprofit.

Support us by subscribing now.

Math Trek

Subtle Logic, Winning Game

9:55am, March 15, 2001

Seemingly simple games can serve as thought-provoking exercises in mathematical logic. They can provide deep insights into subtle issues that confront logicians who are interested in the foundations of mathematics.

So-called Ehrenfeucht games have proved particularly useful for tackling certain aspects of mathematical logic. They were developed in the 1960s by Andrzej Ehrenfeucht, who is now a computer science professor at the University of Colorado in Boulder.

Ehrenfeucht games can also be studied for their own sake as interesting and often surprisingly subtle games, an approach adopted by Caroline Nguyen of Stuyvesant High School in New York City. Nguyen was one of 40 finalists in the 2001 Intel Science Talent Search (STS). Her goal was to identify, for a specific type of two-player Ehrenfeucht game, the starting positions in which the player moving second will always win.

The game is played with two sequences of zeros and ones. Each sequence can be of any lengt

This article is only available to Science News subscribers. Already a subscriber? Log in now.
Or subscribe today for full access.

Get Science News headlines by e-mail.

More from Science News

From the Nature Index Paid Content