Skip to main content

PCP & MPCP

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.



Comments

Post a Comment

Popular posts from this blog

Counter Machines

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
Post a Comment
Read more

Restricted Turing machine

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
Post a Comment
Read more