tag:blogger.com,1999:blog-20067416.post500583163902437023..comments2014-10-22T06:22:55.082-04:00Comments on Recursivity: Yet Another P vs. NP ProofJeffrey Shallitnoreply@blogger.comBlogger67125tag:blogger.com,1999:blog-20067416.post-86293089911030338052014-10-17T13:08:35.848-04:002014-10-17T13:08:35.848-04:00Ok. Now I feel embarrassed that I posted twice som...Ok. Now I feel embarrassed that I posted twice somehow, accidentally.<br /><br />But, seriously - theorems such as Godel's and other theorems proving the impossibility of doing something, such as Matiysevich's resolution of Hilbert's 10th problem, make me very depressed & hopeless. And, I know, that there are other such "impossibility theorems" out there, that I have no idea how to formulate, since I have never taken a formal course in Turing machines & logic, that may (hopefully not) make my attempts to solve certain math problems a certain way impossible.<br />But, I wouldn't even know if I am working on such a problem.IThinkWithMy Liverhttp://www.blogger.com/profile/07799396263113135068noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-35403128020360103312014-10-14T17:34:42.520-04:002014-10-14T17:34:42.520-04:00I now feel embarrassed for having published 2 pape...I now feel embarrassed for having published 2 papers on arxiv.org. After I uploaded, I grimace at the mistakes I made. Luckily, none that were fatal to the math. But, I had asserted more than I had proved.<br /><br />Now, after reading some of THESE doozies, I don't think there's anything reputable about posting papers there.IThinkWithMy Liverhttp://www.blogger.com/profile/07799396263113135068noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-14500238221654120432014-10-14T17:08:55.897-04:002014-10-14T17:08:55.897-04:00I now feel embarrassed for having published 2 pape...I now feel embarrassed for having published 2 papers on arxiv.org. After I uploaded, I grimace at the mistakes I made. Luckily, none that were fatal to the math. But, I had asserted more than I had proved.<br /><br />Now, after reading some of THESE doozies, I don't think there's anything reputable about posting papers there.IThinkWithMy Liverhttp://www.blogger.com/profile/07799396263113135068noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-44470178309951403992014-10-06T07:22:55.534-04:002014-10-06T07:22:55.534-04:00First, tell me whether you intend to pay up or not...First, tell me whether you intend to pay up or not. A clear "Yes, I will pay" or "No, I intend not to pay" will suffice.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-76162265750950462014-10-06T04:23:57.547-04:002014-10-06T04:23:57.547-04:00Since this is what you expect, can you tell me the...Since this is what you expect, can you tell me the topic of the paper as perceived by JACM.kamounahttp://kamouna.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-13992412492784076502014-10-05T13:56:17.590-04:002014-10-05T13:56:17.590-04:00That was not the terms of our bet. I quote, "...That was not the terms of our bet. I quote, "If your "paper" is published in J. ACM within two years (that is, a paper by you, with the same title, on the same subject), I pay you $1000. If it is not published, you pay me $500."<br /><br />Now if you want to wait for the full two years before paying, that would be reasonable. <br /><br />But changing the terms of the bet is not. It is exactly what I expected, though. Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-88899915527151155912014-10-05T13:49:39.972-04:002014-10-05T13:49:39.972-04:00Prove to me that the paper is not a computer scien...Prove to me that the paper is not a computer science paper.kamounahttp://kamouna.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-7028150739740092712014-10-05T13:34:37.997-04:002014-10-05T13:34:37.997-04:00Great!
When can I expect my check for $500? You ...Great!<br /><br />When can I expect my check for $500? You can send it to <br /><br />Jeffrey Shallit<br />School of Computer Science<br />University of Waterloo<br />Waterloo, ON N2L 3G1<br />Canada.<br /><br />I'm looking forward to it!Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-54449650837596493302014-10-05T10:58:55.485-04:002014-10-05T10:58:55.485-04:00Yes, JACM rejeted based on out-of-scope.
best,
R...Yes, JACM rejeted based on out-of-scope.<br /><br />best,<br /><br />Rafee Kamouna.kamounahttp://kamouna.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-72592205654082035502014-08-30T17:27:56.048-04:002014-08-30T17:27:56.048-04:00Less than a year remains for the bet to be settled...Less than a year remains for the bet to be settled.<br />Rafee, any progress?liav teichnerhttp://www.blogger.com/profile/00112618658287948748noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-66618147057024162192014-03-13T19:14:33.247-04:002014-03-13T19:14:33.247-04:00I do not know why you did not discover the truth, ...I do not know why you did not discover the truth, that P = NP, but only under particular conditions. Specifically, P = NP when either N=1 or P=0.<br /><br />I expect lots of acclaim for this insight, which has escaped all computer scientists.<br /><br />;-)Joe Felsensteinhttp://www.blogger.com/profile/06359126552631140000noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-91045467437193465232014-03-13T14:42:34.766-04:002014-03-13T14:42:34.766-04:00Let's see, you already admit one good journal ...Let's see, you already admit one good journal rejected your silly paper. But you claim rejection is impossible! I think that's yet another contradiction.<br /><br />Get your checkbook ready, Rafee!Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-79454997718792841112014-03-13T12:56:59.610-04:002014-03-13T12:56:59.610-04:00It will never get rejected. That's why Scott A...It will never get rejected. That's why Scott Aaronson doesn't allow the above proof at his blog.<br /><br />Van you refute it? or can he?<br />the Theory of Computing Journal rejected on the grounds that KR is undecidable. I proved KR is decidable iff it is undecidable.<br /><br />JACM rejected on the grounds that KR is undefined. I proved it is defined iff it is undefined. The decision took them 10 days only. The new paper is now 9-months pending.<br /><br />Refute it, or tell me why Scott is banning me.<br /><br />best,<br /><br />Rafee Kamouna.<br /><br /> kamounahttp://kamouna.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-31989643320251222832014-03-13T10:47:50.665-04:002014-03-13T10:47:50.665-04:00Fascinating drivel! Did your paper get rejected y...Fascinating drivel! Did your paper get rejected yet? I'm looking forward to my money.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-25773043846782589422014-03-13T09:29:53.042-04:002014-03-13T09:29:53.042-04:00Theorem: P=NP iff P!=NP.
The Kleene-Rosser parado...Theorem: P=NP iff P!=NP.<br />The Kleene-Rosser paradox is a counter-example to NP-completeness.<br />================================================<br />Russell's Paradox: The set that contains all the sets that do not contain themselves. If you ask the question:"Does it contain itself?". The answer would be it contains itself iff it does not contain itself.<br /><br />The Kleene-Rosser Paradox: Roughly, the function that may not be applied to itself, when combined with itself, it negates itself.<br /><br />This function is a lambda expression as "k:= NOT (x x)" which reads: The meaning of k is: "x" may not be applied to "x". Then deriving "kk" results in the paradox:<br />kk= NOT kk<br />If you assume that this function is total, you derive a contradiction, then it is not total. Then, if you assume that it is not total, again, a contradiction is derived, then it is total. So, it is total iff it is not total. The Church-Rosser argument shows that this function is undefined. Here, <br />http://kamouna.wordpress.com/2013/08/16/all-mathematical-systems-are-inconsistent/<br />it has been shown as defined iff it is undefined and decidable iff it is undecidable, both on the lambda-calculus and Turing machines. Below is a proof sketch.<br /><br />================================================<br />Step 1. Cook_Levin: For all w in L in NP, <br />M accepts w iff \exists A(w)=SAT.<br /><br />Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:<br />M_KR accepts w_KR iff e^-1(w_KR)= NOT e^-1(w_KR).<br /><br />Step 3. Put M=M_KR and w=w_KR.<br />==> L.H.S. of (1) = L.H.S. of (2).<br />==> R.H.S. of (1) = R.H.S. of (2).<br />==> There is no SAT(w_KR).<br />==> L_KR={w_KR_i} is in NP and NOT NP-complete.<br />==> L_KR is a counter-example for NP-completeness.<br />==> SAT is (NOT) NP-complete.<br />==> SAT is NP-complete <==> SAT is (NOT) NP-complete,<br /> Cook's proof is still correct despite the contradiction.<br />==> P=NP iff P!=NP.<br />================================================<br /><br />best,<br />Rafee Kamouna.kamounahttp://kamouna.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-59311272526022625242013-08-17T13:53:00.962-04:002013-08-17T13:53:00.962-04:00Rafee:
I have a limited amount of patience for yo...Rafee:<br /><br />I have a limited amount of patience for your incoherent babbling. Please make an effort to restrict your comments to one or two per week.<br /><br />I am looking forward to my $500.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-71701194886485572322013-08-17T13:50:56.004-04:002013-08-17T13:50:56.004-04:00The Church-Rosser Argument
A Function which is TO...The Church-Rosser Argument<br /><br />A Function which is TOTAL if and only if NOT TOTAL<br /><br />Definition: The Kleene-Rosser paradox reads: ``The $\lambda$-calculus expression consisting of the $\lambda$ term (k) which may not be applied to itself, when combined with itself, negates itself (kk)".<br />$$k\ =\ (\lambda x.\neg (xx))$$<br />$$kk\ =\ (\lambda x.\neg (xx)) k\ =\ \neg (kk)$$<br /><br />k_i may be applied to $k_i\ \equiv\ k_i$ may not be applied to k_i<br /><br />k_ik_i is total $\Longleftrightarrow\ k_ik_i$ is not total<br /><br />======================================================<br />Proofs:<br />======================================================<br />Theorem 2.1: Established Belief: The Church-Rosser Argument<br />\forall i, k_ik_i = \neg k_ik_i is undefined<br /><br />It is the $\lambda$-calculus corresponding counter-part for the Turing machine halting problem. Hence, it is undecidable.<br /><br />Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:<br /><br />1. If all functions defined by $\lambda$-expressions in $\Lambda$ were total, then one would have [k_ik_i = \neg k_ik_i] for the diagonal function $k_i$.<br /><br />2. This means that some functions, including the diagonal function, are not total.<br /><br />3. Since one does not have k_ik_i = \neg k_ik_i, instead one has [k_ik_i=\neg k_ik_i] is undefined.<br /><br />4. It is the $\lambda$-calculus corresponding counter-part for the Turing machine halting problem.<br />==========================================================================<br />Refutation:<br />A counter-example is constructed after universal quantification. Since the constructed counter-example (for established belief) is a contradictory expression, so if the universal quantification used an opposite property, still the same counter-example is derived.<br /><br />Theorem: Refutation of Established Belief:<br />\forall i k_ik_i = \neg k_ik_i is defined<br /><br />Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:<br /><br />1. If all functions defined by $\lambda$-expressions in $\Lambda$ were not total, then one would have:<br /><br />2. k_i may not be applied to k_i.<br /><br />3. (2) \equiv k_i may be applied to k_i.<br /><br />4. Implies: [k_ik_i = \neg k_ik_i]$ for the diagonal function k_i.<br /><br />5. Implies: one has [k_ik_i = \neg k_ik_i]. Contradiction derived, (1) must be negated.<br /><br />6. $\exists$ some functions, including the diagonal function, that are total.<br /><br />7. The diagonal function [k_ik_i = \neg k_ik_i] is defined.<br /><br />The Kleene-Rosser paradox can be articulated as in the following re-formulations:<br />[k_ik_i =\neg\ k_ik_i] is defined\ if and only if [k_ik_i=\neg\ k_ik_i] is undefined<br />[k_ik_i=\neg\ k_ik_i] is total\ if and only if [k_ik_i=\neg\ k_ik_i] is not total.<br />[k_ik_i=\neg\ k_ik_i] is decidable if and only if [k_ik_i=\neg k_ik_i]" is not undecidable.<br /><br />================================================================================<br />Best,<br />Rafee Kamouna.<br /><br /><br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-50888974687575592012013-08-17T12:40:18.004-04:002013-08-17T12:40:18.004-04:00Your chance of winning is less than zero. If you k...Your chance of winning is less than zero. If you know with whom I'm corresponding. He comes from a country that teaches differential and integral calculus at primary schools.<br /><br />Best,<br /><br />Rafee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-24009824912716672332013-08-17T12:17:52.050-04:002013-08-17T12:17:52.050-04:00Dear Rafee
who would not be interested when (s)he...Dear Rafee<br /><br />who would not be interested when (s)he sees a solution of a claymilenium open problem :-)<br />So is it correct to say that you have found a finistic formal proof of a contradiction in ZFC?<br />If so, can this be further improved to find a concrete sentence phi such that phi and not phi are both derivable from ZFC<br />together with theirs formal proofs in ZFC?<br /><br />==============================================================<br />Thanks a lot for your message and interest. The concrete sentence phi is there in the paper. There is a result:"SAT is NP-complete iff SAT is (NOT) NP-complete". Re-read it. As you may clearly see, the proof is a one step argument. Just simply consider stating Cook's theorem in the case of a paradoxical input, the contradiction is established. As I said in the paper, all the proofs are not in the form of:"A => B => C => D etc", rather it is a one step argument. The Kleene-Rosser paradox was historically misunderstood as an example of an undefined function, hence undecidable. Rather, it is proved that it is decidable iff it is undecidable. This is because it is defined iff it is undefined, rather than just undefined. This paradox is transformed from the lambda-calculus to Turing machines via a simple diagonalization argument.<br /><br />I would like to emphasize to you that diagonalization is not about mathematics at all. It is about physics. You actually perform an experiement, which is a counting one. It is like counting on your fingers, but you don't have an infinite number of fingers. It is a counting experiment to logically reason about an infinite sequence. It establishes a missing element in the sequence via arguing:"It is missing, because if it is not missing, a contradiction is derived". <br /><br />How can anyone ask me to formalize both the lambda-calculus & the Turing machine proofs in a formal system. I would tell them how the proof of the existence of uncomputable functions can be formalized in any standard proof system. If one reviews, e.g. Arora & Barak, the diagonalization table is drawn and the result follows from negating the diagonal. No definitions, no theorems nor proofs. No ZFC nor PA. Just a logically compelling counting argument that's simple but robust.<br /><br /><br />Best,<br />Rafee.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-162367635021364022013-08-17T11:13:41.058-04:002013-08-17T11:13:41.058-04:00Rafee:
Great! (Although in my experience, my c...Rafee: <br /><br />Great! (Although in my experience, my chance of getting a payment once you lose in vanishingly small.)Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-53517755055615222702013-08-17T10:38:22.495-04:002013-08-17T10:38:22.495-04:00And the discussion goes on:
======================...And the discussion goes on:<br />=================================<br />Dear Rafee<br />I believe that I can add some important consequence to your paper.<br /><br />There cannot be a polynomial TM solving SAT which would yield P=NP, which is impossible by your paper.<br />==============================================================<br />My paper did not claim that this is impossible. On the contrary my proofs show that both sides of the conjecture is provable. One can have two correct proofs, one for P=NP, another for P!=NP, provided by the same person, or by two different persons perhaps at different times.<br />==============================================================<br />P=NP says that *there is* such a TM, not that we can *prove* about it that it is such (polynomially bounded and correctly solving SAT problem)<br />But also we cannot prove *formally* that there is no such a TM.<br />==============================================================<br />Again, a correct proof of P=NP can never rule out a later proof of P!=NP and vice versa. The same holds for the Riemann hypothesis and any other conjecture/theorem.<br />==============================================================<br />As a result, it is the case that P!=NP is true, but we cannot formally prove it.<br />==============================================================<br />I proved both P=NP and P!=NP, hence mathematics is inconsistent. Since it is mathematics, it is about theory. If you want to switch to computer science, so here is not only mathematics where inconsistency is possible, but also PHYSICS, as computers are Boolean machines. No computer can print something if and only if it does not print it. No such inconsistency can be attained in the realm of physics, unlike the realms of logic, language and mathematics. So, in practice, anybody at anytime can devise a polynomial-time algorithm for SAT that works correctly for a particular experiment in a typical situation/instance. No proof of either termination or correctness of such an algorithm is meaningful. After proving mathematics is inconsistent, both proofs and disproofs of all conjectures and/or theorems are possible.<br />However, his claims of Polynomial-time SAT solvability would only be supported by experimental evidence like exhaustive testing of the algorithm.<br />==============================================================<br />The same phenomenon occurs with Godel's sentence Con(PA): it is true but formally unprovable.<br />==============================================================<br />Godel's results can be stated in relation to Hilbert second problem as:"A system can prove its own consistency if and only if it is inconsistent". Godel's results are:"If PA is consistent, then PA is incomplete". Now all theories are inconsistent, then Godel's incompleteness theorems are redundant as its antecedant is no longer true as he assumed it to be.<br /><br />So, it is not the same phenomenon at all. The P vs NP/SAT issue is a theory vs. practice conflicting situation where contradictions can be obtained in theory but not in pracitce, unless you believe in parapsychology which is pseudo-science. But if the language of science (mathematics) is inconsistent, so science is no better than pseudo-science. This is a serious social/public consequence of any proof of the inconsistency of mathematics. What do you think?<br />==============================================================<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-19505847480222711472013-08-17T08:32:54.370-04:002013-08-17T08:32:54.370-04:00Because I'm quite sure I'm the winner and ...Because I'm quite sure I'm the winner and you are the loser.<br /><br />Best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-53023981553779922902013-08-17T08:31:49.662-04:002013-08-17T08:31:49.662-04:00I do agree.I do agree.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-34682062664990203282013-08-17T08:27:04.972-04:002013-08-17T08:27:04.972-04:00Let's have a friendly wager, o great one! If ...Let's have a friendly wager, o great one! If your "paper" is published in J. ACM within two years (that is, a paper by you, with the same title, on the same subject), I pay you $1000. If it is not published, you pay me $500. <br /><br />Deal?Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-87163623322279833892013-08-17T08:18:03.463-04:002013-08-17T08:18:03.463-04:00It is currently being discussed at the Foundations...It is currently being discussed at the Foundations of Mathematics mailing list. This is an email that I have just received:<br />===============================<br />I skimmed through your exciting paper.<br />Do you, personally, believe that you have resolved the P vs. NP problem in it's intended meaning,(and you are going to win 1milion$)<br />or that contrary to this, there is a caveat, as it must seem to a novice, to that formulation in the lambda calculus?<br />Anonymousnoreply@blogger.com