Research in Decidability and Undecidability
by Vesa Halava

Updated November 2006

A decision problem is called decidable, if there exists an algorithm which gives the correct answer for every input instance, and undecidable if no such algorithm exists. Undecidability itself describes limits in mathematics and in theoretical computer science. These limits can be sharpened further. We can take an undecidable problem and study the subproblems of it in order to find the borderline between two subproblems in terms of decidability. In other words, we can take two subsets P and P' of the instances of the original problem such that P' is a subset of P. If P is undecidable but P' is decidable, then we say that the borderline between decidability and undecidability lies between P' and P. The subproblems here are defined by making further assumptions to the instances. This also gives information about general decidability, since from it, it can be seen, which assumptions make a problem decidable or, on the other hand, which assumptions do not help in decision problems.

Post Correpondence Problem

Firstly, we have found new information about borderlines between decidability and undecidability in the Post Correspondence Problem (PCP). In the PCP, the instances consists of two (word) morphisms g,h: A* ® B*, where A and B are alphabets (and A* denotes the monoid of all finite words over A). The task in the PCP is to determine whether or not there exists a (nonempty) word w in A* such that

g(w)=h(w).

The word w is called a solution of the instance (g,h). The PCP is a well-known and important undecidable problem, the undecidability of which was proved originally by E. Post in 1947.

It is known that if the cardinality of the alphabet A is one or two then the PCP is decidable. We gave a new proof for this with T. Harju and M. Hirvensalo [1]. Recently, in the article [2] with S. Holub the article, where we prove that there exists a polynomial time algorithm for the PCP in this binary case (|A|=2).

On the other hand, it is known, that the PCP is undecidable if |A| is at least 7 (Matiyasevich and Sénizergues, Theor. Comput Sci. 330, 2005). Therefore, the borderline between decidability and undecidability lies somewhere between 3 and 6, when considering the subproblems defined by the cardinality of the domain alphabet A.

We give another example of a known borderline. In the infinite PCP the inputs are again pairs of morphisms h,g: A*® B*, but the task is now to determine whether of not there exists an infinite word w such that h(w)=g(w). again for |A|£ 2 (proved in [3]) and undecidable if |A|³ 9 (proved in [4]).

It is also known that the borderline between decidability and undecidability lies somewhere between prefix (which means that no image of a letter is a prefix of an image of another letter) morphisms and marked (every image of a letter begins with different letter) morphisms. The marked PCP was the main topic in my Ph.D. thesis [5], which was chosen to be the Best Ph.D. thesis in Computer Science in Finland in the year 2002 (see also [6]).

Integer matrices

The PCP is very useful in proving undecidability results in other problems. For example, the matrix mortality problem is one such problem, but there are also other examples in the theory of integer matrices. In the mortality problem a finite set of n x n integer matrices is given, and it is asked whether or not the zero matrix belongs to the semigroup generated by these matrices. It was originally proved by M.S. Paterson that for n³ 3 the mortality problem is undecidable, and we gave a new proof of this in [7], also giving better bound for the number of matrices. Our very recent manuscript [8] states that the mortality problem is undecidable already for seven 3 x 3 integer matrix. Indeed, this bound follows from the fact that the PCP is undecidability in the case where |A|=7. Actually, in [8] we were able to improve the known bounds for the number of matrices in the undecidability proofs for many other problems also (such as freeness problem, zero in the left upper corner problem, scalar reachability problem and vector reachability problem). These improvements are based on deeper study of the undecidability proof of the PCP in case |A|=7.

On the decidability side, we have studied the so called Skolem's problem asking to decide whether or not there exists m ³ 0 such that um=0 for a given (integer) sequence (un)n³ 0 defined by linear recurrence equation of order k. In [9] we proved that the Skolem's problem is decidable for recurrence relations of order k£ 5. This bound is the best known. As a corollary we were able to prove in [10] that it is decidable whether or not a given recurrent sequence has un³ 0 for all n for second order linear recurrence relations. This problem is a famous open problem called the Positivity problem in the literature.

All these undecidability results and many other undecidability results concerning the PCP are to be gathered in the book which we (together with Professors T. Harju and J. Karhumäki) are writing at the moment. During the writing we have found many improvements to know undecidability results. The working title of the book is

Undecidability through Post Correspondence Problem

My Homepage

  1. Vesa Halava, Tero Harju and Mika Hirvensalo:
    Binary (generalized) Post correspondence problem ps.gz
    Theoret. Comput. Sci. 276 (2002), 183 - 204.
    doi:10.1016/S0304-3975(01)00157-8
  2. Vesa Halava and Stepan Holub:
    Binary (generalized) Post Correspondence Problem is in P pdf file:
    submitted.
  3. Vesa Halava, Tero Harju and Juhani Karhumäki:
    Decidability of the binary infinite Post Correspondence Problem ps.gz
    Discrete Appl. Math. 130 (2003), 521 - 526.
    doi:10.1016/S0166-218X(03)00330-5
  4. Vesa Halava and Tero Harju:
    Undecidability of Infinite Post Correspondence Problem for Instances of Size 9 pdf file:
    Theory Inform. Appl. (2006), to appear.
  5. Vesa Halava:
    The Post Correspondence Problem for Marked Morphisms pdf file:
    Ph.D. Thesis, University of Turku TUCS Dissertations 37, 2002.276 (2002).
  6. Vesa Halava, Mika Hirvensalo and Ronald de Wolf:
    Marked PCP is decidable
    Theor. Comput. Sci. 255 (2001), 193-204.
    doi:10.1016/S0304-3975(99)00163-2

    Earlier version:ps.gz STACS 1999, Lecture Notes in Comput. Sci. 1563 (1999) pp. 207-206.
  7. Vesa Halava and Tero Harju :
    Mortality in matrix semigroups ps.gz
    Amer. Math. Monthly 108 (2001), 649 - 653.
  8. Vesa Halava, Tero Harju and Mika Hirvensalo:
    Undecidability Bounds for Integer Matrices using Claus Instances pdf file:
    submitted.
  9. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki:
    Skolem's Problem - On the Border Between Decidability and Undecidability pdf file:
    submitted.
  10. Vesa Halava, Tero Harju, and Mika Hirvensalo:
    Positivity of second order linear recurrent sequences pdf file:
    Discrete Applied Math. 154 (2006), 447-451.