Re: 'Recursively enumerable' sets

magadin wrote :

In article
<8741e38b-26bf-48be-abc8-fc2837fb3f6a@xxxxxxxxxxxxxxxx
legroups.com>,
<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).

this seems ok.



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

what ?

which set is that ?

suppose that set is M and M is a subset of the integers N.

M is recursively enumerable so its complement is N/M.

so to enumerate the complement of M , just enumerate N without the elements of M ( which can be found because M is recursively enumerable by definition )



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
Bill Watterson)
======================================================
================

Arturo Magidin
magidin-at-member-ams-org


regards

tommy1729
.

Relevant Pages

  • Re: Recursively enumerable sets
    ... iff there is an alphabet A (i.e. a finite set) such that X is a subset ... A set is decidable if there is a Turing machine which, given an input, ... 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: Shade color recipe from ActiveState fails?
    ... parameter lists -- before realizing that dec2rgb isn't even used! ... left shade and complement intact. ... set R [expr ] ...
    (comp.lang.tcl)
  • 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)
Quantcast