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 a cycle in a directed graph) to ones with a potentially infinite space (tiling, PCP and related problems, matrix mortality, and satisfiability in logical systems).

Does a graph have a cycle?

A graph is a set of points together with a relation on the set. We usually draw the relation with arrows between the points. For example, here is a graph:

Given a graph, we might wonder if there is a cycle: this is a path following the arrows that starts and ends at the same point. This problem is a very well-studied example of a decidable problem. The basic reason is that if there is a cycle, there is one whose length is at most the number of points in the graph.

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.

The first quadrant is the set of squares shown below

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?

Going back to the example of a tile set shown above, the answer is Yes: 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 1

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 2

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 \(\varepsilon\).

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 sequence of dominoes a Post sequence, and the common word a Post word.

For this particular set of dominoes, the answer is Yes, there is a Post sequence:

The Post 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 mortality

This section deals with a specific problem about \(n\times n\) matrices over the set \(\mathbf{Z}\) of integers. It is called the matrix mortality problem.

Problem

Fix a number \(n\). Given a finite set \(S\) of \(n\times n\) matrices with integer entries, is there a finite product of elements of \(S\), allowing repeats, whose product is the zero matrix?

This is the \(n\times n\) matrix mortality problem.

Exercise 3

Here are three matrices:

\[\begin{split} \left[ \begin{array}{rrr} 0 & -4 & -4\\ 0 & -3 & -3\\ 0 & 2 & 2 \end{array} \right] \qquad \left[ \begin{array}{rrr} 1 & 0 & 0\\ -2 & 0 & 0\\ 1 & -1 & -1 \end{array} \right] \qquad \left[ \begin{array}{rrr} 8 & -5 & 7\\ -5 & 3 & -5\\ 0 & 0 & 1 \end{array} \right] \end{split}\]

Find a sequence of these (allowing repetitions) whose product is the zero matrix.

In other words, show that the answer to the \(3\times 3\) matrix mortality problem for the set of three matrices shown above is Yes.

In the cells below I provide a function list_multiply in Python in case you want to take guesses. With a little more, you could write a program that conducted an orderly search for what we want. I leave this to you.

import numpy as np
a = [[0,-4,-4], [0,-3, -3], [0,2,2]] # this is a 3x3 matrix; it's a list of 3 lists of length 3 of numbers
b = [[1,0,0],[-2,0,0],[1,-1,-1]]
## you will want to enter c here

list_multiply([a,b,b,a,b])

np.array_equal(zero_3,list_multiply([a,b,b,a,b]))
## zero_3 is the 3 x 3 zero matrix

The next exercise is important.

Exercise 4

For each natural number \(n\), let \(A_n\) be the set of sets \(S\) of \(3\times 3\) matrices such that (a) for all \(S\in A_n\), \(|S|\leq n\); and (b) every entry in each element of \(S\) has absolute value \(\leq n\).

1. Fix a number \(n\). Show that the following problem is decidable: Given \(S\in A_n\), does \(S\) have a product (allowing repetitions) which is the \(0\) matrix?

[Hint, this has very little to do with matrix multiplication!]

2. Now consider the a variation on the last part. Consider the problem whose inputs are pairs \((n,S\) consisting of a number \(n\) and some \(S\in A_n\). We again ask whether \(S\) has a product (allowing repetitions) which is the \(0\) matrix. Does the last part imply that this problem is decidable? Be sure to give a clear, concise, and convincing answer.

The halting set K

We also want to study a few problems related to 1# words. These include

\[\begin{split} \begin{array}{lcl} \mbox{Prog} & = & \mbox{the set of programs} \\ \mbox{Tidy} & = & \mbox{the set of tidy programs} \\ K_0 & = & \mbox{the programs which halt when run on the all empty registers}\\ K & = & \mbox{the programs which halt when run on themselves} \\ \textit{Fin} & = & \mbox{the programs $p$ such that the domain of $[\![p]\!]$ is finite} \\ \textit{Inf} & = & \mbox{the programs $p$ such that the domain of $[\![p]\!]$ is infinite} \\ \textit{Tot} & = & \mbox{the program $p$ such that $[\![p]\!]$ is a total function} \\ \textit{Equiv} & = & \mbox{the set of pairs $(p,q)$ of programs which are strongly equivalent}\\ \end{array} \end{split}\]

Of course, there are many other sets that we could define. We want to know whether they are computable or not.

We also could ask whether they are computably enumerable or not.

Truth and proof

We would like to ask about the set of sentences in the language of ordinary mathematics and as about the problem of deciding whether a given sentence is true or not.

There are a few reasons why we are not going to directly do this.

1. We really would like to ask about sentences in natural language which are mathematically clear, and this is not so easy to describe mathematically in the first place.

2. Even if we could do this, we still have the problem that for some important sentences \(S\), it is not exactly clear what it means for \(S\) to be true. For example, we have sentences about sets such as the Continuum Hypothesis where it is disputed whether they are intuitively true or not, or whether this even makes sense to ask about.

Given these problems, there are two ways to back off in order to ask and answer related questions.

1. We could fix a first-order structure of some importance in mathematics and only look at the sentences in first order logic which are pertinent to that structure. The canonical choice here would be the structure

\[ \mathcal{N} = (N, 0, 1, +, \times) \]

of the natural numbers with the operations shown above. But we could also ask about other structures, such as the same one with only \(+\), or a model of the axioms of set theory, or some fragment of set theory.

2. We could replace truth by provability in our discussion above. Given some set \(T\) of axioms, especially some set \(T\) with importance in the foundations of mathematics (like standard set theory), we can ask about provability from \(T\). Is the set of provable sentences decidable? We could also ask this when \(T\) is the empty set; this means we would be asking about the set of sentences provable by pure logic alone, without any axioms.
   This, too, is an interesting thing to do.

We are going to investigate both of these back off questions in some detail.