In the last lesson we showed that the set

_{D}= { <M> | Machine M does not accept input <M>}

For a set A, let A be
the complement of A, i.e., all of
the strings of Σ^{*} not in A. If A is computable then
A is also
computable--at the end if we accepted then we reject and
vice-versa.
Note this does not work in general for computably enumerable;
switching reject and accept does not affect whether a machine halts on
a given input.

Now consider the set

_{A}= { <M> | Machine M does accept input <M>}

_{A}is just L

_{D}.

Note the L_{A} *is* computably enumerable as we can just
simulate M on <M>. If L_{A} were computable then so would
L_{D} which we know is not even computably enumerable. Thus we
have L_{A} as our first example of a noncomputable computably
enumerable set.

Besides languages we can also consider computable functions. Consider
a Turing machine with an output tape. We can view it as computing a
function f from Σ^{*} to Σ^{*} where the
value of f is the contents of the output tape after the machine enters
a specified halting state. We say a total function f is computable if
there is such a Turing machine computing f. We can also consider
partially computable functions where f(x) may not be defined for some
inputs x. On these inputs the corresponding machine does not halt.

In the next lesson we will use computable functions to show that other languages are not computable or computably enumerable.

## No comments:

## Post a Comment