FOM: natural examples
bmk at cs.auckland.ac.nz
Wed Aug 18 00:31:34 EDT 1999
My opinion about natural examples of computably enumerable sets is the
following. First of all, I regard the definition of Turing machine natural.
One can view a Turing machine M as a finite directed graph, say G(M),
whose nodes are the states of the machine and whose edges are labelled
with instructions. Secondly, I regard the definition of the halting set of M,
that is the set of all inputs on which M halts, natural. So from this point
of view the halting set of M, whether it is complete or not, is natural.
If one wants a visual picture then just draw G(M) and say that G(M)
defines the halting set of M. I guess there is a machine with sufficiently
small number of states (say < 10, 15 or 20 or 30) whose halting set is
neither computable nor complete. One may want to not even think about
the number of states since finiteness is enough. This can even be considered
simpler (and more natural) than some examples of nowhere differentiable
functions whose definitions use infinite sums, cos(.), sin(.) functions or an
infinite procedure of dividing an interval. --Bakhadyr.
More information about the FOM