P vs NP, Heuristics, Computability & Philosophy of AI · lumen

01 · COMPUTATIONAL COMPLEXITY ZOO

complexity classes: p, np, np-complete & np-hard.

Complexity Theory classifies computational problems according to their inherent difficulty—specifically, the asymptotic time required to solve an instance from scratch versus the time required to verify a candidate solution (certificate).

P refers to Polynomial: the class of decision problems that are tractable, meaning they can be solved deterministically in worst-case polynomial time $\mathcal{O}(n^c)$ or better for some constant $c \ge 0$ . Every P-class problem can also be verified in polynomial time ( $\text{P} \subseteq \text{NP}$ ).

Growth rates in P: $\mathcal{O}(1)$ (Constant), $\mathcal{O}(\log n)$ (Logarithmic), $\mathcal{O}(n)$ (Linear), $\mathcal{O}(n \log n)$ (Log-linear), $\mathcal{O}(n^c)$ (Polynomial).
Canonical Examples: Determining whether a number is prime (AKS primality test), all comparison searches and sorts (Binary Search, Merge Sort), Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall), Minimum Spanning Trees (Prim, Kruskal), and Matrix Multiplication.

NP stands for Non-Deterministic Polynomial (never "Non-Polynomial"): the class of decision problems for which a proposed candidate solution (certificate/proof) can be verified by a deterministic algorithm in polynomial time $\mathcal{O}(n^c)$ , or equivalently solved in polynomial time by a Non-Deterministic Turing Machine.

Intractable NP problems have known deterministic worst-case solving times strictly greater than polynomial ( $> \mathcal{O}(n^c)$ ): exponential $\mathcal{O}(c^n)$ , factorial $\mathcal{O}(n!)$ , or super-exponential $\mathcal{O}(n^n)$ .
Canonical Examples: Travelling Salesman Decision Problem (TSP), Boolean Satisfiability Problem (SAT), 0-1 Knapsack Decision Problem, $N$ -Queens Problem, and Integer Factorisation (verifiable in $\mathcal{O}(n^2)$ by multiplying factors, believed to be in $\text{NP} \setminus (\text{P} \cup \text{NP-Complete})$ ).

NP-Complete problems lie at the exact intersection of NP and NP-Hard ( $\text{NP-Complete} = \text{NP} \cap \text{NP-Hard}$ ). A problem $X$ is NP-Complete iff:

$X \in \text{NP}$ (candidate solutions are verifiable in polynomial time), and
$X \in \text{NP-Hard}$ (every problem in NP can be transformed/reduced to $X$ in polynomial time).

All NP-Complete problems are computationally equivalent up to a polynomial-time factor: if any single NP-Complete problem is solved in polynomial time, then every problem in NP is solvable in polynomial time ( $\text{P} = \text{NP}$ ).

Canonical Examples: SAT (Boolean Satisfiability — the first proven NPC problem via the Cook-Levin Theorem), TSP Decision Problem, 0-1 Knapsack Decision ( $\mathcal{O}(2^n)$ ), Hamiltonian Cycle/Path Decision ( $\mathcal{O}(n!)$ ), $N$ -Queens Decision, and $k$ -Colouring Decision. (Note: Tower of Hanoi requires $\Theta(2^n - 1)$ exponential steps simply to output its move sequence).

NP-Hard is the class of problems that are at least as hard as the hardest problems in NP (every problem in NP reduces to them in polynomial time), but they may or may not belong to NP—meaning they are not required to be decision problems and may not even be verifiable in polynomial time (or computable at all).

Canonical Examples:
- Optimal TSP (Optimisation Version): Finding the minimum tour cost $k$ (verifying optimality requires knowing no shorter tour exists among all $(n-1)!$ tours).
- Chromatic Number $\chi(G)$ (Optimisation Graph Colouring): Finding the minimum number of colours needed for a proper vertex colouring.
- The Halting Problem ( $\text{HALT}_{\text{TM}}$ ): Belongs to NP-Hard ONLY—it is undecidable and cannot be verified or solved in any finite time bound.

FIGURE 01 · EULER DIAGRAM OF COMPLEXITY & COMPUTABILITY CLASSES (UNDER P ≠ NP)

SUMMARY MATRIX · SOLVABILITY VS VERIFIABILITY ACROSS COMPLEXITY CLASSES
COMPLEXITY CLASS	SOLVABLE IN $\mathcal{O}(n^c)$ ?	VERIFIABLE IN $\mathcal{O}(n^c)$ ?	CANONICAL VCE EXAMPLES
P (Polynomial)	Yes (Tractable)	Yes	Merge Sort, Binary Search, Prim's/Kruskal's MST, Dijkstra, Matrix Multiplication, Primality testing
NP (Non-Deterministic Polynomial)	Yes for $\text{P} \subseteq \text{NP}$ ; Unknown/No for $\text{NP} \setminus \text{P}$	Yes (Defining property of NP)	All problems in P, Integer Factorisation, plus all NP-Complete problems
NP-Complete ( $\text{NP} \cap \text{NP-Hard}$ )	No known polynomial algorithm (Intractable, $\mathcal{O}(2^n), \mathcal{O}(n!)$ )	Yes (since $\text{NPC} \subseteq \text{NP}$ )	Boolean SAT, TSP (Decision), 0-1 Knapsack (Decision), Hamiltonian Cycle, $N$ -Queens, $k$ -Colouring (Decision)
NP-Hard	No (Intractable or Undecidable)	May or may not be verifiable in polynomial time	All NP-Complete problems, Optimal TSP (Optimisation), Chromatic Number $\chi(G)$ , Halting Problem (Undecidable, $\notin \text{NP}$ )

02 · COBHAM'S THESIS VS CHURCH-TURING THESIS

soft limits vs hard limits of computation.

Realistic, modern-day physical computers are constrained by the soft limits of computation (time and memory scaling). Theoretical models of computation with unbounded memory—such as the Turing Machine—are constrained only by the hard limits of computation (decidability).

Cobham's Thesis identifies the class of problems that can be feasibly computed on physical hardware with the complexity class $\text{P}$ . Problems whose best deterministic algorithms require super-polynomial time ( $> \mathcal{O}(n^c)$ , such as $\mathcal{O}(2^n)$ or $\mathcal{O}(n!)$ ) are intractable.

While exact brute-force methods hit a soft limit as $n$ grows, we can bypass this barrier by sacrificing guaranteed optimality: using randomised heuristics (such as Simulated Annealing or Hill Climbing) or Machine Learning algorithms to find an approximate, "good-enough" solution in polynomial time.

The hard limits of computation refer to the absolute mathematical impossibility of solving uncomputable (undecidable) problems.

By the Church-Turing Thesis, no matter how fast a processor becomes or how much memory is added, certain problems (such as Alan Turing's Halting Problem, David Hilbert's Entscheidungsproblem, or the Busy Beaver function) admit no algorithmic solution whatsoever.

03 · APPROXIMATING INTRACTABLE PROBLEMS

heuristics: hill climbing & simulated annealing.

A heuristic is any algorithmic technique that is not guaranteed to find the globally optimal solution, but finds a "good-enough" approximate solution in a much faster (tractable) running time. In VCE Algorithmics, primary heuristics include Best-First Search, the A* Algorithm, Hill Climbing, and Simulated Annealing.

1. Hill Climbing (Greedy Local Search)

Hill Climbing is an iterative local-search heuristic that starts at an arbitrary candidate solution and repeatedly moves to the neighbour in its immediate locale with the best evaluation score. It terminates as soon as no neighbour improves upon the current node.

Strength: Extremely simple to implement and uses $\mathcal{O}(1)$ auxiliary state memory (only tracks the current configuration and its immediate neighbours).
Weakness (The Local Optima Trap): Because Hill Climbing never accepts a downhill (worse) move, it frequently gets trapped at a local optimum (a peak higher than all immediate neighbours, or a flat plateau/ridge) and misses the global optimum.

PSEUDOCODE · HILL CLIMBING LOCAL SEARCH GREEDY LOCAL OPTIMA HEURISTIC

ALGORITHM HillClimbing(iterations):
    currentNode <- startNode
    For i from 1 to iterations do:
        neighbours := Get neighbours of currentNode
        nextEval := -infinity
        nextNode := empty
        For x in neighbours (Locale) do:
            If Evaluation(x) > nextEval then:
                nextNode := x
                nextEval := Evaluation(x)
            End If
        End For
        If nextEval <= Evaluation(currentNode) then:
            // Return current node since no strictly better neighbours exist (local optimum reached)
            return currentNode
        Else:
            currentNode := nextNode
        End If
    End For
    return currentNode
End Algorithm

2. Simulated Annealing (Probabilistic Global Search)

Simulated Annealing is a probabilistic metaheuristic designed to escape local optima and approximate the global optimum in a reasonable amount of time. Its name comes from metallurgy, where a metal is heated to a high temperature and then slowly cooled ("annealed") so that atoms have enough thermal energy to escape local crystal defects and settle into a minimum-energy global state.

Generate an initial random candidate solution $s$ and compute its cost $c(s)$ .
Generate a random neighbouring (adjacent) solution $s^*$ and calculate its cost $c(s^*)$ .
Compute the cost difference $\Delta = c(s^*) - c(s)$ (for a minimisation problem):
- If $c(\text{new}) < c(\text{old})$ ( $\Delta < 0$ ), the new solution is better: always move to the new solution (since $e^{-\Delta / T} > 1$ ).
- If $c(\text{new}) > c(\text{old})$ ( $\Delta > 0$ ), the new solution is worse: maybe move to the new solution with Boltzmann acceptance probability:

\Pr(\text{accept worse move}) = e^{-\Delta / T} = \exp\!\left(-\frac{c(\text{solution}^*) - c(\text{solution})}{T}\right)

When temperature $T$ is high (early iterations), $e^{-\Delta / T} \approx 1$ , enabling wide exploration across hills and valleys. As $T$ cools geometrically each iteration (e.g., $T \leftarrow 0.9 \cdot T$ ), the probability of accepting worse moves decays toward $0$ , converging like Hill Climbing near the global optimum.

PSEUDOCODE · SIMULATED ANNEALING PROBABILISTIC METAHEURISTIC

ALGORITHM SimulatedAnnealing(temp, iterations):
    solution <- Randomly Generated Solution
    c() <- Cost Function
    t <- temp
    For i from 1 to iterations do:
        solution* <- Adjacent solution, generated randomly
        delta <- c(solution*) - c(solution)
        pr <- e^(-delta / t)   // e is Euler's constant (2.71828...)
        If pr > random_value between 0 and 1 then:
            solution <- solution*
        End If
        t <- 0.9 * t           // Cooling schedule (can be any decreasing formula)
    End For
    return solution, c(solution)
End Algorithm

04 · CANONICAL COMBINATORIAL & OPTIMISATION PROBLEMS

tsp, n-queens, 0-1 knapsack & graph colouring.

1. The Travelling Salesman Problem (TSP)

In the Travelling Salesman Problem (TSP), a salesman must visit every city in a connected, weighted network exactly once and return to the starting city (forming a Hamiltonian circuit/cycle) with minimum total distance.

"Given a complete weighted graph $G$ and a cost bound $k$ , does there exist a Hamiltonian circuit whose total cost is $\le k$ ?"

Why TSP (Decision) $\in \text{NP}$ (Polynomial Verification Proof): Suppose a candidate tour (proof/certificate) is given. A deterministic verifier checks:

Every vertex is visited exactly once and returns to start: takes at most $\mathcal{O}(n^2)$ time.
Look up and sum the edge weights along the tour: takes at most $\mathcal{O}(n^2)$ time.
Compare the total tour length against $\le k$ : takes $\mathcal{O}(1)$ time.

Total verification time is $2n^2 = \mathcal{O}(n^2)$ (polynomial). Because finding a Hamiltonian circuit is NP-Complete, TSP Decision is NP-Complete.

"Given a complete weighted graph $G$ , find the minimum cost $k$ to complete a Hamiltonian circuit."

This problem is NP-Hard (at least as hard as every problem in NP, and reducible to repeated queries of the Decision Version).

Exhaustive / Brute-Force Analysis: Choosing a start vertex ( $n$ choices), then a second vertex ( $n-1$ choices), and so on yields $n \times (n-1) \times (n-2) \dots = n!$ vertex orderings, or $(n-1)!$ distinct directed cycles from a fixed start vertex. Thus brute-force TSP has worst-case time complexity $\mathcal{O}(n!)$ . (Heuristics such as 2-opt or Christofides' algorithm approximate TSP in polynomial time).

2. The $N$ -Queens Problem

Given an $n \times n$ chessboard, the $N$ -Queens Problem asks whether $n$ queens can be placed on the board so that no two queens attack each other (no two share the same row, column, or diagonal). This decision problem belongs to NP-Complete (when generalised to completion of partial boards) and has no optimisation version.

For $n = 8$ (an $8 \times 8$ board with 64 squares), progressively encoding domain constraints shrinks the brute-force search space by five orders of magnitude before backtracking even begins:

Unconstrained subsets of 8 squares from 64: $\binom{64}{8} = \frac{64!}{8! \times 56!} = 4,426,165,368$ possible ways.
Restricting to 1 queen per row (each of the 8 queens has 8 column choices in its assigned row): $8^8 = 16,777,216$ arrangements.
Permutations of 8 queens (1 per row and 1 per column) (eliminating row and column collisions simultaneously): $8! = 40,320$ permutations.

PYTHON IMPLEMENTATION · N-QUEENS BACKTRACKING SOLVER DEPTH-FIRST STATE-SPACE PRUNING

def n_queens(n):
    board = [[0 for i in range(n)] for j in range(n)]   # Create an n x n board with 0s
    backtrack(0, board, n)                              # Run backtracking from row 0
    for row in board:
        print(row)

def backtrack(row, board, n):
    if row == n:                                        # Base case: all n queens placed safely
        return True
    for col in range(n):
        if safe_move(row, col, board, n):               # Prune branch if position is under attack
            board[row][col] = 'Q'
            if backtrack(row + 1, board, n):
                return True
            board[row][col] = 0                         # Backtrack: undo queen placement
    return False

def safe_move(row, col, board, n):
    for i in range(n):                                  # Check current row
        if i != col and board[row][i] == 'Q':
            return False
    for j in range(n):                                  # Check current column
        if j != row and board[j][col] == 'Q':
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):   # Upper-left diagonal
        if board[i][j] == 'Q':
            return False
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):     # Lower-left diagonal
        if board[i][j] == 'Q':
            return False
    return True

3. The 0-1 Knapsack Problem

Given a set $S$ of $n$ items—each with weight $w_i$ and value $v_i$ —and a knapsack of maximum weight capacity $W$ , the 0-1 Knapsack Problem requires choosing a subset of items where each item is either included ( $1$ ) or excluded ( $0$ ) without splitting items.

Decision Version (NP-Complete): Given items $S$ , target value $V$ , and capacity $W$ , can a total value of at least $V$ be achieved without exceeding weight $W$ ?
Optimisation Version (NP-Hard): Given items $S$ with weights and values, what is the maximum value $V$ obtainable within weight capacity $W$ ?
Brute-Force Power Set Analysis ( $\mathcal{O}(2^n)$ ): Because each of the $n$ items has 2 binary states (in or out of the knapsack), exhaustive search tests the entire Power Set $\mathcal{P}(S)$ of size $2 \times 2 \times \dots \times 2 = 2^n$ , resulting in an intractable $\mathcal{O}(2^n)$ worst-case time complexity.

4. The Graph Colouring Problem (Proper Vertex Colouring)

Let $G = (V, E)$ be a simple undirected graph and $C = \{1, 2, 3, \dots, k\}$ be a set of $k$ colours. A proper vertex colouring assigns a colour $v.\text{colour} \in C$ to every vertex $v \in V$ such that no two adjacent vertices share the same colour:

\forall u \in \text{adj}(v), \quad v.\text{colour} \neq u.\text{colour}

Decision Version ( $k$ -Colouring, NP-Complete for $k \ge 3$ ): Given a graph $G$ and integer $k$ , does $G$ admit a proper vertex colouring using at most $k$ colours?
Optimisation Version (NP-Hard / NP-Complete): Find the chromatic number $\chi(G)$ —the minimum number of colours required to properly colour all vertices of $G$ .

Real-World Applications: Conflict-resolution and allocation problems—such as exam timetabling (subjects with shared students cannot be scheduled in the same slot), seating allocation (incompatible guests cannot sit adjacent), compiler register allocation, and planar map colouring.

Trivial Upper Bound: $\chi(G) \le |V|$ . Equality $\chi(K_n) = |V| = n$ holds iff $G$ is a complete graph $K_n$ .
Four Colour Theorem (Planar Graphs): For any planar graph $G$ , $\chi(G) \le 4$ .
Brooks' Theorem (General Upper Bound): For every connected graph $G$ that is neither a complete graph ( $K_n$ ) nor an odd cycle ( $C_{2m+1}$ ), $\chi(G) \le \deg_{\max}(v)$ (otherwise $\chi(G) \le \deg_{\max}(v) + 1$ ).
Combined Lower & Upper Inequality: Bounded below by the clique/independence ratio ( $\omega(G) \le \chi(G)$ and $\frac{|V|}{K_n} \le \chi(G)$ , where $\alpha(G)$ / $K_n$ denotes the max independent/clique bound in curriculum notation):

\frac{|V|}{K_n} \le \chi(G) \le \deg_{\max}(v)

PSEUDOCODE · GREEDY GRAPH COLOURING HEURISTIC ALWAYS VALID · NOT GUARANTEED OPTIMAL

ALGORITHM GreedyGraphColouring(G = (V, E)):
    // Always produces a valid proper colouring, but optimality depends on vertex ordering
    Initialise C = {c_1}, the set of used colours, with count i = 1
    For each uncoloured vertex v in V do:
        assigned <- False
        For each colour c in C do:
            If colouring v with c creates no conflicts with adj(v) then:
                v.colour <- c
                assigned <- True
                Break
            End If
        End For
        If assigned == False then:
            i <- i + 1
            Add new colour c_i to C
            v.colour <- c_i
        End If
    End For
    return G, C
End Algorithm

05 · FOUNDATIONS OF MATHEMATICAL LOGIC & UNDECIDABILITY

hilbert's program, gödel's incompleteness & the halting problem.

1. Hilbert's Program (1920s Formalism)

In the early 1920s, German mathematician David Hilbert proposed a grand foundational programme—known as Hilbert's Program (or formalism)—to ground all of mathematics in a finite set of axioms written in a precise formal language and manipulated according to well-defined mechanical rules. Hilbert demanded four properties:

Completeness: A proof that all true mathematical statements can be formally proved within the axiomatic system.
Consistency: A proof—using only finitistic reasoning about finite mathematical objects—that no contradiction (paradox) can ever be derived in the formalism of mathematics.

Conservation: A proof that any result about "real objects" obtained using reasoning about "ideal objects" (such as uncountable sets) can also be proved without using ideal objects.
Decidability (The Entscheidungsproblem): There should exist a single finite mechanical algorithm capable of deciding the truth or falsity of any mathematical statement given the axioms.

2. Kurt Gödel's Incompleteness Theorems (1931)

In 1931, logician Kurt Gödel proved that Hilbert's Program can never be achieved for any formal system rich enough to express elementary arithmetic:

First Incompleteness Theorem (Every rich consistent system is incomplete): "Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$ ."
Mechanism (Gödel Numbering & Self-Reference): Gödel encoded every mathematical symbol, formula, and proof in system $F$ as a unique natural number (Gödel numbering). Mirroring the linguistic Liar Paradox ("This statement is false"), he constructed a formal arithmetic statement—the Gödel sentence $G_F$ —asserting: "Statement $G_F$ is not provable in system $F$ ." If $F$ proves $G_F$ , then $F$ proves a false statement (making $F$ inconsistent). Therefore, if $F$ is consistent, $G_F$ is true but unprovable in $F$ .
Second Incompleteness Theorem (No consistent system can prove its own consistency): "For any consistent system $F$ within which a certain amount of elementary arithmetic can be carried out, the consistency of $F$ cannot be proved in $F$ itself."

3. The Halting Problem & The Entscheidungsproblem (Alan Turing, 1936)

While Gödel demolished Completeness and Consistency, Alan Turing and Alonzo Church independently demolished Hilbert's fourth pillar—Decidability (the Entscheidungsproblem)—in 1936.

Hilbert's Original Question: Given an arbitrary formal proof system $\psi$ and statement $S$ , is it possible to algorithmically determine whether $S$ is provable in $\psi$ ?
Turing's Equivalent Restatement (The Halting Problem): Given the description of an arbitrary Turing Machine $T$ and an input string $w$ , can an algorithm determine in advance whether $T$ eventually halts on $w$ or runs forever in an infinite loop?

\text{HALT}_{\text{TM}} = \{ \langle T, w \rangle \mid T \text{ halts on input } w \} \quad \text{is UNDECIDABLE.}

Assume for contradiction that a universal halt-decider $H(P, w)$ exists that always halts and outputs TRUE if program $P$ halts on $w$ , and FALSE if $P$ loops forever on $w$ .
Construct a new adversarial machine $D(P)$ that calls $H(P, P)$ on $P$ 's own source code:
- If $H(P, P) = \text{TRUE}$ , $D$ deliberately enters an infinite while True loop.
- If $H(P, P) = \text{FALSE}$ , $D$ immediately halts.
Feed $D$ into itself by running $D(D)$ :
- If $D(D)$ halts, then $H(D, D)$ returns TRUE, causing $D(D)$ to loop forever.
- If $D(D)$ loops forever, then $H(D, D)$ returns FALSE, causing $D(D)$ to halt immediately.
Both cases yield a logical contradiction ( $D(D) \text{ halts} \iff D(D) \text{ loops}$ ). Therefore, $H$ cannot exist, and $\text{HALT}_{\text{TM}}$ is undecidable.

From formal language theory, the Halting Problem's undecidability also follows by reduction from the TM Acceptance Problem $A_{\text{TM}} = \{ \langle T, w \rangle \mid T \text{ accepts } w \}$ :

The TM Acceptance problem reduces to $\text{HALT}_{\text{TM}}$ .
The TM Acceptance problem is undecidable.
Hence, $\text{HALT}_{\text{TM}}$ is also undecidable.

If $\text{HALT}_{\text{TM}}$ were decidable, then every Turing-recognisable language would be decidable ( $L \text{ is recognisable} \implies L \text{ is decidable}$ ), which is false.

Practical Implication (Static Code Analysis & Rice's Theorem): Because of the Halting Problem, no compiler or automated verification tool can ever determine for every arbitrary program whether it will get trapped in an infinite loop or satisfy any non-trivial semantic property (Rice's Theorem).

06 · MODELS OF COMPUTATION & FORMAL LANGUAGES

church-turing thesis, turing machines & computability.

1. Effectively Calculable & The Church-Turing Thesis (1936)

To prove that no algorithm could solve Hilbert's Entscheidungsproblem, Alan Turing (via Turing Machines) and Alonzo Church (via Lambda Calculus) independently formalised what it means for a method to be an algorithm.

A function or method is effectively calculable iff it satisfies four conditions:

It consists of exact, unambiguous instructions that are finite in length (requiring zero guessing or human intuition).
Given unbounded time and resources, it completes in a finite number of steps.
Its instructions and data are encoded over a finite alphabet (e.g., binary $\{0, 1\}$ ).
It can be executed mechanically by a human working with unlimited time and an unlimited supply of pen and paper.

f \text{ is effectively calculable} \implies f \text{ is computable (by a Turing Machine)}

Any effectively calculable method of computation—whether expressed in Alonzo Church's Lambda Calculus (where functions are defined and applied to arguments), a modern programming language (Python, C++), or cellular automata—is computationally equivalent to a Turing Machine.

2. The Turing Machine (TM) Architecture & Formal 8-Tuple

A Turing Machine (TM) consists of four physical/logical components: (1) an infinite tape divided into discrete cells, each holding a symbol from a finite alphabet; (2) a moveable read/write head that reads the current cell, writes a symbol, and steps Left ( $\text{L}$ ) or Right ( $\text{R}$ ); (3) a state register storing the current state from a finite set; and (4) a finite table of transition instructions.

M = (\Sigma, \Gamma, b, Q, \delta, q_0, q_a, q_r)

$\Sigma$ : The finite input symbol alphabet.
$\Gamma$ : The finite tape alphabet, containing all input symbols plus any extra working symbols written to the tape ( $\Sigma \subseteq \Gamma$ ).
$b \in \Gamma$ : The blank symbol (often written $\sqcup$ ), which fills the infinite tape beyond the input string ( $b \notin \Sigma$ ).
$Q$ : The finite set of all machine states.
$q_0 \in Q$ : The initial (start) state.
$q_a \in Q$ : The halting accept state (sometimes written as an accepting set $F$ ).
$q_r \in Q$ : The halting reject state ( $q_r \neq q_a$ ).
$\delta$ : The state transition function mapping a non-halting state and current tape symbol to a next state, overwritten symbol, and head direction:

\delta: (Q \setminus \{q_a, q_r\}) \times \Gamma \to Q \times \Gamma \times \{\text{L}, \text{R}\}, \qquad \delta(q_{\text{cur}}, w_{\text{cur}}) = (q_{\text{next}}, w_{\text{overwrite}}, \text{L or R})

Three Possible Outcomes on Input $w$ : A Turing Machine can (1) Halt and Accept (reach $q_a$ ), (2) Halt and Reject (reach $q_r$ ), or (3) Run Forever in an infinite loop. A Turing Machine that halts on all inputs (never loops forever) is called a Decider.

3. TM Configurations, Notation & Worked State Diagram

A TM Configuration is an instantaneous snapshot capturing: (1) the current state $q$ , (2) the full contents of the tape, and (3) the exact position of the tape head.

Configuration String Notation: The state symbol $q$ is inserted inline into the tape string at the head position (e.g., abqabb; note the HESS notes remark that the current head is adjacent to where $q$ is placed, with starting configuration $q_0 w$ ).
Yield Relation ( $C \implies C'$ ): Applying $\delta$ transforms configuration $C$ into $C'$ :
- Right move: $u q b v \implies u c t v$ (written in HESS notes as $u q b v \implies u c q v \iff \delta(q, b) = (t, c, \text{R})$ )
- Left move: $u a q b v \implies u t a c v$ (written in HESS notes as $u q b v \implies t u c v \iff \delta(q, b) = (t, c, \text{L})$ )
- Left boundary rule: $q b u v \implies t c u v \iff \delta(q, b) = (t, c, \text{L})$ (the head cannot move left past the first tape cell).
String Acceptance: $M \text{ accepts } w \iff C_1 \implies C_2 \implies \dots \implies C_k$ , where $C_1 = q_0 w$ and $C_k$ is in accept state $q_a$ (or $F$ ).
State Diagram Shorthand: For $M = (\Sigma, \Gamma, Q, \delta, q_0, F, \sqcup)$ with $\Sigma = \Gamma = \{0, 1\}$ , $Q = \{A, B, C\}$ , $q_0 = A$ , $F = \{C\}$ , an edge labelled $a \to b, \text{R}$ represents $\delta(q_0, a) = (q_1, b, \text{R})$ . If the TM does not overwrite the tape symbol, we shorten it to $a \to \text{R}$ .

FIGURE 02 · TURING MACHINE TAPE ARCHITECTURE & STATE DIAGRAM RECOGNISING L = { w | w HAS SUBSTRING 11 }

4. Why Turing Machines Are More Powerful Than FSAs & PDAs

While Finite State Automata (FSAs) recognise regular languages and Pushdown Automata (PDAs) recognise context-free languages such as $\{0^n 1^n\}$ , neither can recognise the context-sensitive language:

L = \{ 0^n 1^n 2^n \mid n \in \mathbb{N}_0 \}

Because a Turing Machine can move its head both Left and Right and overwrite tape cells with markers, it easily decides $L = \{0^n 1^n 2^n\}$ (or equivalently $a^n b^n c^n$ ). Furthermore, by Theorem T1 (Determinism Equivalence), every Non-Deterministic Turing Machine (NTM) has an equivalent Deterministic Turing Machine (DTM)—non-determinism adds zero extra computability power to a Turing Machine.

HIGH-LEVEL TM PSEUDOCODE · DECIDING L = { 0^n 1^n 2^n } CROSS-OFF TAPE ALGORITHM

TM M (on input tape):
    // 1. Preprocessing input
    Move head Right until non-blank character
    Check if tape is of the regular form 0*1*2* (if not, Reject)

    // 2. Iterative cross-off pass
    While unmarked symbols remain:
        Return head to start of tape
        Move head Right
        Replace one instance each of '0' ('a'), '1' ('b'), and '2' ('c') with 'x'
        If any of the three symbols is missing while others remain, Reject

    // 3. Verification
    If crossed out the last instance of '0', '1', and '2' together, Accept

5. Computability: Functions, Sets, Numbers & Uncountable Sets

Computable Function: A function $f: X \to Y$ over $X = \{x_1, \dots, x_n\}$ is computable iff there exists a TM $M$ that, when given encoding $\langle x_i \rangle$ as input, halts with $\langle f(x_i) \rangle$ on its tape.
Computable Set: A set $X$ is computable iff its associated language $L = \{\langle x_1 \rangle, \langle x_2 \rangle, \dots\}$ is Turing-decidable:

\text{Computability} \iff \text{Decidability}, \qquad \text{Undecidable} \iff \text{Uncomputable}

Computable Number (Marvin Minsky): "A computable number is one for which there is a Turing machine which, given $n$ on its initial tape, terminates with the $n$ -th digit of that number encoded on its tape" (or computes a rational Cauchy approximation within $2^{-n}$ ).
The $3.14$ vs $\pi$ Finite-State Dilemma: A terminating decimal like $3.14$ can be printed by a trivial Turing Machine using a hard-coded chain of states that writes 3, moves Right, writes ., moves Right, writes 1, moves Right, writes 4, and halts. However, when we try to compute an irrational real number like $\pi$ —which has infinitely many non-repeating digits—we cannot assign one state per digit because a Turing Machine is restricted to a finite set of states $Q$ . Instead, $\pi$ is computable because a finite-state algorithm (using loops over a convergent series) can take any index $n$ on its initial tape and halt after outputting the first $n$ digits (or the $n$ -th digit) in finite time.
Uncountable Sets Are Not Computable: Because every Turing Machine is described by a finite string over a finite alphabet, the set of all Turing Machines is countably infinite ( $\aleph_0$ ). By Cantor's diagonalisation argument, the set of real numbers $\mathbb{R}$ and the set of all finitary functions $f: \mathbb{N} \to \mathbb{N}$ are uncountable ( $2^{\aleph_0}$ ). Therefore, most real numbers and functions are uncomputable—canonical examples include the Busy Beaver function and Kolmogorov complexity.

07 · HISTORY & PHILOSOPHY OF ARTIFICIAL INTELLIGENCE

timeline of ai, the turing test & the chinese room argument.

Artificial Intelligence (AI) is intelligence demonstrated by machines running algorithms that perceive their environment, adapt, reason, and take actions to maximise the chance of achieving goals. Machine Learning (ML) is a subset of AI where machines are not explicitly programmed rule-by-rule, but instead learn patterns from large volumes of data.

HISTORICAL TIMELINE OF ARTIFICIAL INTELLIGENCE · 1950s TO PRESENT DAY
ERA / YEAR	LANDMARK DEVELOPMENTS & PARADIGMS	COMPUTATIONAL & HISTORICAL SIGNIFICANCE
1950s (1950 & 1956)	Alan Turing's "Computing Machinery and Intelligence" (1950); The Logic Theorist (1956)	Turing proposes the Turing Test; computers are room-sized mainframes with tiny memory limited to defence, big tech, and universities. The Logic Theorist becomes the first proof-of-concept AI program mimicking human theorem-proving.
1950s – 1970s	General Problem Solver (GPS), ELIZA chatbot, and The AI Winter (1974–1980)	Hardware becomes smaller, faster, and cheaper; GPS and ELIZA show early promise in problem-solving and natural language processing. However, combinatorial explosion and limited progress cause government funding to dry up from 1974 to 1980 (The AI Winter).
1980s	Searle's Chinese Room Argument (1980), Expert Systems & Deep Learning revival	John Searle publishes his rebuttal to Strong AI (1980). Funding returns via commercial Expert Systems—programs encoding domain-expert rules to advise non-experts—alongside rediscovery of multi-layer neural network training.
1990s – Present	Windows Speech Recognition, IBM Deep Blue (1997) & Google AlphaGo (2017)	Storage limits vanish; speech recognition ships in Microsoft Windows. In 1997, IBM's Deep Blue (symbolic AI / heuristic search) defeats chess world champion Garry Kasparov. In 2017, Google's AlphaGo defeats Go champion Ke Jie.

Strong AI vs Weak AI & The Turing Test (1950)

Strong AI Hypothesis: A suitably programmed machine can develop genuine human cognitive abilities, semantic understanding, intelligence, and (arguably) consciousness—meaning its "mind" is in essence no different from a biological human mind, capable of teaching itself to solve novel problems across domains.
Weak AI (Narrow AI): Uses advanced algorithms to accomplish specific problem-solving or reasoning tasks (e.g., playing chess or classifying images) without achieving self-awareness, consciousness, or the full range of human cognition.

A human interrogator communicates via text-only messages with two hidden subjects—one human and one computer—who both try to convince the interrogator they are human. According to Alan Turing, if the interrogator cannot reliably differentiate the machine from the human, the computer is capable of thinking.

The test asks: (1) Can a suitably programmed computer imitate human language and behaviour? (2) Is there a theoretical limit on what a computer can input or output in language? (A theoretical Turing Machine with infinite time and memory has no upper bound on state space).

John Searle's Chinese Room Argument (1980)

Philosopher John Searle formulated the Chinese Room Argument as a direct refutation of the Strong AI Hypothesis and the Turing Test, arguing that passing a behavioural test via formal symbol manipulation (syntax) never suffices for genuine mental understanding or meaning (semantics).

The Thought Experiment: Searle (who knows zero written or spoken Chinese) is locked in a room with a large batch of Chinese writing and an English rulebook that correlates one set of formal Chinese symbols with another purely by their shapes. When native Chinese speakers slide questions in Chinese under the door, Searle follows the English rules to output indistinguishable Chinese responses. To observers outside, the room passes the Turing Test for Chinese—yet Searle neither understands a single word of Chinese nor is "thinking" in Chinese. Likewise, a computer running a program only manipulates uninterpreted syntax without semantic understanding.

(A1) Programs are formal (syntactic).
(A2) Minds have mental contents (semantics).
(A3) Syntax by itself is neither constitutive of nor sufficient for semantics.
(A4) Brains cause minds.

(C1) Programs are neither constitutive of nor sufficient for minds.
(C2) Any other system capable of causing minds would have to have causal powers (at least) equivalent to those of brains.
(C3) Any artifact that produced mental phenomena, any artificial brain, would have to be able to duplicate the specific causal powers of brains, and it could not do that just by running a formal program.
(C4) The way that human brains actually produce mental phenomena cannot be solely by virtue of running a computer program.

FOUR CLASSIC OBJECTIONS TO THE CHINESE ROOM & SEARLE'S REBUTTALS
OBJECTING ARGUMENT	CORE CLAIM OF THE OBJECTION	JOHN SEARLE'S COUNTER-REPLY
1. The Systems Argument (Systems Reply)	While the person inside the room does not understand Chinese in isolation, the entire room as a holistic system (person + rulebook + ledger + paper) understands Chinese—just as no single neuron understands English, but the whole human does.	Let the man memorise the entire rulebook and perform all calculations in his head outdoors. Now "the man" and "the system" are the exact same object—yet the man still understands zero Chinese, so the system doesn't either.
2. The Robot Argument (Robot Reply)	Words derive semantic meaning from causal interaction with the real world (e.g., seeing fire for 火). If the Chinese Room were placed inside a robot body with camera eyes and motor limbs, its symbols would acquire grounded meaning.	Camera and sensor inputs simply arrive inside the room as yet more uninterpreted formal symbols, and outputs go to motors. The person in the room "doesn't see what comes into the robot's eyes" and still only follows formal syntax rules without knowing what the symbols mean.
3. The Brain Simulator Argument	A computer that simulates not merely high-level rules, but the exact neurobiological structure of a native Chinese speaker's brain down to every synapse firing must genuinely understand Chinese.	A formal simulation of neuron firings does not reproduce the actual physical and chemical causal properties of biological human brains (simulating the formal structure of a brain no more produces consciousness than simulating a stomach digests food).
4. The Other Minds Argument	We never directly experience another human's consciousness; we infer that other people think purely from their external behaviour. By parity of reasoning, we must grant intelligence to a machine exhibiting equivalent behaviour.	We attribute consciousness to other humans not solely from behaviour, but because we know they share our biological construction formed during gestation—which a synthetic machine does not replicate.

08 · MACHINE LEARNING ARCHITECTURES & ETHICAL GOVERNANCE

support vector machines, neural networks & ethics of ai.

1. Support Vector Machines (SVMs)

A Support Vector Machine (SVM) is a supervised binary classification algorithm. Given two classes of labelled training data plotted in an $N$ -dimensional feature space, the SVM computes an $(N - 1)$ -dimensional decision boundary (hyperplane)—a line in 2D, a plane in 3D—that separates the two classes with the maximum margin.

Maximum-Margin / Optimal Hyperplane: The hyperplane that maximises the perpendicular distance from the boundary to the nearest data point on each side.
Support Vectors: The critical data points from each class that lie closest to the decision boundary (on the margin gutters). Because the decision function depends only on these support vectors, SVMs are highly memory-efficient.
Kernel Transformations ( $\phi$ ): When data is not linearly separable in its original input space, a kernel transformation function $\phi(x)$ lifts the data into a higher-dimensional space where a linear hyperplane can separate the classes—common examples include polynomial kernels ( $\phi(x) = x^c$ , such as $\phi(x) = x^2$ ) and modular kernels ( $x \bmod 3$ ).
Canonical Applications:
1. Image recognition, such as detecting cancerous cells based on millions of medical images.
2. Predicting future driving routes with a well-fitted regression model.

FIGURE 03 · SVM MAXIMUM-MARGIN HYPERPLANE WITH SUPPORT VECTORS (LEFT) & POLYNOMIAL KERNEL TRANSFORMATION φ(x) = x² (RIGHT)

2. Neural Networks & Deep Learning

Deep Learning is a subfield of Machine Learning built on Artificial Neural Networks (ANNs): layered graphs of interconnected artificial neurons comprising an input layer, one or more hidden layers (where "deep" refers to the depth of hidden layers), and an output layer.

Feedforward vs Backpropagation: In a feedforward neural network, signals flow strictly forward from input to output with no loops. Networks with feedback links that propagate error signals backward from output to hidden/input layers use backpropagation.
Perceptron (Step-Function Binary Classifier): Accepts weighted inputs $x_1, x_2, \dots, x_n$ with weights $w_1, w_2, \dots, w_n$ and outputs a hard binary decision ( $0$ or $1$ ). For linearly separable data, its decision boundary is the hyperplane: $w_1 x_1 + w_2 x_2 + \dots + w_n x_n - \text{bias} = 0$
Sigmoid Neuron (Smooth Real-Valued Output): Instead of a discontinuous step function, a sigmoid neuron outputs a smooth real number strictly between $0$ and $1$ using the logistic sigmoid function, allowing small weight adjustments to produce smooth changes in output: $S(x) = \frac{1}{1 + e^{-x}}$

A dataset is partitioned into subsets called folds (some folds used for training, others held out for testing). Across many full passes over the training set (epochs), the network compares its predicted output $A$ against the true label using a loss function $L$ (commonly Mean Squared Error / variance) and updates weights at a learning rate $\eta$ (Greek letter eta).

Gradient Descent & Stochastic Gradient Descent (SGD) iteratively minimise the multivariable loss function $L$ by computing the partial derivative of the loss with respect to each weight $w$ via the calculus Chain Rule:

\frac{dL}{dw} = \frac{dL}{dA} \times \frac{dA}{dw}

where $L$ is the Loss Function, $w$ is the weight of a given input, and $A$ is the neuron's Activation value (output).

COMPARATIVE ANALYSIS · SUPPORT VECTOR MACHINES (SVMs) VS NEURAL NETWORKS
MODEL	ADVANTAGES (PROS)	DISADVANTAGES (CONS)
Support Vector Machines (SVMs)	Highly effective on multi-feature data (financial, medical, cancer cell imagery). Significantly faster to train than Neural Networks. Effective even when the number of features exceeds the number of data points. Memory-efficient: decision boundary uses only a subset of training points (support vectors).	Prone to overfitting if the number of features is vastly larger than the number of data points. Does not directly output probability estimates of classification confidence. Requires complete supervised labelling of input training data. Directly applicable only to binary classification.
Neural Networks (Deep Learning)	Makes use of all training data (no data points are discarded), yielding higher accuracy on massive, well-labelled datasets. Accuracy continues to scale upward as more training data is fed. Effective when no explicit rule-based algorithm is known for solving a complex perceptual task.	Requires significantly more training data than SVMs. Opaque ("black box"): extremely difficult to inspect or trace the internal "train of thought". Computationally much slower to train than SVMs.

3. Ethics of Artificial Intelligence

As AI systems govern high-stakes decisions in finance, healthcare, justice, and media, VCE Algorithmics evaluates AI ethics across three core criteria—Transparency, Responsibility, and Incorruptibility—alongside societal impacts on information integrity and labour:

Transparency (What is going on behind the process?): An AI must maintain a traceable chain of processes so harms can be audited back to their root cause. For example, if a rejected home-loan applicant sues a bank for racial bias, an opaque multi-layer deep neural network makes it nearly impossible to audit how or why the model weighed race, gender, or postcode.
Responsibility (Who takes the blame?): When autonomous AI systems cause catastrophic harm, legal and ethical frameworks must establish clear accountability through regulations co-designed by engineers, lawmakers, and civil society.

Incorruptibility & Personal Data: Datasets containing Personally Identifiable Information (PII) must be protected against misuse at the design stage, and productivity profits generated from public personal data must be equitably shared.
Three Sources of Algorithmic Bias:
1. Existing bias: Pre-existing social, institutional, or historical prejudices embedded in the training data.
2. Technical bias: Distortions introduced by hardware constraints, sampling flaws, or mathematical algorithm design.
3. Emergent bias: Bias arising after deployment as real-world populations, cultural contexts, or user behaviours shift.
Fake News & The Automated Workplace: AI-driven social feeds enable bad actors to micro-target populations with political propaganda, requiring defensive AI detection. Meanwhile, workplace automation displaces routine labour while augmenting other roles, requiring governments, employers, and AI firms to coordinate worker retraining and fair compensation.

09 · ACTIVE VERIFICATION & EXAM MASTERY

worked self-checks & synthesis checklist.

SELF-CHECK 01 · Why is the Decision Version of TSP in NP-Complete, whereas Optimal TSP and the Halting Problem are in NP-Hard?

To belong to NP (and therefore NP-Complete), a problem must be a decision problem whose candidate solution (certificate) can be verified deterministically in polynomial time $\mathcal{O}(n^c)$ . Given a proposed TSP tour and bound $k$ , we can check that every vertex is visited once and sum the edge weights in $\mathcal{O}(n^2)$ time to verify whether total cost $\le k$ .

By contrast, Optimal TSP asks for the minimum possible tour cost; verifying that no strictly shorter tour exists cannot be done in polynomial time from a single tour certificate alone, placing it in NP-Hard. Finally, the Halting Problem is undecidable—it cannot be solved or verified in any finite time bound—so it lies in NP-Hard only ( $\text{NP-Hard} \setminus \text{NP}$ ).

SELF-CHECK 02 · How does Simulated Annealing overcome the primary limitation of Hill Climbing?

Hill Climbing is purely greedy: it only moves to a neighbour if $\text{Evaluation}(x) > \text{Evaluation}(\text{currentNode})$ , causing it to terminate prematurely whenever it hits a local optimum.

Simulated Annealing introduces a temperature parameter $T$ and accepts worse neighbours ( $\Delta = c(\text{new}) - c(\text{old}) > 0$ ) with Boltzmann probability $\Pr = e^{-\Delta / T}$ . At high initial temperatures, the algorithm freely climbs out of local valleys; as $T$ cools ( $T \leftarrow 0.9 T$ ), acceptance of worse moves decays toward zero, allowing convergence near the global optimum.

SELF-CHECK 03 · Distinguish how Gödel's Incompleteness Theorems and Turing's Halting Problem each refuted Hilbert's Program.

Hilbert's Program required mathematics to be Complete, Consistent, Conservative, and Decidable. In 1931, Kurt Gödel used Gödel numbering and self-referential paradoxes to prove that any consistent formal system capable of elementary arithmetic is incomplete (First Theorem: there exist true statements unprovable in the system) and cannot prove its own consistency (Second Theorem).

In 1936, Alan Turing and Alonzo Church refuted Hilbert's fourth requirement—Decidability (the Entscheidungsproblem)—by defining effectively calculable functions (Church-Turing Thesis) and proving that $\text{HALT}_{\text{TM}}$ is undecidable.

I can define and classify problems into P, NP, NP-Complete ( $\text{NP} \cap \text{NP-Hard}$ ), and NP-Hard, and contrast Soft Limits (Cobham's Thesis) with Hard Limits (Church-Turing Thesis).
I can trace Hill Climbing and Simulated Annealing ( $\Pr = e^{-\Delta/T}$ ), and state the decision vs optimisation complexities for TSP ( $\mathcal{O}(n!)$ ), $N$ -Queens ( $\binom{64}{8} \to 8^8 \to 8!$ ), 0-1 Knapsack ( $\mathcal{O}(2^n)$ ), and Graph Colouring ( $\frac{|V|}{K_n} \le \chi(G) \le \deg_{\max}(v)$ ).
I can state the four goals of Hilbert's Program, both of Gödel's Incompleteness Theorems, the 8-tuple definition and configurations of a Turing Machine, and prove why the Halting Problem and uncountable sets are uncomputable.
I can explain the Turing Test, Searle's Chinese Room Argument (axioms A1–A4, conclusions C1–C4, and all four objections + replies), SVMs (hyperplanes, support vectors, kernels $\phi$ ), Neural Networks (Perceptron vs Sigmoid $S(x) = \frac{1}{1+e^{-x}}$ , Chain Rule $\frac{dL}{dw} = \frac{dL}{dA} \times \frac{dA}{dw}$ ), and the three pillars of AI Ethics.