tag:blogger.com,1999:blog-20067416.post500583163902437023..comments2014-09-19T06:40:48.246-04:00Comments on Recursivity: Yet Another P vs. NP ProofJeffrey Shallitnoreply@blogger.comBlogger58125tag: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.comtag:blogger.com,1999:blog-20067416.post-78162577943187573412013-08-17T07:49:34.439-04:002013-08-17T07:49:34.439-04:00Luca Trevisan rejected my JACM 2011 submission in ...Luca Trevisan rejected my JACM 2011 submission in 2 weeks without review. On 20th June 2013, I submitted a new paper with a letter to him and the editor-in-chief Victor Vianu. After 10 days, the paper status became:"Waiting for Referee Selection" which is its status till now. This means Luca Trevisan was unable to refute my 2013 paper as he did in 2011. Boaz Barak is the associate editor handling my submission after Laszlo Babai's rejection of my 2010 two papers.<br /><br />1. Luca proved to me that the Kleene-Rosser paradox must be undefined, hence uncdecidable.<br /><br />2. I proved to him it is defined iff it is undefined. Hence, it is decidable iff it is undecidable over both the lambda calculus and Turing machines.<br /><br />Best,<br /><br />Rafee.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-70906619244043132322013-08-17T06:43:11.927-04:002013-08-17T06:43:11.927-04:00And it has as much chance of being accepted there ...And it has as much chance of being accepted there as a dog turd. Congrats, Rafee!Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-55485858250720830122013-08-17T04:11:25.001-04:002013-08-17T04:11:25.001-04:00The new paper:"The P versus NP Problem is Wro...The new paper:"The P versus NP Problem is Wrong:P=NP iff P!=NP" was recently submitted to JACM. It is available for download here: http://kamouna.wordpress.com.<br /><br />Best,<br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-86947910670187482412012-12-27T10:04:30.758-05:002012-12-27T10:04:30.758-05:00Rafee:
We are always amused by your waggish sense...Rafee:<br /><br />We are always amused by your waggish sense of humor. Your satire on a real academic paper is delightful and inspiring. Jon Stewart and Stephen Colbert have nothing on you!Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-91955466399742582692012-12-25T11:39:27.816-05:002012-12-25T11:39:27.816-05:00Check my recent presentation at CNRS-Paris here:
...Check my recent presentation at CNRS-Paris here:<br /><br />http://kamouna.wordpress.com/<br /><br />Check my posts here:<br /><br />https://rjlipton.wordpress.com/2012/12/21/what-would-be-left-if/#comment-30369<br /><br />I hope that you would comment constructively.<br /><br />Best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-267845128432044102012-12-24T18:09:06.945-05:002012-12-24T18:09:06.945-05:00"Rafee Kamouna's work is refutable iff it..."Rafee Kamouna's work is refutable iff it is irrefutable."Uli Fahrenbergnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-10210334669739837102012-11-08T18:19:19.729-05:002012-11-08T18:19:19.729-05:00And after all these months you cannot make any obj...<i>And after all these months you cannot make any objective argument against my work.</i><br /><br />How could I? You have already told me many times it is irrefutable. Therefore, it is clearly a waste of time to attempt to do so.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-10498176110644456932012-11-08T08:19:59.917-05:002012-11-08T08:19:59.917-05:00So, you regard the CNRS, which is on top of all Fr...So, you regard the CNRS, which is on top of all French universities as crackpots? And after all these months you cannot make any objective argument against my work.<br /><br />Best,<br /><br />Rafee Kamouna.Rafee Kamounahttp://kamouna.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-46526530043078261992012-11-08T06:52:06.918-05:002012-11-08T06:52:06.918-05:00Thanks, Rafee. I am writing a book on mathematica...Thanks, Rafee. I am writing a book on mathematical crackpots, and this will be helpful.Jeffrey Shallithttp://www.blogger.com/profile/12763971505497961430noreply@blogger.com