## ABSTRACT

The foundation of modern computer science is built on the theory of Turing machines. Alan Turing (1912-1954) [44] published his ideas of an abstract computing machine (now called a “Turing machine” (TM)) in 1936, which moved from one state to another using a precise finite set of rules, given by a finite table, and depending on a single symbol it read from a tape [46]. A TM, at the time Alan Turing invented it in his 1936 paper [61], was a hypothetical computer. It consists of the following:

(i) An infinite tape on which symbols may be read and written.