[FOM] A Category of Godel Codings. Comments?
H. Enderton
hbe at math.ucla.edu
Wed Aug 31 16:02:57 EDT 2005
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
More information about the FOM
mailing list