Computable Functions

Partial and total computable functions

A total function assigns an output to every input in its domain. A partial function may be undefined on some inputs, corresponding to a computation that never halts there. This distinction is essential: a program can compute a partial function perfectly even when it runs forever on undefined inputs. Separate the mathematical specification from a particular implementation, because many programs may compute the same partial function while using different amounts of time or memory.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Building functions by composition and recursion

Primitive recursive constructions start from simple initial functions and combine them using composition and bounded structural recursion. Addition can be defined by add(x,0) = x and add(x,y+1) = succ(add(x,y)). Multiplication can then repeat addition. Such constructions terminate because recursion progresses through a finite natural-number argument. Being intuitively recursive is not the same as belonging to this formal class; the permitted construction rules determine what can be expressed.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Unbounded search and partiality

An unbounded minimization procedure searches for the least natural number satisfying a condition. If a witness exists and each tested case can be decided, the search eventually finds it. If no witness exists, the procedure may run forever. Adding this operation increases expressive power but loses guaranteed termination. In proofs, identify whether a search is bounded by known input data or merely expected to succeed; that difference separates a decider from a recognizer.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Programs can be encoded and simulated

Finite program descriptions can be represented by strings or natural numbers and enumerated systematically. A universal machine interprets such an encoding together with an input, modelling one program running another. This enables diagonal arguments in which a hypothetical program is asked about its own description. The Church–Turing thesis connects formal computability models with the informal notion of an effective algorithm; it is not a theorem proved solely by writing a simulator for one model.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Diagonalization and semantic properties

Assume a universal halting decider exists and build a program that loops when the decider predicts it halts on its own description, but halts when the decider predicts it loops. Running this program on itself yields a contradiction. More broadly, nontrivial extensional properties of computably recognizable languages are undecidable under Rice's theorem. Extensional means the property concerns the computed language, rather than a superficial feature such as the number of characters in source code.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Computability and complexity ask different questions

A decidable problem has an algorithm that always stops, but that algorithm may require impractical resources. Polynomial-time reductions compare computational difficulty among decidable problems. To prove a problem NP-complete, show membership in NP and reduce a known NP-complete problem to it. NP-completeness is not undecidability, and it does not establish that a problem lacks a polynomial algorithm unless the unresolved separation P != NP is assumed.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Worked enumeration and the role of bounds

Suppose a predicate P(x,y) is decidable and an explicit bound b(x) is computable. Testing y = 0 through b(x) decides whether a witness exists in that range, because there are finitely many terminating tests. Removing the bound creates only a recognizer for witness existence: it halts when it finds a witness but may search forever otherwise. This small change in specification explains why a seemingly straightforward exhaustive algorithm may fail to decide a language.

References: Carleton 4803 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton 4803 official calendar record ↗Course scope · 2026–27
• Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes ↗Supplementary primary reference