On 20 Jan 2014, at 20:49, Stephen Paul King wrote:
Dear Bruno,
The idea that I am pursuing here is how to think of Becoming in a
way that is consistent with comp.
You have to think about it as an indexical. The logic of becoming, and
why it is so crucial for us, is guven by S4Grz1.
So far all we have are eternal static infinite entities.
Yes, but they have clear notion of internal indexical histories.
Measures are hard to define.
But the one we need has to exists, or comp is false.
bruno
On Mon, Jan 20, 2014 at 4:38 AM, Bruno Marchal <marc...@ulb.ac.be>
wrote:
On 19 Jan 2014, at 21:01, Stephen Paul King wrote:
Dear Bruno,
Thank you for writing this remark! It is very helpful.
You are welcome.
I could see where there could be some debate on the
constructability claim, as the set of all programs in L could be
infinite and thus the lexicographic ordering would be a supertask
in that case, but that can be ignored for now.
Well, the set of all programs is *always* infinite, for universal
and non universal languages. The point is that it can always be
generate by one program (it is recursively or computably
enumerable). But the subset of all programs computing *total*
functions, everywhere defined, is also infinite but is not a
recursively or computably enumerable set. It is not computable,
necessarily so if the language is universal.
My interest now is in the computational Word Problem. I have
more homework to do.
That is a particular case. By the way, the diffeomorphism of 4-
variety is non computable, like the word problem in group theory, or
the semantic of programs in computer science. factorial(x) is a
computable function, but the adjective "being the code of the
factorial function" is a non computable predicate. There are no
algorithm capable to decide if, given an arbitrary programs, it
computes the factorial function. This is easy to prove with the Dx =
xx method, but you can intuitively understand this by meditating on
the following question. Does the following program compute the
factorial function:
<<
Define factorial
read x
If x = 0 output 1
else
search for a formal proof of the Goldbach conjecture in ZF, and if
you find it compute x * factorial(x-1),
else print " I don't compute factorial"
>>
You see that the question how knowing if that code (which is
executable, it is really a program) codes for the factorial
function, is equivalent with solving the Goldbach conjecture.
Bruno
On Sun, Jan 19, 2014 at 6:33 AM, Bruno Marchal <marc...@ulb.ac.be>
wrote:
Stephen, Liz,
On 18 Jan 2014, at 00:02, LizR wrote:
On 18 January 2014 11:39, Stephen Paul King <stephe...@provensecure.com
> wrote:
Dear John,
I invite your comment on a statement and question: There is not
observable difference between "X is non-computable" and "there
does not exist sufficient resources to complete the computation of
Y".
Are X and Y effectively the same thing, everything else being
equal? If there is a difference that makes a difference, what
might it be?
In other words, is anything non-computable because of some
theoretical reason, rather than "merely local geographical" ones
(which might cease to be restrictions if, say, our local even
horizon expands, or we construct wormholes to other universe) ?
Surely the halting problem?
Of more easily the totality problem. It is more complex than
halting, and thus more easily shown to be non computable.
Let me do it here, as I promise to Stephen. It is almost a direct
consequence of Church thesis.
I recall that a function (from N to N) is said TOTAL computable if
you can explain in a finite set of words, in one formal language,
with a decidable simple grammar, how to compute it on each (cf
TOTAL) natural numbers, in a finite time, and this to a
sufficiently dumb person.
Church's thesis: there is a universal language L in which all TOTAL
functions can be described/coded, and my language "lambda calculus"
is such a language.
Theorem: Church's thesis entails that L describes more than just
all TOTAL functions.
Proof: suppose that L describes only the TOTAL functions. We can
lexicographically order all programs in L (due to the clear
decidable grammar) p0, p1, p2, p3, .... Let us call f_i the
function computed by p_i
Then we can define a function g such that g(n) = f_n(n) + 1. Indeed
we can even program it in L. (To compute it on n, generate the list
up to p_n and apply p_n on n, then add 1. As all f_n are total,
this gives a total function (everywhere defined on N).
So that function g as some program p_k, and thus compute some
function f_k belonging to the list (L is universal).
But then, let us apply g on its own code k, we have g(k) = f_k(k),
given that g = f_k.
But we have also that g(k) = f_k(k) + 1, by definition of g. So
f_k(k) = f_k(k) + 1.
And, by totality, f_k(k) is a number. So I can subtract it from
both side in the preceding equality, and we get
0 = 1. Contradiction.
So either L is not universal (and Church is wrong), or f_k(k) is
not defined, and f_k is not total.
Then if you look in "lambda calculus", you can empirically observe
that f_k(k) is indeed not defined: p_k does not stop on k. Making
Church thesis consistent.
So if Church thesis is true, and if some language L is truly
universal, the list of its programs p_i will go through all total
computable functions (by universality), but will also go through
many NON TOTAL functions.
And, the key point, you will not been able to use any program to
distinguish the code of the total function from the code of the non
total one.
Why? Because if that was the case, you would be able to filter out
the non total function from the list of all programs p_i, and you
would get a computable enumeration (list) of all, and only the
total functions, and the diagonal above would again conclude that 0
= 1.
So the attribute of a code "computing a total function" cannot be
computable. QED.
OK? (you have to read this with pencil and paper!)
This was a constructive proof, leading to a meaningful predicate
("TOTAL") being not computable.
Thi entails a strong form of incompleteness: no effective theory
(with checkable proofs) can ever decide if some arbitrary code is
the code of a total, or not, function.
(Note that a far easier, but non constructive and less informative,
proof is given directly by Cantor theorem. The computable functions
are codable, making them enumerable, but N^N, the set of all
functions from N to N is NOT enumerable by Cantor theorem.
So almost all functions from N to N are not computable.)
Bruno
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com
.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to a topic in
the Google Groups "Everything List" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/everything-list/TBc_y2MZV5c/unsubscribe
.
To unsubscribe from this group and all its topics, send an email to everything-list+unsubscr...@googlegroups.com
.
To post to this group, send email to everything-
l...@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
--
Kindest Regards,
Stephen Paul King
Senior Researcher
Mobile: (864) 567-3099
stephe...@provensecure.com
http://www.provensecure.us/
“This message (including any attachments) is intended only for the
use of the individual or entity to which it is addressed, and may
contain information that is non-public, proprietary, privileged,
confidential and exempt from disclosure under applicable law or may
be constituted as attorney work product. If you are not the
intended recipient, you are hereby notified that any use,
dissemination, distribution, or copying of this communication is
strictly prohibited. If you have received this message in error,
notify sender immediately and delete this message immediately.”
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-
l...@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to a topic in
the Google Groups "Everything List" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/everything-list/TBc_y2MZV5c/unsubscribe
.
To unsubscribe from this group and all its topics, send an email to everything-list+unsubscr...@googlegroups.com
.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
--
Kindest Regards,
Stephen Paul King
Senior Researcher
Mobile: (864) 567-3099
stephe...@provensecure.com
http://www.provensecure.us/
“This message (including any attachments) is intended only for the
use of the individual or entity to which it is addressed, and may
contain information that is non-public, proprietary, privileged,
confidential and exempt from disclosure under applicable law or may
be constituted as attorney work product. If you are not the intended
recipient, you are hereby notified that any use, dissemination,
distribution, or copying of this communication is strictly
prohibited. If you have received this message in error, notify
sender immediately and delete this message immediately.”
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.