1. The Need for a Formal Definition

Why isn't a dictionary definition good enough?

Without a precise, language-agnostic model of computation, we cannot prove universal truths about what is and is not possible to compute.

• Why isn't a dictionary definition — 'a process
• Because without a precise, mathematical model of computation
• Problem David Hilbert posed in 1928 with his 'Entscheidungsproblem' —
• He asked for a general procedure to determine the truth
• Answer him, mathematicians realized they first needed to formalize

2. The Algorithm as a Turing Machine

A simple, abstract machine that defines the limits of computation.

An algorithm is any computational process that can be simulated by a Turing Machine—an abstract device with an infinite tape, a read/write head, and a finite set of rules.

• Breakthrough came from several directions at once
• An algorithm, for our purposes
• What is a Turing Machine
• Head can read the symbol
• Infinite tape, a read/write head

3. From Euclid's GCD to Hilbert's Crisis

The idea of an algorithm is ancient, but its formalization is modern.

The intuitive concept of an algorithm dates back to antiquity (Euclid, al-Khwarizmi), but the drive for a formal definition came from the foundational crisis in mathematics in the early 20th century.

• Around 300 BCE, Euclid described an algorithm for finding
• Very word 'algorithm' is a Latinization of the name
• Crisis that forced a formalization came from mathematics itself
• The early 20th century
• His famous 'Entscheidungsproblem' asked for an algorithm

4. The Engine of Computation

How does this abstract machine actually 'think'?

A Turing Machine operates via a simple, deterministic loop: based on its current state and the symbol on the tape, its transition function dictates what to write, where to move, and which state to enter next.

• Turing Machine is deceptively simple
• It’s partitioned into cells, each holding a symbol
• Can read the symbol
• It's a finite set of states
• Function takes the current state

5. The Formalism of a 7-Tuple

Representing a machine with mathematical precision.

A Turing Machine is formally defined as a septuple M = (Q, Σ, Γ, δ, q₀, B, F), which precisely specifies its states, alphabets, and transition rules.

• Have Q, a finite set of states
• Sigma, the input alphabet, which is a finite set
• Gamma, the tape alphabet, which includes Sigma plus the blank
• Most important part, is delta
• Q-nought, the start state, which is an element of Q

6. The Five Defining Properties

What are the necessary conditions for a procedure to be an algorithm?

As defined by Donald Knuth, any true algorithm must satisfy five key criteria: Finiteness, Definiteness, Input, Output, and Effectiveness.

• [object Object]
• [object Object]
• [object Object]
• [object Object]
• [object Object]

7. Example: A Unary Adder

Let's build a machine that performs a simple task: n+1.

A step-by-step trace of a Turing Machine that increments a number represented in unary by scanning to the end of the input and writing one more '1'.

• Unary just means we represent the number 'n'
• Design a very simple Turing Machine
• Machine will chug along to the right
• Eventually, it will hit the first blank symbol after
• Machine has found the end of the number

8. The Uncomputable and the Intractable

A formal definition allows us to prove what is impossible.

Our formal model reveals two kinds of limits: problems that are fundamentally unsolvable (uncomputable, e.g., the Halting Problem) and those that are solvable but require infeasible resources (intractable).

• Power of a formal definition isn't just in what
• Halting Problem is the canonical example of an uncomputable
• Turing Machine, and thus no algorithm
• Another is the Post Correspondence Problem
• Aren't just hard; they are logically impossible to solve

9. Algorithms, Heuristics, and Recipes

How is an algorithm different from other kinds of procedures?

An algorithm guarantees a correct result. A heuristic is a practical but imperfect shortcut. A recipe is an informal procedure for humans that lacks mathematical definiteness.

• Heuristic is a problem-solving approach
• Example, in a chess program
• Instructions like 'bake until golden brown'
• Are not specified with the mathematical precision required
• How does the Turing Machine model compare to others

10. Four Common Conceptual Errors

Avoid these common misunderstandings about algorithms.

Common errors include confusing the abstract algorithm with a concrete program, assuming all problems are computable, and conflating the concepts of correctness and efficiency.

• [object Object]
• [object Object]
• [object Object]
• [object Object]

11. The Foundational Texts

Where to read the primary sources and definitive guides.

To deepen your understanding, consult Turing's original 1936 paper, Sipser's 'Introduction to the Theory of Computation', and Knuth's 'The Art of Computer Programming'.

• [object Object]
• [object Object]
• [object Object]
• [object Object]

12. Your First Turing Machine

Design a machine to solve a simple language recognition problem.

This week's exercise: design and formally specify a Turing Machine that decides the language L = {aⁿbⁿ | n ≥ 0}.

• Your task is to design a Turing Machine
• Language is 'a to the n
• Accepts strings like the empty string
• Need to provide the formal 7-tuple definition of your machine
• Common strategy is to shuttle back

13. What is an Algorithm?

An algorithm is not just a recipe; it is a precise computational procedure, formally equivalent to a Turing Machine, that is finite, definite, effective, and transforms input to output.

• An algorithm is a finite, definite, and effective procedure that takes input and produces output.
• The Church-Turing thesis posits that any computable function can be computed by a Turing Machine.
• Formal model allows us to prove that some problems, like the Halting Problem, are fundamentally uncomputable.
• The definition distinguishes algorithms from heuristics, which are imprecise or not guaranteed to be correct.
• An algorithm's correctness is distinct from its efficiency, which will be our focus for the rest of the course.

Mastery quiz

1. What three components define a Turing Machine?
   • An input file, an output file, and a compiler
   • A CPU, RAM, and a hard disk
   • An infinite tape, a read/write head, and a finite set of rules (states)
   • A stack, a queue, and a register
2. What problem did David Hilbert pose in 1928 that motivated formalizing computation?
   • The Entscheidungsproblem (decision problem)
   • The P versus NP problem
   • The Halting Problem
   • The Traveling Salesman Problem
3. What does the Church-Turing thesis claim?
   • Every program eventually halts
   • All problems can be solved in polynomial time
   • Lambda calculus is more powerful than Turing Machines
   • The Turing Machine can compute anything effectively computable by any means
4. How does an algorithm differ from a heuristic?
   • A heuristic must run on a Turing Machine; an algorithm need not
   • They are exactly the same concept
   • A heuristic always finds the optimal answer; an algorithm does not
   • An algorithm guarantees a correct result; a heuristic is a practical but imperfect shortcut
5. Which is a common conceptual error when first learning the formal definition of an algorithm?
   • Assuming a Turing Machine has finite states
   • Conflating correctness with efficiency
   • Knowing that the Halting Problem is unsolvable
   • Believing algorithms can be analyzed for efficiency