Description
What is computation? This is the question that birthed Computer Science as a discipline, and serves as the focal point of this course. Our plan for answering it is twofold. First, we will introduce functional programming through Scheme (a dialect of Lisp). Unlike imperative languages, functional programming tends to emphasize techniques such as lambda functions, higherorder functions, recursion, and the use of immutable data. We will explore each of these techniques, and discover their significance in diverse contexts.
Second, we will use our understanding of functional programming to explore the nature of computation itself. This will involve reading parts of Alonzo Church’s revolutionary article, “An Unsolvable Problem of Elementary Number Theory.” We will see how the notion of computation emerges from his understanding of functions, and engage with the fundamental conjecture of Computer Science: the ChurchTuring Thesis.
This course is interdisciplinary in nature: we shall be learning skills in Computer Science (functional programming); but we will also be using these skills to explore serious questions at the nexus of Computer Science, Mathematics, and Logic. By the course’s end, you will understand the principles of functional programming, and their connection to computation. Additionally, you will gain insight into the ChurchTuring Thesis and its foundational role in the discipline of Computer Science.
No previous experience in Computer Science, Mathematics, or Logic is necessary to take this course. However, you will be programming in Scheme and reading challenging texts in theory of computation; so your learning will be wellsupported by having already taken a course that emphasizes symbolic thinking. For this reason, at least one course in Computer Science or Mathematics is a prerequisite.
Topics include: function composition, higherorder functions, lambda functions, recursion, primitive recursive functions, murecursive functions, combinatorial logic, fixedpoint combinators, the ChurchTuring Thesis, computation.
Learning Outcomes
 Grasp the Principles of Functional Programming: By the end of the course, you will be proficient in writing, debugging, and analyzing functional programs in Scheme, utilizing constructs like lambda functions, higherorder functions, and recursion.
 Understand Church’s Account of Computation: You will work through Church’s paper on lambda functions, and be able to articulate the relationship between functions and computation, highlighting its significance for computational problems.
 Grapple with the ChurchTuring Thesis: You will consider, critique, and form perspectives on the ChurchTuring Thesis, appreciating its pivotal role in bridging the realms of Computer Science, Mathematics, and Logic.
 Connect Functional Programming to Computation: You will draw connections between specific programming constructs (such as fixedpoint combinators) and overarching theories of computation, emphasizing the relationship between theory and practice.
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
 Church, Alonzo. “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, Vol. 58 No. 2 (April 1936), 345–363. Online.
 Eberbach, E.; Wegner, P. “Beyond Turing Machines,” Bulletin of the European Association for Theoretical Computer Science, No. 81 (October 2003), 279–304. Online.
 Harvey, Brian, and Matthew Wright. Simply Scheme: Introducing Computer Science, 2nd ed. Cambridge: MIT Press, 1999. Online. Available in the Dickinson reading room.
 Nonaka, Ayaka. “The YCombinator (no, not that one): A crash course on lambda calculus,” Medium, September 10, 2014. Online.
 Rojas, Raul. “A Tutorial Introduction to Lambda Calculus,” arXiv, 1503.09060 (March 2015).
 Shapiro, Stewart. “The Open Texture of Computability,” in Copeland, Jack B., Carl J. Posy, and Oron Shagrir, Computability: Turing, Gödel, Church, and Beyond. Cambridge: MIT Press, 2013. Online through the library. On reserve at the library. Available in the Dickinson reading room.
 Smith, Peter. An Introduction to Gödel’s Theorems, 2nd ed. Cambridge: Cambridge University Press, 2013. Online. Available in the Dickinson reading room.
Evaluation
Exercises and Writing 
30% 
Portfolio 
Final Project 
30% 
Subject to approval 
Oral Examination 
40% 
Comprehensive 

Exercises and Writing: Short exercises and writing assignments will be given in coördination with the current topic, and comprise your portfolio. All written submissions should be submitted as PDF, with program code attached as appropriate. Please put your last name and assignment number in the filenames, as well as in the text of the file.

Final Project: You will propose and complete a group project in coördination with the professor. A proposal must be approved in order to submit your final project. See below for details about possible projects.

Oral Examination: The examination is comprehensive and will be a series of oral questions, related to the topics covered in the course.
Portfolio Assignment #1
Portfolio Assignment #1 is due on Thursday, March 28. In preparation to submit your portfolio, please submit (in groups of two) the following exercises:
 Concepts
 For the following, define the concept, provide an example, and explain how the example is an instance of the concept (written; about 1/2 page typing minimum of each): Compound expression; “=” versus “equal?”; semipredicate; Higherorder function; Lambda as a special form.
 Exercises: 8.8, 8.11, 8.12, 8.14
 Exercises: 9.11, 9.14, 9.15, 9.16
 Extend TicTacToe game (from Chapter 10) to a 4x4 game
Fill out the Portfolio Cover Sheet for Assignment #1, and follow the submission instructions on that sheet.
Portfolio Assignment #2
Portfolio Assignment #2 is due on Thursday, May 16. In preparation to submit your portfolio, please submit (in groups of two or three) the following exercises:
 Concepts
 For the following, define the concept, provide an example, and explain how the example is an instance of the concept (written; about 1/2 page typing minimum of each): Beta reduction (in lambda calculus), conditional test (in lambda calculus), standard definition (of primitive recursive functions), extensionality (of functions).
 Exercises (from Simply Scheme): 14.11, 14.12, 14.14, 14.15, Project: Spelling Names of Huge Numbers
 Lambda Calculus
 State the lambda expression equivalent to NAND.
 Consider the following formulae in lambda calculus. Do they have a normal form? Why or why not?
 ((((λabx.((ax)(bx)))(λmn.(n m)))(λn.z))p)
 (λb.((λa.((λx.(a(xx)))(λx.(a(xx)))))b))
 In one to two pages (doublespaced, regular margins) articulate and explain the diagonalization argument (from section 14.5 of Smith) as if you were explaining it to a firstyear student. Are there any reasons to think that it does not hold?
Fill out the Portfolio Cover Sheet for Assignment #2, and follow the submission instructions on that sheet.
Final Project
Your final project is an exploration of a particular topic in computer science that is connected to our course in some way. You will complete your final project in a group of two or more. The project should be a substantive piece of work that correlates with the weight given in the course. Beyond this, there are no preëstablished guidelines: you submit make a proposal for your final project before the midterm break.
Project proposals should be no more than one page in length (single spaced), and should consist of the following: (i) a list of who is going to be involved in the final project; (ii) a brief description of the final product (be it an analysis, a commentary, a program, or some other work), including the steps you will take to complete the project; (iii) a bibliography of works that you intend to consult as part of the project. Note that the bibliography need not be long, and it also does not bind you: you may go beyond these works if you choose.
Here are some examples of final projects:
 A detailed commentary on Church’s paper where he introduces lambda calculus.
 An implementation of Shor’s Algorithm (quantum factoring) in Scheme.
 An analysis of Gandy’s generalisation of the Turing Machine.
 An analysis of Ada Countess of Lovelace’s Note E.
 A set of exercises from the initial chapters of SICP.
 A commentary on linear recursion and tail recursion in Scheme.
 A set of exercises from the Simply Scheme chapters we do not cover.
 A commentary and exercises for the initial chapters of Neural Networks and Deep Learning (caution: some partial differential equations).
Tentative Schedule
Day 
Topic 
Readings 
Notes 
Feb 22 
Introduction 
None 
— 
Feb 26 
Functions and Composition 
Simply 13 
Ex. 2.12.4, 3.13.2, 3.5, 3.9 
Feb 29 
Defining Procedures 
Simply 45 
Ex. 4.1, 4.3, 4.44.10, 5.15.7, 5.135.21 
Mar 4 
True and False, Variables 
Simply 67 
Ex. 6.16.14, 7.17.4 
Mar 7 
Higherorder Functions 
Simply 8 
Ex. 8.18.14 
Mar 11 
Lambda 
Simply 9 
Ex. 9.19.17 
Mar 14 
— 
— 
No class 
Mar 18 
Introduction to Recursion 
Simply 11 
Ex. 11.511.7 
Mar 21 
More Recursion 
Simply 12 
Ex. 12.512.13 
Mar 25 
Still More Recursion 
Simply 13 
Ex. 13.113.6 
Mar 28 
Lambda Calculus Introduction 
Rojas 12.2 
Portfolio #1 Due 
Apr 1 
Lambda Calculus 
Rojas 334 

Apr 4 
Lambda Calculus 
 
Presentations 
Apr 8 
— 
— 
Long weekend 
Apr 11 
The YCombinator 
Nonaka 
 
Apr 15 
The YCombinator 
— 

Apr 18 
The YCombinator 
— 

Apr 22 
Primitive Recursive Functions 
Smith 1414.4 
 
Apr 25 
Primitive Recursive Functions 
Smith 14.5 
 
Apr 29 
MuRecursive Functions 
Smith 3838.2, 38.538.7 
 
May 2 
Church 
Church 1 
— 
May 6 
Church 
Church 2 
— 
May 9 
Church 
Church 3 
— 
May 13 
Church 
Church 45 
— 
May 16 
Church 
Church 67 
Portfolio #2 Due 
May 20 
Church 
Church 8 (Starting: “In order to present”) to end 

Resources
Reading Questions
Install Racket and the Simply Scheme Package
We will be using the Racket language as an integral part of this class. You will need a fullyfledged computer (not just a mobile device) to fully participate. Dickinson 235 has computers with Racket installed if you do not have your own.
 Download Racket from here: http://download.racketlang.org. There are versions for all modern Macs, Linux machines, and Windows. Open the downloaded file (probably called: racket8.xaarch64macosxcs.dmg on an Apple Silicon Mac, racket8.xx86_64macosxcs.dmg on an Intel Mac, or racket8.xx86_64win32cs.exe on a PC).
 On a Mac, open and drag the folder to Applications.
 On a PC, run the installer.
 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 rightclick 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.
 Install the simplyscheme package by opening the “File” menu and selecting “Install Package…”. In the field labelled “Package Source” enter “simplyscheme” and click Install.
 When the package has installed, click Close. You will now be able to write in the language by starting your code with “#lang simplyscheme”.
 You can find documentation for package by opening the “Help” menu and selecting “Racket Documentation”. Then in the “… search manuals …” box, enter “simplyscheme” and select “simplyscheme”. Or, you can find the documentation online.
Downloading and Using Functions.scm
 Here is Functions.scm, which you will need to complete Chapter 2 of Simply Scheme.
 Follow the link, and copy the contents of the text file into the definitions window. Click “Run” in DrRacket.
 In the interaction window, type (functions) to start the program.
External Links
 Electronic Whiteboard: For information sharing during class
 Code from Class: A listing of code we worked on during class
 Lectures on Simply Scheme: by Brian Harvey, coäuthor of our textbook
 SICP Website: Text and exercises
 Land of Lisp: Music Video
 Land of Lisp Comic: Scroll to the (very) bottom to see the “Secrets of the Seven Guilds”
 Xkcd: Lisp Cycles: Elegant weapons for a more civilized age
 Scheme Style Guide: Suggested style for Racket programs
 History of Lisp: by John McCarthy, creator of Lisp
 How Lisp became God’s Own Programming Language: by Sinclair Target
 Beating the Averages (Lisp as a secret weapon): by Paul Graham
 Ada Lovelace Obituary: New York Times, 2018
 Computing Machinery and Intelligence: by Alan Turing
 Consciousness in Human Robots and Minds: by Daniel Dennett
 They’re Made out of Meat: A short story by Terry Bisson
 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.
 Late assignments will not be accepted without an acceptable medical or compassionate reason. Assignments are due according to deadlines on this course outline.
 You must attend classes regularly and ontime. Penalties for unexcused absences and for lateness will factor into the class grade. Two unexcused absences are grounds for a marginal pass, and three are grounds for failure, even if all you other work is good.
 Office hours are firstcomefirstserve, unless you have an appointment. If you request an appointment by email, please send me a selection of several times you are available.
 Please be aware of the college policies on class attendance, as well as academic and artistic ethics. You must declare any work you submit that is generated in part or whole by AI.
 If you are being graded, your mark in the course will be translated into a lettergrade, according to the following scale: A (85–100), 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.