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. |