Skip to main content

Undecidability


Amu_Ke_Fundye

Undecidability


Decidable Problem

  • If there is a Turing machine that decides the problem, called as Decidable problem.
  • A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps.
  • A problem is decidable, if there is an algorithm that can answer either yes or no.
  • A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps.
  • Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable.

Undecidable Problem

  • A problem that cannot be solved for all cases by any algorithm whatsoever.
    Equivalent Language cannot be recognized by a Turing machine that halts for all inputs.

The following problems are undecidable problems:
  • Halting Problem: A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs.
  • Emptyness Problem: Whether a given TM accepts Empty?
  • Finiteness Problem: Whether a given TM accepts Finite?
  • Equivalence Problem: Whether Given two TM’s produce same language?. Is L(TM1) = L(TM2) ?
  • Is L(TM1) ⊆ L(TM2) ? (Subset Problem)
  • Is L(TM1) Ո L(TM2) = CFL?
  • Is L(TM1) = Σ* ? (Totality Problem)
  • Is the complement of L(G1) context-free ?

Undecidable problems are two types: Partially decidable (Semi-decidable) and Totally not decidable.
  • Semi decidable: A problem is semi-decidable if there is an algorithm that says yes. if the answer is yes, however it may loop infinitely if the answer is no.
  • Totally not decidable: A problem is not decidable if we can prove that there is no algorithm that will deliver an answer.

Closure Properties of Formal Languages:
image
REG-Regular Language, CFL-Context free language, DCFL-Deterministic CFL, CSL-Context sensitive language, RC-Recursive language, RE-Recursively enumerable language.

Regards
Amrut Jagdish Gupta
Labels:

Comments

Post a Comment

Popular posts from this blog

ALU and Data Path

Amu_Ke_Fundye ALU and Data Path The CPU can be divided into a data section and a control section. The   data section , which is also called the   datapath. Datapath The registers, the ALU, and the interconnecting bus are collectively referred to as the datapath.  Each bit in datapath is functionally identical.  The datapath is capable of performing certain operations on data items. The  control section  is basically the  control unit ,  which issues control signals to the datapath . Bus : A Bus is a collection of wires or distinct lines meant to carry data, address and control information. Data Bus : it is used for transmission of data. The number of data lines corresponds to the number of bits in a word. Address Bus : it carries the address of the main memory location from where the data can be accessed. Control Bus : it is used to indicate the direction of data transfer and to coordinate the timing of events during the transfer. PC (Pro
Post a Comment
Read more

Sequential Logic Circuits

Amu_Ke_Fundye Sequential Logic Circuits In sequential logic circuit, the output is dependent upon the present inputs as well as the past inputs and outputs. Sequential circuit is of two types. Synchronous Sequential Circuit:  Change in input signals can affect memory elements only upon activation of clock signals. Asynchronous Sequential Circuit:  Change in input signals can affect memory elements at any instant of time. These are faster than synchronous circuit. Flip Flops: It is a one-bit memory cell which stores the 1-bit logical data (logic 0 or logic 1). It is a basic memory element. The most commonly used application of flip flops is in the implementation of a feedback circuit. As a memory relies on the feedback concept, flip flops can be used to design it. In synchronous sequential circuit, Memory elements are clocked flip flops and generally edge triggered. In asynchronous sequential circuit, Memory elements are unclocked flip flops / time delay
2 comments
Read more