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:

- What is computation?
- Does the Church–Turing thesis capture the mathematical notion of an effective method in logic and mathematics?
^{ [4] }^{ [5] }What are its philosophical implications? - What are the philosophical consequences of the P vs NP problem?
- What is information?

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] }

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

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.

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** 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?*

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

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

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

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.

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

- ↑ Tedre, Matti (2014).
*The Science of Computing: Shaping a Discipline*. Chapman Hall. - ↑ 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 - ↑ 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. - ↑ Copeland, B. Jack. "The Church-Turing Thesis".
*Stanford Encyclopedia of Philosophy*. - ↑ Hodges, Andrew. "Did Church and Turing have a thesis about machines?".
- ↑ Copeland, B. Jack (November 10, 2017). "The Church-Turing Thesis". In Zalta, Edward N. (ed.).
*Stanford Encyclopedia of Philosophy*. - ↑ 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. - ↑ 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 . Retrieved 26 September 2018. - ↑ Rosenberger, Jack (May 2012). "
**P**vs.**NP**poll results".*Communications of the ACM*.**55**(5): 10.

- Matti Tedre (2014). The Science of Computing: Shaping a Discipline. Chapman Hall.
- Scott Aaronson. "Why Philosophers Should Care About Computational Complexity". In
*Computability: Gödel, Turing, Church, and beyond*. - Timothy Colburn.
*Philosophy and Computer Science*. Explorations in Philosophy. M.E. Sharpe, 1999. ISBN 1-56324-991-X. - A.K. Dewdney.
*New Turing Omnibus: 66 Excursions in Computer Science* - Luciano Floridi (editor).
*The Blackwell Guide to the Philosophy of Computing and Information*, 2004. - Luciano Floridi (editor).
*Philosophy of Computing and Information: 5 Questions*. Automatic Press, 2008. - Luciano Floridi.
*Philosophy and Computing: An Introduction*, Routledge, 1999. - Christian Jongeneel.
*The informatical worldview, an inquiry into the methodology of computer science*. - Jan van Leeuwen. "Towards a philosophy of the information and computing sciences",
*NIAS Newsletter***42**, 2009. - Moschovakis, Y. (2001). What is an algorithm? In Enquist, B. and Schmid, W., editors, Mathematics unlimited — 2001 and beyond, pages 919–936. Springer.
- Alexander Ollongren, Jaap van den Herik.
*Filosofie van de informatica*. London and New York: Routledge, 1999. ISBN 0-415-19749-X - Tedre, Matti (2014),
*The Science of Computing: Shaping a Discipline*, ISBN 9781482217698 Taylor and Francis. - Ray Turner and Nicola Angius. "The Philosophy of Computer Science".
*Stanford Encyclopedia of Philosophy*. - Matti Tedre (2011).
*Computing as a Science: A Survey of Competing Viewpoints*. Minds & Machines**21**, 3, 361–387. - Ray Turner. Computational Artefacts-Towards a Philosophy of Computer Science. Springer.

- The International Association for Computing and Philosophy
- Philosophy of Computing and Information at PhilPapers
- A draft version of
*Philosophy of Computer Science*by William J. Rapaport - Philosophy of Computation at Berkeley

This computer science article is a stub. You can help Wikipedia by expanding it. |

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.

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.