Towards Methods for Discovering Universal Turing Machines (or How Universal Unicorns can be Discovered, not Created)

Harland, J.

Universal Turing machines are a well-known concept in computer science. Most often, universal Turing machines are constructed by humans, and designed with particular features in mind. This is especially true of recent efforts to find small universal Turing machines, as these are often the product of sophisticated human reasoning. In this paper we take a different approach, in that we investigate how we can search through a number of Turing machines and recognise universal ones. This means that we have to examine very carefully the concepts involved, including the notion of what it means for a Turing machine to be universal, and what implications there are for the way that Turing machines are coded as input strings.

Cite as: Harland, J. (2011). Towards Methods for Discovering Universal Turing Machines (or How Universal Unicorns can be Discovered, not Created). In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 151-160

(from crpit.com) (local if available)