Philosophy of computer science

Last updated

The philosophy of computer science is concerned with the philosophical questions that arise within the study of computer science. There is still no common understanding of the content, aims, focus, or topics of the philosophy of computer science, [1] despite some attempts to develop a philosophy of computer science like the philosophy of physics or the philosophy of mathematics. Due to the abstract nature of computer programs and the technological ambitions of computer science, many of the conceptual questions of the philosophy of computer science are also comparable to the philosophy of science, philosophy of mathematics, and the philosophy of technology. [2]

Contents

Overview

Many of the central philosophical questions of computer science are centered on the logical, ethical, methodological, ontological and epistemological issues that concern it. [3] Some of these questions may include:

Church–Turing thesis

The Church–Turing thesis and its variations are central to the theory of computation. Since, as an informal notion, the concept of effective calculability does not have a formal definition, the thesis, although it has near-universal acceptance, cannot be formally proven. The implications of this thesis is also of philosophical concern. Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind. [6] [7]

P versus NP problem

The P versus NP problem is an unsolved problem in computer science and mathematics. It asks whether every problem whose solution can be verified in polynomial time (and so defined to belong to the class NP) can also be solved in polynomial time (and so defined to belong to the class P). Most computer scientists believe that P ≠ NP. [8] [9] Apart from the reason that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems, philosophical reasons that concern its implications may have motivated this belief.

For instance, according to Scott Aaronson, the American computer scientist then at MIT:

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps", no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss. [10]

See also

Related Research Articles

<span class="mw-page-title-main">Computer science</span> Study of computation

Computer science is the study of computation, information, and automation. Computer science spans theoretical disciplines to applied disciplines. Though more often considered an academic discipline, computer science is closely related to computer programming.

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">Theory of computation</span> Academic subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

Hypercomputation or super-Turing computation is a set of models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

<span class="mw-page-title-main">PH (complexity)</span> Class in computational complexity theory

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

<span class="mw-page-title-main">History of computer science</span> Aspect of history

The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.

<span class="mw-page-title-main">Luciano Floridi</span> Italian philosopher (born 1964)

Luciano Floridi is an Italian and British philosopher. He is the director of the Digital Ethics Center at Yale University. He is also a Professor of Sociology of Culture and Communication at the University of Bologna, Department of Legal Studies, where he is the director of the Centre for Digital Ethics. He is adjunct professor, Department of Economics, American University, Washington D.C. He is married to the neuroscientist Anna Christina Nobre.

The International Association for Computing and Philosophy (IACAP) is a professional, philosophical association emerging from a history of conferences that began in 1986. Adopting its mission from these conferences, the IACAP exists in order to promote scholarly dialogue on all aspects of the computational/informational turn and the use of computers in the service of philosophy.

The philosophy of information (PI) is a branch of philosophy that studies topics relevant to information processing, representational system and consciousness, cognitive science, computer science, information science and information technology.

The K. JonBarwise Prize was established in 2002 by the American Philosophical Association (APA), in conjunction with the APA Committee on Philosophy and Computers, on the basis of a proposal from the International Association for Computing and Philosophy for significant and sustained contributions to areas relevant to philosophy and computing.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

The Covey Award was established in 2008 by the International Association for Computing and Philosophy, to recognise "accomplished innovative research, and possibly teaching that flows from that research, in the field of computing and philosophy broadly conceived".

References

  1. ↑ Tedre, Matti (2014). The Science of Computing: Shaping a Discipline. Chapman Hall.
  2. ↑ Turner, Raymond; Angius, Nicola (2020), "The Philosophy of Computer Science", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Spring 2020 ed.), Metaphysics Research Lab, Stanford University, retrieved 2020-05-21
  3. ↑ Turner, Raymond (January 2008). "The Philosophy of Computer Science". Journal of Applied Logic. 6 (4): 459. doi:10.1016/j.jal.2008.09.006. hdl: 2434/807648 – via ResearchGate.
  4. ↑ Copeland, B. Jack. "The Church-Turing Thesis". Stanford Encyclopedia of Philosophy.
  5. ↑ Hodges, Andrew. "Did Church and Turing have a thesis about machines?".
  6. ↑ Copeland, B. Jack (November 10, 2017). "The Church-Turing Thesis". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy .
  7. ↑ For a good place to encounter original papers see Chalmers, David J., ed. (2002). Philosophy of Mind: Classical and Contemporary Readings. New York: Oxford University Press. ISBN   978-0-19-514581-6. OCLC   610918145.
  8. ↑ William I. Gasarch (June 2002). "The P=?NP poll" (PDF). SIGACT News . 33 (2): 34–47. CiteSeerX   10.1.1.172.1005 . doi:10.1145/564585.564599. S2CID   36828694 . Retrieved 26 September 2018.
  9. ↑ Rosenberger, Jack (May 2012). "P vs. NP poll results". Communications of the ACM . 55 (5): 10.
  10. ↑ "Shtetl-Optimized » Blog Archive » Reasons to believe" . Retrieved 2021-09-16.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.