[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