Algorithmic problems

Algorithmic problems¶

This section is going to have a general discussion of algorithmic problems with examples from ones with a finite search space (like finding paths in a graph) to ones with a potentially infinite space (tiling, PCP and related problems, matrix mortality, and satisfiability in logical systems).

Tiling problems¶

A tile is a square with a color on each side. For example, here are eight tiles The colors involved are red, black, grey, green, yellow, cyan (light blue) and dark blue.

A tile set is a finite set of tiles. A pointed tile set is a tile set that comes with a special tile $t_0$ called the start tile.

Problems

Given a tile set, is it possible to tile all of the squares in the first quadrant in such a way that tiles which share an edge must have the same color on that edge?

Given a pointed tile set, is it possible to tile the first quadrant satisfying the same condition and also tile the corner of the quadrant with the start tile?

For example, here is a tile set: The first question has a trivial answer for this set: since we have a tile with grey on all sides, we can just use it on every square of the quadrant. Of course, this is a special feature of this example.

Continuing, we can turn our tile set above into a pointed tile set by selecting as $t_0$ any of the eight tiles. Let’s choose the one marked in green below. Now here is a finite part of a tiling of the quadrant with this pointed tile set: We should emphasize that given a (pointed) tile set $\TT$, there might or might not be a tiling of the quadrant with $\TT$. The algorithmic question is to determine from $\TT$ whether or not there is a tiling of the quadrant as requested. This means that we want to know in finite time whether or not some infinite task can be completed or not.

Exercise 28

Let $\TT^*$ be the pointed tile set consisting of the tiles in the bottom row of the last set: Does the quadrant have a tiling with this set?

Exercise 29

Construct a (finite) pointed tile set $\TT$ with the following properties:

(a) The quadrant can be tiled using $\TT$ in exactly one way.

(b) In the tiling of the quadrant, the start tile appears on the main diagonal, and nowhere else.

Post’s correspondence problem¶

An alphabet is just a set $A$ of symbols.

Given an alphabet $A$, we define

\[\begin{split}\begin{array}{lcl} A^+ & = & \set{a_1 a_2 \cdots a_n : n \in N, n\geq 0, \mbox{ and } a_i\in A \mbox{ for all $i$}}\\ A^* & = & A^+ \cup\set{\epsilon}\\ \end{array} \end{split}\]

So $A^+$ is the set of non-empty words on $A$. And $A^*$ adds in the empty word $\eps$.

We are given a finite set of dominoes, each of which has two non-empty words on it, a word on the top and a word on the bottom.

For example, with $A = \set{a,b}$, here is a finite set of dominoes:

We have an unlimited supply of all of these dominoes.

Problem

Can we place a finite row of dominoes in such a way that the words on the top concatenate to the same thing as the words on the bottom?

Let’s call this a Post sequence.

For this particular set of dominoes, the answer is Yes:

The common word is $ababaaabbbaabbaababaa$.

Theorem 1 (Post, 1946)

There is no algorithm which, when given any finite set of dominoes with two words on each, tells in finite time whether or not one can find a Post sequence for the given domino set.

We are going to see a proof of this result. It is very important to understand the statement of this kind of result, since frequently people get it wrong. It does not say that that for each particular domino set we cannot tell if there is a Post sequence or not.

It also doesn’t say that there is no “fact of the matter” whether a given domino set has or doesn’t have a Post sequence.

PCP is the set of finite domino sets which have a Post sequence. To say PCP is decidable means that there is a computable function $f$ which inputs a domino set $\DD$ and says Yes or No as to whether $\DD$ has a Post sequence. To say PCP is undecidable means that there is no computable function $f$ like this.

Matrix problems¶

This section will present problems with $n\times n$ matrices over $\mathbf{Z}$ such as matrix mortality.

Computability

What is coding?

Invitation to Computability