CMPUT 474: Midterm Review
Review of first half: Restricted models of computation
Dale Schuurmans
1 Introduction
Three fundamental lessons of computation
1. consequences of simple rules/mechanisms
2. finiteness vs infiniteness
Cantor:
• cardinality: 1 to 1 correspondence
• #(P(S)) > #(S)
3. consequences of self-referability
2 Emergence of computation
• 500 BC-1800s: the struggle representing real numbers
• Late 1800s paradoxes: Weierstrauss function, Russell paradox, Vitali set
• 1900 hope: Hilbert, Russell
• 1930s dies: Church, Gödel, Turing
• 1935 birth of computation
• 1940s; experimental computation
• 1950-70s: commoditization of computation
• 1980s: personal computers
• 1990s: internet
• 2000s: social & media
• 2010s: AI
• now?
1
Review of first half: Restricted models of computation
Dale Schuurmans
1 Introduction
Three fundamental lessons of computation
1. consequences of simple rules/mechanisms
2. finiteness vs infiniteness
Cantor:
• cardinality: 1 to 1 correspondence
• #(P(S)) > #(S)
3. consequences of self-referability
2 Emergence of computation
• 500 BC-1800s: the struggle representing real numbers
• Late 1800s paradoxes: Weierstrauss function, Russell paradox, Vitali set
• 1900 hope: Hilbert, Russell
• 1930s dies: Church, Gödel, Turing
• 1935 birth of computation
• 1940s; experimental computation
• 1950-70s: commoditization of computation
• 1980s: personal computers
• 1990s: internet
• 2000s: social & media
• 2010s: AI
• now?
1
