[FOM] A Category of Godel Codings. Comments?

[H. Enderton]

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?

>It is commonly pointed out, in textbooks and elsewhere, that we don't
>lose much by focusing our study of computability to only the set of
>natural numbers.

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.

>For example, suppose I want to choose a coding method for, say,
>graphs with rationally weighted edges.

Here "coding" is a loaded term.  What you want is to *communicate*
a graph to the computational procedure.  So you describe exactly
the graph you have in mind -- and that description is nothing but
a word over a finite alphabet of k letters.  (Maybe k is the number
of keys on your keyboard.)  And the quality of the description
matters -- a poor description might not work.

And here is the connection:  There is no difference between the
set of words over a k-letter alphabet and the set of numerals
in k-adic notation.  (By k-adic notation, I mean standard base-k
notation, but with the digits {1, 2, ... , k}, without a zero
digit.)

>To be brief, the process of coding discrete objects requires 
>subjective choices and is highly non-canonical.  This lack of
>universality is somewhat disturbing.

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!

--Herb Enderton