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.
6 Key excerpts on "Decidability and Undecidability"
eBook - ePub- Dov M. Gabbay, Paul Thagard, John Woods(Authors)
- 2009(Publication Date)
- North Holland(Publisher)
...This problem was viewed asthemain problem of mathematical logic and begged for a rigorous definition of mechanical procedure or finite decision procedure.How intricately the “Entscheidungsproblem” is connected with broad perspectives on the nature of mathematics is brought out by an amusingly illogical argument in von Neumann’s essayZur Hilbertschen Beweistheoriefrom 1927:… it appears that there is no way of finding the general criterion for deciding whether or not a well-formed formulaais provable. (We cannot at the moment establish this. Indeed, we have no clue as to how such a proof of undecidability would go.) … the undecidability is even aconditio sine qua nonfor the contemporary practice of mathematics, using as it does heuristic methods, to make any sense. The very day on which the undecidability does not obtain any more, mathematics as we now understand it would cease to exist; it would be replaced by an absolutely mechanical prescription (eine absolut mechanische Vorschrift) by means of which anyone could decide the provability or unprovability of any given sentence.Thus we have to take the position: it is generally undecidable, whether a given well-formed formula is provable or not.If the underlying conceptual problem had been attacked directly, then something like Post’s unpublished investigations from the 1920s would have been carried out in Göttingen. A different and indirect approach evolved instead, whose origins can be traced back to the use of calculable number theoretic functions in finitist consistency proofs for parts of arithmetic. Here we find the most concrete beginningof the history of modern computability with close ties to earlier mathematical and later logical developments.There is a second sense in which “foundational context” can be taken, not as referring to work in the foundations of mathematics, but directly in modern logic and cognitive science...
eBook - ePub- Greg Restall(Author)
- 2002(Publication Date)
- Routledge(Publisher)
...Part IV Decidability DOI: 10.4324/9780203016244-17 Chapter 14 Decision Procedures DOI: 10.4324/9780203016244-18 In the terms of the new electronic pragmatism, the truth may not be pure but it had better be simple. For “simple” read “computationally tractable.” — John Slaney, Vagueness Revisited [249], 1988 The deducibility problem for a logic goes like this: we are presented with a consecution X ⊢ A, and we wish to know whether it is valid or not. Is there an algorithm to determine its validity? A logic is said to be decidable if and only if there is an algorithm determining decidability, and it is undecidable if there is no such algorithm. In some logics, there is a simple algorithm. For example, in the two-valued classical propositional logic TV, one algorithm is a truth table test. You check to see whether there are any truth table evaluations for which the antecedent is true and the conclusion false. If there are any, the argument is invalid, otherwise, it is valid. This process can be generalised — if any logic has a finite characteristic algebra, then we have an algorithm for testing its validity. You check! However, many logics are not characterised by a finite algebra. 1 In these cases, we need a more subtle method for determining the validity of arguments. In this chapter, we will examine a few such methods. The first section will focus on methods involving proof theories and the second, on models. 1 See Exercises 8.11 and 8.12. 14.1 Proof Search One method for determining validity is to search for a proof, provided that you have reassurance that you will not have to look too far. If there are bounds on the length of the search, then searching for a proof can provide an algorithm for determining validity...
eBook - ePubComplexity
A Philosophical Overview
- Nicholas Rescher(Author)
- 2020(Publication Date)
- Routledge(Publisher)
...For with respect to purely theoretical problems it is clear from Turingesque results in algorithmic decision theory (ADT) that there will indeed be computer insolubilia—mathematical questions to which an algorithmic respondent will give the wrong answer or be unable to give any answer at all, no matter how much time is allowed. 4 But this is a mathematical fact which obtains of necessity so that this whole issue can be also set aside for present purposes. For in our present context of generalized problem solving (GPS) the necessitarian facts of Gödel-Church-Turing incompleteness become irrelevant. Here any search for meaningful problem-solving limitations will have to confine its attention to problems that are in principle solvable: demonstrably unsolvable problems are beside the point of present concern because an inability to do what is in principle impossible hardly qualifies as a limitation. The sort of limit that a rigid demonstration of impossibility establishes in our present context is one that bears not so much on question answering as on question askability, seeing that it makes no sense to ask for the demonstrably impossible. For present purposes, then, it is limits of capability not limits of feasibility that matter. In asking about the problem-solving limits of computers we are looking to problems that computers cannot resolve but that other problem solvers conceivably can. The limits that will concern us here are accordingly not rooted in conceptual or logico-mathematical infeasibilities of general principle but rather in performatory limitations imposed upon computers by the world’s modus operandi...
eBook - ePub- Bernhard Weiss(Author)
- 2014(Publication Date)
- Routledge(Publisher)
...So a sentence may become decidable when we find a proof of it and thus extend our epistemic position: the notion of decidability concerns what we are able to guarantee in a given epistemic state. 1 The notion does not easily generalize beyond the mathematical realm since, in the empirical case, we do not, in general, have procedures which deliver conclusive verdicts on truth-value. So the notion must be weakened: a statement is decidable if we possess a method which is guaranteed to issue in best possible evidence either in its favour or against it. 2 The paradigm examples that Dummett gives of the operations in language which enable the expression of undecidable statements are use of the past and future tenses, quantification over unsurveyable domains and subjunctive conditionaliza-tion. By means of these operations we can construct sentences that express statements for which we have no guaranteed means of uncovering best possible evidence either for or against. This is not to say that we shouldn’t find ourselves in such a fortunate position, just that we have no guarantee of achieving it. Now the notion of best possible evidence is itself unclear: it can perhaps be explained in terms of that of canonical warrant, a notion which is crucial to antirealist theories of meaning (see Chapter 5). However, since that notion may well be distinctively anti-realist and so unfit for employment in a characterization of the dispute between realist and antirealist, it is best to stick with the less committing notion of best possible evidence, evidence of a kind which cannot be improved upon by addition of evidence of another kind. Now this is to leave matters vague indeed, but they are not, I think, intolerably vague. The debate can be pursued and issues tackled even allowing for a vagueness in the notion of decidablity. This, of course, is not to say that a complete resolution can be achieved in the absence of a clarification of decidability....
eBook - ePub- D.J. White(Author)
- 2018(Publication Date)
- Routledge(Publisher)
...CHAPTER 3 Decidability Chapter (2) discusses value and uncertainty and their dependence on choice behaviour. The choice behaviour was in no way necessarily connected with decision. In this chapter, we shall discuss the content of mathematical (or logical) decision, and several problems arising in the introduction of decidability into choice. It is necessary to note that we can permit several forms of decision, depending on whether it is complete, partial or probabilistic. Although we talk in terms of probabilities, any other valid truth value measure would do. 3.1 Complete, Probabilistic, and Partial Decidability Decidability, as used in the true mathematical sense, is concerned with the ‘proof’ of a proposition, or its negation, based on a set of axioms and the usual two-valued logic. Thus, in geometry, we can ‘prove’ or ‘disprove’ propositions about intersections of lines, given the properties (axioms) of the manifolds with which we deal: in the field of number theory we can ‘prove’ certain propositions about sets of numbers, given the arithmetical axioms. The important point here is that of ‘proof and its identity with ‘decision’. Dunlop (27) stresses this identity. In such usage, of course, our problems contain only two alternatives, viz: truth or falsity of the theorems proposes. The axioms may, however, not be sufficient to determine truth or falsity. In this case we have three alternatives, viz: true, false, undecided. However ‘undecided’ just reproduces Q and need not be considered separately. Thus, if, in convergence analysis, we take as an axiom that, for the series u 1 + u 2 + u 3... u n, | u n | ⩽ k | u n −1 |, 0 ⩽ k < 1, then the problem is and the selected alternative is T, i.e., the series will converge). If k > 1...
- Mette Leonard Høeg(Author)
- 2022(Publication Date)
- Routledge(Publisher)
...1 The Concept of Undecidability DOI: 10.4324/9781003244622-2 The Constitution of Literary Undecidability: Author, Text, Reader The conceptualisation of undecidability presented here is based on a view of the meaning of a literary text as constituted in combination by the author, the text and the reader. My interest is undecidability in the objective sense of the incapability of being decided, i.e., as a textual feature and quality, as well as undecidability in the subjective sense as the incapability of deciding, i.e., the effect of textual undecidability on the reader’s interpretation and reaction in the meeting with a work of undecidability. I define undecidability as a specific form of uncertainty applied by the author as part of a narrative strategy, as a form of uncertainty that characterises the readerly experience of a narrative, and as a textual feature that renders it impossible for the reader to decide on one single reading of a text. This entails a distinction between undecidability on different levels of meaning-production in a literary text – and a distribution of the authority over the meaning between author, text and reader – and at the same time a view of undecidability as a consolidation of the meanings activated on these interdependent levels. The conceptualisation of undecidability includes a cognitive perspective in literature and draws on the theory of Terrence Cave in which the fundamentality of uncertainty in literature and its effect of reader engagement are cognitively explained. In Thinking ‘with’ Literature, Cave shows that, cognitively speaking, the very act of reading is a process of filling out gaps by inferring meaning – mostly done unconsciously, unhesitatingly and with ‘extraordinary rapidity’ (2016: 26)...
