On 02 Dec 2011, at 13:26, Stephen P. King wrote:
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
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
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
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
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
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
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
(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
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.
Could we be in a frame that includes both Model theory and
computer theory and number theory?
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.
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
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 email@example.com.
To unsubscribe from this group, send email to
For more options, visit this group at