Re: immune to Cantor's diagonalization

[Bruno Marchal]

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:


snip





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, 

Re: immune to Cantor's diagonalization

[Bruno Marchal]

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


Dear Bruno,

Thank you very much for this explicit remark. It is very helpful  
for 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 only  
notion 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.


--


It seems that g is not necessarily specified by g(k), since k  
assumes too much.



?






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.


Part of the Non-halting result... OK.


It is easier than the non halting.






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.





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





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 the  
function without having to define the function?


This is too vague.





(Something like this is discussed here 
http://ndpr.nd.edu/news/24157-on-pr

Re: immune to Cantor's diagonalization

[Stephen P. King]

Dear Bruno,

Thank you very much for this explicit remark. It is very helpful 
for 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 only 
notion 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.


--


It seems that g is not necessarily specified by g(k), since k 
assumes too much.




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.


Part of the Non-halting result... OK.


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. It reminds me strongly of the problem of the 
axiom of choice, 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. How do we get around 
this impasse? What if there is a way to sequester the pathological parts 
of the function without having to define the function? (Something like 
this is discussed here 
http://ndpr.nd.edu/news/24157-on-preserving-essays-on-preservationism-and-paraconsistent-logic/) 

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

Re: immune to Cantor's diagonalization

[Bruno Marchal]

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 only  
notion 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 the  
universal machine, but he discovered the equivalent of Church  
thesis, which is the key notion to understand that the universal  
machine is truly universal.
Universality = universality with respect to computing, or any  
digital processes. Computing does not need to be restricted on  
numbers, but it happens that the natural numbers together with  
addition and multiplication is Turing universal, so that the  
numbers' restriction is an apparent restriction.
Computability is the only notion immune to Cantor's  
diagonalization, and that gives a conceptual very deep argument for  
Church 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 gr

Re: immune to Cantor's diagonalization

[Stephen P. King]

Hi Bruno,

Could you eleborate a bit about how "Computability is the only 
notion immune to Cantor's diagonalization"?


Onward!

Stephen

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





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