Hello Stephen, On 01 Dec 2011, at 13:16, Stephen P. King wrote:

## Advertising

Hi Bruno,Could you eleborate a bit about how "Computability is the onlynotion immune to Cantor's diagonalization"?

`Cantor proved that infinity is sensible to diagonalization. Given an`

`infinite set, you can find a bigger set by diagonalization.`

`Gödel proved that any effective provability system (theory) is`

`incomplete. Given a theory rich enough to talk on numbers, you can`

`build a richer provability system by diagonalization.`

`Tarski proved that any system of definition will lack the expressive`

`power to define some notion, notably its truth notion. Again, this`

`follows from diagonalization.`

`Diagonalization is a sort of transcendental operation in mathematics.`

`If you have about anything pretending to be a universal notion in the`

`domain, you can diagonalize against it.`

`That is why Stephen C. Kleene was skeptical when Church told him that`

`his lambda-calculus defined a universal notion of computability.`

`At first, it looks like computability is sensible, NOT immune, to`

`diagonalization. Imagine that there is a universal language for`

`computability L. Consider all the computable function defined on N and`

`with value in N, enumerated from their code in that language:`

f_0, f_1, f_2, f_3, f_4, etc.

`Let g be defined on n by g(n) = f_n(n) + 1 (g is said to be defined`

`by diagonalization)`

`Each f_i are computable function from N to N, so f_n(n) is well`

`defined, and "+ 1" is obviously computable, so g seems to be computable.`

`But if L is universal, the g should be in the list. So g = f_k, for`

`some k.`

But then g(n) = f_k(n), given that g = f_k In particular, with n = k g(k) = f_k(k) But by definition of g, we know that g(k) = f_k(k) + 1 By Leibniz identity rule f_k(k) = f_k(k) + 1

`And by using the fact that f_k is a function from N to N, we know that`

`f_k(n) is a number for any n, so f_k(k) is a number, and this number`

`can be subtracted at the left and right hand side of the equality`

`above, so`

0 = 1. Church's pretension that L is universal seems to be refuted. But that proof is wrong. Do you see why?

`Take the time to find the mistake by yourself before reading the`

`solution below.`

------

`What is wrong is that the language L might define more than the`

`computable functions from N to N, but can also define functions from`

`from subset of N to N. In that case, the reasoning just shows that`

`g(k) = f_k(k) is not defined.`

`This shows that an universal machine can crash (run in a loop without`

`ever giving an output), and this necessarily so to be universal.`

`Worse, there will be no effective means (and thus no complete theory`

`of universal machine or language) to decide if some f_i is defined on`

`N or a proper subset of N. If that was the case, we would be able to`

`filter out the functions from a proper subset of N to N from the`

`functions from N to N, and then the diagonalization above would lead`

`to 0 = 1.`

`Let us call a function partial if that function if either from N to N,`

`or from a subset of N to N, and a function is total if it is defined`

`on N. The reasoning above shows that the set of total functions is not`

`immune to diagonalization. But the superset of the partial functions`

`is, and that is a deep strong argument for Church thesis.`

`As far as I know, in mathematics, only computability, and`

`computability related notion (like their relativization on oracles)`

`are immune for the diagonalization. Gödel, in his Princeton lecture`

`called that immunity a miracle.`

`Everything that I explain depends on this. UDA works thanks to the`

`universality of the UD, which relies on that diagonalization closure,`

`and AUDA uses the fact that self-reference is build on the`

`diagonalization procedure. Unfortunately, or fortunately, all`

`diagonalizations are hidden in Solovay's theorem on the arithmetical`

`completeness of G and G*.`

`You might search on "diagonalization" in the archive of this list to`

`find more on this.`

Bruno

On 12/1/2011 4:21 AM, Bruno Marchal wrote:I have an original thesis on that. Not only Babbage discovered theuniversal machine, but he discovered the equivalent of Churchthesis, which is the key notion to understand that the universalmachine is truly universal.Universality = universality with respect to computing, or anydigital processes. Computing does not need to be restricted onnumbers, but it happens that the natural numbers together withaddition and multiplication is Turing universal, so that thenumbers' restriction is an apparent restriction.Computability is the only notion immune to Cantor'sdiagonalization, and that gives a conceptual very deep argument forChurch thesis.

http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.