Turner ITI – Fundamentals
Basic Principles
(MIT‑Level, First‑Principles Analysis, Edge‑Case Exploration, & A Challenging Problem)
Audience – Advanced undergraduate / early graduate students in Computer Science or Information Technology.
Goal – Master the conceptual bedrock that underpins all subsequent coursework in the ITI curriculum.
1. Foundations of Computation
1.1 The Turing Machine (TM) – A First‑Principle Model
| Component | Symbol | Purpose |
|---|---|---|
| Tape | infinite sequence of cells | unbounded memory |
| Head | read/write head | inspects and changes symbols |
| State register | finite set (Q) | current configuration |
| Transition function | (\delta: Q\times\Gamma\to Q\times\Gamma\times{L,R}) | deterministic evolution |
Definition – A TM computes a partial function (f:\Sigma^\to\Sigma^).
Computation – A sequence of configurations ((q_i, T_i, h_i)) where (h_i) is the head position.
Halting – When (\delta) is undefined for the current symbol.
Why TM?
- Simplicity – minimalistic yet universal.
- Mathematical rigour – allows formal proofs.
- Church–Turing Thesis – any effectively computable function is TM‑computable.
1.2 Formal Languages & Automata Theory
| Model | Language Class | Closure Properties |
|---|---|---|
| Finite Automaton (FA) | Regular | union, concatenation, Kleene star |
| Pushdown Automaton (PDA) | Context‑Free | union, concatenation, Kleene star |
| Turing Machine | Recursively Enumerable | union, concatenation, Kleene star |
Key Theorems
- Pumping Lemma for Regular Languages – proves non‑regularity.
- Myhill–Nerode Theorem – characterizes regularity via equivalence classes.
- Undecidability of the Halting Problem – no TM decides (HALT={ \langle M,w\rangle \mid M \text{ halts on } w}).
1.3 Computational Complexity – From First Principles
1.3.1 Time & Space Complexity
- Time – (T(n) = \max_{x\in\Sigma^n} \text{steps}(M, x)).
- Space – (S(n) = \max_{x\in\Sigma^n} \text{tape cells used}(M, x)).
1.3.2 Complexity Classes
| Class | Formal Definition | Representative Problems |
|---|