(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0,...

(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0, 1}.

Solutions

Expert Solution

Solution 10:

Proof method 1:

We can encode every string in a finite alphabet into a binary string (like a computer using binary to encode text). As PCP for a random alphabet is undecidable, a random encoding in binary is also undecidable.

Proof method 2:

Please give thumbsup, or do comment in case of any query. Thanks.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Let L be the set of all languages over alphabet {0}. Show that L is uncountable,...

Let L be the set of all languages over alphabet {0}. Show that L is uncountable, using a proof by diagonalization.

2. i. Consider a binary source alphabet where a symbol 0 is represented by 0 volt...

2. i. Consider a binary source alphabet where a symbol 0 is represented by 0 volt and a symbol 1 is represented by 1 volt. Assume these symbols are transmitted over a baseband channel having uniformly distributed noise with a probability density function: px= {18 for-4≤x≤4 0 Assume that the single decision threshold T is in the range of 0 and l volt. If the symbols 0 and 1 are sent with probabilities p0 and 1- p0 respectively, derive...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet {a, b} defined inductively as follows: • Base case: the empty word λ and the word a belong to S • Inductive rule: if ω is a string of S then both ω b and ω b a belong to S as well. 1. Prove that if a string ω belongs to S, then ω does not have two or more consecutive a’s. 2....

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many...

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many n-bit binary strings are there? How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly...

Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable?

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules...

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules for L1 are as follows: S → TT S → U T → 0T T → T0 T→ 1 U → 0U00 U → 1 Q → λ P → QU Transform this grammar into Chomsky Normal Form, consistent with the CNF specification in the Quick Reference, and using only Variables { S, T, U, V, W, X }. Implement that CNF grammar in...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines Y...

rogram that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary.

Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x // 2Note: The above algorithm outputs the 0's and 1's in reverse order. You will need to write a second function to reverse the string.Ex: If the input is:6the output is:110Your program must define and call the following two functions. The function integer_to_reverse_binary() should return a string of 1's...

(§3.4 # 3) Use the previous problem to show that the average number of binary comparisons...

(§3.4 # 3) Use the previous problem to show that the average number of binary comparisons required to sort n items is at least O(n log2 n).

Subjects