On 02 Dec 2011, at 05:16, Stephen P. King wrote:

Dear Bruno,Thank you very much for this explicit remark. It is very helpfulfor my research. I have some comments and a question.On 12/1/2011 11:34 AM, Bruno Marchal wrote:Hello Stephen, On 01 Dec 2011, at 13:16, Stephen P. King wrote: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. Givenan infinite set, you can find a bigger set by diagonalization.Gödel proved that any effective provability system (theory) isincomplete. Given a theory rich enough to talk on numbers, you canbuild a richer provability system by diagonalization.Tarski proved that any system of definition will lack theexpressive power to define some notion, notably its truth notion.Again, this follows from diagonalization.Diagonalization is a sort of transcendental operation inmathematics. If you have about anything pretending to be auniversal notion in the domain, you can diagonalize against it.That is why Stephen C. Kleene was skeptical when Church told himthat his lambda-calculus defined a universal notion of computability.At first, it looks like computability is sensible, NOT immune, todiagonalization. Imagine that there is a universal language forcomputability L. Consider all the computable function defined on Nand 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 bedefined by diagonalization)Each f_i are computable function from N to N, so f_n(n) is welldefined, and "+ 1" is obviously computable, so g seems to becomputable.But if L is universal, the g should be in the list. So g = f_k, forsome 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) + 1And by using the fact that f_k is a function from N to N, we knowthat f_k(n) is a number for any n, so f_k(k) is a number, and thisnumber can be subtracted at the left and right hand side of theequality above, so0 = 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 thesolution below.------It seems that g is not necessarily specified by g(k), since kassumes too much.

?

What is wrong is that the language L might define more than thecomputable functions from N to N, but can also define functionsfrom from subset of N to N. In that case, the reasoning just showsthat g(k) = f_k(k) is not defined.This shows that an universal machine can crash (run in a loopwithout ever giving an output), and this necessarily so to beuniversal.Part of the Non-halting result... OK.

It is easier than the non halting.

Worse, there will be no effective means (and thus no completetheory of universal machine or language) to decide if some f_i isdefined on N or a proper subset of N. If that was the case, wewould be able to filter out the functions from a proper subsetof N to N from the functions from N to N, and then thediagonalization above would lead to 0 = 1.Let us call a function partial if that function if either from N toN, or from a subset of N to N, and a function is total if it isdefined on N. The reasoning above shows that the set of totalfunctions is not immune to diagonalization. But the superset of thepartial functions is, and that is a deep strong argument for Churchthesis.But it still seems that there is something missing in thisconclusion about the Church thesis. It is that for computation allthat one needs to consider in a model is the N -> N and n /subset N -> N maps/functions. The problem of time that I have complainedabout is part of this problem that I see.

Time is not relevant here. We need only the natural numbers.

It reminds me strongly of the problem of the axiom of choice,

`The axiom of choice is not relevant here. This can be made precise: ZF`

`and ZFC proves the same arithmetical truth. I don't use set theory at`

`all.`

where the existence of unmeasurable sets cannot be excluded inducingsuch things as the Banach-Tarski paradox. The same problem thatoccurs in the result you discuss above: there is a function/objectthat cannot be exactly defined.

Which one? You confuse computation and definition.

How do we get around this impasse?

I don't see an impasse. I explain old and basic uncontroversial notions.

What if there is a way to sequester the pathological parts of thefunction without having to define the function?

This is too vague.

(Something like this is discussed here http://ndpr.nd.edu/news/24157-on-preserving-essays-on-preservationism-and-paraconsistent-logic/)

Nothing there is relevant with the issue I was talking about.

We see a similar process in physics where the abstract spacesare defined to be well behaved ab initio. What if this "goodbehavior" is emergent, like what happens when we couple a largenumber of chaotic systems to each other. The entrainment processbetween them forces them to behave as if they are nice and linear!(L. M. Pecora and T. L. Carroll, “Synchronization in chaoticsystems,” Phys. Rev. Lett. 64, 821 (1990). )

?

As far as I know, in mathematics, only computability, andcomputability related notion (like their relativization on oracles)are immune for the diagonalization. Gödel, in his Princeton lecturecalled that immunity a miracle.Immune from diagonalization but not from forcing.

`? (forcing is a technic in set theory or in model theory. It does not`

`concern us here). Modal logic, which have a role in computability (but`

`not here) generalizes forcing in some way.`

It seems to me, and I admit that this is just an intuition, that weare constraining the notion of computation to too small of a boxto realize its full potential. Why is the notion of time so scaryfor computer scientists and logicians?

`It is not scary, and it plays some role in some chapter. but we`

`generalize it by using any recursive function on the inputs and`

`programs. It is hard to make sense of your comment. You introduce`

`difficulties where they don't exist, I think.`

Everything that I explain depends on this. UDA works thanks to theuniversality of the UD, which relies on that diagonalizationclosure, and AUDA uses the fact that self-reference is build on thediagonalization procedure. Unfortunately, or fortunately, alldiagonalizations are hidden in Solovay's theorem on thearithmetical completeness of G and G*.OK, but I want to go further. We need for logics the equivalentof a principle of variation so that we do not have to resort to theansatz of Platonic walls to explain where universal computation isimplemented.

?

You seem to know a something about this idea given your previousreference to amenable groups ,

OK, but that has nothing to do with Church thesis.

but it is as if you are afraid to look over the edge and stare intothe abyss. I think that the Tennenbaum theorem offers us a clue. Itstates that "no countable nonstandard model of Peano arithmetic (PA)can be recursive".

I think that you mix many things. We were not in Model theory.

We need to retain the property of countability and recursivity forcomputation but need the spectrum of possibilities that non-standardmodels allows to act as a range of variation. Is there a version ormodel of arithmetic that would allow this but retain theexpressiveness of PA?

`PA. The non standard models are models of PA. I have no clue what you`

`are trying to say. You should not mention more technical stuff when`

`simpler one are presented to you, unless you can make a specific point.`

Bruno

You might search on "diagonalization" in the archive of this listto find more on this.BrunoOnward! Stephen PS. Some related papers:http://arxiv.org/abs/1110.5456 "Meaning in Classical Mathematics: Isit at Odds with Intuitionism?" A good discussion with examples ofconsequences.http://arxiv.org/abs/1109.5886 "Non-Archimedean Whitney-stratifications" Another good example of a similar idea.http://arxiv.org/abs/1108.5062 "A Non-Standard Semantics for KahnNetworks in Continuous Time" The picture that this paper paints isvery close to my intuition.--You received this message because you are subscribed to the GoogleGroups "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.

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.