Page 161 - Textos de Matemática Vol. 40

A note on the history of functional self-application 149 ‘one-minute proof’ of the undecidability of a special case (viz. self-divergence)”
[Der05, Section 3]:
Consider any programming language supporting programs as data [...], which has some sort of conditional (if ...then ...else ...) and includes at least one non-terminating program (which we denote loop). Consider the decision problem of determining whether a pro- gram X diverges on itself, that is, X(X) = ⊥, where ⊥ denotes a non-halting computation. Suppose A were a program that pur- ported to return true (T) for (exactly) all such X. Then A would perforce fail to answer correctly regarding the behavior of the fol- lowing (Lisp-ish) program:
C(Y ) := if A(Y ) then T else loop(),
since we would be faced with the following contradiction:
C(C) returns T ⇔ A(C) returns T ⇔ C(C) diverges.
This argument follows exactly Hilbert’s argumentation, just with true instead of “= 0” and non-halting instead of “̸= 0”.
There are many other cases, in which self-application is used for unde- cidability, undefinability, and inconsistency results, cf. e.g., [Bee85, Theorem 11.1, p. 235]. They might not be directly linked to the form of Hilbert’s ar- gumentation, but they share with Hilbert’s paradoxical function the spirit of self-application as a special case of diagonalization.
A.7 A modern perspective
In this Section we discuss how Hilbert’s paradoxical function f is treated in systems which allow self-application. Since Hilbert’s argument is correct, the possibility to define such a function f would prove the inconsistency of the system. However, the definition of f does not only involve self-application, but also a case-distinction with (in)equality tests. In fact, theories with self- application only have restricted capacity to perform these (in)equality tests.
In some approaches, case-distinction is restricted to natural numbers, i.e., before testing t ̸= 0 one has to show that t is a natural number. However, a case- distinction on whether t is a natural number or not, is not available. Therefore, all one could deduce from Hilbert’s definition in this context is that f f is not a natural number.
In general, theories with self-application are best suited to a partial con- text, where one considers functions which could be undefined for certain argu- ments. In this case, t ̸= 0 can only be tested, if it is shown before that t is defined. Thus, in Hilbert’s case we only get that f f is not defined. Again, a test of definedness is not available (this is just the conclusion drawn in Der- showitz’s argument above).