What is the minimum number of states in a Universal Turing Machine?

May 1, 2005 4:09 AM

What is the absolute minimum number of states required in a Turing Machine (that uses binary tape) for it to be able to serve as a Universal Turing Machine?

More generally, what is the simplest "spec" for a Universal Turing Machine (UTM)? I'm looking into designing a visual aid to help explain the Turing machine, and I want the system it depicts to be as simple as possible, yet sufficient (in theory at least) to operate as a UTM. I don't expect the aid will normally, if ever, be used to demonstrate a UTM, but it would be nice to be able to say "and this is all you need to do any computation", so if there is a choice between a "person-useable" minimum number of states, and a "extreme optimised to the point of obfuscation" minimum number of states, I'd lead towards the later unless the difference is just one or two states.

Also of interest - what would be the minimum states for a UTM using a 3-symbol tape?

(The internet is loaded with UTM information, and references to "a minimum finite number of states" abound, but nothing seems to mention what that number actually happens to be, and I don't really have the time or the ability to reinvent the wheel)

posted by -harlequin- to computers & internet (3 comments total)

Wikipedia says 22 states for a binary tape, 10 states for 3 symbols, or 2 states for an 18 symbol tape.
posted by cillit bang at 4:36 AM on May 1, 2005

Additional lesson learned: Add Wikipedia to searches.

Thanks!
posted by -harlequin- at 5:05 AM on May 1, 2005

that Rogozhin paper only provides an example which gives a lower bound on the minimal complexity of a UTM. there may be simpler UTMs.

kolmogorov/chaitin/descriptive complexity theory says that, in general, you cannot determine the absolute minimal description of a formal structure. i very much doubt that a UTM is one of the finitely many counter examples.
posted by paradroid at 8:52 AM on May 1, 2005