Computer simulation design for universal Turing machine
Lixin An · 2008
The transition function of a standard Turing machine,defined as δ(qi,aj)=(qk,al),was encoded as(i,Unicode(aj),k,Unicode(al)).It was applied to the universal Turing machine model whose temporary storage was two tapes.One was a one dimension tape used to store input data ω,the other was a two dimension tape used to store the encoding of a standard Turing machine M.The universal Turing machine model was simulated on a PC machine.The arithmetic of the controller in the universal Turing machine model had a time complexity O(|K|2) which is exceled other reference models based on the traditional encoding in time complexity.