Explain why the trivial properties of the recursively enumerable sets are decidable, by suggesting suitable total Turing machines for these properties

Solution: There are exactly 2 trivial properties: the empty set (of r.e. sets) and the set of all r.e. sets. Since we represent every r.e. set by some (encoding of a) Turing machine accepting this set, the two trivial properties can be represented, by using some fixed encoding of Turing machines, as the languages {ˆM |  false} , which is the empty set, and {ˆM| true} , which is the set of all legal Turing machine encodings.

A total Turing machine MF accepting the first language is simply one that upon reading |-  immediately enters its reject state, while a total Turing machine MT accepting the second language is one which decides whether the input string is a legal encoding of some Turing machine according to the chosen encoding scheme.

Leave a Reply