Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Foundations and history of AI

Foundations and history of AI: core definitions, key theorems (Turing test, Church–Turing, halting undecidability, Gödel), major paradigms (symbolic vs connectionist), timeline of milestones, and how these shape modern AI practice.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

AI foundations and history explain why certain problems are solvable, why others are not, and why modern methods (for example, those used in machine learning and deep learning) rose or fell. Engineers use these ideas to choose appropriate algorithms, understand limits (decidability and complexity), and to place techniques such as neural networks, expert systems, or search in context.

Key ideas

  • Strong AI vs Weak AI — Strong AI (also called strong artificial intelligence) claims that machines can have minds and consciousness equivalent to humans. Weak AI (also called narrow AI) aims only to perform intelligent tasks without claiming consciousness.

  • Church–Turing thesis — informal but standard statement: any function which would naturally be regarded as computable by effective (mechanical) means can be computed by a Turing machine. Assumptions: “effectively calculable” corresponds to algorithmic procedures; this is a thesis (not a formal theorem) comparing informal notions to formal models of computation.

  • Turing machine (TM) — an abstract model of computation with a finite-state control, read/write head, and an infinite tape divided into cells. Definition: a TM is a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject) with standard meanings (list them if needed in an answer).

  • Undecidability and Halting problem — The halting problem: given (encoded) program P and input x, decide whether P halts on x. The theorem: there is no Turing machine that decides the halting problem for all (P, x). Assumptions: standard (deterministic) Turing-machine model; encoding of programs as inputs.

    • A standard exam derivation: proof by contradiction using a hypothetical decider H and constructing a machine D that leads to a contradiction when D is given its own encoding. (Detailed step-by-step proof appears in Worked examples.)
  • Gödel's first incompleteness theorem — In any consistent, effectively axiomatizable formal system S capable of expressing arithmetic, there exists a sentence G(S) that is not provable in S; moreover, if S is sound for arithmetic (or at least ω-consistent/1-consistent), then G(S) is true in the standard model and ¬G(S) is also not provable. Assumptions: S is recursively (effectively) axiomatizable and sufficiently expressive to represent basic arithmetic; consistency suffices for unprovability of G(S), and ω-consistency or soundness is needed for the “true but not provable” clause.

  • Symbolic (good-old-fashioned AI) vs Connectionist paradigms — Symbolic AI: knowledge represented explicitly with symbols, logical rules and search (examples: logic-based agents, production systems, expert systems). Connectionist AI: knowledge distributed in weights of networks (neural networks); learning by adjusting weights. Draw a diagram to compare: left box "Symbols & rules" with arrows labeled "explicit reasoning, proofs, rules"; right box "Neural nets" with arrows "learning, weights, distributed representation".

  • Historical milestones to remember — short list and why each mattered: Turing (1950) — test and computational view; Dartmouth Workshop (1956) — birth of AI as field; Logic Theorist (Newell & Simon) — symbolic reasoning; ALPAC report (1966) — setback for machine translation; Perceptron (Rosenblatt, 1958) — early neural model; Minsky & Papert perceptron book (1969) — highlighted single-layer perceptron limits; Lighthill report (1973) — UK funding cuts; First AI winter (mid‑1970s); Expert-systems era (1970s–80s) — commercial AI; Backpropagation revival (Rumelhart, Hinton & Williams, 1986) — renewed neural nets; Second AI winter (late 1980s–early 1990s) — expert-systems collapse; Chess and game milestones (Deep Blue 1997); Deep learning resurgence (2012, ImageNet/AlexNet) — large-scale learning successes; AlphaGo (2016) — combining deep nets and search; Large language models era (late 2010s–2020s). Put dates on a horizontal timeline for exam diagrams.

  • Computational complexity and practical limits — define P (decision problems solvable in polynomial time by a deterministic TM) and NP (decision problems whose yes-instances have polynomial-size certificates verifiable in polynomial time by a deterministic TM). Facts to recall: P ⊆ NP and it is unknown whether P = NP. Define NP-complete (in NP and NP-hard under polynomial-time many-one reductions) and NP-hard (at least as hard as NP-complete, not necessarily in NP). Note relation to AI: many search and optimization tasks are NP-hard/NP-complete; this motivates heuristics, approximation algorithms and learning-based methods.

  • Connections to later course topics: precise algorithms and proofs of search complexity appear in "Uninformed search" and "Informed search"; uncertainty formalized in "Uncertainty and Bayesian networks"; learning methods detailed in "Neural-net and genetic learning".

Formulas

N = 1 + b + b^2 + ... + b^d — N is number of nodes in a complete tree with branching factor b and depth d (root at depth 0); unitless; applies when the tree is uniform. Use when estimating search cost.

N = (b^(d+1) - 1)/(b - 1) — exact closed form for b ≠ 1; unitless. For b = 1, N = d + 1. For large d and b > 1, N ≈ b^(d+1)/(b - 1) (dropping the −1 term).

P(A|B) = P(B|A)·P(A) / P(B) — Bayes' theorem; P(·) denotes probability (unitless); applies to events with P(B) > 0. (Bayes is used in probabilistic foundations though full Bayesian networks are later topics.)

No other physics-like SI units apply here: symbols are mathematical.

Worked examples

  1. Prove that the halting problem is undecidable (model exam answer).

    • Statement: There is no Turing machine H that, given encoding ⟨P, x⟩, accepts iff program P halts on input x and rejects iff P does not halt on x.
    • Proof (by contradiction):
      1. Assume H exists and decides halting for every ⟨P, x⟩.
      2. Construct a program D that takes a single input y, and does: "Run H on ⟨y, y⟩. If H says 'halts', then loop forever. If H says 'does not halt', then halt." (D uses H as a subroutine.)
      3. Let d be the encoding ⟨D⟩. Consider the behaviour of D on input d.
        • If H(⟨d, d⟩) predicts D halts on d, then by D's code it will loop forever — contradiction.
        • If H predicts D does not halt on d, then D halts — contradiction.
      4. Both possibilities contradict the correctness of H. Therefore H cannot exist. QED.
    • Marking points: clear statement of decider assumption, construction of D, self-application ⟨D, D⟩, and contradiction.
  2. Long-answer model: Explain the Turing test, its purpose, and two major criticisms.

    • Model answer structure: define the test, explain Turing's reasoning (replace question "Can machines think?" with behaviourist operational test), describe the test process, and give two criticisms with brief justification.
    • Example criticisms: (a) The test measures only linguistic imitation, not internal understanding (Searle's Chinese Room objection argues syntax is not semantics). (b) Passing the test could be achieved by shallow tricks or statistical mimicry (chatbots) without general intelligence.
    • Conclude: The Turing test is historically important as an operational milestone but is insufficient as a definition of intelligence for many researchers.

Common mistakes

  • Mixing up dates or attributing an idea to the wrong person (e.g., saying Backpropagation originated in the 1950s without noting its revival and credit to multiple authors).
  • Equating the Turing test with a formal proof of intelligence — forgetting it is an operational test with philosophical limits.
  • Omitting assumptions when stating Gödel or halting results (must state system is sufficiently expressive / model is Turing-complete).

For your exam

Kinds of questions:

  • Definitions and short notes: define Turing machine, Church–Turing thesis, halting problem, strong/weak AI.
  • Derivations and proofs: prove halting undecidability; outline Gödel's incompleteness idea at high level.
  • Timeline/diagram: draw a labelled timeline highlighting 4–6 milestones and explain why each matters.
  • Comparisons and essays: differences between symbolic and connectionist paradigms; pros/cons and applications.
  • Short numerical estimate: use tree size formulas to estimate search costs (connects to later search topics).

What full-marks answers include:

  • Precise definitions with assumptions (e.g., 'decidable' means exists a TM that halts and answers correctly on all inputs).
  • Complete proof steps for logical theorems (assumption, construction, contradiction, conclusion).
  • Neat diagrams when asked (timeline, Turing test diagram, symbolist vs connectionist block diagram) with labels and brief captions.
  • Clear distinction between similar terms (undecidable vs intractable, strong vs weak AI).

Quick check

  1. What does the Church–Turing thesis claim in one sentence?
  2. State the halting problem in one line.
  3. Give one reason why symbolic AI lost popularity in the late 1960s/70s.

Answers: 1) Any effectively calculable function can be computed by a Turing machine. 2) Decide, given program P and input x, whether P halts on x. 3) In the late 1960s/70s it was mainly connectionist/neural approaches that lost popularity (after Minsky & Papert’s critique of the perceptron and limited hardware); symbolic AI’s major downturn came later (late 1980s–early 1990s) with expert systems’ knowledge-acquisition bottleneck, brittleness, and maintenance cost.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?