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, aim, focus, or topic 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, and the philosophy of technology. [2]



Many of the central philosophical questions of computer science are centered on the logical, 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 PNP. [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.

Scott Aaronson, an American computer scientist then at MIT, said:

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.

See also

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

Computer science Study of the foundations and applications of computation

Computer science is the study of computation and information. Computer science deals with theory of computation, algorithms, computational problems and the design of computer systems hardware, software and applications. Computer science addresses both human-made and natural information processes, such as communication, control, perception, learning and intelligence especially in human-made computing systems and machines. According to Peter Denning, the fundamental question underlying computer science is, What can be automated?

P versus NP problem Unsolved problem in computer science

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

In computability theory, the Church–Turing thesis is a hypothesis 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:

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, 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.

Quantum computing Study of a model of computation

Quantum computing is the use of quantum-mechanical phenomena such as superposition and entanglement to perform computation. Computers that perform quantum computations are known as quantum computers. Quantum computers are believed to be able to solve certain computational problems, such as integer factorization, substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science.

Theory of computation subfield of computer science

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm. 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?".

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

Stephen Cook American-Canadian computer scientist

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

In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is describable by information. It is a form of digital ontology about the physical reality. According to this theory, the universe can be conceived of as either the output of a deterministic or probabilistic computer program, a vast, digital computation device, or a mathematical Isomorphism to such a device.

Complexity class set of problems in computational complexity theory of related resource-based complexity

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, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

The history of computer science began long before our 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.

Luciano Floridi Italian philosopher

Luciano Floridi is currently Professor of Philosophy and Ethics of Information and Director of the Digital Ethics Lab, at the University of Oxford, Oxford Internet Institute, Professorial Fellow of Exeter College, Oxford, Senior Member of the Faculty of Philosophy, Research Associate and Fellow in Information Policy at the Department of Computer Science, University of Oxford, and Distinguished Research Fellow of the Oxford Uehiro Centre for Practical Ethics. He is also Adjunct Professor, Department of Economics, American University, Washington D.C. He is Turing Fellow and Chair of the Data Ethics Group (DEG) of the Alan Turing Institute

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

The Barwise 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.

Structural complexity theory

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.

NP-completeness Complexity class

In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly, such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it, and a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If any NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.

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".


  1. Tedre, Matti (2014). The Science of Computing: Shaping a Discipline. Chapman Hall.
  2. Turner, Raymond; Angius, Nicola (2020), Zalta, Edward N. (ed.), "The Philosophy of Computer Science", 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 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 . doi:10.1145/564585.564599 . Retrieved 26 September 2018.
  9. Rosenberger, Jack (May 2012). "P vs. NP poll results". Communications of the ACM. 55 (5): 10.

Further reading