Re: 'Recursively enumerable' sets

In article <8741e38b-26bf-48be-abc8-fc2837fb3f6a@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<sanchopancho80@xxxxxx> wrote:

I have read the term 'recursively enumerable set' and do not know
exactly what it means.

Perhaps the following make sense: A set X is recursively enumerable
iff there is an alphabet A (i.e. a finite set) such that X is a subset
of A* and the indicator function 1_X:A*--->{0,1} is a partial
recursive function. The same should work for the term 'recursive set'
with 'total recursive function'.

I confess I am not sure if this is equivalent. The notion I am
familiar with is that a set is recursively ennumerable if there is a
Turing machine that generates a list of the elements of the set, so
that any given element that is in the set will occur at some finite
step.

A set is decidable if there is a Turing machine which, given an input,
will determine whether the in put is in the set or not.

For subsets of N, the natural numbers (one of the most common settings
for the discussion), finite sets are always decidable; a set is
decidable if and only if its complement is decidable. A decidable set
is always recursively enumerable. And if both the set and its
complement are recursively enumerable, then the set is decidable
(given an input, start both the Turing machine that lists the set and
the one that lists the complement running. The input will eventually
appear in one of the two lists, and this determines whether the
element is or is not in the set).

However, there are sets that are recursively enumerable but whose
complement is not recursively enumerable.

Wikipedia (http://en.wikipedia.org/wiki/Recursively_enumerable) states
that a set is 'recursively enumerable' iff there is a partial
recursive function f with f(x)=0 if x is an element of X and undefined
otherwise. But this makes no sense! Where does x come from?

x is a natural number; these discussions are, unless otherwise
specified, usually in the context of subsets of N. You have a Turing
machine that will eventually answer "yes" if x is in the set, but will
run without halting if x is not in the set. If you are sitting around
waiting for an answer, you do not know if the Turing machine has not
halted because it hasn't quite finished, or because it will never
halt...

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: Recursively enumerable sets
    ... Turing machine that generates a list of the elements ... for the discussion), finite sets are always ... decidable if and only if its complement is decidable. ... the one that lists the complement running. ...
    (sci.math)
  • Re: [PO] Halting Problem Final Conclusion
    ... such program (for a Universal Turing Machine) could be written. ... A Turing Machine using that method will never halt, ... Indeed, no Turing Machine can list the elements of NHalt2, the ... Let's assume that there exists a Turing Machine, N, which lists the ...
    (comp.theory)
  • Re: [PO] Halting Problem Final Conclusion
    ... such program (for a Universal Turing Machine) could be written. ... A Turing Machine using that method will never halt, ... Indeed, no Turing Machine can list the elements of NHalt2, the ... Let's assume that there exists a Turing Machine, N, which lists the ...
    (sci.logic)
  • Re: Need help with terminology
    ... Here is how three textbooks define a Turing Machine's number of states: ... Q is a finite set of internal states. ... that includes every automata with a transition function (and possibly a state ... >> Finite State Machine has much less power than a Turing Machine. ...
    (comp.theory)
  • Re: Cantor Confusion
    ... lists, there are also uncountably many WM-constructible numbers. ... If you mean that there are more finite definitions than numbers, ... This is the definition of countablity. ... the n-th Turing machine the n-th digit of the number it represents. ...
    (sci.math)