[FOM] Simple Turing machines, Universality, Encodings, etc.

[James Harland]

Perhaps this has been explored already, but one thing that this discussion has brought to mind is whether a reasonable restriction of infinite initial conditions would be that the initial tape be generated by a Turing machine of the same dimension as the universal one. What I mean is that if we have a universal machine M with k states and m tape symbols, then we allow initial condition C for this machine if C is the output of some machine T with up to k states and m tape symbols, starting from a blank tape. Naturally T would have to be non-terminating to generate an infinite number of non-blank symbols on the tape.

This may actually be too generous, in that some generated conditions may be too complex (as anyone who has dealt with busy beaver machines will attest! :-), in which case further restricting T may be appropriate.  They may also be some reasonable inputs that cannot be generated by a Turing machine of this size (ie a larger one is required), which suggests a means of measuring the complexity of the input by the size of the smallest Turing machine needed to generate it (a la Kolmogorov). Note that if we require T to be terminating, but allow it to be of unrestricted dimension,  then we can allow all finite inputs this way (as for any finite input, there is some terminating Turing machine which outputs it, starting from a blank tape).

This is intuitively equivalent to allowing the input to the universal machine to be a specific machine, rather than a specific tape input. The idea behind the dimensions of the machines being the same is that this means the input is in some sense limited by the complexity of the universal machine. The intention is that this will prevent a simple machine relying on a highly complex input, which seems similar in spirit to Minsky's original idea.

This seems a bit too obvious not to have been explored previously, though.

Cheers,
James.