On 02 Dec 2011, at 13:26, Stephen P. King wrote:

Dear Bruno,

Please re-read that last post slowly. I fear that you are rushing to a judgement of what I am trying to communicate and completely missing the idea that I am trying to sketch out.

On 12/2/2011 6:26 AM, Bruno Marchal wrote:

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


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.

But it still seems that there is something missing in this conclusion about the Church thesis. It is that for computation all that 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 complained about is part of this problem that I see.

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

Your notion of time seems to be lifted directly from the ordering of the natural numbers, so in a sense you are taking time as the sequence 1 2 3 4 .. as inducing a ab initio measure of change. The problem is that unmeasurable sets exists and restricting ourselves to tiny little islands of thought is not progressive. We may find solutions to the measure problem by considering more carefully exactly how we define measures. Ordinary notions of measure seem to be based on Platonic notions, definitions given by fiat. Are you familiar with how topos theory treats the notion of a set? The following is from Jonhstone's Topos theory" p. xvii

    I am considering an evolving universe, not a "fixed" one.

The notion of classical computability is topos independent. Non classical computability is interesting but not relevant for the issue of the classical Church thesis that we need to make sense of comp in cognitive science. The notion of time is also not relevant.

The role of topos is comp is explained in "conscience et mécanisme". A topos basically is good to modelize a mathematician's mind, not the arithmetical reality.

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.

Are not the natural numbers a set and thus have an implicit set theory?

Natural numbers are no more set than fortran program. You can represent numbers with set, but this does not make a number a set. Natural numbers admit a simpler first order theory than set or elementary toposes.

Just because you did not invoke a set theory specifically does not absolve you from the implicit use of a set theory.

I don't, in the theory. I do in the epistemology at the naive level, like engineers, philosophers or like when I do shopping. Set theory is just not relevant for Church thesis.

I write "a set theory" instead of "set theory" because set theories are Legion! I have seen instances where huge fights have occurred in academia because of people having completely different set theories with which they are interpreting a theory.

That is one good reason to not use set theory. I don't believe in sets, actually. But even this remark is not relevant for what we were talking about.

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

Which one? You confuse computation and definition.

When are definitions computable (constructable by recursive functions) and when are they otherwise? This is not a trivial point!

That is a reason for keeping those notion apart.

How do we get around this impasse?

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

LOL! It seems that I am more radical in my thinking and you are conservative in yours here.

I have never hide that I am an extreme conservative. Modernity has ended in 523.

The problem is that these "old and basic uncontroversial notions" are causing problems for the advancement of physics and our understanding of "old" problems, such as the mind-body problem.

Indeed, I show that those old and uncontroversial notions makes physics a branch of number theory. Just study and criticize the proof, instead of escaping forward with technical notions none knows in the list. Or use them specifically.

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

This is too vague.

I agree, my apologies, but if I knew the explicit well formed statement required then I would not be asking the question that I am asking.

(Something like this is discussed here 

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

It is relevant to the question I am asking. Please re-read my original post and try to see the idea that I am considering.

I did. I don't see the point at all. Sorry.

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


Are you familiar with configuration, state and phase spaces used in physics?

What is the point of this with Church's thesis? Church's thesis has nothing to do with physics. Don't confuse Church's thesis and Deutsch physicalist version (which is a different thing).

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.

    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.

Do you see that I am considering generalizing the notion of computation and with it the notion of information? The current notion of information (Shannon) is based on the differences that make a difference for physical systems and thus assumes a particular form of physics. This is what D. Deutsch mentions in his writings that you seem to argue is wrong, but I think it is you that are thinking too narrowly about what is physics.

Physics is not part of the theory. I presume nothing. And the result is that physics is a number dream. But that is a result in a theory.

It seems to me, and I admit that this is just an intuition, that we are constraining the notion of computation to too small of a box to realize its full potential. Why is the notion of time so scary for 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.

No, I see short-comings in the current set of conceptual tools that we use to build explanations. I am trying to explore further out in the undiscovered country...

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*.

OK, but I want to go further. We need for logics the equivalent of a principle of variation so that we do not have to resort to the ansatz of Platonic walls to explain where universal computation is implemented.


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

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

Can you think of the trail of ideas connecting these two concepts? You have cut my post into little pieces here and thus have ambiguated the context, please re-read the original post.

You don't make specific point. I sell you an aquarium, and you complain we cannot put birds in it.

but it is as if you are afraid to look over the edge and stare into the abyss. I think that the Tennenbaum theorem offers us a clue. It states 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.

Could we be in a frame that includes both Model theory and computer theory and number theory?

Not simultaneously, and without purpose.

We need to retain the property of countability and recursivity for computation but need the spectrum of possibilities that non- standard models allows to act as a range of variation. Is there a version or model of arithmetic that would allow this but retain the expressiveness 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.


Is there something like PA but more expressive that allows for a notion of countability (maps to some set of number) and recursive (so that we can have a more general notion of "countable" and "recursive" in the sense of the quote from Johnstone about sets)?

Yes we can. The question is "why do you want to do that?".



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 
For more options, visit this group at 

Reply via email to