On 19 Jan 2014, at 21:01, Stephen Paul King wrote:

## Advertising

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 constructabilityclaim, as the set of all programs in L could be infinite and thusthe lexicographic ordering would be a supertask in that case, butthat 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 morehomework 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 notobservable difference between "X is non-computable" and "there doesnot exist sufficient resources to complete the computation of Y".Are X and Y effectively the same thing, everything else beingequal? If there is a difference that makes a difference, what mightit be?In other words, is anything non-computable because of sometheoretical reason, rather than "merely local geographical" ones(which might cease to be restrictions if, say, our local evenhorizon expands, or we construct wormholes to other universe) ?Surely the halting problem?Of more easily the totality problem. It is more complex thanhalting, and thus more easily shown to be non computable.Let me do it here, as I promise to Stephen. It is almost a directconsequence of Church thesis.I recall that a function (from N to N) is said TOTAL computable ifyou can explain in a finite set of words, in one formal language,with a decidable simple grammar, how to compute it on each (cfTOTAL) natural numbers, in a finite time, and this to a sufficientlydumb person.Church's thesis: there is a universal language L in which all TOTALfunctions can be described/coded, and my language "lambda calculus"is such a language.Theorem: Church's thesis entails that L describes more than just allTOTAL functions.Proof: suppose that L describes only the TOTAL functions. We canlexicographically order all programs in L (due to the cleardecidable grammar) p0, p1, p2, p3, .... Let us call f_i the functioncomputed by p_iThen we can define a function g such that g(n) = f_n(n) + 1. Indeedwe can even program it in L. (To compute it on n, generate the listup to p_n and apply p_n on n, then add 1. As all f_n are total, thisgives a total function (everywhere defined on N).So that function g as some program p_k, and thus compute somefunction 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. Sof_k(k) = f_k(k) + 1.And, by totality, f_k(k) is a number. So I can subtract it from bothside in the preceding equality, and we get0 = 1. Contradiction.So either L is not universal (and Church is wrong), or f_k(k) is notdefined, and f_k is not total.Then if you look in "lambda calculus", you can empirically observethat f_k(k) is indeed not defined: p_k does not stop on k. MakingChurch thesis consistent.So if Church thesis is true, and if some language L is trulyuniversal, the list of its programs p_i will go through all totalcomputable functions (by universality), but will also go throughmany NON TOTAL functions.And, the key point, you will not been able to use any program todistinguish the code of the total function from the code of the nontotal one.Why? Because if that was the case, you would be able to filter outthe non total function from the list of all programs p_i, and youwould get a computable enumeration (list) of all, and only the totalfunctions, and the diagonal above would again conclude that 0 = 1.So the attribute of a code "computing a total function" cannot becomputable. 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 isthe 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 functionsare codable, making them enumerable, but N^N, the set of allfunctions 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 GoogleGroups "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 inthe 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 theuse of the individual or entity to which it is addressed, and maycontain information that is non-public, proprietary, privileged,confidential and exempt from disclosure under applicable law or maybe constituted as attorney work product. If you are not the intendedrecipient, you are hereby notified that any use, dissemination,distribution, or copying of this communication is strictlyprohibited. If you have received this message in error, notifysender immediately and delete this message immediately.”--You received this message because you are subscribed to the GoogleGroups "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.