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. -- http://mail.python.org/mailman/listinfo/python-list
