## Research in Decidability and Undecidability

by Vesa HalavaUpdated November 2006

A decision problem is called

decidable, if there exists an algorithm which gives the correct answer for every input instance, andundecidableif 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 subsetsPandP'of the instances of the original problem such thatP'is a subset ofP. IfPis undecidable butP'is decidable, then we say that the borderline between decidability and undecidability lies betweenP'andP. 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) morphismsg,h: A, where^{*}® B^{*}AandBare alphabets (andAdenotes the monoid of all finite words over^{*}A). The task in the PCP is to determine whether or not there exists a (nonempty) wordwinAsuch that^{*}

g(w)=h(w).The word

wis called asolutionof 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

Ais 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 least7(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 alphabetA.We give another example of a known borderline. In the

infinitePCP the inputs are again pairs of morphismsh,g: A, but the task is now to determine whether of not there exists an infinite word^{*}® B^{*}wsuch thath(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 andmarked(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 problemis one such problem, but there are also other examples in the theory of integer matrices. In the mortality problem a finite set ofnxninteger 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 forn³ 3the 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 seven3x3integer 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 ³ 0such thatufor a given (integer) sequence_{m}=0(udefined by linear recurrence equation of order_{n})_{n³ 0}k. In [9] we proved that the Skolem's problem is decidable for recurrence relations of orderk£ 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 hasufor all_{n}³ 0nfor second order linear recurrence relations. This problem is a famous open problem called thePositivity problemin 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

Vesa Halava, Tero Harju and Mika Hirvensalo:

Binary (generalized) Post correspondence problem

Theoret. Comput. Sci.276 (2002), 183 - 204.doi:10.1016/S0304-3975(01)00157-8

Vesa Halava and Stepan Holub:

Binary (generalized) Post Correspondence Problem is in Ppdf file:

submitted.

Vesa Halava, Tero Harju and Juhani Karhumäki:

Decidability of the binary infinite Post Correspondence Problem

Discrete Appl. Math.130 (2003), 521 - 526.doi:10.1016/S0166-218X(03)00330-5

Vesa Halava and Tero Harju:

Undecidability of Infinite Post Correspondence Problem for Instances of Size 9pdf file:

Theory Inform. Appl.(2006), to appear.

Vesa Halava:

The Post Correspondence Problem for Marked Morphismspdf file:

Ph.D. Thesis, University of TurkuTUCS Dissertations37, 2002.276 (2002).

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: STACS 1999,Lecture Notes in Comput. Sci.1563 (1999) pp. 207-206.

Vesa Halava and Tero Harju :

Mortality in matrix semigroups

Amer. Math. Monthly108 (2001), 649 - 653.

Vesa Halava, Tero Harju and Mika Hirvensalo:

Undecidability Bounds for Integer Matrices using Claus Instancespdf file:

submitted.

Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki:

Skolem's Problem - On the Border Between Decidability and Undecidabilitypdf file:

submitted.

Vesa Halava, Tero Harju, and Mika Hirvensalo:

Positivity of second order linear recurrent sequencespdf file:

Discrete Applied Math.154 (2006), 447-451.