[FOM] A Category of Godel Codings. Comments?

[Arnon Avron]

On Wed, Aug 31, 2005 at 01:02:57PM -0700, H. Enderton wrote:
 
> Rex Butler wrote:
> >I have been studying basic recursion/computability theory lately, 
> 
> In ten years, one terminology or the other (i.e., either "recursion"
> or "computability") will look terribly dated.  For some things I am
> presently writing up, I wish I knew which one!  Either "c.e." or "r.e."
> is not going to survive in good health.  But which?

I am sure that "r.e." will survive. First, it is established and used in
too many textbooks (and too many people are used to it. In fact, except 
for people strictly working in recursion theory, I personally know
nobody who uses "c.e."). Second, "recursive" is a well-defined
mathematical concept, while "computable" will never be one. The attempt
to change terminology is an attempt to force Churchr thesis as a 
mathematical definition, But it is far from clear (and in my opinion
never will be fully clear) what exactly this thesis exactly says - I
have heard too many contradicting interpretations of it. This is the 
reason why I, for one, will never use "c.e." 

> 
> Yes and no.  I claim that the correct objects of study are not
> *numbers*, but *numerals*.  (Remember the short-lived "New Math"?  
> I have an old elementary-school workbook where on one page the
> instructions read, "Circle the correct numeral.")  That is, in
> computability theory one examines procedures that, *given* x will
> *return* f(x).  One cannot be given a number, but only a numeral.
> Numerals are strings of symbols -- little pieces of language.
> As such, numerals can be communicated (to your computer, from your
> computer).  Numbers cannot.

I dont agree. We all know what addition is, but addition is done
completely differently when one is using decimal representations
of numbers, binary ones, or a representation as a list of strokes. If computation is
done only with numerals or string of symbols, then I dont see how 
 completely different functions, applied to the same numerals (say
111+11) can all be refered to as "addition" (by the way: "string of symbols"
is also just an abstract object - a symbol written by me with a pen
using my "beautiful" handwriting is not really identical to the "same"
symbol typed by machine. Moreover: what is a string? what should be the
maximal distance between two symbols in a "string" that we still call
it a "string"?). 

   I maintain that all real computations and construction are done with
abstract objects (not *too* abstract - but this is another issue). Already 
the solutions of  construction problems
in Geometry were algorithms for *abstract* lines and points, using
abstract ruler and compass, not anything done by actual ruler and compass!

> Yes, descriptions are not unique.  Conclusion:  Computing on graphs
> is not different from computing on N, except that there is a hidden
> equivalence relations that gets swept under the rug by the adoption
> of a coding.  And under the rug is the right place for it!

Perhaps here is hidden your possible answer to my argument: there are
equivalence relations involved. But "an equivalence relation" is a more
abstract notion then the notion of a natural number. Moreover: what is the
equivalence relation when it comes to different systems of numerals
(except "representing the same number")?.

Arnon Avron