This homework covers material from Lecture 5: Foundational Theories of Computation and Lecture 6: Classifying Programming Languages. You will explore the four pillars of computer science, discover new computational models, reason about the limits of computation, and analyze how pragmatic design choices shape programming languages.
All questions require written responses. Show your work where applicable, and provide clear justifications for your answers. Several questions require independent research — cite your sources. Partial credit will be awarded based on the quality of your reasoning.
The following four code snippets all compute the factorial of a number. Each is written in a language you likely have not used before.
APL:
factorial ← {×/⍳⍵}
Forth:
: factorial ( n -- n! ) 1 swap 1+ 1 do i * loop ;
Prolog:
factorial(0, 1).
factorial(N, F) :- N > 0, N1 is N - 1, factorial(N1, F1), F is N * F1.
Brainfuck:
+++++ Set cell 0 to 5 (input)
[>+>+++<<-]>>+>+<<< Setup for multiplication loop
[>[>+>+<<-]>>[<<+>>-]<<<-] Compute factorial
>>>. Output result
Choose two of these snippets. For each:
Natural language is famously ambiguous. Consider these two English sentences:
For each sentence:
The Fundamental Hypothesis of Language Theory (LN5) claims that any piece of human-usable information can be represented as a string of symbols — but this hypothesis is unprovable.
Consider the following example of information that seems to resist symbolic capture:
A chess grandmaster's "positional intuition" — the ability to glance at a board and immediately sense which side has the advantage, without calculating any specific lines of play.
Programming languages are not the only formal languages. Many domains use their own formal notations to represent structured information as strings.
Research one of the following formal languages (or propose your own, subject to instructor approval):
For your chosen formal language:
In LN5, we studied Turing Machines — the most powerful computational model we know. But Turing Machines are complex: an infinite tape, a read/write head, arbitrary movement. What happens when we strip away that complexity?
In Part 2, you will discover two simpler classes of automata by researching them independently, building examples, and exploring their capabilities and limits. By the end, you will construct the complete hierarchy of computational power — connecting machines, languages, and decidability.
In LN5, we defined Turing Machines as tape + head + states + transition function. But what if we removed the tape entirely? What if all a machine had was a finite set of states and transitions between them? In this problem, you will research the simplest class of automata, build one, discover what it cannot do, and connect it to regular expressions.
Research: What is a Finite Automaton?
Look up Deterministic Finite Automata (DFAs). A DFA has no tape and no stack — just a finite set of states, transitions between them based on input symbols, a start state, and a set of accepting states. It reads input one symbol at a time, left to right, with no backtracking.
In your own words:
Build and Trace a DFA
Design a DFA that accepts binary strings containing an even number of 1s and rejects those with an odd number of 1s. (The empty string has zero 1s, which is even.)
10110, showing the state after each symbol is consumedDiscover a Limitation
Now consider the language of balanced parentheses: the set of strings like (), (()), (()(())), etc.
Attempt to design a DFA for this language. You will find that you cannot.
Regular Expressions and the Chomsky Connection
The regular expression (a|b)*abb describes a language — the set of all strings over the alphabet abb.
You have just discovered that DFAs are elegant but limited — they cannot count beyond a fixed bound. What if we gave our finite automaton a single additional data structure? In this problem, you will research Pushdown Automata, see how they overcome the DFA's limitation, discover their own limits, and build the complete hierarchy of computational power.
Research: What is a Pushdown Automaton?
Look up Pushdown Automata (PDAs). A PDA is a finite automaton augmented with a stack — an unbounded last-in, first-out (LIFO) data structure.
In your own words:
Solving What DFAs Cannot
In Q2c, you showed that DFAs cannot recognize the language of balanced parentheses because they cannot count unbounded nesting depth.
(? What does it do when it reads )? How does it know the string is balanced when input ends?(()()), showing the stack contents after each symbol is consumed.Discovering PDA Limitations
Consider the language of strings consisting of equal numbers of a's, b's, and c's, in that order — for example, abc, aabbcc, aaabbbccc, and so on.
Building the Complete Hierarchy
You have now encountered three machines: DFAs (Q2), PDAs (Q3), and Turing Machines (LN5). Each has strictly more computational power than the last.
In LN5, we learned that most functions are not computable — there are more functions than programs. The proof uses the same diagonal argument from LN3's set theory. In Part 3, you will work through this argument yourself and connect the machine hierarchy you built in Part 2 to the fundamental limits of computation.
This is a guided proof. Each sub-question builds on the previous one. By the end, you will have constructed a formal argument for why most functions have no program — using the set theory tools from LN3.
Step 1: Programs Are Countable
Using the set theory from LN3:
Step 2: Functions Are Uncountable
Now consider the set of all functions
Apply Cantor's diagonal argument (from the cardinality section of LN3):
Step 3: The Implication
Combine your results from Q4a and Q4b:
Step 4: Connection to the Halting Problem
The diagonal argument shows that uncomputable functions exist. The Halting Problem (LN5) gives us a specific, famous one.
fox(f) that does the opposite of what halts predicts — eerily similar to how the diagonal function In Q2 you built a DFA for binary parity, and in Q3 you built a PDA for balanced parentheses. Consider these three languages:
For each language, state the weakest machine from the hierarchy you built in Q3d that can recognize it. Then explain why the next weaker machine cannot — what specific capability does it lack?
The Halting Problem (LN5) defines a language: the set of all (program, input) pairs where the program eventually halts.
In LN4, we showed that the Simply Typed Lambda Calculus always terminates — every well-typed expression has a normal form (strong normalization). This means its set of expressible computations is a proper subset of what a Turing Machine can do.
Defining Reduction
In complexity theory, a polynomial-time reduction from problem
Using the set theory and logic from LN2 and LN3:
A Guided Reduction: Building Structural Transformation Intuition
Consider two classic NP-complete problems on graphs:
Consider the following graph with 5 vertices and 6 edges:
Loading graph...
Looking ahead: Notice how a systematic structural transformation showed that two problems that look different are actually the same in disguise. This is the same skill you will use throughout this course: parsing transforms strings into trees, trimming a Concrete Syntax Tree to an Abstract Syntax Tree removes redundant structure while preserving meaning, and evaluating an AST into a semantic value transforms structure into computation. Each of these is a reduction — a systematic mapping between representations that preserves what matters.
Formalizing Complexity with Our Tools
The formal tools from LN2 (logic) and LN3 (set theory) are exactly what we use to define complexity classes precisely. In this problem, we give you the formal components — your job is to explain what they mean and assemble them correctly.
1. The formal definition of Big-O is:
This single definition uses three of our formal tools simultaneously. Identify each one and explain its role:
2. Now define the complexity class P. We give you the building blocks — assemble them into a single formal definition using set-builder notation:
Fill in each blank and explain your choices. (Hint: you need to say there exists a machine and a polynomial such that for every input, the machine decides correctly within the polynomial bound.)
3. Define NP similarly. The key difference is that NP uses a verifier instead of a decider:
Fill in the blanks. Then explain: why does NP have an extra existential quantifier that P does not? What is being "guessed" versus "checked"?
Complexity Analysis
Consider this Python function:
def find_pair(items, target):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] + items[j] == target:
return (i, j)
return None
1. Formally prove the worst-case time complexity of find_pair using the Big-O definition from Q6c. We break this into guided steps:
2. Is the problem solved by find_pair in P? Use your definition of P from Q6c. (Hint: you just proved its time complexity — does it fit within a polynomial bound? What would the polynomial
3. Is it in NP? Describe a polynomial-time verifier: given a proposed solution (a pair of indices
In LN6, we explored how programming languages force programmers to think at different levels of abstraction — and how choosing the right tool is a pragmatic decision about matching the level of concern to the problem domain. In Part 5, you will research real languages and apply the pragmatic principles from lecture.
For each language pair below, research both languages and perform a comparative pragmatic analysis. You should look at documentation, tutorials, and example programs in each language. Cite your sources.
Functional Pair: Erlang vs. Haskell
Both Erlang and Haskell are functional programming languages, but they were designed for very different problem domains and make very different pragmatic trade-offs.
Systems Pair: Rust vs. C++
Both Rust and C++ are systems programming languages that give the programmer fine-grained control over memory and performance. But they take fundamentally different approaches to safety and correctness.
Perform the same analysis as Q7a:
Pit of Success or Pit of Despair?
LN6 introduced the concept of pragmatic gravity — some languages make the easiest path the correct path ("pit of success"), while others make the easiest path the dangerous path ("pit of despair").
Choose a language from the LN6 abstraction spectrum that was not already analyzed in lecture (do not choose Rust, Elm, C, JavaScript, or PHP). Argue whether your chosen language is a pit of success or a pit of despair for its primary problem domain.
Provide a specific code example that demonstrates the pragmatic gravity — show how the language's defaults either guide the programmer toward correct code or toward error-prone code.
The Blub Paradox
Paul Graham's Blub Paradox (LN6) argues that programmers can look down the abstraction spectrum and recognize inferior tools, but cannot look up and recognize what they are missing.
Error Messages as a Pragmatic Design Dimension
LN6 argued that error messages are a kind of meta-language with their own pragmatic properties.
Find a single type error or syntax error that can occur in two different languages (or the same error reported by two different compilers/tools). Show the error message produced by each.
Compare:
| Section | Question | Points |
|---|---|---|
| Part 1: Language Theory | Q1: Exploring Forms of Expression | 15 |
| Part 2: Automata Theory | Q2: Guided Discovery — Finite Automata | 12 |
| Q3: Guided Discovery — PDAs + Hierarchy | 13 | |
| Part 3: Computability Theory | Q4: The Diagonal Argument (Guided Proof) | 15 |
| Q5: Machine Capabilities Across the Hierarchy | 10 | |
| Part 4: Complexity Theory | Q6: Reducibility and Formalizing Complexity | 15 |
| Part 5: Language Pragmatics | Q7: Paradigmatic Friction (Research) | 12 |
| Q8: Pragmatic Principles in the Wild | 8 | |
| Total | 100 |