Overview

Textbook: Introduction to the Theory of Computation, Michael Sipser

Note that the course only included up to Chapter 5, and I self-studied the rest

Shit, this is crowded.

“Wtf, man. I just wanted to learn how to program video games.”

This field of research started in the 1930s, before computers existed, when logicians wanted to understand computation. The big question is whether all mathematical problems can be solved in a systematic way?

A problem is a single question with infinitely many instances. Everything can be converted into questions about strings…

These subjects have applications to compiler design, computer architecture, processing that uses a finite-state machine, and theories of programming languages

We can divide the theory of computation into,

1. Automata Theory - deals with definitions and properties of different types of computation models
2. Computability Theory - deals with solvable and unsolvable problems
3. Complexity Theory - asks what makes some problems hard and some problems easy

Is this course useful for developers? Depends who you ask! But Antonella says yes

Computational Problems

A problem is a set of strings that we would like to distinguish

• For each candidate string, we decide whether it is in the target set
• The input to our machines are always strings
• We can convert any format to a string

A string is made up of symbols taken from a finite set called an alphabet
The closure of an alphabet $\Sigma$ is denoted as ${\Sigma }^{\ast }$

The reversal of a string $x$ is denoted $x^R$
All strings of length $n$ are denoted as ${\Sigma }^n$
$ϵ$ is the null string

A language $L$ is a set of strings over an alphabet $\Sigma$, i.e. $L\subseteq {\Sigma }^{\ast }$
$L$ can be finite or countably infinite
$\varnothing$ is a language, and so is $\{ϵ\}$

Since languages are sets, we can use standard set operations $A\cup B$, $A\cap B$, and $\bar{A}$
We also use the reversal operator $A^R$ and the concatenation operator $A\circ B$ (which consists of all symbols which are a concatenation of something in $A$ and $B$)

We will define classes of languages based on which machines can recognize them,

• Regular
• Context-free
• Recursively-enumerable
• Undecidable