at work. Some of these simulators include Java applets, from which ready-made TM programs may be selected through pop-up menus and then executed. Some of these sites make it possible to create and test one's own programs, with the option to run them either step by step or at some preselected speed. It is quite fascinating to observe in real-time the execution of a TM program, as it conveys the impression of an elementary intelligence. But let us not be mistaken, the intelligence is not that of the machine, but of the human logic that built the action table! We may wonder how long it takes the TM to perform big operations, or operations involving big operands. Actually, we ought to measure it not by mere execution time, but by the number of required TM transitions from start to halt states. Such transitions are the elementary tape moves from one TM state to the next TM state, passing through one cell at a time. Recalling that the TM is not a physical machine, it can be made with arbitrarily small size and arbitrarily high speed, SO that the execution time for any single transition is not a relevant parameter. The number of states defined in the action table provides a measure of the complexity of the algorithm (the word "complexity" is not chosen here by chance, as we shall see later on). But as we know, the TM can use any of these states several times before reaching the halt state, therefore, a simple algorithm may have a long execution length. Also, the size of the input and of the output data affects the execution length. For instance, a simple character-erasure algorithm may take as many transitions as there are symbol characters in the input data. Therefore, the relevant parameter to measure the execution length is the number of transitions required 7.2 The Turing machine 200 000 100 000 Integer to be squared Figure 7.2 Number of Turing-machine transitions to compute the square of small integers, according to action-table program defined in Table 7.6. The dots correspond to results obtained with a Turing-mac