Dear Bruno,
Thank you for writing this remark! It is very helpful. 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.
My interest now is in the computational Word Problem. I have more
homework to do.
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-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.
