 can be formulated as follows: Any computation process or algorithm that can be devised by a mathematician can be effectively implemented on a Turing machine. Or, equivalently: Anything a real computer can compute, a Turing machine can compute. As mentioned, there are, however, a few qualitative differences between a TM and a real computer. A first key difference is that the TM's memory is theoretically infinite. A real computer can be equipped with whatever amount of memory space is required. But the need to manage this finite-size memory space affects the program structure and algorithms. A real computer also efficiently accesses and manages its memory space by indexing and virtual caches. But this is difficult, if not impractical, to implement in a TM. A TM can be built with several parallel tapes (and read/write heads), but it can be shown that this only partly alleviates the problem of memory access. A second key difference is that the TM algorithms are usually more general or universal than those implemented in real computers. The main reason is that they are not bounded to data type or format limits and, therefore, do not encounter unexpected program failures or crashes. The only peculiar situation to be encountered with a TM is that where it would run forever or never halt. Given a table of instructions, and a specific input tape or all possible input tapes, the question of whether or not a TM will eventually halt is known as the halting problem. Turing showed that, in the general case, the halting problem cannot be solved. In algorithmic information-theory jargon, the problem is said in this case to be undecidable. The term "undecidable" means that the YES/NO answer to the question, "Can it be solved?" is neither formally provable nor unprovable. Given all possible instructions and input data there is no universal algorithm enabling one to determine whether a TM would halt. It has been shown, however, that the halting problem is solvable for TMs having fewer than four states, the four-state case being st