- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Thu, 27 Jun 2002 15:59:49 +0200

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

Received on Thu Jun 27 2002 - 06:57:27 PDT

Date: Thu, 27 Jun 2002 15:59:49 +0200

At 11:41 -0700 25/06/2002, Wei Dai wrote:

Ah! A paper by Soare. Very good.

computability/recursion theory.

Yes. Classification of unsolvable problems has been the main purpose

in recursion theory since the fundamental papers by Emil Post.

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.

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.

"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

Received on Thu Jun 27 2002 - 06:57:27 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*