FOM: small machines

[José Félix Costa]

Neil,

Let UTM(m,n) be the class of universal Turing machine with m states and n
symbols.
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,

Felix

+++++++++++++++++++++++++++++++++++++++++++++++
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 math.ist.utl.pt
www:    http://fgc.math.ist.utl.pt/jfc.htm
+++++++++++++++++++++++++++++++++++++++++++++++