[FOM] Complexity of (Universal) Turing Machines

Andrej Bauer Andrej.Bauer at andrej.com
Tue Apr 22 03:14:11 EDT 2008

If your motivation is a machine which can "generate" all _finite_
strings then you should not be looking at universal Turing machines,
which can also enumerate all computable infinite strings, and they
can diverge (not give an answer), etc. How do you account for these
possibilities in your idea of looking at a UTM as a probability
distribution? Furthermore, the set of inputs for which a UTM stops and
gives a finite output is not decidable.

Perhaps you should be looking at machines that enumerate all finite
strings. Of course there will be some pretty simple machines that do
that, e.g., the one computing the identity function. Not so interesting,
but perhaps still better.

Andrej Bauer

More information about the FOM mailing list