Course Outline

Description

This is not your typical class in computer science, or in formal logic; but you will learn a lot about both by taking it. Our subject will be one of the most important and influential papers that has ever been written—“On Computable Numbers, with an Application to the Entscheidungsproblem,” by Alan Turing. This is the paper that birthed computer science as a discipline. Understanding it requires that you be comfortable with some mathematical concepts (powers and roots) and with thinking abstractly; but the most important prerequisite for understanding this paper is determination.

Turing’s 1936 paper proves something very interesting. We usually believe we have made progress in solving a mathematical problem when we come up with a general procedure. When you were young, you learned a procedure to subtract one number from another. Later, you learned a procedure to solve for the unknown in a quadratic equation. What Turing shows is that there is a large class of mathematical problems that cannot be solved procedurally. By this, we mean not merely that we do not know what the procedure is, but that no procedure will ever be found!

This is a shocking result! How can we know that no procedure will ever be found? Could it not be that we simply have yet to stumble on the right procedure to solve the problem? No, says Turing! In fact, he proves it, and his mind-bending proof is the centerpiece of our course. His proof lies at the center of three disciplines that have profoundly shaped the modern world: formal logic, foundations of mathematics, and theoretical computer science. Each of these disciplines looks back to Turing’s paper as a flashpoint, a moment which defined how each understands reality. What is the best way to characterize Turing’s paper? Simple. It changed the world.

Learning Outcomes

1. Understand and articulate Turing’s proof of uncomputability, together with its implications.
2. Engage with complex logical and computational concepts, and enhance the ability to think abstractly.
3. Explore the intersection of formal logic, mathematics, and theoretical computer science, and understand how Turing shaped these disciplines.
4. Gain a critical appreciation for the historical and philosophical impact of Turing’s paper, as well as its influence on theory of computation.
5. Cultivate the ability to read, analyze, and interpret a foundational text computer science.

An overarching objective of this course is to help you develop as a student of the liberal arts. True students of the liberal arts are able to reflect on the context in which they live, and reason about what it means to live a meaningful and happy life. Thus, they are able to be more than just children of their own time. But this means we must be willing to put our ideas to the test, see our own errors, and develop intellectual courage and humility. It also helps not to take ourselves too seriously.

Readings

• Petzold, Alan. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine. Indianapolis: Wiley, 2008.

Evaluation

• Turing Machine Exercises: The Turing Machine Exercises will be completed using the Turing language in DrRacket, and submitted electronically.

• Examinations: The examinations are written in class, and are comprehensive.

External Links

1. Class Schedule: Current schedule of readings and assignments
2. Electronic Whiteboard: For information sharing during class

Install DrRacket and the Turing Language

We will be using the Turing language in DrRacket as an integral part of this class. You will need a fully-fledged computer (not just a mobile device) to fully participate. Dickinson 235 has computers with Racket installed if you do not have your own.

1. Download Racket from here: http://download.racket-lang.org. There are versions for all modern Macs, Linux machines, and Windows. Open the downloaded file (probably called: racket-8.x-aarch64-macosx-cs.dmg on an Apple Silicon Mac, racket-8.x-x86_64-macosx-cs.dmg on an Intel Mac, or racket-8.x-x86_64-win32-cs.exe on a PC).
   • On a Mac, open and drag the folder to Applications.
   • On a PC, run the installer.
2. Start DrRacket.
   • On a Mac, this is in the Racket folder of your Applications list. If your computer complains that DrRacket is not from a “trusted developer,” you may have to go into the Finder, then Applications, then right-click DrRacket, and click “Open” to bypass this. You only need to open it this way once.
   • On a PC, this is in the Racket folder of your Applications list.
3. Install the turing package by opening the “File” menu and selecting “Install Package…”. In the field labelled “Package Source” enter “turing” and click Install.
4. When the package has installed, click Close. You will now be able to write in the language by starting your code with “#lang simply-scheme”.
5. You can find documentation for package by opening the “Help” menu and selecting “Racket Documentation”. Then in the “… search manuals …” box, enter “turing” and select “turing”. Or, you can find the documentation online.

Additional Information

1. This course outline is subject to arbitrary change. I shall announce any changes in class; if you are not present, you are still responsible for finding out what I announce.
2. Late exercises or assignments will not be accepted without a medical or compassionate reason. Exercises or assignments are due according to deadlines articulated in class.
3. The use of notebook computers or mobile devices is not permitted during class, except as allowed by the professor to do work directly related to some activity in class. You are expected to use analogue technologies (e.g., pen, pencil, and paper) to take notes, unless you have a special dispensation to use digital devices in class.
4. Please consult the college policy on class attendance. You must attend classes regularly and on-time. In accordance with the college’s policy on class attendance, credit will not be given to a student who has more than two weeks’ worth of absences.
5. Please consult the college policy on academic and artistic ethics. The use of artificial intelligence in coursework is not permitted, except as explicitly stated in this outline or allowed by the professor. You must fully cite your use of artificial intelligence if you use it.
6. Office hours are first-come-first-serve, unless you have an appointment. If you request an appointment by email, please send me a selection of several times you are available.
7. If you are being graded, your mark in the course will be translated into a letter-grade, according to the following scale: A+ (90–100), A (85–89), A– (80–84), B+ (77–79), B (73–76), B– (70–72), C+ (67–69), C (63–66), C– (60–62), D (50–59), F (0–49). Your grade will not be otherwise curved or adjusted.