2012-05-16T20:53:36Z James Harland Copyright 2012, James Harland SPHPBLOG Alain ColmerauerAlain Colmerauer has observed the following property of universal Turing machines. Given a universal Turing machine U, a Turing machine M and an input w to M, the operation of U on code(M)code(w) should simulate that of M on w (where code() is an encoding of Turing machines and their input into the tape alphabet of U). Consider the case when U = M. Then we have that U on code(U)code(w) should simulate U on w and hence U on code(U)code(U)code(w) should simulate U on code(U)code(w) etc. We shall call this Colmerauer's property. Colmerauer uses this observation to define a measure of complexity of U. For more details, see Colmerauer's paper.

Here we are interested in the case when w is empty. Then by Colmerauer's property we have that U on code(U) should simulate U on the empty input. This may be thought of as a cheap test for universality, in that if a machine M on code(M) does not simulate M on the empty input, then M is not universal. Of course, M on code(M) simulating M on empty does not imply that M is universal, but it would generally indicate that M is probably of interest. Let us call machines that pass this test pseudo-universal. The quality of this test can then be measured by how many machines are pseudo-universal but not universal. This is clearly connected to the busy beaver problem, which involves analysing the behaviour of M on the empty input for a large class of machines (including testing for non-termination). It would be interesting to add an extra test to this evaluation, ie the above universality test. Intriguingly, this may be a way to generate some even more staggering productivities than the currently known busy beaver champions, in that if M on code(M) does simulate M on the empty input where M is a busy beaver champion, then the computation of M on code(M) must not only terminate (as it simulates M on the empty input, which terminates), but must do so for a much larger number of steps than the computation of M on the empty input.

Hence the key technical problem is to be able to find an appropriate way to determine whether or not M on code(M) simulates M on the empty input. As Colmerauer points out, a key point is the definition of the function code(). This will be the starting point for an investigation ...

Alain Colmerauer, On the Complexity of Universal Programs, Proceedings of the Fourth International Conference on Machines, Computations and Universality 18-35, St. Petersburg, September 21-24, 2004. Published as Lecture Notes in Computer Science volume 3354, April, 2005.]]> http://goanna.cs.rmit.edu.au/~jah/bbblog/index.php?entry=entry081107-151532 2008-11-07T00:00:00Z 2008-11-07T00:00:00Z this website More recent thoughts, often not yet fully formed, are discussed in this blog. Of course, comments are most welcome. ]]> http://goanna.cs.rmit.edu.au/~jah/bbblog/index.php?entry=entry081104-235431 2008-11-04T00:00:00Z 2008-11-04T00:00:00Z