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

From: Wei Dai <weidai.domain.name.hidden>

Date: Tue, 25 Jun 2002 11:41:32 -0700

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?

Received on Tue Jun 25 2002 - 11:42:35 PDT

Date: Tue, 25 Jun 2002 11:41:32 -0700

On Mon, Jun 17, 2002 at 12:39:49PM +0200, Bruno Marchal wrote:

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).

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?

Received on Tue Jun 25 2002 - 11:42:35 PDT

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