Fundamentals of Computing and Discrete Mathematics

Yuri Matiyasevich

Steklov Institute of Mathematics - Russia

May 2011

Distinguished Lecture Colloquium

Decidable and undecidable cases of the code problem for partially commutative monoids

A map $\phi : A \to B^*$ from an alphabet $A = \{a_1, \ldots, a_n \}$ into the set of all words in an alphabet B can be extended in a natural way to a map $\Phi : A^* \to B^*$ from the set of all words in the alphabet $A^*$. There is an easy algorithm to decide for given words whether $\phi (a_1), \ldots , \phi (a_n)$ is injective or not, that is whether $\Phi$ could be used for coding words from $A^*$ by words from $B^*$. The situation is quite different if we replace an ordinary alphabet $B$ by a partially commutative alphabet, that is, if we allow some letters to interchange their positions. In this situation recognizing the injectivity of $\Phi$ might be an undecidable problem, but we still haven't complete description when this is the case. This problem has close connections with automata of different kinds. P. Cartier and D. Floata began to study words in partially commutative alphabets as combinatorial objects in the 1960's. They were named later “traces” by A. Mazurkievicz who showed how one can use them for describing parallel computations.

A PDF version of this abstract can be downloaded here.

TUCS Short Course

Alfred Tarski's Great Algorithm (Decidability of elementary algebra and geometry)

Algorithm of Alfred Tarski for deciding the validity of a closed first-order formula with variables ranging over real numbers is one of the most difficult known decision procedures. In two lectures a version of this algorithm will be presented with all details. This version is:

  • easy to understand
  • easy to implement on a computer
  • extremely inefficient

    • On-line word pattern recognition on two dimensional Turing machines

    It is usually supposed that celebrated Knuth-Morris-Pratt linear-time algorithm for pattern recognition is implemented on RAM. It will be shown that even such an apparently slow device as (multihead) Turing machine (with two-dimensional tape) can solve this problem on-line.

    Some “small” undecidable problems for words

    When certain decision problem is shown to be in general undecidable, one can still hope to find algorithm for “small” (in some suitable sense) instances. Sometimes one succeeded but often not, so it became important to find as sharp as possible boundary between decidable and undecidable. For example, the activity about constructing as small as possible universal Turing machines is well known. In the lecture I'll speak about some results and techniques for obtaining undecidability theorems for Thue systems, semiThue systems and Post Correspondence Problems defined by a small number of rules or pairs of words.

    Last modified: