Illusion and Reality

The article «  Complexity Theory’s 50-Year Journey to the Limits of Knowledge »  [1] provides a fascinating review of the study of the P versus NP problem, especially tracing it back to Hilbert’s Project, where the Entscheidungsproblem appeared, and relating the P versus NP problem to the work of Gödel, Turing, and others, which gives the article an openness that is hard to see in similar articles!  The article is developed by the research career of Marco Carmosino, now a theoretical computer scientist at IBM: moving from an interest in Gödel's work to the study of the P versus NP problem. Faced with years of stagnation in the study of the P verses NP problem, Carmosino says, " It's one of the most obvious facts in theoretical computer science that when you come across a phenomenon that is so persistent, you need some explanation. " In an effort to break out of the P verses NP problem dilemma, Carmosino and some scholars have turned to the "Minimum Circuit Size

Contents I. Introduction II. Turing’s criticism of the traditional diagonal method - Inappropriate presupposition III. Turing’s proof - the essence of undecidability IV. Conclusion Appendix. Some basic concepts from Turing's 1936 paper I. Introduction Turing's 1936 paper is, as its title suggests, On Computable Numbers, with an Application to the Entscheidungsproblem [1]. The computable number is defined by Turing as the real in terms of its binary number representation computed by the computing machine (Turing Machine ), and it is used to express the integrative concept of computability (see Appendix). Thus, the computable number becomes a guiding thread through Turing's 1936 paper. The Entscheidungsproblem ( decision problem ) is derived from the 10th problem, Determination of the solvability of a diophantine equation , of the 23 mathematical problems formulated by Hilbert at the International Congress of Mathematicians in Paris in 1900 [2]. A general form