Extensions of Basic Turing Machine
摘要
There exists many extensions/variants of standard Turing machine Model. These are 2-tape, 3-tape, and k-tape TMs; two-dimensional and multidimensional TMs; multi-track and two-way infinite tape TMs; nondeterministic TM and Universal TM. It is shown that these extension machines have the same problem-solving capability as the standard TM, in other words, they are in no way more powerful than the standard TM. These machines, however, require fewer number of steps (transitions) in comparison to standard TM, hence the complexity/difficulty of problem-solving through these machines may be lesser. This is due to the reason that most of these machines have capability to read/write on many tapes together, and make head movements together; in effect, do the parallel processing, like most modern computers do. The chapter also presents Universal TM, where the tape can hold encoding of some other TM; thus, a TM can be designed to simulate any other TM, in effect, it is like a subroutine/function call in conventional computer programs. The halting problem of TM proves that it is undecidable whether a TM will halt for some or all the inputs. The explanation of extended TMs are supported with worked out problems to strengthen their concepts. Also, there are number of exercises at the end of the chapter for practice, and review questions for self-assessment.