Communicated by: J. Paul GibsonTechnical report:

Key words: small universal Turing machine, polynomial time, universality. Abstract. We present a number of time-efficient small universal Turing ma-chines. We show that there exists deterministic polynomial time universal Turing machines with state-symbol products of (3, 11), (5, 7), (6, 6), (7, 5) and (8, 4).These machines are the smallest known universal Turing machines that simulate TMs in polynomial time. 1 Introduction Shannon [1] first posed the question of finding the smallest possible universal Turingmachine (UTM). Initially small UTMs were constructed that directly simulated Turing machines (TMs) [2, 3]. Subsequently the technique of indirect simulation via other uni-versal models was successfully applied. In the early 1960s Minsky used 2-tag systems to create a 7-state, 4-symbol machine [4]. Minsky's technique was more recently usedby Rogozhin et al to create the smallest known UTMs