What is the minimum number of states in a Universal Turing Machine?
May 1, 2005 4:09 AM Subscribe
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)
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)
Response by poster: Additional lesson learned: Add Wikipedia to searches.
Thanks!
posted by -harlequin- at 5:05 AM on May 1, 2005
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
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
« Older LinkSys router setup on Tiger help needed | How do I use Thunderbird's inbuilt encryption? Newer »
This thread is closed to new comments.
posted by cillit bang at 4:36 AM on May 1, 2005