Just another WordPress.com weblog

Latest

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

Any comments are welcome.

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.

Le Centre National de la Recherche Scientifique – Paris

In the link below, my prsentation there:

Best,

Rafee Kamouna.

http://www.4shared.com/office/IezDgtsi/P_vs_NP_-_Presentation_4.html

P = NP iff P != NP

The P vs. NP Problem, see: http://www.claymath.org/millennium.

The Kleene-Rosser Paradox ==> P = NP  iff  P != NP

P = NP  iff  P != NP, A Turing Machine that Diagonalizes Against Itself

Mathematics is Inconsistent: at http://www.4shared.com/office/OpzjDoKb/3_Papers.html

As the lambda calculus is equivalent to Turing machines. By direct encoding of the lambda calculus paradox, you obtain it on Turing machines.

This proof was syntactic, the same result can be reached 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.
Follow

Get every new post delivered to your Inbox.