Re: recursion theory

2002-06-27 Thread Bruno Marchal
Title: Re: recursion theory


At 11:41 -0700 25/06/2002, Wei Dai wrote:
On Mon, Jun 17, 2002 at 12:39:49PM +0200,
Bruno Marchal wrote:
 Recursion theory is the same as Computability Theory,
although
 the name recursion theory is used when the emphasis
is on the abstract
 theory. Recursion theory has born with Emil Post 1944 paper,
which is still
 a good introduction. Post paper can be find in Davis The
Undecidable.

I found a 38 page paper on the web
(http://www.math.ucla.edu/~asl/bsl/0203/0203-002.ps)



Ah! A paper by Soare. Very good.




about why
computability theory is historically called recursion theory, and why
we
should stop calling it that. I knew that recursive functions are the
same
as Turing-computable functions, which is a key result of
computability/recursion theory.
What I didn't realize until recently
was
how much work has been done on unsolvable problems, for example
classifying them according to the degree of unsolvability, and that
also
falls under the name recursion theory.



Yes. Classification of unsolvable problems has been the main
purpose
in recursion theory since the fundamental papers by Emil
Post.


I'm hoping this theory will offer some
insights about what uncomputable
universes might be like, and whether we should assign a non-zero
probability of being inside a uncomputable universe (i.e. whether
there could be uncomputable physical laws).



The problem is that there is no clear standart definition of
computability
with the reals. Well, there exists *too much* standart
definitions I should
say. Richard Pour El has wriiten a book showing that some
differential
equation can have non computable solutions but I have never
understand its
motivation for its definition of computable reals. At another
extreme you
have the entire relativisation of computability *on a ring* by
Blum Smale and
Shub which is far more interesting and also admit natural
extension for
quantum computing ...
Now, and we have discussed this before, I have no understanding
of the
expression being inside a universe. I really believe
that the uda shows
such an expression being senseless. The *apparent* partially
computable
universe is itself a result of averaging on all relative
computation
going through states closed to my *actual* state. This shows comp
implies
that our local universe must have non computable and computable
features.




 *The* classical treatise is the book
by Hartley Rogers:

 ROGERS H., Theory of Recursive Functions and Effective
Computability,
 McGraw-Hill, 1967. (2ed Ed. MIT Press, 1987).

I got this book yesterday. It seems to cover everything I want but
hasn't
been updated since 1967. (The second edition only fixes a few errors.)
I
wonder what interesting new results I might miss.



You just miss a bunch of highly technical results which will find
applications
in two or three centuries! Modern recursion theory has lose its
grip with
the original motivation and looks like, imo, a machine working
for itself.
I may be wrong of course. I have try to use some results and
methodologies
inspired by Drake work on the degree below O' but without
success. I think
that recursion has given important tools for more mundane
theoretical
computer science, for exemple in complexity theory or in
theoretical
inductive inference (Case and Smith, Oherson Stob Weinstein),
though.



I assume
Odifreddi's book is more up to date, but why is it called
Classical
Recursion Theory? Which parts of recursion theory is
considered
not classical?

Classical is a not well chosen term because in logic
not classical is
used for non classical logic. Here classical means the
elementary
theory on which the rest (of recursion theory) is based.
Not classical
means either generalisation of recursion theory, like
alpha-recursion
theory (where natural numbers are replaced by church-kleene
constructive
ordinals), or axiomatic approach to recursion theory, where the
axioms
fit different sort of recursion (including alpha recursion, or
beta recursion
with beta some other high ordinal, etc.). It is beyond the
elementary need
I make in my thesis.
Actually I believe that high ordinal recursion theory can be used
to show
that some result in my thesis can be applied in the non comp
context.
I have written some text on alpha-comp (alpha constructive
ordinal) and
comp-in-a-ring. Could be usefull for non-computationalist
approach, or
for weaker sort of comp.

I recall for the interested one that I have send two introductory
post
on recursion theory on line:
Diagonalisation 1:
http://www.escribe.com/science/theory/m3079.html
Diagonalisation 1 (answers)
http://www.escribe.com/science/theory/m3344.html

Bruno



Re: recursion theory

2002-06-25 Thread Wei Dai

On Mon, Jun 17, 2002 at 12:39:49PM +0200, Bruno Marchal wrote:
 Recursion theory is the same as Computability Theory, although
 the name recursion theory is used when the emphasis is on the abstract
 theory. Recursion theory has born with Emil Post 1944 paper, which is still
 a good introduction. Post paper can be find in Davis The Undecidable.

I found a 38 page paper on the web
(http://www.math.ucla.edu/~asl/bsl/0203/0203-002.ps) about why
computability theory is historically called recursion theory, and why we
should stop calling it that. I knew that recursive functions are the same
as Turing-computable functions, which is a key result of
computability/recursion theory. What I didn't realize until recently was
how much work has been done on unsolvable problems, for example
classifying them according to the degree of unsolvability, and that also
falls under the name recursion theory.

I'm hoping this theory will offer some insights about what uncomputable
universes might be like, and whether we should assign a non-zero
probability of being inside a uncomputable universe (i.e. whether
there could be uncomputable physical laws).

 *The* classical treatise is the book by Hartley Rogers:
 
 ROGERS H., Theory of Recursive Functions and Effective Computability,
 McGraw-Hill, 1967. (2ed Ed. MIT Press, 1987).

I got this book yesterday. It seems to cover everything I want but hasn't
been updated since 1967. (The second edition only fixes a few errors.) I
wonder what interesting new results I might miss. I assume
Odifreddi's book is more up to date, but why is it called Classical
Recursion Theory? Which parts of recursion theory is considered
not classical?




recursion theory

2002-06-16 Thread Wei Dai

I'm trying to learn about recursive ordinals and related topics such as
the arithmetical hierarchy, which are studied under the name recursion
theory. Is anyone here familiar with recursion theory? Can anyone
recommend a book on it?