Columbian College of Arts and Sciences

Department of Mathematics

 

Dean’s Seminar for First-Year Students # 26725 MATH 801-10

Turing machines, Chomsky languages, digital and quantum computing

GCR Quantitative and Logical Reasoning

 

SPRING 2007

TuTh 12:45 pm–2:00 pm

2020 K Street, Room 7

Professor: Valentina Harizanov

Office: Old Main (1922 F Street), Room #109

Phone: (202) 994–6595

E-mail: harizanv@gwu.edu

http://home.gwu.edu/~harizanv/

 

Office hours: Tuesdays 3:45–4:45p.m.

Thursdays 11:25a.m.–12:25p.m.

Other times by appointment

Any time by e-mail

 

Math Department

Old Main (1922 F Street), Room #102 (contains faculty mailboxes)

Phone: (202) 994–6235

 

Description

In the 1930’s, Alan Turing invented Turing “machine,” an abstract and powerful computing model that led to modern digital computers.  During World War II, Turing played a major role in breaking German cipher.  He also initiated the debate over whether a machine can think.  In the 1950’s, Noam Chomsky created his theory of generative grammars, which is considered to be one of the most significant contributions to the theoretical linguistics in the 20th century.  Trying to capture key properties of human language, Chomsky investigated various kinds of formal languages.  Surprisingly, it turns out that Chomsky’s grammars that generate these languages are closely related to Turing machines that recognize languages.  Current computers, like Turing machines, work by manipulating bits that exist in one of two states: 0 or 1.  This limits the machine power. Quantum computers have the potential to revolutionize computing.  They are not limited to two states; instead they encode information as quantum bits, or qubits.  A qubit can be 0 or 1, or it can exist in a superposition that is simultaneously both 0 and 1.  Will mankind succeed in building a quantum computer?  The seminar will feature guest lectures and a visit to the Turing exhibit at the International Spy Museum.  No math background is required beyond high school algebra.

 

Grading

Final Exam (take-home): 20%

Midterm Exam (take-home): 10%

Two Take-Home Exams: 20% (10% each)

Class Project (preferably a group project): 20%

Attendance, class participation, discussion, and in-class presentations of weekly take-home assignments: 30%

 

Best wishes for a successful semester!