Computer Science
Decidability and Undecidability
Decidability refers to the property of a problem being solvable by an algorithm, while undecidability refers to the property of a problem being unsolvable by any algorithm. In computer science, these concepts are fundamental to understanding the limits of computation and the classification of problems based on their solvability. The halting problem is a classic example of an undecidable problem.
Written by Perlego with AI-assistance
Related key terms
1 of 5
7 Key excerpts on "Decidability and Undecidability"
- Ernst L. Leiss(Author)
- 2006(Publication Date)
- Chapman and Hall/CRC(Publisher)
When discussing impossi-bility, it is important to differentiate these two for two reasons. First, it 200 A Programmer’s Companion to Algorithm Analysis should be clear that a specific instance of a problem will always have a definite answer. For example, recall the question (posed in Chapter 4) of whether two context-free grammars generate the same language. While the general problem is undecidable, meaning there is not an algorithm that answers for any two grammars, yes or no, it should be perfectly obvious that given any two specific grammars, either they do generate the same language or they do not — there is no third alternative. In other words, for any specific instance of a problem, there is a specific answer. The question that decidability addresses is how we can obtain this answer, in all possible instances. Second, given a specific instance, even if we have an algorithmic solution approach, it makes no sense to talk about the complexity of solving this instance because of the overall approach of computational complexity. The complexity of a problem is a function of some measure of the input. If one selects a specific instance of the problem, if one can solve it, the measure of that instance is a constant; it may be large, but a constant it is. As a result, the computational complexity of solving this instance is also a constant. 1 Consequently, it makes little sense to talk about the computational complex-ity of solving an instance; computational complexity can only be used to reflect the effort required to solve all instances of a problem, as a function of the chosen measure of the size of the instances. The second issue we must address pertains to two types of impossibility. A problem may be such that no algorithm solving it is known. If we can tighten this up and manage to show that no such algorithm can exist, then we say this problem is undecidable. This is, in a way, a positive result. We can actually show that something is impossible.
eBook - PDFInterpreting Gödel
Critical Essays
- Juliette Kennedy(Author)
- 2014(Publication Date)
- Cambridge University Press(Publisher)
The writing of this chapter was supported by the Guggenheim Foundation and National Science Foundation grants DMS-0841321 and DMS-1069236. 211 Remark 2.1 In modern literature, the word “undecidability” is used more commonly in sense 2, given that “independence” adequately describes sense 1. To make sense 2 precise, one needs a formal notion of algorithm. Such notions were introduced by Church (1936a) and Turing (1936) independently in the 1930s. From now on, we interpret algorithm to mean Turing machine, which, loosely speaking, means that it is a computer program that takes as input a finite string of 0s and 1s. The role of the finite string is to specify which problem in the family is to be solved. Remark 2.2 Often in describing a family of problems, it is more conveni- ent to use higher-level mathematical objects such as polynomials or finite simplicial complexes as input. This is acceptable if these objects can be encoded as finite binary strings. It is not necessary to specify the encoding as long as it is clear that a Turing machine could convert between reasonable encodings imagined by two different readers. Remark 2.3 One cannot speak of a single YES/NO question being undecidable in sense 2, because there exists an algorithm that outputs the correct answer for it, even if one might not know which algorithm it is! There is a connection between the two notions of undecidability. Fix a decision problem and an axiom system A such that (a) there is a computer program that generates exactly the axioms of A; and (b) there is a computer program that, when fed an instance i of the decision problem, outputs a statement Y i in the language of A such that • if Y i is provable in A, then the answer to i is YES, and • if : Y i is provable in A, then the answer to i is NO. Under these assumptions, if the decision problem is undecidable in sense 2, then at least one of its instance statements Y i is undecidable in sense 1, i.e., independent of A.
- Song Y Yan(Author)
- 1998(Publication Date)
- World Scientific(Publisher)
That is, a Turing machine can be used to solve any decision problem that is solvable by any effective procedure. 3 Instead of saying decidable, one can also speak of solvable. Moreover, the addi-tional attributes effectively, recursively, or algorithmically do not alter the meaning. That is, effectively decidable, recursively decidable, algorithmically decidable are all synonymous. Similarly, one can freely use any one of the following synonymous terms for undecidable: unsolvable, recursively undecidable, recursively unsolvable, effectively unde-cidable, effectively unsolvable, algorithmically undecidable, algorithmically unsolvable. But of course, the decidable is Turing-decidable, and the undecidable is Turing-undecidable, because the definition of all the terms are based on Turing machines. co-L = { 0 , l } * -L . (3.33) A t P — = (100101, yes) D Lprimes = (10101, no). ^Primes = { f o Y eS ) '■ X G ^Primes} U { ( z , n o ) I X & Z/Primes} • CO-Lpri m es — {0, 1} — {0, 1} — -^Composite CO-Lcomposite = {0, 1} — {0, 1} — Z/primes- 3.2. Decidability and Undecidability 185 3.2.2 Decidable Problems A decision problem may or may not be decidable. In this subsection, we study some decidable problems, and in the next two subsections, we shall study some undecidable problems.
eBook - PDFThree Views of Logic
Mathematics, Philosophy, and Computer Science
- Donald W. Loveland, Richard Hodel, S. G. Sterrett, Susan Sterrett(Authors)
- 2014(Publication Date)
- Princeton University Press(Publisher)
Our final example of an unsolvable problem is rather natural, given the ubiquity of computers in modern society. The problem was actually raised by Turing as a first step in his solution of Hilbert’s Decision Problem. Turing’s Halting Problem (modern version). Fix a computer program-ming language, for example, BASIC. Let P be the collection of all BASIC programs with the following property: the input for each program is an arbitrary natural number. Find an algorithm that, given any program P in P and any natural number a, decides (YES or NO) whether program P with input a halts or continues forever. In Chapter 5 we will prove the following result due to Turing (1936): There is no such algorithm. What constitutes a decision problem? The general setting is as follows. We have a countably infinite set of inputs, say X = { x 0 , x 1 , x 2 , . . . } = { x n : n ∈ N } and a subset A of X (i.e., A ⊆ X). x n X • A Input: x n ∈ X. Question: Is x n ∈ A? 100 Part 2: Computability Theory The decision problem A, X asks: Is there an algorithm that, given an arbitrary element x n of X, decides (YES or NO) whether x n ∈ A? If there is such an algorithm, we say that the decision problem A, X is solvable ; on the other hand, if no such algorithm exists, we say that the decision problem A, X is unsolvable . We can view a decision problem as follows, we want a finite list of instructions that will answer an infinite number of YES/NO questions: Is x 0 ∈ A? Is x 1 ∈ A? Is x 2 ∈ A? . . . , and so on. Each of the above (Hilbert’s Tenth Problem, certain Word Problems, Hilbert’s Decision Problem, the Halting Problem) is a decision problem that is unsolvable . On the other hand, let FOR = all formulas of propositional logic and TAUT = all tautologies of propositional logic. The decision problem TAUT, FOR is solvable (use truth tables). Algorithms Algorithms play a fundamental role in mathematics, computer science, and modern linguistics.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false. Many problems of mathematics have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided. Extending this result, Pyotr Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. In 1970, Yuri Matiyasevich proved Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation over the integers has a solution in the integers. The list of undecidable problems gives additional examples of problems with no computable solution. The study of which mathematical constructions can be effectively performed is som-etimes called recursive mathematics ; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field. Turing computability The main form of computability studied in recursion theory was introduced by Turing (1936). A set of natural numbers is said to be a computable set (also called a decidable , recursive , or Turing computable set) if there is a Turing machine that, given a number n , halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a recursive or (Turing) computable function if there is a Turing machine that, on input n , halts and returns output f ( n ).
- Chitat Chong, Mariko Yasugi, Qi Feng(Authors)
- 1998(Publication Date)
- WSPC(Publisher)
151 DECIDABILITY A N D UNDECIDABILITY IN THE E N U M E R A B L E TURING DEGREES STEFFEN LEMPP Department of Mathematics University of Wisconsin Madison, WI 53706-1388, USA ABSTRACT. We survey some recent work on the (recursively) enumerable Turing degrees, with particular emphasis on work relating to Decidability and Undecidability. Two fundamental notions of mathematics are those of a computable set and of an enumerable set. A set S is called computable (or recursive) if there is an effective algorithm which for any input x can compute whether x is an element of S. A set S is called (recursively) enumerable if there is an effective algorithm listing all elements of S. Clearly, these notions only make sense for countable sets. However, all basic countable sets (such as the set of all fc-tuples of natural numbers for some fixed k, the set of all finite strings of O's and l's, the set of words over some finite alphabet, or the set of first-order formulas over some finite language) are easily seen to be in effective 1-1 correspondence with the set of natural numbers. (The code number for an element of such a countable set is often called its Godel number.) Thus, for investigating computability, one can restrict oneself to studying computability over the natural numbers. The above intuitive notions of a computable set and an enumerable set were made precise in various equivalent ways in the mid-1930's and later. For example, Turing [Tu36] defined effective algorithm to mean what is now called a Turing machine, i.e., a very simple-minded computer with no limitations on run time or memory space. This (and its many equivalent def-initions) is nowadays generally accepted as the way to define computability (see also Soare [Sota]). 1980 Mathematics Subject Classification (1985 Revision). 03D25. Key words and phrases, (recursively) enumerable Turing degrees, decidability.
eBook - PDFWorldviews, Science And Us: Bridging Knowledge And Its Implications For Our Perspectives Of The World - Proceedings Of The Workshop On Times Of Entanglement
Bridging Knowledge and Its Implications for Our Perspectives of the World
- Diederik Aerts, Jan Broekaert, Bart D'hooghe(Authors)
- 2011(Publication Date)
- World Scientific(Publisher)
REFOCUSSING UNDECIDABILITY: QUESTIONING THE USE OF THE NOTION OF FORMAL UNDECIDABILITY IN OTHER DOMAINS LIESBETH DE MOL Centre for Logic and Philosophy of Science Universiteit Gent, Belgium E-mail: [email protected] Alonzo Church, Emil Post and Alan Turing were among the first to provide for-malizations of the informal notion of computability and prove the unsolvability of certain decision problems relative to these formalizations. Kurt G¨ odel proved that for any finite axiomatic theory containing Peano arithmetic, there are al-ways undecidable propositions, i.e. propositions which can neither be proved nor disproved within that theory. While these results are fundamental from a theoret-ical point of view, they are sometimes dismissed as being of no relevance for the working mathematician. Looking at domains further removed from mathematical logic, it is however clear that terms such as ‘undecidability’, ‘incompleteness’ and ‘non-computability’ do play a role, and are often used in many different ways. In discussing several such examples, it will be shown how undecidability has indeed been applied to and reinterpreted in other domains. Through this discussion it will be argued that there are many problems involved here, problems which will finally lead to the question for a good theoretical framework which can be used to generalize undecidability to these domains. 1. Introduction The influence of the work of Emil Post, Alonzo Church, Alan Turing and Kurt G¨odel in mathematical logic and theoretical computer science can hardly be underestimated. The incompleteness results by G¨odel, proving the existence of relatively undecidable propositions (UP), the different for-malizations of the notion of computability and the consequent proofs of unsolvable decision problems (UDP) by Church, Post and Turing and the several techniques that were developed in this context by these logicians, have played a major role not only in the evolution but also in the con-72
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
