Computer Science
Decidable Languages
Decidable languages are a subset of formal languages that can be recognized by a Turing machine. These languages can be decided by an algorithm that always halts and correctly determines whether a given input string belongs to the language or not. In other words, decidable languages are those for which there exists an effective method to determine whether a given string is a member of the language or not.
Written by Perlego with AI-assistance
Related key terms
1 of 5
7 Key excerpts on "Decidable Languages"
eBook - PDF- Michael Sipser(Author)
- 2012(Publication Date)
- Cengage Learning EMEA(Publisher)
Like any tool, computers have capabilities and limitations that must be appreciated if they are to be used well. The second reason is cultural. Even if you deal with problems that clearly are solvable, a glimpse of the unsolvable can stimulate your imagination and help you gain an important perspective on computation. 193 Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 194 CHAPTER 4 / DECIDABILITY 4.1 Decidable Languages In this section we give some examples of languages that are decidable by al-gorithms. We focus on languages concerning automata and grammars. For example, we present an algorithm that tests whether a string is a member of a context-free language ( CFL ). These languages are interesting for several reasons. First, certain problems of this kind are related to applications. This problem of testing whether a CFG generates a string is related to the problem of recogniz-ing and compiling programs in a programming language. Second, certain other problems concerning automata and grammars are not decidable by algorithms. Starting with examples where decidability is possible helps you to appreciate the undecidable examples. DECIDABLE PROBLEMS CONCERNING REGULAR LANGUAGES We begin with certain computational problems concerning finite automata. We give algorithms for testing whether a finite automaton accepts a string, whether the language of a finite automaton is empty, and whether two finite automata are equivalent. Note that we chose to represent various computational problems by lan-guages.
- Kenneth H. Rosen(Author)
- 2017(Publication Date)
- Chapman and Hall/CRC(Publisher)
5. The set of Turing machines has a Gödel numbering.Examples:1. Every finite set of numbers is recursive.2. The prime numbers are a recursive set.3. The problem of deciding which Turing machines halt on all inputs is undecidable. The set of Gödel numbers for these Turing machines is neither recursive nor recursively enumerable.4. For any fixedc ∈ N, the problem of deciding which Turing machines halt when the number c is supplied as input is undecidable. The set of Gödel numbers for these Turing machines is recursively enumerable, but not recursive.5. The problem of deciding which Turing machines halt when their own Gödel number is supplied as input is undecidable. The set of Gödel numbers for these Turing machines is recursively enumerable, but not recursive.6. Hilbert’s tenth problem: Hilbert’s tenth problem (posed in 1900) was the problem of devising an algorithm to determine, given a polynomial p(x1 , …, x17.3 LANGUAGES AND GRAMMARSn) with integer coefficients, whether there exists an integer root. Y. Matiyasevich proved in 1970 that no such algorithm exists. That is, the set of polynomials with integer coefficients that have an integer solution is not recursive. Hilbert’s tenth problem is called a “natural example” of an undecidable problem, since the concepts used to define it are not from within computability theory (i.e., unlike problems concerned with the behavior of Turing machines). [Ma93]Strings of symbols are a general way to represent information, both in written text and in a computer. A language is a set of strings that are used within some domain of discourse, and a grammar is a system for generating a language. A grammar is what enables a compiler to determine whether a body of code is syntactically correct in a given computer language. Formal language theory is concerned with languages, grammars, and rudiments of combinatorics on strings. Applications of formal language theory range from natural and programming languages, developmental biology, and computer graphics, to semiotics, artificial intelligence, and artificial life.
- 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.
- Song Y Yan(Author)
- 1998(Publication Date)
- World Scientific(Publisher)
3.2. Decidability and Undecidability 187 3.2.3 Decidable Problems in Formal Languages In Chapter 2, we have studied regular languages Z/REG, context-free languages LcF) context-sensitive languages Lcs> recursive languages Z/REC> recursively enu-merable languages LRE and their accepting machines. Now we present some decidability results for these classes of languages. Definition 3.2.5 The set of languages accepted by a machine M with n states, denoted by L(M), is (i) nonempty, if L(M) / 0. (ii) infinite, if |L(M)| = I, where n < I < 2n. Two machines Mi and M 2 are equivalent if they accept the same language, that is, L(Mi) = L(M 2 ). Note that the machine M in the above definition can be a FA, a PDA, a LBA or a TM, depending on the accepting languages. (I) Decidability in LREG Theorem 3.2.1 Let L(M) be the language accepted by a DFA, M = (Q,E,£ ) go,i ? )> ie -> L(M) = {(M, w) : M is a DFA that accepts input string U J G E } . Then it is decidable whether or not (i) L{M) = 0. (ii) L(M) is finite. (iii) L(M) is infinite. Theorem 3.2.2 Let L(Mi) and L(M 2 ) be the languages accepted by a DFA, Mi = {Q u E,8 u q 0l ,Fi), and a DFA M 2 = (Q 2 , £,<5 2 ,go 2 ,^2)-T h e n it: i s d e c i d able whether or not L{M) = L{M 2 ). Theorem 3.2.3 It is decidable whether or not two given regular grammars G = (Vi,T, 5i,Pi) and G = (V 2 ,T,S 2 ,P2) are equivalent. That is, it is decid-able whether or not L(Gi) = L(G 2 ). 188 Chapter 3. Turing Computability and Complexity (II) Decidability in L C¥ Theorem 3.2.4 Given any push-down automaton PDA, M, it is decidable whether or not (i) L(M) = 0. (ii) L(M) is finite. (iii) L(M) is infinite. Theorem 3.2.5 Given any context-free grammar GCF, it is decidable by a TM whether or not (i) L(G) = 0.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Orange Apple(Publisher)
The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ -recursive functions obtained from primitive recursion and the μ operator. The terminology for recursive functions and sets is not completely standardized. The definition in terms of μ -recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions computable by a Turing machine. The word decidable stems from the German word Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term computable function has various definitions: according to ________________________ WORLD TECHNOLOGIES ________________________ Cutland (1980), it is a partial recursive function (which can be undefined for some inputs), while according to Soare (1987) it is a total recursive (equivalently, general recursive) function. Not every set of natural numbers is computable. The halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but there are uncountably many sets of natural numbers. Although the Halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a recursively enumerable set , which is a set that can be enumerated by a Turing machine (other terms for recursively enumerable include computably enumerable and semidecidable ). Equivalently, a set is recursively enumerable if and only if it is the range of some computable function.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ -recursive functions obtained from primitive recursion and the μ operator. The terminology for recursive functions and sets is not completely standardized. The definition in terms of μ -recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions com-putable by a Turing machine. The word decidable stems from the German word Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term computable function has various definitions: according to Cutland (1980), it is a partial recursive function (which can be undefined for some ________________________ WORLD TECHNOLOGIES ________________________ inputs), while according to Soare (1987) it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. Soare (1996) gives additional comments about the terminology. Not every set of natural numbers is computable. The halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but there are uncountably many sets of natural numbers. Although the Halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a recursively enumerable set , which is a set that can be enumerated by a Turing machine (other terms for recursively enumerable include com-putably enumerable and semidecidable ).
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
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 ). The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines; for example the μ -recur sive functions obtained from primitive recursion and the μ operator. The terminology for recursive functions and sets is not completely standardized. The definition in terms of μ -recursive functions as well as a different definition of rekursiv functions by Gödel led to the traditional name recursive for sets and functions computable by a Turing machine. The word decidable stems from the German word ________________________ WORLD TECHNOLOGIES ________________________ Entscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term computable function has various definitions: according to Cutland (1980), it is a partial recursive function (which can be undefined for some inputs), while according to Soare (1987) it is a total recursive (equivalently, general recursive) function. Not every set of natural numbers is computable. The halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but there are uncountably many sets of natural numbers. Although the Halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a recursively enumerable set , which is a set that can be enumerated by a Turing machine (other terms for recursively enumerable include com-putably enumerable and semidecidable ).
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.
