SM Ryan wrote:
# easy way to see this, is to ask yourself: how come in mathematics
# there's no such thing as "addresses/pointers/references".
The whole point of Goedelisation was to add to name/value references into
number theory.
Is that so? That implies that there is some table where you can
associate names (or whatever type of locators: call them pointers,
whatever) with arbitrary values. But in fact that's not the case.
Thus Goedel was able to add back pointers contrary to the
set hierarchy of the theory of types and reintroduce Russel's paradox.
Nope. Goedel didn't add anything, he just revealed what was already
there: that you can have statements of number theory, well-formed
formulas constructed out of existing operators without any backpointer
tricks, which have true interpretations , but are not theorems.
Everything in a Goedel's string can be recursively expanded to yield an
ordinary formula! There is no infinite regress, no unchased embedded
pointer-like things left behind.
Self-reference is achieved using two tricks: Goedel numbering, and
indirect reference. Godel numbering allows a formula to talk about
formulas, by way of embedding their Godel numbers, and translating
formula-manipulations into arithmetic manipulations (of interest are
finite ones that will nicely unfold into finite formulas). In essence
that which used to be ``code'' can be now treated as ``data''', and
operations on code (logical derivations) become arithmetic operations
on data.
Indirect reference is needed because a formula G's Goedel number cannot
be inserted into itself directly. If you start with a formula G which
has some free variable V, and then produce some new formula by
substituting G's Goedel number into it directly for occurences of V,
you no longer have G but that other formula. You want whatever comes
out to be G, and so the input formula, the one with the free variable,
cannot be G, but perhaps a close relative which either talks about G,
or whose constituent formulas cleverly end up talking about G after the
substitution takes place.
Instead of a direct (Goedel number) reference, you can insert into a
formula some /procedure/ for making that formula's Goedel number out of
another formula's Goedel number and talk about it that way. As an
example, instead of saying ``here is a number'' by inserting its
literal digits, you can say ``the number that results by applying this
formula to this other number''. For instance, instead of writing the
number 4 we can write successor(3). or 2 + 2. We explicitly
mention some other number, and say how 4 is constructed out of it.
Douglas Hofstadter exposition of all this is very good. To allow the
formula G to mention its own Goedel number, Douglas Hofstadter uses
another formula which he calls U, the ``uncle''. The trick is that: the
procedure for making G's Goedel number out of U's number is the
arithmetic equivalent of the same procedure that's used to substitute
the Goedel number of U for the free variable in U itself. So as U (the
formula) is treated by substituting its own Godel number for its one
and only free variable, it produces G, and, at the same time, the
arithmetic version of that substitution, fully contained inside the U
formula itself, turns the now substituted copy of U into G also. U
contains the fully expanded ``source code'' for the arithmetic version
of the free-variable substitution procedure, and it contains a free
variable representing the arithmetic version of the formula on which
that algorithm is to be done. As that free variable within U is
replaced by the Goedel number U, the overall formula becomes G, and the
embedded free-variable-replacement procedure is instantiated concretely
over U's Goedel number, so it becomes a constant, unparameterized
calculation that produces G's Goedel number.
Voila, G contains a procedure that computes the arithmetic object
(Goedel number) that represents G's ``source code'' (the symbolic
formula), out of the embedded number representing U's source code.
Using that giant formula, G can assert things about itself, like ``I am
not a theorem'' (i.e. ``there exists no integer representing the Goedel
numbers of a list of true statements that represent a derivation
deducing myself as the conclusion'').
There are no name references or pointers or anything. All the functions
are primitive recursive, and so can be expanded into finite-length
formulas which contain only numbers and operators and variables---dummy
ones that are bound to existential quantifiers, not to concrete values
some external name/value table.
