ill an open issue. The five-state case has been shown to be almost certainly undecidable. It is not in the scope of this chapter to venture into the details of this rather complex and abstract domain of mathematical science. However, it is possible to provide here a 8 See: http://en.wikipedia.org/wiki/Church-Turing_thesis,http://www.cs.princeton.edu/introcs/76universality/ In particular (as abridged from http://en.wikipedia.org/wiki/Church-Turing_thesis), an algorithm must satisfy the following requirements: (a) It must consist of a finite set of simple and precise instructions described with a finite number of symbols; (b) It must always produce the result in a finite number of steps; (c) In principle, it could be carried out by a human being with paper and pencil; (d) Its execution requires no intelligence of the human being except that which is needed to understand and correctly execute the instructions. 9 http://en.wikipedia.org/wiki/Universal_Turing_machine. 7.3 Universal Turing machine simple sketch of proof of the insolvability of the halting problem in the general case, as the following illustrates. As we know, any TM is uniquely defined by its action table or program. Such a program can be encoded into a string of symbols, for instance, in the binary system with 0 and 1 bits. According to the coding rules, each individual instruction k in the table takes the form of a binary number Sk of defined size. Concatenating the coded instructions gives the string = S1S2S3 SN#, where N is the total number of instructions in the table, and # is an end delimiter, e.g., S = 110101110 1000010#. Because of the coding rules, not every binary string picked at random defines a TM, but the contrary is true: for any TM there is a corresponding unique binary string S. We can then index each TM according to its unique string value and put these TMs into an ordered list. Although there exists an infinity of such strings, it is said that they are countable, just like integer numbers, 11 but unlike real numbers. Let this counter