From: Hector Zenil (hzenilc@gmail.com)
Date: Tue Dec 05 2006 - 15:57:19 MST
On 12/5/06, Philip Goetz <philgoetz@gmail.com> wrote:
> On 12/5/06, Hector Zenil <hzenilc@gmail.com> wrote:
> > The complexity theory you are referring to is called "computability theory".
> >
> > sincerely,
> >
> > Hector Zenil
>
> http://en.wikipedia.org/wiki/Computational_complexity_theory
¿?
Understanding the difference between recursive, recursively
enumerable, and co-recursively-enumerable (or replace recursive by
computable) could easily be the fundamental theorem of the
Computability theory (which gives rise to the first Turing degree),
which of course could be seen as part of a wider computational
complexity theory but I am just pointing out the particular field to
which such subject belongs if one wants to differentiate it from
traditional complexity theory as you wanted.
On 12/5/06, Philip Goetz <philgoetz@gmail.com> wrote:
>
> (here I'm using "complexity theory" to refer to i.e. understanding
> the difference
> between recursive, recursively enumerable, and co-recursively-enumerable,
> not to "complexity studies" a la the Santa Fe Institute)
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:57 MDT