The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. T...The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. The first is the classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor's theorem, it is shown that an NTM is not equipotent to a DTM. This means that "generating the power set P(A) of a set A" is a non-canonical example to support that P is not equal to NP.展开更多
This paper starts from the analysis of how Alan Turing proceeded to build the notion of computability in his famous 1936 text ＂On computable numbers, with an application to the Entscheidungsproblem＂. Looking in deta...This paper starts from the analysis of how Alan Turing proceeded to build the notion of computability in his famous 1936 text ＂On computable numbers, with an application to the Entscheidungsproblem＂. Looking in detail at his stepwise construction, which starts from the materialities to achieve a satisfactory level of abstraction, it is considered how his way of doing mathematics was one that constructs mathematical knowledge by evading a definite separation between matter and form; in this way, making the world and language come together. Following the same line of reasoning, it is argued in this paper that the abstract and the concrete, the deduction and the induction, the technical and the social as well as the objective and the subjective are unthinkable as pure entities. By considering the controversies and discussions from the mid-nineteenth century until now, it is shown that local （social） elements necessarily participate in what is usually considered ＂technical content＂ or ＂objectivity＂. While Alan Turing was a precursor of what today might be said to be an ＂anthropological approach to mathematical culture＂, unveiling and reviving approaches that enable the axis of authority for mathematics, logic and computing to be shifted, he also opened different paths for the construction of a variety of mathematical knowledge as well.展开更多
文摘The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. The first is the classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor's theorem, it is shown that an NTM is not equipotent to a DTM. This means that "generating the power set P(A) of a set A" is a non-canonical example to support that P is not equal to NP.
文摘This paper starts from the analysis of how Alan Turing proceeded to build the notion of computability in his famous 1936 text ＂On computable numbers, with an application to the Entscheidungsproblem＂. Looking in detail at his stepwise construction, which starts from the materialities to achieve a satisfactory level of abstraction, it is considered how his way of doing mathematics was one that constructs mathematical knowledge by evading a definite separation between matter and form; in this way, making the world and language come together. Following the same line of reasoning, it is argued in this paper that the abstract and the concrete, the deduction and the induction, the technical and the social as well as the objective and the subjective are unthinkable as pure entities. By considering the controversies and discussions from the mid-nineteenth century until now, it is shown that local （social） elements necessarily participate in what is usually considered ＂technical content＂ or ＂objectivity＂. While Alan Turing was a precursor of what today might be said to be an ＂anthropological approach to mathematical culture＂, unveiling and reviving approaches that enable the axis of authority for mathematics, logic and computing to be shifted, he also opened different paths for the construction of a variety of mathematical knowledge as well.
