Decidable Languages

5 Key excerpts on "Decidable Languages"

• 

  eBook - ePub

  Theory of Computation Simplified

  Simulate Real-world Computing Machines and Problems with Strong Principles of Computation (English Edition)

  • Dr. Varsha H. Patil, Dr. Vaishali S. Pawar, Dr. Swati A. Bhavsar, Dr. Aboli H. Patil(Authors)
  • 2022(Publication Date)
  • BPB Publications

    (Publisher)

  There are specific problems that cannot be solved using a computer. These problems are called as undecidable problems. Till now, we learnt various and diverse mathematical models of computational processes that accomplish concrete computational tasks. In this chapter, we will see a class of language generators – Turing machines. Turing machine is the accurate model for what any physical computing device is capable of doing. This Turing machine is the best tool to develop the theory of undecidability. There are many such problems that are easy to express but are undecidable. We exclude here the TMs that may not halt on some inputs. We adopt TMs that halt on all inputs as the precise formal notion corresponding to the algorithms.

  According to the Church-Turing hypothesis, any algorithm can be programmed on a Turing machine. Any problem that cannot be solved by a Turing machine is called as unsolvable. Unsolvable problems are those which cannot have algorithmic solution, also called as undecidable problems. We use TM to prove that undecidable problems do exist. We shall study techniques for showing problems to be undecidable, that is, to have no algorithm, regardless of whether or not they are accepted by TM that fails to halt on some inputs.

  9.1.1 A Language that is not Recursively Enumerable

  A language L is recursively enumerable if there is a TM that accepts L, and recursive if there is a TM that recognizes L. These languages are also called as Turing acceptable and Turing decidable respectively. The set of recursively enumerable languages is countable, and the set of non-recursively enumerable languages is uncountable. If we could somehow choose a language at random, it would almost certainly not be recursively enumerable. This observation does not make it obvious how to find a specific language L which no TM can accept. But we can find the one by using the diagonalization principle. Hence, to show that there exists a language which is not recursively enumerable, we complete the following steps:

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Cybernetical Intelligence

  Engineering Cybernetics with Machine Intelligence

  • Kelvin K. L. Wong(Author)
  • 2023(Publication Date)
  • Wiley-IEEE Press

    (Publisher)

  The decision problem of determining, given a Turing machine and an input, whether the machine will eventually halt or run forever. It has been proven to be undecidable, meaning there is no algorithm that can solve it for all possible inputs. Church‐Turing thesis The informal claim that any problem that can be solved by an algorithm (i.e. a step‐by‐step procedure) can be solved by a Turing machine. This thesis has not been proven or disproven, but it is widely believed to be true. Recursively enumerable set A set of numbers that can be generated by a Turing machine (i.e. the machine can eventually halt and output the number). Recursive set A set of numbers for which there exists a Turing machine that can decide whether a given number is a member of the set (i.e. the machine will always halt and output either “yes” or “no”). Undecidable problem A decision problem for which no algorithm exists that can solve it for all possible inputs. Examples include the halting problem and the problem of determining whether two given Turing machines compute the same function.

  In summary, the concepts and principles of computability theory can be used to develop and optimize intelligent control systems that are more efficient and effective than traditional control systems. The integration of these two fields can lead to the development of more advanced and sophisticated intelligent control systems that can operate autonomously and adapt to changing conditions.

  12.4.1 Complexity Theory

  Complexity theory is a field of study that seeks to understand the inherent complexity of computational problems and algorithms, and the resources required to solve them. It is an important area of research in intelligent control, as it helps to determine the efficiency and scalability of algorithms used in intelligent control systems. One of the main measures of complexity in computational problems is time complexity, which measures the amount of time required to solve a problem as a function of the size of the input. Another important measure is space complexity, which measures the amount of memory required to solve a problem. One of the most famous problems in complexity theory is the P versus NP problem, which asks whether or not problems that can be verified in polynomial time can also be solved in polynomial time. If P = NP

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Handbook of Discrete and Combinatorial Mathematics

  • (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 fixed

  c ∈ 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 , …, x

  n

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

  17.3    LANGUAGES AND GRAMMARS

  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.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Automata and Computability

  A Programmer's Perspective

  • Ganesh Gopalakrishnan(Author)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  w,3 is RE.

  1   A claim that, we know, must be shifted to the “can’t” category.

  2   Some authors also call this family Turing recognizable (TR)—a term that we may occasionally use.

  3   Recursive languages are also called decidable languages. Decid able languages are almost always desir able too.

  4   Technically, the word “family” in mathematics is used when we don’t necessarily want a “set-like behavior.” Thus (for some reason), we may want to allow two distinct members of a family to be identical; we know that two distinct members of a set aren’t identical.

  5   String x could well be the markdown description of a DFA.

  6   Can you think of an algorithm to check whether a given DFA’s language is empty? Hint: Think of the most general way to characterize a DFA that does not have any string in its language—not even ε.

  7   Hereafter, we will use D to denote a DFA and 〈D〉 to denote its description. This applies to other entities too—for instance, a Boolean function φ and its description 〈φ〉.

  8   Say by hiring a soothsayer or asking an oracle…

  9   The shock may be too much.

  10   If a purveyor sells us a decider when we have proof that a decider cannot exist, then we can take the purveyor to court and sue him! However, note that under “some weather conditions,” a semi-decider may print “no, x ∉ L” and halt. Thus, taking the person to court or not simply by testing out a handful of cases is not a wise idea, for, the purveyor may have “jimmied” his semi-decider to return enough “no” answers. In other words, prove before you sue.

  11   This is like claiming that sorting is O(2

  n

  ) in an algorithms class which makes one eligible for a failing grade. While there are exponential sorting algorithms, one always strives to do better.

  12   It is in fact interesting to note that our classification is not based on the superficial structure of the production rules that represent CFGs. In fact, the production rules that represent CFGs syntactically are regular languages: they consist of simple repetitions of productions, where the productions themselves are repetitions of nonterminals and terminals coming after an arrow symbol. We are given the syntactic representation of G1 and G2 but then asked to consider L(G1 ) and L(G2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Mathematical Logic

  Extended Edition

  • Micha?? Walicki(Author)
  • 2016(Publication Date)
  • WSPC

    (Publisher)

  Part II

  TURING MACHINES

  Passage contains an image

  Chapter 3

  COMPUTABILITY AND DECIDABILITY

  The idea of “mechanical” reasoning underlies the whole development of logic, and this chapter presents its ultimate expression as a Turing machine or, in more modern language, a computer program. It captures the “mechanical” decidability of a problem in terms of purely symbolic transformations of the input following precisely defined rules. It relies on the idea of an uninterpreted language, so we begin with this concept.

  3.1ALPHABETS AND LANGUAGES

    a background story

  The languages we use for daily communication are what we call natural languages . They are acquired in childhood and are suited to just about any communication we may have. They have evolved along with the development of mankind and form a background for any culture and civilisation. Formal languages , on the other hand, are explicitly designed by people for a clear, particular purpose. A semi-formal language was used in the preceding chapters for the purpose of talking about sets, functions, relations, etc. It was only semi -formal because it was not fully defined. It was introduced along as we needed some notation for particular concepts.

  Formal language is a fundament of formal logical system and we will later encounter several examples of formal languages. Its most striking feature is that, although designed for some purposes, it is an entity on its own. It is completely specified without necessarily referring to its possible meaning. It is a pure syntax. Similar distinction can be drawn with respect to natural languages. The syntax of a natural language is captured by the intuition of the grammatically correct expressions . At the basic (written) level, there is an alphabet, e.g., the Latin one with a, b, c, . . . from which words are formed. Yet, not all possible combinations of the letters form words; aabez is a syntactic possibility but there is no such word. Using only valid words, still does not guarantee correctness. But even grammatically correct sentences may remain meaningless. Quadrille drinks procrastination is a grammatically correct expression consisting of the subject quadrille , verb in the proper form drinks , and object procrastination

  Sign up to read

  Learn more about book