Wednesday, September 01, 2010

Intelligent questions about the alleged P NE NP proof

People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the aftermath. Most of the discussion was about the same questions I had posted a few days ago. In fact, here is a direct quote: Your post mixed interesting questions, which were ignored, and stupid thoughts, which is all anyone commented on. Why don't you repost just the interesting questions?

SO, here is that posts questions, minus the stupid things I said, plus things I heard at the conference.
  1. Why did this proof get so much attention before it was verified? Because Lipton and Cook took it seriously.
  2. Was this all good for the community? YES- more people know what P vs NP is. YES- if Gowers and Tao now begin working on it more. YES- stone soup.
  3. Do mathematicians care about complexity theory? The answer is surely yes, but how strongly? Is the answer yes or Yes or YES or HELL YES! ? If you count number-of-mathematicians then its hard to say. If you take a weighted sum based on quality of mathematicians then Gowers and Tao alone make the weighted sum enormous. In any case, when did the change happen? Was it drastic or slow?
  4. If someone claims to prove a big result and its public and problems are found with the proof, should they retract? If so then by when? One thing problematic with the question is the word should. Should for the good of the field? Should for the good of ones own career? Should if you want to be taken seriously? If someone has minor mistakes and just needs a little more time to fix them then a retraction is not needed. But the terms minor mistakes and a little more time are not well defined.
  5. How much progress has been made on P vs NP? Scott thinks so. (See the talk Has there been progress P vs NP which is on his homepage.)
  6. Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan? Finding and intermediary c.e. degree was such a problem, but it wasn't anywhere near as hard or as important as P vs NP.
  7. What criteria SHOULD we use to determine if a proof of a major result is worth looking at?
  8. What criteria DO we use to determine if a proof of a major result is worth looking at?
  9. Has Descriptive Complexity Theory been ruled out as a way to solve P vs NP (something like oracles or natural proofs)?
  10. The story about the story has reached the New York Times: here

125 comments:

  1. So your last post on this topic was not really the `last' post? Why don't you leave this topic behind and write something useful.

    ReplyDelete
  2. Sorry, but I totally disagree with your view of all this nonsense as something useful. With all my respect to Lipton and Cook (add any names to this list, e.g., my own PhD supervisors), I think that a brief comment from them is not a reason for so many clever people to start wasting their time on reading nonsense.

    I feel a bit sorry that Scott, whose initial reaction was the most reasonable among those who openly responded, started apologizing later. If those willing to waste their time feel that Scott's (or anybody else's) not taking this seriously is offensive, that shouldn't be Scott's problem at all.

    I understand that he might have some "tenure considerations" to start apologizing, that is totally understandable, I am also not going to sign this with my real name. I am only saying that I would love to have seen at least one both reasonable and signed reaction to all this Deolalikar's nonsense, which I, unfortunately, did not...

    ReplyDelete
  3. Apparently, the guy has given a talk at HP and said that his new, better and revised manuscript, that has not been released publicly, was endorsed by some unnamed people who he send them to. The same people seem to have send "confirmations" early on.

    Of course, since his proof has been shred to peaces without any hope of rescue (the fatal blow being dealt by Tao and a couple of other diligent commentators), he can maybe show off in intimate HP meeting. That may help sooth the pain of failure, damage control at least in his own backyard. He is not going to be fired from HP for this. However, if they do not extend his contract, he will be hard pressed to find any decent job. Maybe he can work as a cook, or in a bakery, though they might fire them there too if he tries to sell half baked shabby cakes to the general population. Like HP, he might damage the reputation of the bread shop.

    ReplyDelete
  4. Dear Lance & Bill,

    You were editors of papers for which I received the below comments:


    ----- Forwarded Message ----
    From: Rafee Ebrahim
    Cc: rafee102000@yahoo.com
    Sent: Thu, August 26, 2010 9:27:17 AM
    Subject: Re: your proof


    Thanks a lot for your message. It is nice to hear from you again. Here is the link for CH & AoC:

    http://arxiv.org/abs/0807.2543

    Also here, a new theory of Quantum Gravity as the last paper in the .pdf file:
    http://arxiv.org/abs/0806.2947v1

    I hope you would be able to convince the third reviewer soon: I gave semantic as well as syntactic proofs of the same result. So, I hope you would be able to. I announced my results in many blogs that discussed Vinay D. solution, but I was ignored. The impact is when somebody specialist announces verification of my proofs.

    Regarding the implications, I preferred every CS, Mathematics, Physics researcher to reflect what it means for himself rather than myself, but I shall try. Thanks a lot for such recommendation which I appreciate.

    Thanks again for hearing from you, something that I wish all the time.

    Best,

    Rafee.

    --------------------------------------------------------------------------------
    To: Rafee Ebrahim
    Sent: Thu, August 26, 2010 8:57:56 AM
    Subject: Re: your proof

    We would love to annouce Rafee but right now the third reviewer is not
    yet ready to declare acceptance. So kindly be patient with us while
    we try to convince.

    But you can announce on the many TCS theoy blogs out there, they are
    already discussing a lot on P vs. NP result of Vinay D., so there
    couldn't be a better time for you to announce. Please point me to the
    CH and AOC results, I am interested in them.

    Also I highly recommend you write a paper (more readable by the
    masses) on what the implications of your results are. I think they
    have very broad (and tragic) ramifications to CS, Mathematics, and
    Physics. People will not take you seriously because they are so
    sudden and negative, but be assured: all the top brains including
    Einstein have had an uphill climb to start with.

    Best,
    L.

    On Mon, Aug 23, 2010 at 3:45 AM, Rafee Ebrahim wrote:
    > That's great news from you. I hope that you announce this news or someone on
    > behalf of the journal.
    >
    > Thank you for your congratulations for me, I wish the best for you too.
    >
    > For other results you can check that of the Continuum Hypothesis and the
    > Axiom of Choice.
    >
    > Best,
    >
    > Rafee.
    >
    > ________________________________
    > To: rafee102000@yahoo.com
    > Sent: Mon, August 23, 2010 11:28:14 AM
    > Subject: your proof
    >
    > Rafee,
    >
    > I'm reviewing your PNP proof for a reputed journal, and it is
    > fascinating. I cannot reveal my identity right now, due to obvious
    > anonymity reasons, but I'm a TCS researcher at a top university on the
    > west coast of the United States and you've written on my blog in the
    > past. I and other reviewers have almost finished verifying your proof
    > and its correctness. I suggest you annonce it more widely at this
    > point and claim the Clay Millennium Prize:
    > http://www.claymath.org/millennium/
    >
    > I am happy for you. Congrats on your achievement and I look forward
    > for more groundbreaking results from you. It is truly amazing, but
    > also sad at the same time, given the implications of your results.
    >
    > Best,
    > L.
    >
    >

    ReplyDelete
  5. Anon 3: Were you always such a dickhead??
    Vinay D. made an attempt and he was not successful. He was not running for publicity. But, it seems you have nothing better to do then pass some smart ass comments.
    Anon 4: Congrats. I think L. mean Luca Trevisan.

    ReplyDelete
  6. Dear Anon.

    I suppose he put his initial "L." to let me able to figur out but he supplied other information to make it conclusive. I wrote in two blogs whose intial "L", Lance and Luca, but he said he is in the west cost.

    Thanks a lot for your congratulation.

    ReplyDelete
  7. "Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan?"
    Don't know if any of these count:

    Gödel's incompleteness theorem solved Hilbert's Second Problem after the whole Hilbert school (von Neumann, Ackermann, etc) had spent years battling in the wrong direction.

    The Robbins conjecture was proposed in 1933 and nobody got anywhere with it for 6+ decades. Then in the 1990's somebody put it into a computerized theorem prover and the answer fell out.

    Gauss's construction of the 17-gon was the first new Euclidean regular polygon construction since the ancient Greeks.

    ReplyDelete
  8. didn't Andrew Wiles work in secret for 7 years and then surprise everyone at a talk?

    ReplyDelete
  9. I wouldn't worry a second about all this fuss about the proof. Remove all the information about the proof, and view this situation as another problem. If this proof was published in... 1982, would this have happened? Most of the fuss was online. Every CS had something to say about it, from "Finally!" to "Meh!" . That talk attracted the media and there you are.

    The stone soup is a very good analogue of what happened. Only that Deolalikar was in his house , thinking he was the only one that could "smell the soup".

    Concluding, this proof allowed many people to work together, which is good thing. It also attracted the attention of the media, which is both positive and negative. It's positive because it attracts "good" elements, such as funding, new people who are REALLY interested in CT etc. , but also think of the avalanche of P NP proofs that are to follow , from people who want their 15 minutes of fame.

    ReplyDelete
  10. GASARCH asks: Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan?

    Claude Shannon's A mathematical theory of communication and Communication in the presence of noise attacked much-studied problems, and obtained unlooked-for results, via novel proof technologies, from an unlooked-for author.

    ReplyDelete
  11. I guess the distance between academic dishonesty and forgery is not that large...

    ReplyDelete
  12. Are the bloggers like the rogue banks that messed up our economy and lives -- all up side and no down side? Clearly it is in their interest to beat the drum rolls. their success is linked to eyeballs. Surely there should be a reprimand for needlessly causing so much commotion, specially for the Lipton blog which wasted so much of our time.

    ReplyDelete
  13. Surely there should be a reprimand for needlessly causing so much commotion, specially for the Lipton blog which wasted so much of our time.

    No one but you can waste your time.

    ReplyDelete
  14. I felt Lipton committed a well-intentioned error of judgment about that post. It may have had something to do with his perspective about the P/NP problem itself, which he's written up in earlier blog posts and which I find a bit odd, though he's of course entitled to it.

    ReplyDelete
  15. I was not so much upset by the time wasted as by Regan's statement that he and Lipton had pondered the question of "sharing credit". Quite revealing and distasteful, considering that they had no really new ideas to add.

    ReplyDelete
  16. This incindent sure uncovered A LOT of dirt. TCS community was pwned in many ways, and it was not only Deolalilalilalikakar that kicked own goal.

    ReplyDelete
  17. Bill, let's stop talking about this paper and move on. The questions other than items 7 and 8 are not intelligent.

    When will you post Report from Barriers II Part 2?

    ReplyDelete
  18. Augustine: "Et vae tacentibus de Te, quoniam loquaces muti sont."

    "Woe to those who say nothing concerning thee [God] because the chatterboxes talk nonsense."

    ---------

    That is why my appreciation and gratitude are extended to the entire "first-name" cadre of mathematics bloggers—Bill, Lance, Scott, Dick, Gil, Terry, Tim, Dave (and others)—for praising mathematics so effectively, publicly, and generously. May they never lose heart or be daunted by criticism.

    ReplyDelete
  19. The spate of aggressive trolling on this blog has reached a level where I am now removing it from my RSS feed. Perhaps you could consider requiring people not to post anonymously, encourage the use of real names, or use blog software that allows filtering out the anonymous comments.

    Best regards.

    ReplyDelete
  20. Requiring an openid or a username won't restrict open speech or nasty comments, anyone can obtain a nickname, it will just make commenting harder for anonymous and will drop the total number of anonymous comments. May turn out to be good thing.

    ReplyDelete
  21. This episode had mostly positive consequences, in terms of stirring up interest in complexity in people (both Mathematicians and the general public) who normally don't think about it. I also think it didn't hurt people in our community to imagine for a second that it may be possible to see a proof in the near future.

    There is probably a misconception left in the general public, in the sense that people may think that there was some kind of technical progress on P vs NP made by Deolalikar. (To my knowledge there wasn't.) But of course since the P vs NP problem is likely to be with us for a few decades, am sure this misconception will be forgotten within a couple of years. (I doubt that in 2050 when the problem is solved they'll say in the new york times "X, building on the work of Deolalikar, proved that P \neq NP"...)

    The important thing is that there is no such misconception in the TCS community. So as far as we are concerned, it doesn't matter much whether or not he retracts his claims. (Retraction is more important where there is a chance people unaware of errors may use the paper as a basis for further work.)

    Boaz Barak

    p.s. Bill/Lance: I concur with Andras. I think people with a sensible comment can sign their name, and we don't need to see the non-sensible comments.

    p.p.s. Rafee: That email is a hoax. There is no way Lance/Luca or any other reputable researcher believe you (or anyone else) currently has a proof resolving P vs NP.

    ReplyDelete
  22. Dear Boaz Barak,

    Have you read my proof? It's not available publicly.

    ReplyDelete
  23. Dear Rafee, I haven't read your proof, but was trying to do you a favor by pointing out the email you received was a hoax. Feel free to ignore my comment If you prefer to think otherwise.
    Best,
    --Boaz Barak

    ReplyDelete
  24. Suppose it's a hoax, still there is the journal decision. It's now 7 months under review.

    ReplyDelete
  25. Boaz, ignore that Rafee Kamouna guy, he wrote the "email" himself.

    ReplyDelete
  26. Forget about the email and try to falsify the following proofs:

    Proof of: “P=NP iff P!=NP” – Syntactic.
    The proof is by diagonalization as follows:

    NP={L_1,L_2,L_3,…}
    L_1={w_11,w_12,w_13,…}
    L_2={w_21,w_22,w_23,…}
    L_3={w_31,w_32,w_33,…}

    Each string w_ij can be written as the Turing machine describing it which can be written as two substrings, the first its input and the second is the computation configurations:
    = w_iw_j

    Hence we have,

    L_1={w_1w_1,w_1w_2,w_1w_3,…}
    L_2={w_2w_1,w_2w_2,w_2w_3,…}
    L_3={w_3w_1,w_3w_2,w_3w_3,…}

    Note that both the diagonal and its complement can easily encode the Kleene-Rosser paradox as:

    KR={kk_1,kk_2,kk_3,…}={Not kk_1, Not kk_2, Not kk_3…}

    Use the encoding e(kk_i)=w_iw_i and e(Not kk_i) = \bar w_i\bar w_i

    You obtain: e(KR) in NP iff e(KR) NOT in NP, of course e(KR) irreducible to SAT iff it is reducible to SAT.

    Hence, P=NP iff P!=NP.

    This should not be surprising as the lambda calculus is equivalent to Turing machines. By direct encoding of the lambda calculus paradox, you obtain it on Turing machines.

    ReplyDelete
  27. This proof was syntactic, the same result can be reached via independently via semantics.

    The line of argumentation of Cook's proof of CNF SAT being NP-complete is as follows:

    "Let A be a language in NP accepted by a non-deterministic Turing machine M. Fix an input x, we will create a 3CNF formula \phi that will be satisfiable if and only if there is a proper tableau for M and x"

    1. Let w be the encoding of the Kleene-Rosser paradox, thus e^-1(w)=Not e^-1(w), where e is an encoding function.
    2. M accepts w.
    3. SAT is NP-complete, Cook's theorem.
    4. There must exists \phi(w):\phi(w) is satisfiable.
    5. Then \phi(w) is satisfiable iff M accepts w iff e^-1(w)=Not e^-1(w)
    6. M accepts w is "True".
    7. Then: \phi(w) is satisfiable iff e^-1(w)=Not e^-1(w) – Logical Contradiction.
    8. Then There must be no \phi(w) which is satisfiable.
    9. Then SAT is (NOT) NP-complete.

    ReplyDelete
  28. I wonder if Rafee Kamouna itself is a hoax. Someone just wants to have fun with us? Have anyone met Mr. Kamouna in person? Was he at any TCS conference? I am dying to meet him. :D

    ReplyDelete
  29. Talk scientifically and falsify the proofs.

    ReplyDelete
  30. Rafee, your proof does not even make sense. Look at the line 8th. You should be writing somewhat opposite of it. There are some problems with line 15, 31 and 42 too.

    I checked your core reports too. I think you are a dreamer and do not want to work in life. Otherwise how could you let these trivial errors crept in your proof.

    http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/k/Kamouna:Rafee_Ebrahim.html

    ReplyDelete
  31. You are referring to papers more than 2 years old. Though the results are correct but they were using fuzzy logic. The same results are reached without it using the Kleene-Rosser paradox as in the proof sketch above.

    So do you refer to the proof in relation to Cook's proof or the proof by diagonalization?

    The line numbers you mentionm can you tell me to which paper you refer?

    ReplyDelete
  32. line number in this blog.

    ReplyDelete
  33. how come line number 42??

    Can you tell me how to reduce a paradox to SAT?

    Otherwise SAT is not NP-complete?

    ReplyDelete
  34. JACM Lance's review of my 2008 paper said:"A Turing machine cannot diagonalize against itself", here:
    http://lucatrevisan.wordpress.com/2008/12/24/inducing-percussions-in-all-of-mathematics/


    The above proof (diagonalization) shows that if the input is a paradox the Turing machine would diagonalize against itself.

    ReplyDelete
  35. Rafee why do not you shut up now with your garbage. Given that the previous poster pointed out the meaningless lines.

    ReplyDelete
  36. He mentioned numbers that do not exist, where is 42? where is 30?

    Don't say garbage since you don't understand and rely on somebody else's non-existing comments.

    ReplyDelete
  37. Rafee Kamouna is not a troll. He is just a misguided delusional Egyptian mathematician. You wouldn't believe what state mathematics is in some parts of the world. Someone please explain him that he cannot prove inconsistency of ZFC starting from misinterpreted version of Kleene-Rosser paradox.

    ReplyDelete
  38. I did not prove the inconsistency of ZFC starting from the Kleene-Rosser paradox. Instead, I proved P=NP iff P!=NP giving a paradox as an input to a Turing machine. There is no mention of ZFC in the above proofs, why do you refer to it?

    Instead, you would explain how can you reduce a paradox to SAT. Thus, SAT is not NP-complete, which is my proof here.

    I confirm that ZFC inconsistency cannot be proven starting with the Kleene-Rosser paradox. The proof of P=NP iff P!=NP is not a proof of ZFC ==> False.
    Please advise how would you reduce a paradox to SAT following Cook's proof of SAT being NP-complete.

    ReplyDelete
  39. Again, please concentrate on one single point:

    Cook's proof with the input as a paradox, show me how he can derive A(w)=3-SAT from w encoding a paradox.

    Suppose this is possible. What does it mean LOGICALLY to derive SAT from a paradox.

    To put simply, Cook's theorem becomes Cook's paradox in the case of a paradoxical input.

    ReplyDelete
  40. Please write your paradox P as a formula phiin propositional logic with no quantifiers (ie an input to SAT), so that SAT answers true for phi if and only if P is true. If you cannot do that, then your entire point is moot: You just said that you cannot encode the paradox as a formula preserving the truth value, which has nothing to do with P vs NP.

    ReplyDelete
  41. Thanks a lot for your serious comment. The Turing machine poses no obligation as you are suggesting. Who said the input to a Turing machine must be a formula in propositional logic??? This is unfair! The input is a string and it encodes whatever it encodes as long as it refers to a decision problem. The decision problem here is paradox recognition. It the input string w encodes a Paradox, then the Turing machine M outputs "Yes", otherwise "NO".

    Your trouble appeared when you considered every decision problem must be a Boolean question. This decision problem is not a Boolean question.

    You say "input to SAT", there is nothing input to SAT. The input is for the Turing machine.

    You say "SAT answers", while the Turing machine answers and not SAT. According to Cook's theorem SAT is derived from the input.

    ReplyDelete
  42. Church-Rosser should have read Kleene-Rosser, sorry.

    ReplyDelete
  43. The paradox of Kleene & Rosser of Church's inconsistent lambda calculus. Encode it, you obtain its counter-part on Turing machimes:P=NP iff P!=NP. This is due to the fact that SAT is both NP-complete and not NP-complete. The later for paradoxical input, the former for non-paradoxical input.

    ReplyDelete
  44. "A Syntactico-Semantical Bi-Polar Disorder FLP Paradox Implies SAT is NOT NP-complete, P vs. NP does not exist, and ZFC is Inconsistent!
    Authors: Rafee Ebrahim Kamouna"

    This is title of your archive paper.

    http://arxiv.org/abs/0806.2947v1

    Now, it does say ZFC is inconsistent.

    It seems that you are confusing lot of things. Just like VD, but in a more explicit way, so it is appropriate to discuss it here, since VD and RK are in the same class, only RK is a more honest one.

    The reason why they ignore RK and did not ignore VD (though they will now, they will), is that RK claims do not even look plausible on the first glance. His prose is confusing (but so was VD's), perhaps not deliberately so.

    RK: try to explain your "proof" in a straightforward way, not recalling results that perhaps do not mean what you think. State your construction explicitly. If you say "encoding" explain precisely what it means. Otherwise, your "proof" is imprecise and you look like VD, which is to say, vary vague and very bad.

    ReplyDelete
  45. The paper entitled: "The Kleene-Rosser Paradox ==> P=NP iff P!=NP" is here:

    http://www.4shared.com/document/WwpvyYUG/Kleene-Rosser_Semantics.html

    ReplyDelete
  46. The paper entitled:"P=NP <==> P!=NP, A Turing Machine that Diagonalizes Against Itself" is here:
    http://www.4shared.com/document/P6pDyYGG/Diagonalization.html

    Please refer to the two above papers at the moment. ZFC consistency results were obtained via the Continuum Hypothesis & the Axiom of Choice which are irrelevant to P vs. NP. It's OK if you want to discuss them but point by point.

    ReplyDelete
  47. No one is going to study your "papers". You are almost as bad as this guy "vinay", and your "math" is even worse. You will have to figure out your mistakes on your own, its part of learning. Or if you have someone in mathematically civilized part of the world, try a person to person communication (another thing "vinay" didn't do even though he was not in mathematical wasteland, quite the contrary, which implies he is a serious cheat), discuss it and convince someone in person instead of abusing and spamming blogs. If you see nothing suspicious with your claims (ZFC is inconsistent, P vs NP does not exist etc.) then you are not just mathematically illiterate, but also have some serious propensity for hallucination. Too much hashish?

    ReplyDelete
  48. You are referring to my 2-year old paper. You say it claims such and such, so I'm pointing you to the right path. ZFC inconsistency is not about P vs. NP.

    You tell me present your constructions, your proofs and not me. Whether you study it or not, my papers are being peer-reviewed by journals for years now.

    ReplyDelete
  49. It is very easy to be a great scientist, but very difficult to be a human being.

    ReplyDelete
  50. "show me how he can derive A(w)=3-SAT from w encoding a paradox."

    Here. try to make this encoding explicit. Say PRECISELY, and I mean PRECISELY AND EXPLICITLY, what 3 SAT formula you are using to encode "paradox". So you need to describe enough detail so that this can be written down. Then you can analyze the "proof", or can try asking about it.

    Unless you give a clear enough exposition of your work, no one is going to bother with what is with almost certainty wrong anyway. If you do provide clear detail, than
    1. People will be able to point out whats wrong
    2. Even better, you will see it yourself

    If you don't do this, after this well intentioned advice, then we will have no doubt that you yourself (and not your papers) are a hoax.

    ReplyDelete
  51. Who said that SAT encodes a paradox. Cook's theorem claims that A(w)=SAT is derived from any input string w. Now consider the string w to be an encoding of a paradox, not SAT.

    Have you read the papers in the above links?

    ReplyDelete
  52. He seems to be a troll. Just stop feeding him!

    ReplyDelete
  53. If they are being reviewed, why then you spam the blogs. Obviously, you won't be able to publish nonsense in any reputable journal (and you sent some to Journal of AMS, which is a top shot). So, you will get a review in a couple of years (if ever - you can always ask editor what goes on), you will get rejected and so what? Why bother everyone else with your case.

    ReplyDelete
  54. Your claims are so nonsensical that people are just skipping your spam and ignoring you completely, thinking - what a crackpot - that is exactly what goes on. So assuming you are just delusional and not an outright cheat (VD might be that though, but even there we can give it some doubt), and if you want for some reason to summon peoples opinion on your "work" than it is your task to present it clearly. If you claim nonsense and write confused sentences, than don't be surprised that you are being ignored (and it seems also ridiculed, to the point that some people believe you are receiving hoax e-mail ridiculing you). Sober up. With huge claims there is always a good attitude - assume there is an error in your proof, and try to find it yourself. That will bring you much more fruit than this what you are doing. Assuming you are not a troll, which of course, is a very realistic possibility - you talk like a troll, walk like a troll, think like a troll so you might as well be one.

    ReplyDelete
  55. Read the papers, falsify the proofs instead of writing all this.

    ReplyDelete
  56. Why would anyone read a paper of delusional illiterate would be mathematician?

    You appear to be unable even to comprehend what is being asked from you - to explain your "encoding" explicitly, for instance. You refuse to do that because you cannot do that, or you lack intelligence to understand what is being asked from you and why.

    Certainly, you do not deserve patience and attention of people on these blogs. You just proved that - you refuse to explain your own work, thinking it is somehow up to other people to read your nonsense. It is not. It is up to you to show that it makes any sense, that is why you supposedly come here. But you show no desire to make your ideas clear.

    Oh wait. I am wrong. You come here to troll, and we are idiots for giving you the pleasure. Good for you!

    ReplyDelete
  57. I pointed to you that your question is wrong and you haven't read Cook's proof nor you really understand Cook's theorem. Look at your question:"... 3-SAT formula encodes a paradox..."

    I pointed to you w encodes a paradox. What do you want me to clarify here, you encode a formula into a binary string w via any encoding function. Let the set
    {kk_1,kk_2,kk_3,...} be a set of lambda-calculus expressions of the Kleene-Rosser paradox, then
    w_1=e(kk_1),w_2=e(kk_2),w_3=e(kk_3), for an encoding function e, from the alphabet of lambda-calculus to the set of binary strings.

    Any more clarification required. Please consider Cook's proof with the input as a paradox to get the result SAT is not NP-complete, have you done that?

    ReplyDelete
  58. Yeah right. It is me who doesn't understand Cooks theorem. And then you butcher some sentences to "show" that. You are plain ridiculous.

    You need to do the following: find a SAT formula (that is a Boolean formula in conjunctive normal form), that corresponds to your input. That way, it will be clear what you are doing.

    Supposedly, you have some input w (corresponding to a paradox) that you use. Based on that you get a SAT formula. You need to explain that. Saying things like "put paradox w into Cooks theorem" means nothing. Cook's theorem gives you a SAT problem (that is, a CNF Boolean formula), based on any question in NP. That formula is satisfiable if and only if original NP question has a positive answer. So, you need to explain what exactly are you doing with your input in this context.

    But you can't even see that there is a problem in the way you are explaining things, far less you can find a problem in your own reasoning.

    ReplyDelete
  59. The Turing machine answers positively if the input is a paradox. The input is a lambda-calculus formula. Why do you assume the input to be SAT or any Boolean formula. OK, the input is a lambda-calculus formula, if it is a paradox, then a positive answer. Cook's theorem derives a satisfiable formula iff the output is positive i.e. the input is a paradox, is that correct for you now?

    ReplyDelete
  60. Several years ago I read an article that one should never reply to cranks. Just don't remember the name of the article. The author mentioned many examples from different ways of dealing with cranks from his own experience. I think the the bottom line was being nice to cranks does not work and might get you into very serious trouble, and ignoring them works best.

    ReplyDelete
  61. "What to do when the trisector comes", by Underwood Dudley, John Ewing and Ian Stewart, http://www.springerlink.com/content/183843866421q603/


    "Mathematical cranks", by Underwood Dudley, http://books.google.com/books?id=HqeoWPsIH6EC&printsec=frontcover&ie=ISO-8859-1

    ReplyDelete
  62. ""Crank" is a pejorative term used for a person who unshakably holds a belief that most of his or her contemporaries consider to be false.[1] A "cranky" belief is so wildly at variance with commonly accepted belief as to be ludicrous. Cranks characteristically dismiss all evidence or arguments which contradict their own unconventional beliefs, making rational debate an often futile task."

    "Although a crank's beliefs seem ridiculous to experts in the field, cranks are sometimes very successful in convincing non-experts of their views. A famous example is the Indiana Pi Bill where a state legislature nearly wrote into law a crank result in geometry."

    "The rise of the Internet has given another outlet to people well outside the mainstream who may get labeled cranks through internet postings or websites promoting particular beliefs."

    http://en.wikipedia.org/wiki/Crank_%28person%29

    ReplyDelete
  63. I'll help.

    The paragraph you need to fix is this:

    "Obviously, the language L(lambda) is decidable and in P. However, it is obvious that L(lambda) is not poly-time reducible to SAT, as how strings which are both true and false can be converted to strings which are either true or false. It is implausible to consider such a simply computable language as uncomputable. Also, writing L(lambda) as a series
    of in finite non-halting computations simply ignores that it is programmably implemented and certainly halts."

    You don't get to just say things are obvious when proving such a monumental statement. Also, you can't rely on it having to halt: this is an infinite Turing Machine. It is absolutely capable of running forever. So, here's how you firm up this proof:

    Provide a polynomial algorithm that identifies paradoxical inputs. f(x)=~x(x) is easy, but can't a paradox be wrapped in other computations?

    Then prove that its not reducible to SAT. You seem to be relying on a symbolic identification of L(lambda) for the 'in P' part, as expanding the function goes on forever. the SAT converter doesn't care about paradoxes, just whether each statement is a paradox. Thus it needn't have any explicit true/false output state, it's perfectly valid for that machine to symbolically identify paradox/not and return t/f without actually evaluating. Thus explicitly prove membership in the paradoxes in not convertible to SAT.

    If you can give proofs of those, then you might have a valid proof. But I suspect those statements aren't true. Either way, you need to address those concerns to have any hope of this being taken seriously

    ReplyDelete
  64. Thanks a lot for your serious comments. My proofs do not depend on KR is in P or not. It suffices that KR is in NP. That's why you will find the result in the diagonalization paper is:
    e(KR) in NP iff e(KR) NOT in NP.

    So, I rely on KR being in NP. A polynomial time verifier for KR would evaluate kk and NOT kk. If they are equivalent, hece a paradox, then the Turing machine accepts, otherwise it rejects.

    However, what is important is that no one can derive SAT from KR using logical methods, but Cook's theorem does. That's to say, Cook's theorem works against logical laws in the case of a paradoxical input.

    Try to work it by your hand to derive SAT from a paradox, it's impossible using logical laws but using Cook's theorem it's possible.

    That's why I said semantically SAT is not NP-complete, but syntactically it is. Cook's proof is based on syntax only.

    The diagonalization paper encodes KR into a Turing machine paradox of the form:
    e(KR) in NP iff e(KR) NOT in NP.

    Thanks a lot for your inspiring comment. Waiting for more.
    So, no need to prove that KR is in P, and NP suffices. The algorithm for paradox recognition is trivial and obvious.

    ReplyDelete
  65. Remember that a paradox is a logical statement which is satisfiable iff it is unsatisfiable. Thus, impossible to reduce it to SAT, in contradiction to Cook's theorem.

    Please follow Cook's proof of SAT being NP-complete in the case of a paradoxical input.

    ReplyDelete
  66. But how would that polynomial time verification of kk occur? You'd get k(k) = k(~k(k)) = k(~k(~k(k))) ... You can expand that forever. forever >> P.

    At some point your verifier would have to do something like say 'oh, this is of the form k(k)=~k(k).' Accept. It would be acting symbolically, 'reasoning' about the equation and not blindly expanding it.

    If you reread Cook-Levin, it doesn't care about whether the input to the tape is a paradox or not, the procedure just encodes the rules of your TM. You've posited the existence of a TM that can solve this problem. Now Cook-Levin's formula will build a 3SAT representation of that TM.

    Or, put another way, why couldn't 3SAT represent True and False? It doesn't need one boolean variable per intermediate truth value, it could be interpreted such that variable A means some equation is true, variable B means some equation is false, and they can both be true. If the whole equation is true, there's a paradox, if the whole equation is false there isn't. That's what's being detected: lambda equations ultimately are or aren't part of this language

    ReplyDelete
  67. If you review the Kleene-Rosser paradox:

    http://en.wikipedia.org/wiki/Kleene%E2%80%93Rosser_paradox

    Symbolic evaluation without expansion can be verified in polynomial time since KR has a normal form, so it is in NP.

    I agree with you that Cook-Levin would construct a 3-SAT from KR. However, you should agree with me that this is against logical laws. You can never do what the Turing machine does using pencil and paper via logical laws. Thus, via syntax Cook-Levin derives 3-SAT from a paradoxical input despite this is impossible for a logician or a mathematician.

    That's it. Think of this:

    The line of argumentation of Cook’s proof of CNF SAT being NP-complete is as follows:

    ”Let A be a language in NP accepted by a non-deterministic Turing machine M. Fix an input x, we will create a 3CNF formula \phi that will be satisfiable if and only if there is a proper tableau for M and x”



    1.Let w be the encoding of the Kleene-Rosser paradox, thus e^-1(w)=Not e^-1(w), where e is an encoding function.
    2.M accepts w.
    3.SAT is NP-complete, Cook’s theorem.
    4.There must exists \phi(w):\phi(w) is satisfiable.
    5.Then \phi(w) is satisfiable iff M accepts w iff e^-1(w)=Not e^-1(w)
    6.M accepts w is “True”.
    7.Then: \phi(w) is satisfiable iff e^-1(w)=Not e^-1(w) – Logical Contradiction.
    8.Then There must be no \phi(w) which is satisfiable.
    9.Then SAT is (NOT) NP-complete.

    ReplyDelete
  68. As far as I'm aware, the normalizing forms of Lambda calculus are limited so that they can't represent the paradox.

    Look at it this way: What's your decision question?

    Is it: "Is this lamda calculus equation true?" From Church-Turing, this is trivially not in NP.

    Or is it: "Is this lambda calculus equation a paradox?" I'm still not convinced that's in NP, but even if it is, why couldn't that machine be represented in 3-SAT? Every string either is, or isn't, representing a paradox. There's no need to evaluate them. To create a logically inconsistent SAT, you'd need an input that is a paradox iff it isn't a paradox.

    I think you're using the second decision problem as your NP problem, but then deriving your contradiction based on the first.

    ReplyDelete
  69. My decision problem is "Is this lambda expression is a paradox?"

    As I told you, it can be represented by 3-SAT but only syntactically. Semantically, the Turing machine accepts iff input is a paradox iff "True" = "False". Hence, a contradiction. If you think there is a mistake in my reasoning, then point out which line number above is the mistake.

    ReplyDelete
  70. #7. Phi(w) accepts if w=~w - logical contradiction.

    That's not a logical contradiction. It's just saying, "oh, you passed f=~f in.

    Either these lambda expressions are actually being evaluated, in which case you can't determine if they're valid in NP, or we're doing symbolic work in which case you don't need any semantic value. You're asking: is this statement in the class of paradoxes? And phi is saying 'yes it is'.

    Which is all moot anyways, because the normalized forms of lambda calculus can't represent paradoxes, so you still need an NP paradox verifier. But if you did have one, that your 3SAT would use whatever semantic or syntatic rules that verifier did.

    ReplyDelete
  71. Review Cook's proof in Cook's paper (available at Lipton's blog), it says

    M accepts w iff ....

    How can iff is not a logical statement. Suppose you are correct, what shall you do with the fact that the inconsistent lambda-calculus is equivalent to Turing machines. Please derive the paradox withing Turing machines. I did that for you in the diagonalization paper, have you read it. Here is the sketch:

    ReplyDelete
  72. Proof of: “P=NP iff P!=NP” – Syntactic.

    The proof is by diagonalization as follows:

    NP={L_1,L_2,L_3,…}

    L_1={w_11,w_12,w_13,…}

    L_2={w_21,w_22,w_23,…}

    L_3={w_31,w_32,w_33,…}

    Each string w_ij can be written as the Turing machine describing it which can be written as two substrings, the first its input and the second is the computation configurations:

    = w_iw_j

    Hence we have,

    L_1={w_1w_1,w_1w_2,w_1w_3,…}

    L_2={w_2w_1,w_2w_2,w_2w_3,…}

    L_3={w_3w_1,w_3w_2,w_3w_3,…}

    Note that both the diagonal and its complement can easily encode the Kleene-Rosser paradox as:

    KR={kk_1,kk_2,kk_3,…}={Not kk_1, Not kk_2, Not kk_3…}

    Use the encoding e(kk_i)=w_iw_i and e(Not kk_i) = \bar w_i\bar w_i

    You obtain: e(KR) in NP iff e(KR) NOT in NP, of course e(KR) irreducible to SAT iff it is reducible to SAT.

    Hence, P=NP iff P!=NP.

    This should not be surprising as the lambda calculus is equivalent to Turing machines. By direct encoding of the lambda calculus paradox, you obtain it on Turing machines.

    ReplyDelete
  73. We now see what a crank looks like. This is why Deolalikar still thinks he has a proof. Moot definition+moot reasoning=big theorem

    ReplyDelete
  74. Is there any way to blacklist this guy Rafee Kamouna? He seems to spam the blogosphere with his nonsense.

    ReplyDelete
  75. Forget about my papers completely. Church, Turing, Godel, Kleene & Rosser all know that the (inconsistent) lambda-calculus is equivalent to the Turing machine. What does this mean to a complexity theorist other than: P=NP iff P!=NP???

    ReplyDelete
  76. Dear Rafee Kamouna: by now, it is more or less undeniable that there is *definitely* something wrong with the way in which you are thinking about this question. Please relearn the following fields *thorougly* from scratch: automata theory, computability theory, complexity theory, axiomatic set theory.

    After that, try to carefully look at your proof, and re-read all these comments you got up till now. If you have relearned all of this correctly, you will suddenly understand what these commenters were talking about, and probably realize how stupid you have been to think your proof was correct.

    You will really have to believe me and take it as a fact that you are the one who is currently wrong. We are constantly pointing out what is wrong, but you simply refuse to believe it; probably because the "theory" in which you are thinking is incompatible with what is universally accepted, or because you are a dreamer and are simply enjoying the idea to0 much that you have found a proof for this question.

    The truth is often difficult to accept, as it is in this case: your proof is incorrect. You will have to accept it. The question is not whether or not your proof is correct, but how to get you to understand and accept what is wrong with it. Because it is wrong, that is for sure. People who react to your posts do this to help *you*, not to help science.

    Good luck with trying to understand and accept your failure! This sentence sounds harsh, but I actually mean this in a positive way.

    ReplyDelete
  77. As above, you don't need my proof to establish P=NP iff P!=NP. What does it mean the (inconsistent) lambda calculus is equivalent to Turing machines other than this?

    Again forget about my proof. What does it mean that the (inconsistent) lambda-calculus is equivalent to Turing machines for everybody here???

    ReplyDelete
  78. Churh's original Lambda Calculus was inconstant, it was too strong, but that is not the version which has been shown to be equivalent to Turing machines. For this reason they modified it. The modified version which is not inconsistent is what is proven to be equivalent to Turing machine computation. So are confusing the two versions.

    You are acting like an arrogant ignorant person. The mistakes you are making are similar to what we face with undergraduate students taking their first computability/logic/complexity/set theory/... course. You are really confused about the concepts you are talking about, which is not unusual, what is unusual is your arrogant behavior. I believe that you have no serious rigorous education in these topics that you are talking about.

    ReplyDelete
  79. The opposite of what you are saying is correct. Review

    http://en.wikipedia.org/wiki/Turing_completeness

    "The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors."

    Try to be respectful.

    ReplyDelete
  80. The "untyped lambda calculus" you are referring to is the modified version, and is not inconsistent. Go learn these topics in a rigorous way.

    ReplyDelete
  81. The Y-combinator is part of the untyped lambda-calculus and it can express the Kleene-Rosser paradox directly.

    http://en.wikipedia.org/wiki/Fixed_point_combinator

    So, the untyped lambda calculus is inconsistent.

    ReplyDelete
  82. "Y" combinator does not lead to inconsistency, and is similar to Kleene's Fixed Point Theorem for Turing machines.

    YOU ARE ARROGANT AND IGNORANT.

    ReplyDelete
  83. It is called the Paradoxical Operator, look at these:

    http://www.google.com.eg/#hl=en&rlz=1R2TSEA_en-GB&q=Y-combinator+-+Paradoxical+operator&aq=f&aqi=&aql=&oq=&gs_rfai=&fp=6349042cfb598b9d

    ReplyDelete
  84. His only two papers appear to be in the Computing Research Repository. Is there a way for papers to be "rejected" or removed from this?

    ReplyDelete
  85. Dear Rafee Kamouna,

    please go read real serious rigorous books on these topics and stop wasting your and our time. That is what you should do if you are a mathematician. The untyped lambda calculus that is equivalent to Turing machines is not inconsistent. "Y combinator" and "Kleene's Fixed Point Theorems" are well known concepts in functional programming and recursion theory and they do NOT lead to inconsistency.

    ReplyDelete
  86. That's why it is called the:"Paradoxical Operator".

    ReplyDelete
  87. Narendra Chaundari, professor at Indian Institute of Technology, here is his list of some of his papers

    http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Chaudhari:Narendra_S=.html

    He has published a peer reviewed article less than a year ago that P=NP, offering precise algorithm, and everything seems to be defined in his paper:

    http://dcis.uohyd.ernet.in/~wankarcs/index_files/pdf/Vol-31-No-2-2009-pp407-444-scanned-copy.pdf

    So why is noone paying attention? Is this another Indian cheat? Is his proof wrong? Does anyone know anything about this?

    ReplyDelete
  88. I hope that people here found the source of their confusion. Recusion is a form of self-reference which if combined with negation is paradoxical. For practical purposes, recursion is used without logical negation and there is no inconsistency.

    Now, suppose you are right and correct, what happens if the Kleene-Rosser paradox is input to a Turing machine. Still you believe there would be no inconsistency.

    Maybe you view the Turing machine as a healer???

    ReplyDelete
  89. Rafee Kamouna, you desperately need a healer yourself!

    ReplyDelete
  90. Talk science. I feel sorry for you.

    ReplyDelete
  91. Rafee Kamouna, it is only because people feel sorry for you, that they give you any attention.

    But you do not deserve this kindness. Your behaviour clearly shows: All you deserve is contempt.

    As you continue to be arrogant and ignore all the people who tried to help you, you well earned all the contempt you will get in your pathetic little life of a crank.

    ReplyDelete
  92. You have nothing scientific to say, that's why you talk like this. What wrong did I do???

    I told them you are correct. You are right. But, what happens if a paradox is input to a Turing machine?

    Review all my posts, you won't find anything unethical despite I'm called a crank, troll and crackpot.

    ReplyDelete
  93. To say that reduction is in polynomial time does not mean that the algorithm you get is polynomial. It simply means that it adds no more than polynomial factor to the running time. So an algorithm that was polynomial in register machines is going to be polynomial on Turing Machine, but an algorithm which is exponential will not be polynomial on Turing Machine. Certainly, polynomial time reduction/equivalence in the sense of Turing-Church thesis does NOT mean Universal Turing Machine runs in polynomial time.

    Connected to the paradox you are talking about is the Halting problem: It is the question will the Universal Turing Machine halt, given a certain input. This problem (a function having true/false answer) is somewhat analogous to what you might be asking (if "input" is paradox or not). This function - halting problem - is known not to be recursive. So, no Turing machine can solve this problem, it is a function that can be computed with no algorithm - not only it is not in P, it is not in any class, there is no algorithm, no matter how slow, that can compute this function. This is well known, and argument to show this is similar to paradox you mention - it is called diagonalization argument.

    P vs NP cannot be dealt with by this diagonalization argument (and that is essentially what you are talking about). That is the FIRST thing people tried, and it is not possible to do in a simple way on the level which you are trying, be sure of that. Diagonalization arguments are great for showing that there are non recursive functions, you can even show that LOGSPACE is not the same as PSPACE, and rough results like that, but P vs NP is much harder. Beleive me, people have considered these things, and so, while most people who learn this stuff usually try to do it, if they have sufficient intelligence to do this stuff, they realize that diagonalization does not help.

    Is this enough math for you, you little pathetic crank? Your error is in not trying to see if there is something wrong in YOUR approach, you stubbornly refuse to believe that you are wrong despite of all the explanations and spoon feeding by the people here. That is why you are a crank, and why you are despised. Your attitude is wrong. Instead, you should say, OK maybe I am wrong, let me try to understand what these people are talking about and what might be problem with my "work". But you insist there is no problem, your attitude lacks healthy dose of self-examination, and hence, you have these results. It is unethical to bother people like this, and not take their advice, but to stubbornly refuse to reexamine your trials, which makes all communication with you futile. You can still change - just try to understand what is wrong with your proof and take a critical distance from your own proof. This exercise is essential for doing science, unless you can examine your proof in a dispassionate way, you will never be more than a crackpot.

    ReplyDelete
  94. To say that reduction is in polynomial time does not mean that the algorithm you get is polynomial. It simply means that it adds no more than polynomial factor to the running time. So an algorithm that was polynomial in register machines is going to be polynomial on Turing Machine, but an algorithm which is exponential will not be polynomial on Turing Machine. Certainly, polynomial time reduction/equivalence in the sense of Turing-Church thesis does NOT mean Universal Turing Machine runs in polynomial time.

    Connected to the paradox you are talking about is the Halting problem: It is the question will the Universal Turing Machine halt, given a certain input. This problem (a function having true/false answer) is somewhat analogous to what you might be asking (if "input" is paradox or not). This function - halting problem - is known not to be recursive. So, no Turing machine can solve this problem, it is a function that can be computed with no algorithm - not only it is not in P, it is not in any class, there is no algorithm, no matter how slow, that can compute this function. This is well known, and argument to show this is similar to paradox you mention - it is called diagonalization argument.

    P vs NP cannot be dealt with by this diagonalization argument (and that is essentially what you are talking about). That is the FIRST thing people tried, and it is not possible to do in a simple way on the level which you are trying, be sure of that. Diagonalization arguments are great for showing that there are non recursive functions, you can even show that LOGSPACE is not the same as PSPACE, and rough results like that, but P vs NP is much harder. Beleive me, people have considered these things, and so, while most people who learn this stuff usually try to do it, if they have sufficient intelligence to do this stuff, they realize that diagonalization does not help.

    Is this enough math for you, you little pathetic crank? Your error is in not trying to see if there is something wrong in YOUR approach, you stubbornly refuse to believe that you are wrong despite of all the explanations and spoon feeding by the people here. That is why you are a crank, and why you are despised. Your attitude is wrong. Instead, you should say, OK maybe I am wrong, let me try to understand what these people are talking about and what might be problem with my "work". But you insist there is no problem, your attitude lacks healthy dose of self-examination, and hence, you have these results. It is unethical to bother people like this, and not take their advice, but to stubbornly refuse to reexamine your trials, which makes all communication with you futile. You can still change - just try to understand what is wrong with your proof and take a critical distance from your own proof. This exercise is essential for doing science, unless you can examine your proof in a dispassionate way, you will never be more than a crackpot.

    ReplyDelete
  95. To say that reduction is in polynomial time does not mean that the algorithm you get is polynomial. It simply means that it adds no more than polynomial factor to the running time. So an algorithm that was polynomial in register machines is going to be polynomial on Turing Machine, but an algorithm which is exponential will not be polynomial on Turing Machine. Certainly, polynomial time reduction/equivalence in the sense of Turing-Church thesis does NOT mean Universal Turing Machine runs in polynomial time.

    Connected to the paradox you are talking about is the Halting problem: It is the question will the Universal Turing Machine halt, given a certain input. This problem (a function having true/false answer) is somewhat analogous to what you might be asking (if "input" is paradox or not). This function - halting problem - is known not to be recursive. So, no Turing machine can solve this problem, it is a function that can be computed with no algorithm - not only it is not in P, it is not in any class, there is no algorithm, no matter how slow, that can compute this function. This is well known, and argument to show this is similar to paradox you mention - it is called diagonalization argument.

    ReplyDelete
  96. To say that reduction is in polynomial time does not mean that the algorithm you get is polynomial. It simply means that it adds no more than polynomial factor to the running time. So an algorithm that was polynomial in register machines is going to be polynomial on Turing Machine, but an algorithm which is exponential will not be polynomial on Turing Machine. Certainly, polynomial time reduction/equivalence in the sense of Turing-Church thesis does NOT mean Universal Turing Machine runs in polynomial time.

    Connected to the paradox you are talking about is the Halting problem: It is the question will the Universal Turing Machine halt, given a certain input. This problem (a function having true/false answer) is somewhat analogous to what you might be asking (if "input" is paradox or not). This function - halting problem - is known not to be recursive. So, no Turing machine can solve this problem, it is a function that can be computed with no algorithm - not only it is not in P, it is not in any class, there is no algorithm, no matter how slow, that can compute this function. This is well known, and argument to show this is similar to paradox you mention - it is called diagonalization argument.

    ReplyDelete
  97. If a paradox is input to which Turing machine?

    What is the program the Turing machine is running. A Turing machine has a tape, a program (list of states with transitions) and initial position of the tape.

    There is also Universal Turing machine, which is a Turing machine that can runs a specific program, that allows it to execute any other program. This other program is then specified as input on a tape.

    Perhaps you mean Universal Turing Machine. Then supposedly you enter a lambda calculus paradox into it. But does this work? Think about that. In Universal Turing machine you have to give program as list of states with transitions, not in the form of a lambda calculus formula. So you have to be careful there. What exactly are you giving Universal TM as input?

    Also, even if you put input into Universal Turing machine, it does not have to halt. It will halt only if the Turing machine running program that you gave it halts.

    ReplyDelete
  98. So, supposing you are talking about Universal TM (otherwise, what program you have in mind)
    1. Describe what input you are giving to it - how exactly are you translating your lambda calculus "paradox" to the input of your UTM. This is important, you have to know what you are doing.
    2. When you give your input to UTM three things might happen: it will not halt, it will halt with value true, or it will halt with value false (provided you interpret output as value under the head after stopping). What does this have to do with P vs NP?

    Universal Turing Machine certainly does not run in polynomial time. Perhaps this is what is confusing you? Universal Turing Machine is able to emulate any program, so its running time is a function that is far more rapidly growing (for some inputs) than polynomial.

    ReplyDelete
  99. Any under-graduate student can write a simple program to recognize a paradox. It is impossible from you because you are totally immersed in theory.

    A paradox is an example of a Turing machine that diagonalizes against itself. JACM Lance's reviewer wrote to me 2 years ago:"A Turing machine cannot diagonalize against itself as the author claims..."

    Of course I know that proofs of P vs NP using diagonalization relativize. But my proof shows that in case of a paradoxical input, the Turing machine diagonalizes against itself. It halts accepting the input and rejecting another equivalent input, under certain encoding. Please read my papers first, then comment. There is another proof not using diagonalization, you haven't referred to it. I'm ready to retract my claims, but you just make me stronger.

    P.S. Kids can write programs to recognize a paradox, saying it is an example of the halting problem makes the reader realize who is the crank, what a proof!!!

    ReplyDelete
  100. You miss the point. The reason you were asked to specify the input is not because someone else does not know how to do it, it is because it is not clear what you mean (and it is probably not clear to you what you are talking about, a typical crackpot situation). But your arrogant attitude blinds you from seeing that.

    So, you have to make yourself precise (that is if you want to be understood at all, which apparently you do):

    1. Which Turing Machine you are running? Namely, Universal TM, or some other TM (then specify the program).

    2. What is exactly the input you are giving this TM.

    These are two very clear and constructive questions, helping YOU clarify things, and see where you are wrong.

    But you are incapable of understanding this. Your lack of emotional intelligence blinds you from seeing you are the one who is being helped here by a couple of people. Your lack of intellectual intelligence blinds you from being able to figure out the things yourself. Your arrogant crackpot attitude bars you from improving yourself.

    You are just hopeless, and are a living proof why crackpots should be ignored, and trolls should be removed!

    ReplyDelete
  101. Anon 97: Thanks a lot for your nice comment. I refer to a Turing machine in my papers here: http://kamouna.wordpress.com/. I never mentioned the Universal Turing machine. In your answer to what program the Turing machine is running, I defined my interesting decision problem. In the semantic paper:"The Kleene-Rosser Paradox implies P=NP iff P!=NP", the decision problem was to accept the input iff it is a paradox. So, the input is any lambda expression. The decision problem to decide whether it is in the Kleene-Rosser paradox form can be verified in polynomial time, so in NP. The results of my paper does not depend on it being in P. KR has a mormal form unlike an arbitrary lambda expression, so it is clearly in NP.

    In the second diagonalization paper there are two decision problems. Alice is deciding the set {kk_1,kk_2,kk_3,…} and Bob is deciding the set {Not kk_1, Not kk_2, Not kk_3,…}. I proved that there exists an encoding when Alice's language is accepted Bob's is rejected and vice versa. Thus, diagonalizing against itself. The encoding is simple:
    e(kk_i)=\bar e(Not kk_i). So, Bob encodes his formulae via the binary complement of Alice's. Read the papers please and I'm ready for further clarifications to help me retract my 3-year old claims. I enjoyed your post.

    ReplyDelete
  102. Anon 98: I never mentioned the Universal Turing machine. Please read my papers then comment. My reply to Anon 97 clarifies everything to you.

    Thanks a lot for your informative remark.

    ReplyDelete
  103. You really are an idiot. Anon 98 is the same person as Anon 97. Can't you see the comments have been broken. Lol

    ReplyDelete
  104. Anon 100: You haven't read my papers. You refer to UTM which I never mentioned. Who taught you to comment without bothering reading???

    ReplyDelete
  105. Rafee Kamouna: Who gave you PhD??

    ReplyDelete
  106. Is the Ph.D. something so big for you. Does it make any difference to the validity of my claims. Anyway, I shall answer your question: Didier Dubois is my External Examiner who awarded me Ph.D., look at what he wrote here:

    http://www.4shared.com/photo/g_MpK0Rd/France_1.html

    http://www.4shared.com/photo/o2ZfVBz2/France_2.html

    ReplyDelete
  107. This guy is a serious hoaxer. His "papers" that he links to from his page are infected exe files. His "papers" that are on archive (there are two in 10 versions) change titles from version to version, and are worst trash you can find: there is a "quantum gravity theory" (has nothing to do with it in fact, its a joke), claims that ZFC is inconsistent, Continuum Hypothesis is inconsistent etc.
    A look at these papers reveals not a somewhat misguided amateur, but a seriously deranged mental hospital outpatient. Please STOP feeding this troll. This is either someone seriously sick, or more likely some bored kid malicious imposter, a wikipedia vandal kind of type (his english is much better than that of a typical egyptian scientist, especially at a comparably low level of achievment). This is just disgusting - this is some deranged kid making fun of both archive and blogs!

    ReplyDelete
  108. @Anon Sep 5, 4:04am "So why is noone paying attention? Is this another Indian cheat? Is his proof wrong? Does anyone know anything about this?"

    I am surprised that this paper is actually published in a journal. This paper is from IIT Indore, which is one of the new institutes created for political reasons. The faculty here compare in no way to the faculty at the original set of IITs. That aside, there's no need to use words such as "another Indian cheat". For instance, because of Mark Hauser from Harvard, would you call any other US scientist with flawed results "another American cheat"?

    ReplyDelete
  109. Many people are all downloading my papers without problems. You have a sick computer as yourself.

    I thought you are intelligent to know that I proved not only ZFC is inconsistent but also Peano's arithmetic.

    ReplyDelete
  110. "For instance, because of Mark Hauser from Harvard, would you call any other US scientist with flawed results "another American cheat"?"

    Americans more likely have unlimited supply of trolls, vandals and other such creatures, of which "Rafee Kamouna" is a prime example. This is no Egyptian, this is AMERICAN home bread kid-vandal who tries to hoax the world (a lot of fun if you are a lonely teenage nerd with lots of free time and too few friends). If you look at his posts carefully, you will see that he does not care about "proof" - all he cares is how to engage more people in an empty discussion. This explains his illogical interaction with people.

    As for Indians, it is a public secret that in selecting grad school applications in cs there is discrimination against Indian applicants, based on past experience. They simply do not trust the recommendation letters, even though there are plenty of talented students there. This is really a shame, but is not surprising given the experience we have - and it is just affirmed with Deolalikar, Chaundari, Deepak Chopra an the like.

    ReplyDelete
  111. It is pretty easy to check who this troll is. Didier Dubois?
    Here is his page, no mention of supervision of Rafee Kamouna

    http://www.irit.fr/~Didier.Dubois/

    Supervisions:

    Doctoral Students / Encadrements Doctoral

    Sébastien Destercke -> depuis Octobre 2005 (Coopération avec IRSN)

    Hazael Jones -> Thèse soutenue en Décembre 2007 (Coopération avec INRA + CEMAGREF, Montpellier)

    Jérome Fortin -> Thèse soutenue en Décembre 2006 (Coopération avec H. Fargier et Univ. Techn. Wroclaw, Pologne)

    Asma Brini -> Thèse soutenue en Décembre 2005 (Coopération avec M. Boughanem, SIG-IRIT)

    Cédric Baudrit -> Thèse soutenue en Octobre 2005 (coopération avec BRGM, IRSN, INERIS)

    Now if he really was supervisor of "Rafee Kamouna" it is really easy to check - isn't it. And if he was, than perhaps we can get to the bottom of this. In academia, real people are accountable.

    So, a simple e-mail to Didier Dubois will clarify if there is such a guy, in what capacity is this guy working, and why does he behave like a crackpot.

    But apparently, there is something fishy going on. The reason - this guy "Rafee Kamouna" is a hoax, as suspected.

    ReplyDelete
  112. You are really sick. Did I say Didier Dubois is my supervisor? I said he is my External Examiner becaue the question was who awarded you the PhD. So, the question was about the examiner and not the supervisor.

    Second, do you think this list of students is exclusive.

    Third, I put links to the official report on the www.irit.fr paper, have you read it?

    Another proof of who's a crackpot here, indeed.

    ReplyDelete
  113. He is not a hoax. He holds a PhD from
    De Montfort University, Leicester, England. Here is the link:

    Rafee Ebrahim

    http://www.dmu.ac.uk/research/technology/uoa23_phd_completions.jsp

    He is not lying, he is a real person, somewhat misguided. Lots of harsh words have been said, but his papers do seem to be way off the standards. This De Montfort University takes a lot of students from Egypt. Business, I suppose.

    ReplyDelete
  114. You are the one hiding your identity because you are ashamed ot if. You are the one who has no scientific talk, then ask about my Ph.D. If one presents a P vs NP solution to a journal, do they ask him about his Ph.D.???

    Instead of searching the net for my name, you would have read the papers and commented. If you have read my Ph.D. reports you would have realized who is Didier Dubois whom one of you want to send him an email. He receives 200 emails a day. He is the top authority of fuzzy logic in the whole world second only to Zadeh.

    Please who has science writes science, nothing else please. You have seen how much you make me stronger via your criticism.

    ReplyDelete
  115. You are disgrace to the university that gave you PhD.

    ReplyDelete
  116. Thanks a lot. That's very nice of you.

    ReplyDelete
  117. I see what is happening.Kamouna found some serious inconsistencies in mathematics, which is not new, as has been found during ancient time or even one recent example KR-paradox Kamouna provided. People then must have fought such a discoverer. Eventually the truth is the truth and those serious lovers of mathematics listened and decided to frame mathematics in a formal way to avoid inconsistencies.

    This is exactly happening with Kamouna. Serious lovers of computational mathematics should reframe computational mathematics in order to avoid inconsistencies. Kamouna you are wasting your time here. Just continue the next step of your science. Fix all the problems you are raising. Find a framwork which is consistent. Go under hiding for a few more years until you have such a framework. Stop reading blogs etc, since the current mathematicians are working with inconsistent mathematician. You are a serious lover of mathematics, so your time is far more valuable.

    ReplyDelete
  118. Thanks a lot for your advice. Obviously, I thought about a new consistent frameworkd. But this is P vs. NP which is not only about mathematics but also about meta-mathematics rendering all future mathematical systems (like ZFC etc.) inconsistent. Maybe a paraconsistent framework is possible.

    Thanks a lot for your comment.

    ReplyDelete
  119. I have worked out a solution to the square root of -1. I submitted my work a few years ago and one of the anonymous reviewers has told me that it is correct and they are just waiting on the other reviewers before accepting my work. Once accepted, what will happen to mathematics as we know it?

    ReplyDelete
  120. Kamouna, this is the same anonymous. I think you should stop participating in this or such blogs, and spend your valuable time pursuing the meta mathematics implied by P and NP. Nobody will hear on this blog and I am worried about your time.

    ReplyDelete
  121. almost two years later and much of the same

    http://lucatrevisan.wordpress.com/2008/12/24/inducing-percussions-in-all-of-mathematics/#comment-1346

    ReplyDelete
  122. As Rafee Kafuna solved P vs. NP problem years ago he should not lose momentum and focus on Riemman hypothesis as well.

    ReplyDelete
  123. Errata: Riemman -> Riemann.

    ReplyDelete
  124. It is not Kafuna but Kamouna. Why should Kamouna move from a harder P vs NP problem to a relatively trivial Riemann Hypothesis problem?

    As suggested above, he should focus on meta or para mathematics.

    Also, it is a bit insulting to all the great mathematicians that you issue an Errata to correct the spelling of Riemann, when a far -- far more important mathematician's name is mis-spelled and an Errata is not even issued. Riemann is nothing in front of Kamouna.

    I could live if Riemann is spelled Riemman, but spelling Kamouna as Kafuna is the greatest insult the world would ever bear.

    On behalf of all the mathematician, I sincerely issue both an apology to Kamouna and also the following Errata.

    Errate: Kafuna -> Kamouna.

    ReplyDelete