Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
Indices of Turing machines (in your favorite enumeration) that halt on the empty input? Gödel numbers of theorems of pure predicate calculus? –  Henning Makholm Mar 3 '12 at 19:36
    
@HenningMakholm I think your answer works if "your favorite enumeration" is a computable enumeration. –  Michael Hardy Mar 3 '12 at 21:21
1  
@Michael, if it wasn't computable, why would it be anyone's favorite? :-) –  Henning Makholm Mar 3 '12 at 21:27
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
This is only true if the non-logical language contains binary relation symbol. Pure first-order logic, by itself, is decidable. –  David Harris Mar 4 '12 at 0:12
    
I'm not sure I've ever thought about the "pure" form. –  Michael Hardy Mar 5 '12 at 1:18
add comment

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.

share|improve this answer
    
Or more simply put: "the halting set": en.wikipedia.org/wiki/… –  Quinn Culver Mar 4 '12 at 17:51
    
~A~ halting set. –  David Lewis Mar 5 '12 at 1:57
    
Yes, the halting set depends on the choice of universal machine. However, most people still use the definite article. –  Quinn Culver Mar 12 '12 at 14:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.