e form of a symbol string of finite length, followed by a delimiter symbol. The rest of the tape thus contains the input data string to be processed by this program. Thus, the first string in the input tape instructs the TM on how to process the second string in the input tape. Let us refer to this implementation as an enhanced TM. Nicely enough, Turing has shown that not only can such an enhanced TM be implemented, but it also has the capability to simulate the behavior of any other TM. For the second reason, it is called a universal Turing machine or UTM. Basically, a UTM is a TM that executes a program stored in its input tape. Sim- ple UTMs can be built with a surprisingly small number of states and small alpha- bet sizes. The smallest known UTM uses two states and 18 symbols, and is noted UTM 2 X 18, or is conventionally referred to as UTM(2, 18). Other well known small UTMs are UTM(3, 10), UTM(4,6), UTM(5, 5), UTM(7,4), UTM(10, 3), and UTM(22, the latter being the smallest known binary UTM. As we have seen in the previous section, and its related exercises, the TM is able to emulate all basic operators (+, -, X, , <, >, and, thus, to execute any algorithm that a real computer can perform. The internal TM variables are identified by specific symbol markers, as first initialized or assigned from the input tape data, and then processed by means of these operators. All features of a high-level computer program can be implemented by a TM: loops with conditional blocks (IF GOTO), function calling, variable retrieval, or procedures or subroutines (which we can conceive as representing a subset of instructions within the action table and having specific enter and exit states). The so-called Church-Turing thesis states that a UTM is capable to solve all problems that have a solution under an "algorithm" or an "effective computation method," as these Algorithmic entropy and Kolmogorov complexity terms are usually understood, provided sufficient storage space and computing time are provided. 8 The Church-Turing thesis