6
$\begingroup$

What is an example of recursively enumerable subset of the natural numbers which is not recursive?

  • 1
    @Michael, if it wasn't computable, why would it be anyone's favorite? :-)2012-03-03

2 Answers 2

6

The set of universally valid formulas of first-order logic becomes such an example if you index formulas by natural numbers in a computable way. This is called Church's theorem, after Alonzo Church. He proved this in the 1930s. This means that although there is a fast proof-checking algorithm, there is no fast proof-finding algorithm.

The set of polynomial equations in several variables with integer coefficients that have integer solutions is another such example. That's called Matiyasevich's theorem. It was proved in 1970 by Uri Matiyasevich, who built on earlier work of Julia Robinson, Hillary Putnam, and Martin Davis. It disposed of Hilbert's tenth problem.

  • 0
    I'm not sure I've ever thought about the "pure" form.2012-03-05
1

Set up a coding scheme for Turing Machines that work on binary input with an initially empty input tape using an alphabet with k symbols -- like {'(', ')', '0', '1', 'B', ',', ...}.

We can then programmatically (that is, computably) convert each coded Turing machine to an integer by treating the encoding string over the k symbols as a k-ary integer. For example, the string "(B)01" converts to the integer 15234 (we can skip 0 to avoid leading zero complications, so it's really a (k+1)-ary integer). That particular string is probably not a syntactically correct Turing Machine encoding, but it shows how to do the conversion: '(' becomes 1, ')' becomes 2, '0' becomes 3, etc.

The integers you get that correspond to syntactically correct Turing Machine encodings will be a recursive set of integers, say T (they can be checked by a TM "compiler"). But the subset H of T corresponding to TMs that halt when actually run will not be recursive, but it will be recursively enumerable.

  • 0
    Yes, the halting set depends on the choice of universal machine. However, most people still use the definite article.2012-03-12