Theory Of Computation

Primitive recursion function is another subclass of partial recursive function and can be defined using initial functions. Initial functions are defined over a set of natural numbers   N={0,1,2,...}  and some alphabet of symbols. A function is primitive if it follows the condition : i) It is an initial function    or ii) It is obtained from recursion or composition of initial functions. Total Function Example: Ackerman Function.

Total recursive function All those partial functions for which turing machine halts are called total recursive functions.  From the definition of both it is clear that total recursive function is the subset of partial recursive function. A total function is a subclass of partial function.  A function is called total function if it is defined for all its arguments. Let   f(a1,a2,....,an)   be a function and defined on function    g(b1,b2,....,bm), then   f  is a total function if every element of   f  is assigned to some unique element of function  g.

Partial recursive function are turing computable. It means that there exist a turing machine TM for every partial recursive function. Recursion: A function which calls itself directly or indirectly and terminates after finite number of steps is known as recursive function. In recursive functions,terminating point is known as base point. A function is called partial recursive if it is defined for some of its arguments.  Let   f(a1,a2,....,an) is a function and defined on function     g(b1,b2,....,bm) , then f is a partial function if some elements of     f  is assigned to almost one element of function   g. A partial function is recursive if i)It is an initial function over N, or ii)It is obtained by applying recursion or composition or minimalization on initial function over N. 'N' Natural numbers  {0,1,2,....}

godelization is a encoding technique which encodes a string as a number. This is known as Godel numbering.

PCP(Post's Correspondence Problem) MPCP(Modified PCP) PCP consists of two lists A=w1,....,wk and B=x1,....,xk , of strings over some alphabets SIGMA. This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with m>=1. Such that wi1,wi2,....,wim=xi1,xi2,....,xim. The sequence i1,....,im is a solution to this instance of PCP. MPCP  Lists A & B of k strings each from Sigma*.say A=w1,w2,...,wk and B=x1,x2,.....,xk does there exist a sequence of integers i1,i2,....,ir. such that w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ? Difference between PCP and MPCP is that in the MPCP, a solution is required to start with the first string on each list.

PCP(Post's Correspondence Problem) can be used to show that a wide variety of problems are undecidable.  One application : the undecidability of ambiguity for context free grammars. 

http://www.gliffy.com/gliffy/# Using this website i had drawn this diagram. Save -> Need to pay Better : Use this website If u finished .... Just Press Print Screen Button.... Win+R mspaint paste Will add scanned procedure soon...

Counter machine has the same structure as the multi-stack machine  but in place of each stack is a counter. Counters hold any non-negative integer,but we can only distinguish between zero and nonzero counters. That's the move of the counter machine depends on its state,input symbol and which if any of the counters are zero. In one move,the counter machine can a)change state b)Add or subtract 1 from any of its counters,independently. However a counter is not allowed to become negative,so it cant subtract from a counter that is currently 0. Counter Machine may also be regarded as a restricted multi-stack machine. The restrictions are as follows, a)There are only two stack symbols,which we shall refer to as Z0(the bottom of stack marker) and X. b)Z0 is initially on each stack. c)We may replace Z0 only by a string of the form X^iz0 for some    i >=0. d)We may replace X only by X^i for some i >= 0. That's Z0 appears   only on the bottom of each stack and all other

A two push down stack machine,a 2PDA is like a PDA except that it has two push down stacks STACK1 and STACK2 . When we wish to push a character x into a stack,we have to specify which stack, either PUSH1 x or PUSH2 x. When we POP a STACK for the purpose of branching we must specify which STACK,either POP1 and POP2 (Read character from read only input tape).

1)Linear Bounded Automaton 2)Multi-stack Machines 3)Counter Machines 4)Limits on the number of states and symbols Explanation:  1)Linear Bounded Automaton:          is a type of turing machine wherein the tape is not permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input,the head stays where it is,in the same way that the head will not move off the left-hand end of an ordinary turing machine's tape.      A Linear bounded automaton is a TM with a limited amount of memory. It can only solve problems requiring memory that can fit within the tape used for the input. Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor.  2)Multi-stack Machines:         A deterministic two-stack machine is a deterministic TM with a read only input and two storage tapes. If a head moves left on either tape, a blank is printed on that tape

Clique  in an undirected graph is a subgraph, wherein every 2nodes are connected by an edge. Clique Problem   is to determine whether a graph contains a clique of specified size. Satisfiability Problem   is to test whether a boolean formula is satisfiable. Boolean formula is an expression involving boolean variable & operations.  Halting Problem   is the problem for determining whether a turing m/c halts(by accepting/by rejecting) on a given input. Decidable    is a problem whose language is recursive.  A problem is  undecidable  if there exist no algorithm that takes as input an instance of the problem and determine whether the answer to that instance is "yes" or "no". Halting Problem is undecidable theorem and proof's scanned copy will upload next day.  Church's Thesis: -  What function cant be computed by turing machines? This is very surprising. It is believed that there are no functions that can be defined by humans,whose