CS 3343
 Analysis of Algorithms 
  Word Problem  
  Undecidable   

Introduction. Before reading this page, you should first read Turing Machines and Undecidable Problems. Here we give a proof that the word problem is undecidable

The Halting Problem. This is the basic problem for computing machines. Wouldn't if be nice if we had a program which would input some other program (along with its input data) and would answer the question: Will the given input program running with the given input data eventually halt or will it run indefinitely, without ever halting? We could detect undesirable infinite loops and avoid other problems. Turing showed that no such algorithm or program can exist. Humanity will never be able to solve this problem. Of course specific instances of the problem can be solved, as when you detect an infinite loop, or when you run the program to completion. The general problem can never be solved.

Repeating: there cannot exist a single program that for all input finite programs (along with their finite data) will correctly answer the question: will the input program eventually halt or not when it is executed?

The proof is simple but annoyingly technical and confusing. It involves supposing such a program exists, and running it with itself as input data. Plus a further construction.

The Word Problem. I start with an example from my main reference:

Example of the Undecidable Word Problem:
Given an alphabet of three symbols a, b, c, and given three equations

    ba = abc
    bc = cba
    ac = ca
we can obtain other equations by substitution:
        bac = abcc
        bac = bca = cbaa = cabca = acbca = ...
= cabca = cabac = ...
= cabca = cacbaa = ...
(bold letters above are what is about to be replaced)
One might ask questioning like: "Can we deduce for the three equations that bacabca = acbca?"

The word problem for any finite set of equations is the general question: given an equation, can it be deduced from the given equations or not?

The word problem is undecidable. The proof is given in ouline form in the next section. One must model an arbitrary Turing machine T as an instance of the word problem. This is done is such a way that if one could solve this word problem, then one could solve the halting problem for T. Thus we are reducing the halting problem to the word problem.

The Word Problem Undecidable. Here is an outline of the proof that the Word Problem is undecidable. The text below uses "GO RIGHT" instead of the "MOVE RIGHT" as we use for Turing machines. The text is slightly garbled, in that it isn't clearly stated that the symbol qi in a word (properly located) means that the instruction i is about to be executed. The symbol qn+1

is used to mean that computations has halted.


Revision date: 2012-12-04. (Please use ISO 8601, the International Standard Date and Time Notation.)