[FOM] Seeking information on Watanabe's 4-5 UTM

Benjamin Wells wells at usfca.edu
Mon Apr 13 14:35:05 EDT 2009


I am looking for information on Shigeru Watanabe's 4-symbol, 5 state, 18 
quintuple machine, the subject of an abstract at one time found at:
http://www.ipsj.or.jp/members/Magazine/Eng/1309/article002.html
but no longer at this address. 

This is the abstract:

Since the first universal Turing machine (UTM) was made in 1937, its 
size has become smaller and smaller through many trials of obtaining a 
minimum UTM. The UTM for which the product of number of symbols and 
number of states is the smallest in the published papers is 4-symbol 
7-state UTM made by Dr. M. Minsky. In this paper, the author has got 
4-symbol 5-state UTM (18 quintuples) as shown in Table 7.

I am more interested in the full paper:
Shigeru Watanabe. 4-symbol 5-state universal Turing machines. Journal of 
Information Processing Society of Japan, 13(9):588-592, 1972.

This journal is not available on IPSJ's website, but I found a legible 
PDF scan through joining CiNii (http://ci.nii.ac.jp), but as expected it 
is in Japanese.  Does anyone have an account of this machine/s (there is 
also a 4-6 machine here) in English?

I assume it requires a preprinted periodic input tape.

--Pete


More information about the FOM mailing list