CS365 Course Notes

Professor: Eric Blais | Lecture Content

Introduction

Question

What questions can computers solve?

This is a broad question, but throughout the course we will obtain remarkably definite answers to it.

Definition

Problem: Task where for each possible input to the problem, there is one or more valid outputs that is to be produced.

This idea of a problem is general enough to capture anything we want to do on a computer, but we start with two simplifying restrictions.

Simplifying Restrictions

Simplifying Restriction 1: We only consider problems whose inputs are binary strings.

We use $\{0,1\}$ to denote two elements of the binary alphabet, and to denote the set of string that contain exactly $n$ binary symbols, we use $\{0,1{\}}^n$.

The unique string in $\{0,1{\}}^0$ is the empty string, which is denoted by $\epsilon$.

We can write $\{0,1{\}}^{\ast }={\bigcup }_{n\ge 0}\{0,1{\}}^n$ to denote the set of all possible binary strings.

The first simplifying restriction states that the only problems we will consider are those whose inputs are $\{0,1{\}}^{\ast }$. This is a basic observation, but will be extremely useful.

Here is a proposition that makes this claim more precise.

Proposition

For every finite set $\mathcal{X}$ with $k$ elements, there is a one-to-one encoding function $h:\mathcal{X}\to \{0,1{\}}^{\lceil \log k\rceil }$.

Proof: Fix any ordering $a_1,a_2,\dots ,a_k$ of the elements of $\mathcal{X}$. Then define the encoding function $h$ that maps $a_i$ to the string that gives the binary representation of $i$>

Simplifying Restriction 2: We only consider decision problems, where there is exactly one valid output for each input. This output is either ‘yes’ or ‘no’.

In other words, in a decision problem, the output on every input to the problem is exactly one of the elements in $\{0,1\}$.

This is more restrictive than our first restriction.

Functions and Languages

With the two simplifying restrictions in place, a decision problem where all the inputs are binary strings of length $n$ can be described with a Boolean function

$$\begin{array}{r}f:\{0,1{\}}^n\to \{0,1\}\end{array}$$

where for each $x\in \{0,1{\}}^n$, the value $f(x)$ represents the valid output for input $x$.

However we want to consider problems where all inputs don’t necessarily have the same length. Such problems can be represented by a family of Boolean functions, or equivalently, by languages that we represent as subsets

$$\begin{array}{r}L\subseteq \{0,1{\}}^{\ast }\end{array}$$

Notice that for any $n\ge 0$, the set of inputs of length $n$ in a language $L$ can be represented with the Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ defined by setting $f(x)=1⟺x\in L$.

Similarly, any family of Boolean functions $\{f_n{\}}_{n\ge 0}$ where $f_n:\{0,1{\}}^n\to \{0,1\}$ for each $n\ge 0$ corresponds to the language $L={\bigcup }_{n\ge 0}{f}_n^{-1}(1)$.

Cardinality of Languages

Counting arguments are useful in establishing fundamental limits of computers.

Definition

A set $S$ is finite if there is a one-to-one mapping between the elements of $S$ and the elements in the set $\{1,2,\dots ,n\}$ for some $n\ge 0$. Otherwise, $S$ is an infinite set (MATH239).

Definition

A set $S$ is countable if there is a one-to-one mapping between the elements of $S$ and the set of natural numbers $\mathbb{N}=\{1,2,3,\dots ,\}$. Otherwise $S$ is uncountable.

For any fixed value of $n$, the set of binary strings $\{0,1{\}}^n$ is finite. The set $\{0,1{\}}^n$ of all binary strings is infinite, and it is countable.

Proposition

The set $\{0,1{\}}^{\ast }$ is countable.

Proof: Consider $h:\{0,1{\}}^{\ast }\to \mathbb{N}$ where for each $x\in \{0,1{\}}^{\ast }$, we define $h(x)$ to be the natural number with binary representation $1x$. We use $1x$ to denote string concatenation, where we add $1$ at the front of the string $x$. The mapping $h$ is one-to-one $■$.

This implies that the set of strings in any language is countable. The set of all languages is uncountable.

Theorem

The set of all languages is uncountable.

Proof:

This proof is an example of a diagonalization argument.

Assume for contradiction that the set of all languages is countable. Then we can list the set of languages in some order $L_1,L_2,L_3,\dots$

We can build a table whose columns are labelled by the strings in $\{0,1{\}}^{\ast }$ in lexicographical order and rows are labelled by the languages $L_1,L_2,L_3,\dots$, in the order we just defined. For each cell $(L_k,x)$ in the table, enter a $1$ in the cell if $x\in L_k$ and $0$ otherwise. The table will look like:

	$\epsilon$	$0$	$1$	$00$	$01$	$10$	$\cdots$
$L_1$	$0$	$0$	$0$	$0$	$0$	$0$	$\cdots$
$L_2$	$1$	$0$	$0$	$0$	$0$	$0$	$\cdots$
$L_3$	$0$	$1$	$1$	$0$	$0$	$1$	$\cdots$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$\ddots$

Consider the language $D$ that we obtain by looking at the diagonal entries of this table, and using their negation to determine if the corresponding string is in $D$.

Namely, if $x$ is in the $k$th string in the lexicographic ordering of $\{0,1{\}}^{\ast }$, then $x\in D⟺x\notin L_k$.

$D$ is a language, so by our assumption, there is a value $n\in \mathbb{N}$ such that $D=L_n$ is the $n$th language in our list.

Let $x$ denote the $n$th string in the lexicographical order of $\{0,1{\}}^{\ast }$. But then $x\in D$ holds if and only if $x\notin L_n$, so $D\ne L_n$. This is a contradiction, so the set of all languages must be uncountable $■$.

First Uncomputability Result

We can use the last two results to obtain a result regarding the limitations of computers.

Proposition

$\exists L$ for which there is no program that accepts each input $x\in \{0,1{\}}^{\ast }⟺x\in L$.

Assume for the contrary, there is a program that accepts exactly the set of strings in that language. Then there is a map from the set of all languages to the set of programs. But every program can be represented as a binary string, so there is a mapping from the set of all languages to the set of Boolean string $\{0,1{\}}^{\ast }$. But since $\{0,1{\}}^{\ast }$ is countable, there is a mapping from the set of all languages to $\mathbb{N}$. This is a contradiction to our previous theorem.

As a result, for any fixed machine model, there are decision problems that cannot be computed by algorithms in this model.

However, there are two reasons to be unsatisfied with this result.

First, the result is non-constructive. It tells us that there do exist problems that can’t be solved by computers, but doesn’t tell us anything about what these uncomputable problems might be. It could be that we can’t even describe these uncomputable problems.

Second, this result says nothing about languages that are uncomputable by all machine models simultaneously. It leaves open the possibility that we can solve every problem with computers, as long as we are allowed to build different types of computers for each problem.

Turing Machines

We know that for every fixed machine, $\exists$ a language that cannot be computed by algorithms for that specific machine.

We will identify an explicit language that cannot be computed by algorithms over any machine model.

Deterministic 1-tape Turing machine

Two main components

• Machine with a finite number of possible internal states
• Infinite tape split up into squares

Each square contains exactly one symbol. The machine has a tape head that is always positioned over one of the squares of the tape.

At each step in the execution, the machine uses its internal state along with the symbol on the square of the tape that is under the tape head to determine the next action.

The action consists of the internal state it goes to, the symbol overwritten over the previous symbol on the square of the tape under the tape head, and a movement of left or right to the square adjacent to the current one in the tape.

There are two special actions that it can take to halt, one accepts and one rejects.

This is covered in CS245.

Definition

A deterministic one-tape Turing machine is an abstract machine described by the triple

$$\begin{array}{r}M=(m,k,\delta )\end{array}$$

with $m$, $k\ge 1$ where

• $\mathbf{Q}=\{1,2,\dots ,\mathbf{m}\}$ is the set of internal states,
• $\Gamma =\{\square ,0,1,2,\dots ,k\}$ is the tape alphabet, and
• $\delta :\mathbf{Q}\times \Gamma \to (\mathbf{Q}\cup \{\mathbf{A},\mathbf{R}\})\times \Gamma \times \{L,R\}$ is the transition function.

The state 1 denotes the initial state of the Turing machine $M$.

We need to keep track of its internal state, the current string on the tape, and the position of the tape head on the tape. We call this information the configuration of a Turing machine. It can be represented conveniently in the following way.

Definition

Configuration of a Turing machine is a string $w\mathbf{q}y$

• $\mathbf{q}\in \mathbf{Q}\cup \{\mathbf{A},\mathbf{R}\}$
• $wy\in {\Gamma }^{\ast }$ is the current string on the tape, and
• the position of the tape head is on the first symbol of $\mathbf{y}$.

Two configurations are equivalent when they are identical (up to blank symbols at the beginning of $\mathbf{w}$ or end at the end of $\mathbf{y}$). In other words, they satisfy

$$\begin{array}{r}w\mathbf{q}y=\square w\mathbf{q}y=w\mathbf{q}y\square \end{array}$$

When $\mathbf{q}=\mathbf{A}$, the string $w\mathbf{q}y$ represents an accepting configuration. When $\mathbf{q}=\mathbf{R}$, it represents a rejecting configuration. A configuration is a halting configuration if it is either accepting or rejecting.

A list of configurations obtained during the execution of a Turing machine is called a tableau. We can formally define which configurations follow each other in the execution of a Turing machine in the following way.

Definition

For any strings $w,y\in {\Gamma }^{\ast }$, symbols $a,b,c\in \Gamma$, and states $\mathbf{q}\in \mathbf{Q}$ and $\mathbf{r}\in \mathbf{Q}\cup \{\mathbf{A},\mathbf{R}\}$, the configuration $wa\mathbf{q}by$ of the Turing Machine $M$ yields the configuration $w\mathbf{r}acy$, denoted

$$\begin{array}{r}wa\mathbf{q}by⊢w\mathbf{r}acy\end{array}$$

when $\delta (\mathbf{q},b)=(\mathbf{r},C,L)$. Similarly,

$$\begin{array}{r}wa\mathbf{q}by⊢wac\mathbf{r}y\end{array}$$

when $\delta (\mathbf{q},b)=(\mathbf{r},c,R)$.

By simulating many steps of computation, a Turing machine can reach some other configurations. We say that configuration $w\mathbf{q}y$ derives the configuration $w^{\prime }{\mathbf{q}}^{\prime }{y}^{\prime }$ in the Turing Machine $M$, denoted

$$\begin{array}{r}w\mathbf{q}y{⊢}^{\ast }{w}^{\prime }{\mathbf{q}}^{\prime }{y}^{\prime }\end{array}$$

when $\exists$ a finite sequence of configurations $w_1{\mathbf{q}}_1,y_1,\dots ,w_k{\mathbf{q}}_k,y_k$ such that

$$\begin{array}{r}w\mathbf{q}y⊢w_1{\mathbf{q}}_1{y}_1⊢\cdots ⊢w_k{\mathbf{q}}_k{y}_k⊢w^{\prime }{\mathbf{q}}^{\prime }{y}^{\prime }\end{array}$$

The Turing Machine $M$ accepts an input $x\in \{0,1{\}}^{\ast }$ if the initial configuration $1x$ derives an accepting configuration. It rejects $\mathbf{x}$ if $1x$ derives a rejecting configuration. It halts on $\mathbf{x}⟺$ it either accepts or rejects $\mathbf{x}$.

We can now formally define what it means for a Turing machine to compute a language.

Definition

The Turing machine $M$ decides the language $L\subseteq \{0,1{\}}^{\ast }$ if it accepts every $x\in L$ and rejects every $x\notin L$.

A language is also decidable $⟺$ there is a Turing machine that decides it. There is a closely related notion of recognizability of languages.

Definition

The Turing machine $M$ recognizes the language $L\subseteq \{0,1{\}}^{\ast }$ if for every $x\in \{0,1{\}}^{\ast }$, $M$ accepts $x⟺x\in L$.