Small universal Turing machines 论文

摘要

Let UTM(m, n) be the class of universal Turing machine with m states and n symbols. Universal Turing machines are proved to exist in the following classes: UTM(24,2), UTM(10,3), UTM(7,4), UTM(5,5), UTM(4,6), UTM(3,10) and UTM(2,18).