FOM: small machines

José Félix Costa fgc at
Thu Jun 6 07:32:00 EDT 2002


Let UTM(m,n) be the class of universal Turing machine with m states and n
Yurii Rogozhin published a paper in TCS, 1996, showing that the following
classes exist:
UTM(24,2), UTM(10,3), UTM(7,4), UTM(5,5), UTM(3,10) and UTM(2,18).

Pavlotskaya proved that the classes UTM(3,2) and UTM(2,3) are empty. Kudlek
proved that UTM(2,2) is empty.

I can provide full references (Pavlotskaya did not published her result).

One expert in small machines is Maurice Morgenstern, Université de Metz.

I hope that this might be useful.

Best regards,


J. Felix Costa
Departamento de Matematica
Instituto Superior Tecnico
Av. Rovisco Pais, 1049-001 Lisboa, PORTUGAL
tel:      351 - 21 - 841 71 45
fax:     351 - 21 - 841 75 98
e-mail:   fgc at

More information about the FOM mailing list