Foundations of Computation

About this book

Carol Critchlow and David Eck’s Foundations of Computation develops theoretical computer science through logic, discrete structures, formal languages, and models of computation. The linked second edition is version 2.3.2, Summer 2011. Five substantial chapters connect mathematical definitions with programming applications and culminate in computability limits. This guide adds clearly labeled study focuses within the chapters so the transition from concrete programs to abstract machines remains visible.

Chapter and section guide

1. Logic and Proof

Propositional logic describes compound statements and valid inference, while predicates and quantifiers extend the language to objects and properties. Boolean algebra connects these patterns with symbolic manipulation and circuits. Proof methods explain why a claim follows from assumptions rather than only how to evaluate a formula. Students should distinguish truth under one assignment from validity across all assignments and identify the scope of each quantified variable.

Study application: Construct a truth table for a small argument and state whether its conclusion follows from the premises. Then explain how a quantified mathematical claim requires more than the same finite table.

Chapter 1 study focus: Induction and Recursion

Induction and recursive definitions connect logical reasoning with computational structure. A base case establishes an initial object or fact, and a recursive step specifies how later cases depend on earlier ones. Correctness requires that the construction or proof actually reaches the intended cases. Students should distinguish a recursive procedure’s termination from its production of the right result. The chapter’s applications make these separate obligations concrete.

Study application: Define a simple recursive function and prove a property by induction. State a measure that decreases toward the base case and explain why that supports termination.

Chapter 1 study focus: Logic Circuits

Boolean expressions can describe the input-output behavior of circuits. Equivalent expressions may correspond to different arrangements of gates while computing the same function. Students should trace all relevant inputs and distinguish a logical specification from a physical implementation. A diagram becomes meaningful when each connection and operation is defined. This application demonstrates how abstract laws support the analysis and simplification of computational systems.

Study application: Translate a small Boolean expression into a gate diagram and verify its output on every input combination. Explain why a simplified circuit can preserve behavior.

2. Sets, Functions, and Relations

Sets organize collections, functions describe unique-output mappings, and relations express more general connections. Operations on sets parallel logical operations, making earlier reasoning useful in a new representation. Injectivity, surjectivity, and composition prepare comparisons of finite and infinite collections. Students should define domains and codomains explicitly and distinguish a relation’s properties from how it is drawn or stored.

Study application: Create a finite relation and test equivalence-relation properties. Then define a function on the same underlying set and explain the additional unique-output condition.

Chapter 2 study focus: Programming and Databases

Programming applications connect abstract sets and functions with representations and operations, while relational databases provide another use of relations. The mathematical object and its stored representation are different levels of description. A program may use a particular encoding without changing the abstract property being modeled. Students should explain what an operation means before discussing its implementation and identify any information lost in the chosen representation.

Study application: Model a small fictional database relation and state a query in ordinary language and set-oriented terms. Explain why a tuple’s identity and the relation’s meaning matter to the result.

Chapter 2 study focus: Infinity

The discussion of counting beyond finite sets compares collections through mappings. A list that continues indefinitely is not automatically an enumeration of every object in a target set. Bijections and diagonal reasoning provide precise tools for testing such claims. Students should state the assumed listing rule and the construction that defeats it when appropriate. These ideas later support an understanding of limits on possible computational procedures.

Study application: Explain a countable infinite collection and outline why a different collection cannot be captured by a proposed complete list. Identify the role of the constructed diagonal object.

3. Regular Expressions and Finite-State Automata

Formal languages are sets of strings over an alphabet. Regular expressions describe certain languages, and finite-state automata recognize them through states and transitions. Deterministic and nondeterministic descriptions can differ in form while having equivalent expressive power for regular languages. Students should separate a string, a language, and a machine recognizing it. A handful of accepted examples cannot prove that the machine recognizes exactly the intended language.

Study application: Design a small automaton for a binary-string property. Trace accepted and rejected examples and explain the invariant represented by each state.

Chapter 3 study focus: Nonregular Languages

Finite-state machines have limited memory, which restricts the relationships they can recognize across arbitrarily long strings. The nonregular-language discussion requires a general argument rather than an unsuccessful attempt to draw a machine. Students should state the theorem’s assumptions and quantifier order carefully. An adversarial choice in a proof must remain valid for every case the argument requires, not only the easiest decomposition.

Study application: Take a standard counting-dependent string language and explain why a finite collection of states cannot simply remember an unbounded count. Distinguish that intuition from the formal proof still required.

4. Grammars

Grammars describe how strings can be generated through production rules. Context-free grammars, BNF, parse trees, and parsing connect formal structure with the description of programming languages. A grammar can generate a language while allowing more than one parse for some string, so ambiguity is a separate issue. Students should distinguish the syntax tree from the linear sequence of symbols and understand what a derivation demonstrates.

Study application: Construct two parse trees for a deliberately ambiguous expression grammar, then revise the grammar to express a chosen precedence convention.

Chapter 4 study focus: Pushdown Automata and General Grammars

Adding stack-like memory changes what a machine can recognize and connects pushdown automata with context-free languages. The chapter then examines limits of that framework and the greater power of general grammars. Each increase in expressive power requires a precise model rather than a vague claim that a machine has more memory. Students should identify what operation is permitted and how it supports the proposed recognition or generation.

Study application: Trace a stack-based process for balanced delimiters. Explain what the stack stores and why the same mechanism does not automatically solve every language problem.

5. Turing Machines and Computability

A Turing machine provides a simple but powerful model for examining algorithms. The model’s significance lies in the computations it can represent, not in being a realistic diagram of modern hardware. The chapter connects formal machines with broader notions of effective procedure. Students should distinguish accepting an input, rejecting it, and continuing forever. These distinctions become essential when defining recognition and decision procedures.

Study application: Outline a Turing-machine procedure for a small language and state what happens on both members and nonmembers. Identify whether the description guarantees termination on every input.

Chapter 5 study focus: Limits of Computation

The final material establishes that some precisely stated problems have no algorithmic solution in the relevant general sense. This is different from a problem being slow on present hardware or inconvenient to program. Diagonal and reduction arguments explain such limits through assumed procedures and their consequences. Students should track the exact input class and conclusion rather than turn undecidability into a claim that nothing useful can be computed.

Study application: Explain a reduction at the level of inputs, transformation, assumed solver, and resulting consequence. State why failure of a general decision procedure does not forbid solving particular instances.

Study instructions

1. Translate each formal definition into a concrete example and a carefully chosen nonexample.
2. Keep strings, languages, grammars, and recognizing machines distinct in your notation.
3. Trace small computations, then state an invariant or proof supporting the general claim.
4. When proving a limitation, identify the model, quantifiers, assumptions, and exact conclusion.
5. Connect programming examples with the abstract structures they implement without assuming implementation details define the mathematical object.

Practice and review task

Choose a small language and describe it with a regular expression, an automaton, and test strings where possible. Then compare it with a related language requiring more memory, explaining what changes in the model and the proof obligations.

Questions for reflection

What separates a recognizer from a decision procedure? Why is an impossibility theorem about all inputs different from a claim that every particular instance is unsolvable?

Sources and coverage

This original study guide follows Second edition, version 2.3.2, Summer 2011. It draws on the source contents, chapter introductions, selected explanations and examples, and review material. It condenses the resource rather than replacing the full text; study applications are original exercises.

Reviewed source text; Book and cover catalog record.