Theory of computation / Post’s Correspondence Problems (PCP)

1. PREPARED FOR: Dr. Gede Pramudya Ananta PREPARED BY: THAMER J.ABBAS M031020009 SAIF MOHAMMED MAKKI M031020010 SAIF ZUHAIR ABDULMAJEED M031110012

2. Turing machines a device with a finite amount of read-only “ hard” memory (states), and an unbounded amount of read/write tape-memory The output depends only on input and the previous output Black box reads a sequence of 0’s and 1’s The main thing is ???? That the changes from one output state to the next Given by definite rules, called the TRANSITION rules

3. Reducibility Definition Primary method for Proving that problems are computationally unsolvable. Reducibility also occurs in mathematical problems . A Reduction : is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem. Such reducibilities come up often in everyday life, even if we don't usually refer to them in this.

4. EXAMPLE: use problem B to solve problem A CAN'T TAKE IT DIRECT.. XX A B

5. Recall that: A language A is decidable, if there is a Turing machine M (decider ) that accepts the language A and halts on every input string. Turing Machine Input string Accept Reject Decider for YES NO M A Decision On Halt : DECIDABLE

6. UNDECIDABLE Undecidable problems have no algorithm, regardless of whether or not they are accepted by a TM that fails to halt on some inputs Undecidability : undecidable languages that cannot be decided by any Turing Machine

7. Example for: Decidable And Undecidable Assume, we have a program which assigns all possible combination of 3 integers to variables x, y and z. For the first case there is at least one solution (x = 2, y = 1, z =5). Thus, the program will eventually stops. But for the second case we don’t know if this system has a solution. If there is no solution for the second system, then the program never stops. x = 2 y = 1 z =5

8. Examples: Halting Problem halts(“ 2+2 ”) True halts(“ def f(n): if n==0: return 1 else: return n * f(n-1) f(5) ”) True halts(“ def f(n): if n==0: return 1 else: return n * f(n-1) f(5.5) ”) false

9. X 2 + Y 2 + Z 2 = A 2 + B 2 10 11 12 13 14 = 365 365 6 7 8 9 10 149 ≠ 182

10. Post’s Correspondence Problems (PCP ) Definition An instance of PCP consists of two lists of strings over some alphabet S. The two lists are of equal length, denoted as A and B. The instance is denoted as (A, B). We write them as A = w 1 , w 2 , …, w k B = x 1 , x 2 , …, x k for some integer k. For each i , the pair ( w i , x i ) is said a corresponding pair.

11. PCP Instances An instance of PCP is a list of pairs of nonempty strings over some alphabet Σ Say (w 1 , x 1 ), (w 2 , x 2 ), …, ( w n , x n ). The answer to this instance of PCP is “yes” if and only if there exists a nonempty sequence of indices i 1 ,…, i k , such that w i1 …w in = x i1 … x in .

12. Post’s Correspondence Problem (PCP) is an example of a problem that does not mention TM’s in its statement, yet is undecidable . From PCP, we can prove many other non-TM problems undecidable .

13. Example: PCP Let the alphabet be {0, 1}. Let the PCP instance consist of the two pairs (0, 01) and (100, 001). We claim there is no solution. You can’t start with (100, 001), because the first characters don’t match .

14. Example: PCP Recall : pairs are (0, 01) and (100, 001) 01 100 001 100 001 But we can never make the first string as long as the second . As many times as we like Can add the second pair for a match Must start with first pair

15. Example: PCP – (3) Suppose we add a third pair, so the instance becomes: 1 = ( , 01); 2 = ( 100 , 001); 3 = ( 110 , 10). Now 1,3 is a solution; both strings are 0110 . In fact, any sequence of indexes in 12 * 3 is a solution.

16. A Simple Undecidable Problem We say this instance of PCP has a solution , if there is a sequence of integers, i 1 , i 2 , …, i m , that, when interpreted as indexes for strings in the A and B lists, yields the same string, that is, w i 1 w i 2 … w i m = x i 1 x i 2 … x i m . We say the sequence is a solution to this instance of PCP.

17. A Simple Undecidable Problem The Post’s corresponding problem is: given an instance of PCP, tell whether this instance has a solution. The solution to an instance of PCP sometimes is not unique . Also, an instance of PCP might have no solution.

18. 18 Post’s (Domino) Correspondence Problem PCP as a game Usually dominoes is played as follows:

19. 19 Post’s (Domino) Correspondence Problem Usually dominoes is played as follows: • • •

20. 20 Post’s (Domino) Correspondence Problem Usually dominoes is played as follows: • • • • • • • • •

21. 21 Post’s (Domino) Correspondence Problem Usually dominoes is played as follows: • • • • • • • • • • • • • • • •

22. 22 Post’s (Domino) Correspondence Problem Usually dominoes is played as follows: • • • • • • • • • • • • • • • • • • • • • •

23. 23 Post’s (Domino) Correspondence Problem Usually dominoes is played as follows: • • • • • • • • • • • • • • • • • • • • • • • • • • • •

24. 24 Post’s (Domino) Correspondence Problem We’ll play horizontally instead of vertically. Furthermore, dominoes will not be allowed to be flipped so each half will be a different color: • • •

25. 25 Post’s (Domino) Correspondence Problem Aim of the game is to have same total number of dots on the top as on the bottom. Player is given a set of domino prototypes to choose from, and can choose as many of a given prototype as necessary. Let’s play with the following 2 prototypes: • • • • • • • • • •

26. 26 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • Total Total • • • • • • •

27. 27 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • • • • • • • • Total 1 Total 2 • • •

28. 28 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • • • • • • • • Total 2 Total 4 • • • • • •

29. 29 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • • • • • • • • Total 8 Total 5 • • • • • • • • • • • • •

30. 30 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • • • • • • • • Total 9 Total 7 • • • • • • • • • • • • • • • •

31. 31 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: • • • • • • • • • • Total 10 Total 9 • • • • • • • • • • • • • • • • • • •

32. 32 Post’s (Domino) Correspondence Problem Let’s play with the following 2 prototypes: WINNER! • • • • • • • • • • Total 11 Total 11 • • • • • • • • • • • • • • • • • • • • • •

33. 33 Post’s (Domino) Correspondence Problem Could have represented dominos using unary strings: Point of game is to get the same string to be written on top as bottom. • • • • • • • • • • 111111 1 1 11

34. 34 Post’s (Domino) Correspondence Problem In general, could use arbitrary strings. EG: Aim: Get the same string on top as bottom. PCP: Given an alphabet S and finite set of string pairs ( u 1 ,v 1 ), ( u 2 ,v 2 ), … , ( u n ,v n ) with u i ,v i  S *, can a non-empty sequence of indices i1 , i2 , i3 , … , it be chosen so that u i1 u i2 u i3 … u it = v i1 v i2 v i3 … v it ? c ba a ac acb b ba a

35. 35 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Total Total Indices c ba acb b ba a a ac

36. 36 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Total a Total ac Indices 1 c ba a ac acb b ba a a ac

37. 37 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Total ac Total acba Indices 12 c ba a ac acb b ba a a ac c ba

38. 38 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Total acba Total acbaa Indices 123 c ba a ac acb b ba a a ac c ba ba a

39. 39 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Total acbaa Total acbaaac Indices 1231 c ba a ac acb b ba a a ac c ba ba a a ac

40. 40 Post’s (Domino) Correspondence Problem Let’s play with the following 4 prototypes: 1: , 2: , 3: , 4: Answer: YES! (solution is 12314) Total acbaaacb Total acbaaacb Indices 12314 c ba a ac acb b ba a a ac c ba ba a a ac acb b

41. PCP is undecidable We can try all lists i 1 , i 2, … , i k in order of k. if we find a solution, the answer is “yes” But if we never find a solution, how can we be sure no longer solution exists? So, we can never say no

42. A Simple Undecidable Problem Example 1 Two lists of an instance of PCP are shown A solution is 2, 1, 1, 3 (strings may be repeated) because w 2 , w 1 , w 1 , w 3 = 10111 1 1 10 = 10 111 111 = x 2 , x 1 , x 1 , x 3 Another solution is 2, 1, 1, 3, 2, 1, 1, 3 Example 1 Two lists of an instance of PCP are shown A solution is 2, 1, 1, 3 (strings may be repeated) because w 2 , w 1 , w 1 , w 3 = 10111 1 1 10 = 10 111 111 = x 2 , x 1 , x 1 , x 3 Another solution is 2, 1, 1, 3, 2, 1, 1, 3 List A List B i w i x i 1 1 111 2 10111 10 3 10

43. There is much more I haven’t told you about It ..