## All Mathematical Systems are Inconsistent

The paper entitled:“The P versus NP Problem is Wrong, P=NP iff P=!NP” was submitted to the Journal of the Association for Computing Machinery on 20th June, 2013. Its current status is:”Awaiting Referee Selection”. It can be accessed at the following link:

https://www.4shared.com/office/wEF-PqOr/JACM_Lambda.html

Best,

Rafee Kamouna.

=======================================================================

Abstract

After analysis of the “Y” paradoxical fixpoint operator that is used to define recursion over the $\lambda$-calculus, a similar paradox is discovered over Turing machines. Established belief in computation theory for decades is that the $\lambda$- calculus Kleene-Rosser paradox recognition problem is {\em undefined} over the $\lambda$-calculus and {\em undecidable} over Turing machines. It is the $\lambda$-calculus corresponding counter-part to the halting problem over Turing machines. This long-established result is {\bf\underline{refuted}} by a proof in this paper. Instead, it is shown that the recognition problem of the $\lambda$-calculus Kleene-Rosser paradox is {\em decidable if and only if it is undecidable}, over both the $\lambda$-calculus and Turing machines. Via {\bf\underline{diagonalization}}, the paradoxical recursion in  $\lambda$- calculus is directly transported to a paradox over Turing machines resulting in the subtitle paradoxes.

### 36 Responses

1. It is currently being discussed at the Foundations of Mathematics mailing list. This is an email that I have just received:
===============================
I skimmed through your exciting paper.
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$) or that contrary to this, there is a caveat, as it must seem to a novice, to that formulation in the lambda calculus? Best, Rafee Kamouna. August 18, 2013 at 7:23 am 2. 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. Deal? By Jeffery Shalit http://recursed.blogspot.com/2012/05/yet-another-p-vs-np-proof.html August 18, 2013 at 7:24 am 3. Anonymous said… And the discussion goes on: ================================= Dear Rafee I believe that I can add some important consequence to your paper. Q: There cannot be a polynomial TM solving SAT which would yield P=NP, which is impossible by your paper. ============================================================== A: 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. ============================================================== Q: 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) But also we cannot prove *formally* that there is no such a TM. ============================================================== A: 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. ============================================================== Q: As a result, it is the case that P!=NP is true, but we cannot formally prove it. ============================================================== A: 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. However, his claims of Polynomial-time SAT solvability would only be supported by experimental evidence like exhaustive testing of the algorithm. ============================================================== Q: The same phenomenon occurs with Godel’s sentence Con(PA): it is true but formally unprovable. ============================================================== A: 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. 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? ============================================================== Best, Rafee Kamouna. August 18, 2013 at 7:28 am 4. Dear Rafee who would not be interested when (s)he sees a solution of a Clay milennium open problem So is it correct to say that you have found a finistic formal proof of a contradiction in ZFC? If so, can this be further improved to find a concrete sentence phi such that phi and not phi are both derivable from ZFC together with theirs formal proofs in ZFC? ============================================================== 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. 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”. 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. Best, Rafee. August 18, 2013 at 7:29 am 5. The Church-Rosser Argument A Function which is TOTAL if and only if NOT TOTAL 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)”. $$k\ =\ (\lambda x.\neg (xx))$$ $$kk\ =\ (\lambda x.\neg (xx)) k\ =\ \neg (kk)$$ k_i may be applied to$k_i\ \equiv\ k_i$may not be applied to k_i k_ik_i is total$\Longleftrightarrow\ k_ik_i$is not total ====================================================== Proofs: ====================================================== Theorem 2.1: Established Belief: The Church-Rosser Argument \forall i, k_ik_i = \neg k_ik_i is undefined It is the$\lambda$-calculus corresponding counter-part for the Turing machine halting problem. Hence, it is undecidable. Proof: The proof is by contradiction. After universal quantification over$\Lambda$, a counter-example is constructed: 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$. 2. This means that some functions, including the diagonal function, are not total. 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. 4. It is the$\lambda$-calculus corresponding counter-part for the Turing machine halting problem. ========================================================================== Refutation: 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. Theorem: Refutation of Established Belief: \forall i k_ik_i = \neg k_ik_i is defined Proof: The proof is by contradiction. After universal quantification over$\Lambda$, a counter-example is constructed: 1. If all functions defined by$\lambda$-expressions in$\Lambda$were not total, then one would have: 2. k_i may not be applied to k_i. 3. (2) \equiv k_i may be applied to k_i. 4. Implies: [k_ik_i = \neg k_ik_i]$ for the diagonal function k_i.

5. Implies: one has [k_ik_i = \neg k_ik_i]. Contradiction derived, (1) must be negated.

6. $\exists$ some functions, including the diagonal function, that are total.

7. The diagonal function [k_ik_i = \neg k_ik_i] is defined.

The Kleene-Rosser paradox can be articulated as in the following re-formulations:
[k_ik_i =\neg\ k_ik_i] is defined\ if and only if [k_ik_i=\neg\ k_ik_i] is undefined
[k_ik_i=\neg\ k_ik_i] is total\ if and only if [k_ik_i=\neg\ k_ik_i] is not total.
[k_ik_i=\neg\ k_ik_i] is decidable if and only if [k_ik_i=\neg k_ik_i]” is not undecidable.

================================================================================
Best,
Rafee Kamouna.

August 18, 2013 at 7:30 am

6. I received the following questions from a dear colleague in the Czech republic.

=====================================================================
Dear Rafee
please can you describe parts of page 11 in words for me to understand?
First, why is
|M_w_i|=2|w_i|?
The computation tree of M_w_i on w_i may be very long, longer then 2|w_i|.

Next, what is A and A(w)?

What mean in the definition 5.1 in e_2
bars over w_i w_i?
They are negations, bit by bit, of w_i w_i, right?

Finally, what page in [4] is the proof of what you use in theorem 5.1 on the last line of page 9?
This is exactly the Halting problem of TM over their own indices, right?

Thank you
====================================================================

I shall try to answer them as soon as I can.

Best,

Rafee Kamouna.

August 19, 2013 at 4:53 am

7. Dear Rafee

please can you describe parts of page 11 in words for me to understand?

First, why is
|M_w_i|=2|w_i|?
The computation tree of M_w_i on w_i may be very long, longer then 2|w_i|.

==============================================================

The notation M_w_i describes the Turing machine denoting the string w_i. So, the computation M_w_i on w_i is precisely the computation of w_i on w_i, which is w_iw_i\in L_w_iw_i.

==============================================================

Next, what is A and A(w)?
The Cook-Levin theorem states that for any non-deterministic Turing machine
\forall w\in L\in NP, there exists A(w)=SAT
A(w) is the SAT logical formula consisting of propositional symbols as detailed in Cook’s 1971 proof. You can have a look at his STOC 1971 paper, it is available for download at Richard Lipton’s blog. He uses the same notation, for all w, there exists A(w)=SAT.

==============================================================

What mean in the definition 5.1 in e_2
bars over w_i w_i?
They are negations, bit by bit, of w_i w_i, right?
Yes, w_i is a Boolean string, so \bar w_i is its binary complement.

==============================================================

Finally, what page in [4] is the proof of what you use in theorem 5.1 on the last line of page 9?
This is exactly the Halting problem of TM over their own indices, right?
The theorem is:”The Proof of the Existence of Uncomputable Functions”. There is no definition, there is no proof. Just draw the diagonalization table. It is easy to see that the language obtained by the negation operation on the table diagonal is uncomputable. Later the authors use this result to prove the uncomputability of the halting problem via a reduction, hence the attack strategy:”Diagonalization with Reduction” for attempting to prove P!=NP relativize, the 1975 Baker, Gill & Solovay theorem, SICOMP.

The fact that I used “Diagonalization” alone not even with reduction was called a twist on diagonalization in my 2009 paper available at this blog submitted to the Theory of Computing Journal in 2010, rejected after 27 months-long review. You can review the papers available for download from this blog to compare them with the 2013 paper. If so, I suppose you would become an expert on this particular approach to attack the problem. If you want me to publish the previous ToC & JACM reviews, I don’t mind.

==============================================================

Thank you

Best,

Rafee Kamouna.

August 19, 2013 at 5:51 am

8. Jan Pax

>Here I do not understand something. You say: The notation M_w_i describes the Turing machine denoting the string w_i. So, the computation >M_w_i on w_i is precisely the computation of w_i on w_i, which is w_iw_i\in L_w_iw_i.

First, you wanted to say not “denoting the string w_i” but rather “denoted by the string w_i”, right?

The string w_i is an *encoding* of a TM which ,btw,can be further simulated by an Universal TM.This w_i is a description of some TM obtained via Goedel’s encoding.If w_i is in L_w_i w_i then after halting of the TM described by w_i, there will be on the writing tape the string w_i w_i, but how do you encode the transition function and the changes of the states into 2 bits,0 and 1? Especially, how do you force the w_i TM to move only from left to right, one by one cell to get time 2|w_i|? It may be explanatory to know how precisely your TM look like. Do they have 1 read and 1 write tape…?You may also want, after writing on the write tape the first w_i go back to the beginning of the read tape, which would after all increase the time constant 2 in 2|w_i|.

Finally, I do not understand how fixed w and fixed A can yield all the SAT?

Thank you, JP

August 19, 2013 at 1:55 pm

9. Dear Jan Pax,

Your misunderstanding is because you are trying to describe the operation of the TM M_w_i without asking yourself what does it do. You should have asked yourself, is it a searching, sorting program or whatever it might be.

M_w_i happens to be in the proof of theorem 6.1 which states that L_w_iw_i \in P. So, what does L_w_iw_i represent which is mentioned above in the paper. Search the pdf file for the word “viruses”.

The language L_w_iw_i must be:

1. A TM string w_i performing a self-replication operation on no input.

2. A TM string w_i with identical input w_i with no any type of processing.

I supposed the self-replicating comment (viruses) would be sufficient for the reader to understand the semantics of M_w_i and the self-replicating viruses in everyday computing a proof that this language does exist in practice and not just a theoretical endeavour for the sake of providing the proof.

Anyway, this section does not affect the inconsistency results obtained over the lambda-calculus and Turing machines. However, it is an important construction (actually 1000+ constructions, i.e. for all NP-complete problems) of a contradiction obtained since 2008 where the result appeared in the ArXiv paper:

A Syntactico-Semantical Bi-Polar Disorder FLP Paradox implies: P vs NP does not exist, SAT is (NOT) NP-complete & ZFC is inconsistent

If you are interested you can compare the Fuzzy Logic Programming approach which is the first formalism to establish the results if you are interested in the history of the approach. You must know your native logician, the great Prof Petr Hajek. He is from the Czech republic.

Thank you for all your questions. Don’t hesitate to debate more.

Best,
Rafee.

August 19, 2013 at 3:28 pm

10. RafeeIsEinstein

Are you arguing with yourself? Also you seem to be losing!

August 19, 2013 at 6:50 pm

11. Jan Pax

Can you describe how to achieve this *exact* bound?
|M_w_i|=2|w_i

——————————–

>1. A TM string w_i performing a self-replication operation on no input.

>2. A TM string w_i with identical input w_i with no any type of processing.

In 2, you must check that the input is of the form w_i w_i and this cannot be done in 2|w_i| time.
Similarly in 1, self replication on no output cannot be done in this time.

My objection is irrelevant to your result, since L_w_iw_i is certainly intuitively in P, but I disagree with the bound 2|w_i| given in you paper.

I would also like to know how bit string w_i can be understood as a TM; do you have a reference in PDF?
Another question may be, if we simulate w_i on w_i by an Universal TM, how this universal gets to know where program w_i ends and input to w_i, w_i, begins.
Thank you, Jan Pax

August 20, 2013 at 9:18 am

12. Dear Jan,

Since you’ve got it that this is a proof of L_w_iw_i \in P, then you must have noticed that going asymptotically infinitely diagonally to whatever your imagination might reach, the language remains as a string w_i concatenated to itself nothing more. The rate of growth is constant. Your above argument would lend the upper bound by a constant factor nothing else, i.e. M_w_i = 2 c |w_i|, if this satisfy you. As you said, you definitely see the language in P.

I don’t even need to prove it is in P to reach this section contradictory result, it suffices to prove it is in NP.

For checking how a Turing machine M can be described by a string , check Cook’s official P vs NP problem definition at the Clay Math Institute web site.

Best,

Rafee Kamouna.

August 20, 2013 at 9:46 am

• Jan Pax

I seem to have identified the main problem with your paper.
There are 2 senses how to understand the language {w_0w_0,w_1w_1,w_2w_2,…}

First as a formal language and second as pairs TM index and it’s input.
In the first case, this language is in P, in the second case this language is undecidable.

Now, you use incorrectly the sense that suits you. If you wish L_w_iw_i to be decidable, you use the first sense, if you wish L^complement_w_iw_i to be undecidable you use the second sense.

Note also, that we don’t have the table on the top of page 10 at ours hand. On the diagonal say, we don’t know whether there is w_0w_0,x, or if
it is undefined.

Jan Pax

August 20, 2013 at 11:01 am

13. Dear Jan,

Unfortunately you are completely wrong. The language \bar L_\bar w_i\bar w_i is undecidable, so there can never be any Turing m/c describing the string \bar w_i\bar w_i.

Think it again.

Best,

Rafee Kamouna.

August 20, 2013 at 11:19 am

• Jan Pax

This is what I say. It does not matter whether you are trying to decide {w_0w_0,w_1w_1,w_2w_2,…} or
{w_0w_0^BAR,w_1w_1^BAR,w_2w_2^BAR,…}

There is only one significant difference. Are the first components w_0,w_1,w_2,…. of this languages indexes of TM or given strings?
In the first case, both languages are undecidable, and in the second case both are decidable.

In the second case you can easily decide both languages.
***Note, that if a language is decidable, then so is it’s complement.***

In the first case, {w_0w_0,w_1w_1,w_2w_2,…} is NOT decidable either.
Because what can you do if you are given TM with index w_i and input w_i?
You can only simulate it and wait if the output will be w_iw_i.

This is what I already asked. How did you arrived at 2|w_i|?
Not only this is not linear, it is undecidable.

Jan Pax

August 20, 2013 at 12:38 pm

14. We have only two languages: The diagonal which is decidable, its complement which is undecidable.

Any TM or program can print itself in theory as a direct consequence to Kleene recursion theorems, review them in any computability theory book like Sipser or Lance Fortnow blog, maybe you would find it helpful to through it:”Foundations of Complexity”.

Best,

Rafee Kamouna.

August 20, 2013 at 1:03 pm

• Jan Pax

You say, any TM can print itself??
What about TM that do not print anything?
Rather there are TM that print itself.

Once again, L is decidable iff L^complement is decidable.

You confuse two things.
Suppose we have lexicographically ordered binary strings w_0,w_1,w_2,…
You say that w_0w_0^BAR,w_1w_1^BAR,w_2w_2^BAR,…
is NOT decidable.
What prevents a suitable TM, given w_5w_5^BAR, to check that this string is indeed in L^complement, where L is
{w_0w_0,w_1w_1,….}?
In this situation even L=L^complement. But this meaning is not the intended one.

The intended meaning is this:
The problem you haven’t accepted yet, is that rows of your table on page 10 are not indexed by strings, but by indexes of TM.
***In this setting, L={w_0w_0,w_1w_1,….} is NOT decidable either!***
How would you decide M_w_5 with input w_5 outputs w_5w_5??

August 20, 2013 at 1:26 pm

• Jan Pax

Here I mean
In this situation even L=L^complement
not the usual complement of languages, but your bit by bit negation:
{w_0w_0,w_1,w_1,w_2w_2,…}={ w_0w_0^BAR,w_1w_1^BAR,w_2w_2^BAR,…}

August 20, 2013 at 1:31 pm

15. You didn’t even cover the proof I told you to review of Arora & Barak, review the table again please:

The diagonal language is decidable if and only if its complement is undecidable.

I told you this many times, and you insist to re-state it wrong.

Best,

Rafee Kamouna.

August 20, 2013 at 1:51 pm

• Jan Pax

Sorry for the troubles.
The only thing I claim is that the set of viruses is not decidable.
Do you agree?
How would you decide M_w_5 with input w_5 outputs w_5w_5?
Your only possibility is to feed to M_w_5 with
w_5 and wait if it outputs w_5w_5.
It may cycle.

Next,which page in Barak should I read?

August 20, 2013 at 2:14 pm

16. Please read the section in Sipser that any program may have acces to itself so that if can print itself. This is a direct consequence of Kleene’s recursion theorems, fundamental results in computability theory.

Best,

Rafee Kamouna.

August 21, 2013 at 4:42 am

• Jan Pax

There are programs that print themselves.But you would have to change a particular TM so that it prints itself.
If every program prints itself without a change of the program, we could not compute anything else.
The theorem says that there are TM that prints themselves and not that any TM does so.
Otherwise the language L_w_iw_i would consist of ALL binary strings w_i.

August 21, 2013 at 2:25 pm

17. Your argument is irrelevant to the correctness of any result in the paper. In computation theory, you can handle data as programs and vice versa. So you can assume any piece of data as a program that has access to itself and can print itself.

Please if you have an argument against my paper, present your prof the L_w_iw_i is not in NP.

Best,

Rafee Kamouna.

August 21, 2013 at 3:08 pm

• Jan Pax

I do not have an exact proof, but imagine you have arbitrary TM M which has index w and you feed it with w and want to know if it ever halts.
This is a semidecidable complete problem. So in analogy with this I believe that to know if M_w on w will print ww won’t be much easier.
The only way I can imagine how to find out what does M_w on w is to simulate by an universal TM this w on M_w and wait. How can this be in NP?
Note that M_w can move it’s head right and left, erasing what it previously printed. By what polynomial would you bound an accepting path
if it after all really prints ww?

August 21, 2013 at 6:38 pm

• Jan Pax

**************I’m right, it is undecidable.**************

Your request to the FOM mailing list

Posting of your message titled “TM and viruses/decidability”

has been rejected by the list moderator. The moderator gave the
following reason for rejecting your request:

“Your message was deemed inappropriate by the moderator. It’s surely
undecidable. But why therm “virus”?”

at:

fom-owner@cs.nyu.edu

August 22, 2013 at 1:50 pm

18. You sent this message to FOM and it was rejected. Maybe you did not ask the right question. They are discussing all of my messages that I sent. They apologized to me. You are confused. You did not even cover the first chapter of Barak, which is an undergraduate text, unfortunately.

Best,

Rafee.

August 22, 2013 at 2:26 pm

• Jan Pax

I asked this, i.e. is L_w_iw_i decidable?You claim it is in NP.

Dear All,
does anyone know if the set of all viruses,
i.e. indexes w_i of Turing machines which, given on input their index w_i, will produce “w_i w_i”
is decidable?
Thank you, Jan Pax

August 22, 2013 at 2:50 pm

19. Consider w_iw_i as a single TM. It definitely can print itself in w_iw_i steps.

When you want to examine decidability, you examine the problem you are solving and not the language. The problem being solved is the Kleene-Rosser paradox recognition problem. It has been proven decidable in the paper as the least fixpoint of the mapping T.

I thought people from the Czech republic are much better than this in mathematics before making such claims in public.

Best.

Rafee Kamouna.

August 22, 2013 at 3:01 pm

• Jan Pax

I can now understand what you mean. Please, if you can read it ALL:
That are not people in Czech Republic, it was Davis that rejected this question as it is almost trivially true that the set of TM which on their input print
w_iw_i is an undecidable set.Me and 2 more professors claim the same.

Do you know what you are saying by this:

>>Consider w_iw_i as a single TM. It definitely can print itself in w_iw_i steps.
???

You are saying that any program of the shape w_iw_i, where w_i is an arbitrary string, prints, without a modification,w_iw_i.
Then roughly said, TM can do nothing more than print their own code.

|However, what you *can* do, is that you can have a specific TM, that given a code w_i of any TM it can print this code twice as w_iw_i.
|BUT, this does not mean that M_w_i will print it’s code twice as w_iw_i as we need.

So,
>>Consider w_iw_i as a single TM. It definitely can print itself in w_iw_i steps.
|it cannot print itself, but a *new one* very special TM can print this w_i as w_iw_i for all codes of TM w_i.

——————————————-

Let me ask you, is the set on TM which halt on their own input decidable?
I.e. the set of indexes of TM M_w_i that halt on w_i.

Yes, they all halt and print w_i.
FUNNY…
——————————————-

You say
>>You did not even cover the first chapter of Barak, which is an undergraduate text,

I do not think that Barak is undergraduate. If I did not cover first chapter of it, you did not cover the very notion of TM.
You change it’s code before running it…

August 22, 2013 at 4:22 pm

20. You are constantly mixing theory and practice. w_i is a string that encodes k_i in the paper. w_iw_i is another string that encodes k_ik_i in the paper. k_ik_i is proven to be decidable.

In theory, w_iw_i can print itself in w_iw_i steps. It is a string. Yes, data. In theory, you can assume it is a TM that prints itself.

In practice, it is a different story. Any program that prints itself will never have the form of two identical substrings w_iw_i. This is an example of a theory vs practice conflicting situation.

I proved that all theories are contradictory. This is my paper. Review Sipser, he even considers a C compiler processing a C program is an example program running itself, while this is not precisely true, in his discussion of Kleene’s recursion theorems, and the fact that every program can print itself.

Best,

Rafee Kamouna.

August 22, 2013 at 4:38 pm

21. C.L.

Congrats Rafi, hope it works out. Your claim is also being considered below:

[Equal]: In June 2008, Rafee Ebrahim Kamouna proved that P and NP coincide. His proof first establishes (in contradiction to Cook’s theorem) that SAT is in fact not NP-complete, then observes that there are no NP-complete problems, and finally deduces P=NP from this. The paper”The Kleene-Rosser Paradox, The Liar’s Paradox & A Fuzzy Logic Programming Paradox Imply SAT is (NOT) NP-complete” is available at http://arxiv.org/abs/0806.2947.

August 30, 2013 at 1:43 am

22. Thanks a lot, but this is not accurate. My proof is:”P=NP iff P!=NP” and not a proof of P=NP.

Best,

Rafee Kamouna.

August 30, 2013 at 2:01 am

23. RafeeIsEinstein

I don’t hear nothing from you. Did you suicide?

November 20, 2013 at 7:43 pm

• kamouna

I’m still alive. The status of the paper is:”Awaiting Referee Scores.

Best,

Rafee Kamouna.

November 21, 2013 at 4:47 am

24. C.L.

I sincerely hope that your paper gets accepted by the referees this time. C.L.

December 11, 2013 at 3:23 am

25. kamouna

Thanks a lot. This time, they have no choice but to accept.

1. JACM 2008: rejected on the grounds that a Turing machine cannot diagonalize against itself.
2. ToC 2010 (decision 2012): KR is undecidable.
3. JACM 2011: KR is undefined.
4. JACM 2013, Current Paper:
KR is defined iff KR is undefined.
KR is decidable iff KR is undecidable.

JACM 2008 was rejected in 40 days.

JACM 2011 was rejected in 10 days.

JACM 2013 status is:”Awaiting referee scores” since 20 June, 2013.

Best,

Rafee Kamouna.

December 11, 2013 at 5:32 am