A Universal Turing Machine with 22 States and 2 Symbols

ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY
Volume 1, Number 3, 1998, 259 - 265

A Universal Turing Machine with 22 States and 2 Symbols
Yurii ROGOZHIN
Institute of Mathematics, Kishinev,
5 Academiei Str., Kishinev, Republic of Moldova
E-mail: rogozhin@math.md

Abstract.
Let UTM(m,n) be the class of universal Turing machines with m states and n symbols. It is known that universal Turing machines 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). In this paper it is shown that universal Turing machine exists in the class UTM(22,2), so previous result UTM(24,2) is improved.