What is the difference between a recursively enumerable and recursive set?

What is the difference between a recursively enumerable and recursive set?

In automata theory, the difference between a recursively enumerable set and a recursive set lies in their computability properties.

A recursively enumerable set, also known as a semidecidable set, is a set of strings for which there exists a Turing machine that will eventually halt and accept any string in the set, but may either halt or loop indefinitely for strings not in the set. In other words, there is an algorithm that can recognize the set, but it may not always be able to reject strings not in the set.

On the other hand, a recursive set, also known as a decidable set, is a set of strings for which there exists a Turing machine that will always halt and either accept or reject any string. In other words, there is an algorithm that can recognize the set and will always provide a definitive answer for any given string.

In summary, the main difference between a recursively enumerable set and a recursive set is that a recursively enumerable set can be recognized by a Turing machine that may not always halt for strings not in the set, while a recursive set can be recognized by a Turing machine that always halts and provides a definitive answer for any string.