On 14 May 2013, at 00:57, Russell Standish wrote:

On Mon, May 13, 2013 at 03:24:09PM -0700, meekerdb wrote:
On 5/13/2013 2:49 PM, Stephen Paul King wrote:
Does the UD compute *all* functions or only those that are
recursively enumerable?

It computes all of them.

Brent


Sorry - it does not compute all functions, just all partially
recursive ones. As Stephen says, there are only countably many
recursive functions, but a continuum of functions from N->N.

As for Stephen's question of why we might want to single out that set
- it so happens that that set is closed under diagonalisation - which
is Goedel's "miracle".

Its an aesthetic thing - just like Einstein's theory of general
relativity is the simplest, and most elegant, formulation of geometric
spacetime theories of gravitation.

It doesn't mean its right, of course, but elegant theories have a
habit of  being more likely right than inelegant ones.

PS - I am unsure whether the set of partially recursive functions is
the only such set closed under diagonalisation - do you know Bruno?

It should be possible to build some ad hoc other sets. Some sets, like those related to truth and knowledge can be said to be also immune, but this is due to the fact that they cannot be defined formally. It is a different sort of diagonalization immunity. Many non computable set will be like that too. I am pretty sure, that the set of partial recursive functions (with or without oracle) is (are) the only non trivial , effective (RE) definable sets close for diagonalization.

Bruno





Cheers

--

----------------------------------------------------------------------------
Prof Russell Standish                  Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Professor of Mathematics      hpco...@hpcoders.com.au
University of New South Wales          http://www.hpcoders.com.au
----------------------------------------------------------------------------

--
You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en .
For more options, visit https://groups.google.com/groups/opt_out.



http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.


Reply via email to